第三章复习 (2).pptx

第三章集合与关系 1 组织结构是明确的 但是内容比较多 2 集合 直积 关系这些概念是简单的 3 主要难点在于 复合 闭包和特殊关系 等价关系 相容关系 序关系 习题3 1 p86 6 确定下列集合的幂集a a a b 1 2 3 解答 a a a a a b 1 2 3 这种题目通常通过 P A 2 A 来计算幂集中元素的个数 然后验证解答是否正确 抓住这个 我们可以计算难题 习题3 1 p86 6 确定下列集合的幂集d P e P P 习题 解答 d 没有元素 所以 P 20 1 P P P 21 e P P P P P P 22 习题3 1 p86 7 设A B P P A 问 a 是否 B 是否 B b 是否 B 是否 B c 是否 B 是否 B 解答 由上题得到 P P 所以a B B b B B c B B 拆括号法 习题3 2 p95 5 证明 对任意集合A B C 有a A B C A B C 证明 x A B C x A B x C x A x B x C x A x B C x A B C 所以 A B C A B C 习题3 2 p95 8 a 已知A B A C 是否必须B C b 已知A B A C 是否必须B C c 已知A B A C 是否必须B C a A 1 2 B 3 C 2 3 为反例b A 1 2 B 1 C 2 为反例c A B A C A A B A A C B C B C 习题3 2 p95 a A B C A B A C 左边 A B C C B A B C C B A B C A B C 右边 A B A C A C A B A B A A B C A C A A C B A B C A B C 习题3 3 p100 5 A1 学数学 A2 学物理 A3 学生物 A1 67 A2 47 A3 95 A1 A3 26 A1 A2 28 A2 A3 27N 200 A1 A2 A3 50又 A1 A2 A3 A1 A2 A3 A1 A3 A1 A2 A2 A3 A1 A2 A3 所以200 50 67 47 95 26 28 27 A1 A2 A3 因此 A1 A2 A3 22 习题3 4 p105 3 下列各式中哪些成立 哪些不成立 为什么 b A B C D A C B D d A B C A C B C b A 1 2 B 1 C 1 2 D 1 A B C D A C B D 习题3 4 p105 d A B C x A x B y C x A y C y C x A y C x B y C A C B C A C B C 所以 A B C A C B C 习题3 4 p105 4 证明 若X X Y Y 则X Y证 1 X X 则 Y Y 所以x Y X Y 2 反之 设 Y Y 则 X X y X Y X 所以X Y 习题3 5 p110 5 对式中所给出A上的二元关系 试给出关系图 0 x y 3 A 0 1 2 3 4 R 习题3 5 p110 6 对 0 1 2 3 4 5 6 上的二元关系 x 习题3 5 p110 7 设P 和Q 找出P Q P Q domP domQranP ranQ dom P Q ran P Q 解 P Q P Q domP 1 2 3 domQ 1 2 4 ranP 2 3 4 ranQ 2 3 4 dom P Q 2 ran P Q 4 习题3 6 p113 1 分析集合A 1 2 3 上的下述五个关系 R S T 判断A中的上述关系是不是a 自反的 b 对称的 c 可传递的 d 反对称的 解答 1 R满足反对称性和传递性 2 S满足自反 对称和传递性 3 T满足反对称性 破坏传递 习题3 6 p113 2 给定A 1 2 3 4 考虑A上的关系R 若R a 在A A的坐标图中标出R 并绘出它的关系图 b R是自反的 对称的 可传递的 反对称的吗 解答 可传递的 反对称的 习题3 6 p114 6 设R是集合X上的一个自反关系 求证 R是对称和传递的 当且仅当和在R之中则有在R之中 证明 1 若R是对称的 则由和在R中 因此 在R中 R是传递的 因此在R中 由对称 在R中 2 a b c任意 a取c 和在R中 故R对称 因此由在R中知道在R中 在R中 推出R传递 习题3 7 p118 1 设R1和R2是A上的任意关系 说明以下命题的真假 并予以证明a 若R1和R2是自反的 则R1 R2也是自反的c 若R1和R2是对称的 则R1 R2也是对称的解答 a 成立 在R1中有 R1 在R2中有 R2 因此 R1 R2 有自反性 c 不成立 设R1 R2 则R1 R2 无对称性 习题3 7 p119 5 R是A上的一个二元关系 如果R是自反的 则Rc一定是自反的吗 如果R是对称的 则Rc一定是对称的吗 如果R是传递的 则Rc一定是传递的吗 解答 1 R自反 R 所以 Rc Rc自反 2 R对称 Rc R 也对称 3 R Rc 因此满足传递性 习题3 8 p127 2 设集合A a b c d A上的关系R a 用矩阵运算和作图方法求出R的自反闭包 对称闭包和传递闭包 b 用Warshall算法求出R的传递闭包解答 图略 直接解说传递性 要解说一步边 两步边 三步边 四步边 习题3 8 p127 矩阵运算 加法为析取 自反M1 M Ix 对称M2 M Mc 传递M3 M1 M1 2 M1 3 M1 4b 习题3 8 p127 7 设R1和R2是A上的关系 证明 a r R1 R2 r R1 r R2 b s R1 R2 s R1 s R2 解答 a 左边 R1 R2 I 右边 R1 I R2 I R1 R2 Ib 左边 R1 R2 R1 R2 c R1 R2 R1c R2c右边 R1 R1c R2 R2c 两边相等 习题3 9 p130 4 题略 证明 1 Ai不包含于Aj 因此Ai不可能为空集 2 有Ai Aj 这是因为若有Ai Aj不为空 设共同元素有x 因此Ai中的元素ai和Aj中的元素aj 由题意有 R R 由对称和传递 可以得到 R 因此ai aj在一个集合中 因此Ai Aj 这和Ai Aj互不包含相排斥 3 a A 由自反性 R 因此a和a在某个子集As中 由a的任意性 遍历s 得到a A1 A2 Ak a A1 A2 Ak推出a A显然 上面可以证明a A推出a A1 A2 Ak 因此A1 A2 Ak A 习题3 10 p134 3 给定集合S 1 2 3 4 5 找出S上的等价关系R 此关系R能够产生划分 1 2 3 4 5 并画出关系图 R 1 2 2 3 2 4 5 2 关系图分为三部分 为两个完全2边形和一个完全0边形 用画笔画一下 习题3 10 p135 6 设R是集合A上的对称和传递关系 证明如果对于A中的每一个元素a 在A中同时也存在一个b 使在R中 则R是一个等价关系 证明 只需证明R是自反的 对于任意的a 存在b 有 R 由对称性 R 由传递性 R 因此R是自反的 所以R是一个等价关系 习题3 11 p139 1 设R是X上的二元关系 试证明r Ix R Rc是X上的相容关系 证明 1 Ix 因此 r r自反 2 R 则 Rc 因此 r并且 r r是对称的 因此r是相容关系 习题3 11 p139 2 题目省略 解答 完全覆盖为 最大相容类集合 x1 x2 x3 x1 x3 x6 x3 x5 x6 x3 x4 x5 习题3 11 p139 4 设C A1 A2 An 为集合A的覆盖 试由此覆盖确定A上的一个相容关系 并说明在什么条件下 此相容关系为等价关系 R A1 A1 A2 A2 An An当R满足传递性 此相容关系为等价关系 一般的 只要C不仅是一个覆盖 还是一个划分的时候 R就能满足传递性 R就是等价关系 习题3 12 p145 1 设集合为 3 5 15 1 2 3 6 12 3 9 27 54 偏序关系为整除 画出这些集合的偏序关系图 并指出哪些是全序关系 第3个图代表全序 习题3 12 p146 6 题见书本极大元最大元极小元最小元Px1x1x4 x5无上界上确界下界下确界 x2 x3 x4 x1x1x4x4 x3 x4 x5 x1 x3x3无无 x1 x2 x3 x1x1x4x4 习题3 12 p146 7 题目省略画哈斯图 注意先看出射点和入射点 全序和良序只为 c 图 习题4 1 p151 1 题目省略解答 a 都不是 b 都不是 c 是满射 d 都不是 i 1和i 1 值相同 e 是双射 习题4 1 p151 5 假定X和Y是有穷集合 找出从X到Y存在入射的必要条件是什么 解答 1 x1 x2 则f x1 f x2 即y1 y22 Y集合的点多 X集合的点少 即 Y X 条件1 2 分别为从X到Y存在入射的必要条件 条件1 2 合起来是充要条件 习题4 2 p156 1 题目省略解答 f要有f 1 f必须为双射 构造f f 2 f 3 f f 2 f I ff 1 ff f 1 令g f g 2 f 2 I 习题4 2 p156 3 要证明c 只需要证明a b a 比较明显 按定