离散数学--第三章--集合与关系---习题课 PPT课件

离散数学 第三章集合与关系 3 2 9 在什么条件下 下面命题为真 a A B A C A A B A C A B A C A B C A B C A B C A所以满足此式的充要条件是 A B C 或A B C b A B A C A B A C A B C A B C 所以满足此式的充要条件是 A B Cc A B A C A B A C A B A C A B C A B C A B C 所以满足此式的充要条件是 A B Cd A B A C 因为当且仅当A B 才有A B 所以满足此式的充要条件是 A B A C 3 2 4 集合的证明a 证明 A B C A B C iffC A证明 C A A B C A B C A B C A C B C A B C C A A C A A B C A B C C A x C x C x A B C x A B C x A所以C A所以 A B C A B C iffC A 3 2 5 b 证明 A B C A C B A B C A B C A C B A C B所以 A B C A C B x x A B C x A B x C x A x B x C x A x C x B x A C x B x A C B所以 A B C A C B 第104页 b A 0 1 B 1 2 求A2 B A B x A y B A2 A A A2 B 1 1 1 1 2 2 2 2 注意 A2 B A A B A A B第105页 设A a b 构成集合P A AP A a b a b P A A 第109页 X a b c Y s X到Y的所有关系 X Y X Y的任何一个子集都是一个从X到Y的关系 如果 X m Y n则有2mn个从X到Y的关系 故 有23 8个关系 R0 R1 R2 R3 R4 R5 R6 R7 设 A n 有多少个A上的关系 因为R A A 所以A A有多少个子集就有多少个A上关系 由集合的幂集就是该集合的子集构成的 所以A上关系个数就是A A的幂集P A A 的元素个数 P A A 而2 A A 2nn 所以有个不同的A上关系 P1093 5 5 注意 A上的关系 结点数为A中元素的个数 第113页 A 1 2 3 A上五个关系如下 R S T A A R A A T S 自反反自反对称反对称传递 NNNYY YNYNY NNNYN NYYYY YNYNY 上述五个关系中 哪些是等价关系 如果是等价关系 求其商集 哪些是相容关系 如果是相容关系 求其完全覆盖 哪些是偏序关系 如是偏序关系 画Hasse图 并求 的极小 大 元 最小 大 元 上界与下界 上确界和下确界 等价关系 S和A A 对应的商集分别是 A S 1 2 3 A A 1 2 3 相容关系 S和A A 对应的完全覆盖分别是 CS A 1 2 3 CA A A 1 2 3 偏序关系 T 的极小元 最小元 下界 下确界都是 1 的极大元 最大元 上界 上确界都是 3 T 1 2 3 P113 3 举出A 1 2 3 上关系R的例子 使其具有下述性质 a 既是对称的 又是反对称的 b 既不是对称的 又不是反对称的 c 是可传递的 1 2 3 1 2 3 1 2 3 归纳 关系性质证明方法 设R是A上关系 一 证明R的自反性 方法1用自反定义证 任取x A 证出 R 方法2用恒等关系IA证 证出IA R P119 2 b 方法3用自反闭包证 证出r R R 即R IA R 二 证明R的反自反性 方法1用反自反定义证 任取x A 证出 R 方法2用R IA 证三 证明R的对称性 方法1用对称定义证 任取x y A 设 R 证出 R 方法2用求逆关系证 证出Rc R 方法3用对称闭包证 证出s R R 即R Rc R 四 证明R的反对称性方法1用定义1证 任取x y A 设 R R 证出x y 方法2用定义2证 任取x y A x y 设 R 证出 R 方法3用定理证 证出R Rc IA 见教材P118 五 证明R的传递性 方法1用传递定义证 任取x y z A 设 R R 证出 R 方法2用传递闭包证 证出t R R 即R R2 R3 R 方法3用定理证 证出R R R P119 2 a 下面证明第113页 4 证明 一 证明R S的自反性方法1用自反定义证 任取x A 证出 R S 因R和S都自反 所以有 R S 于是有 R S 所以R S也自反 方法2用恒等关系IA证 证出IA R S 因R和S都自反 所以IA R IA S 所以IA R S所以R S也自反 方法3用自反闭包证 证出r R S R S 即 R S IA R S 因R和S都自反 所以r R R r S S r R S R S IA R IA S IA r R r S R S所以R S也自反 P113 4 R和S都A上是自反 对称 传递的 求证R S也是自反 对称和传递的 二 证明R S的对称性 方法1用对称定义证 任取x y A 设 R S 证出 R S 则 R S 因为R和S对称 所以有 R S 于是 R S R S对称 方法2用求逆关系证 证出 R S c R S 因为R和S对称 所以有Rc R Sc S 而 R S c Rc Sc R S R S对称 方法3用对称闭包证 证出s R S R S 即 R S R S c R S 因为R和S对称 所以s R R s S Ss R S R S R S c R S Rc Sc R Rc R Sc S Sc S Rc s R R Sc s S S Rc R R Sc S S Rc R S 吸收律 R S对称 五 证明R的传递性 方法1用传递定义证 任取x y z A 设 R S R S 证出 R S R S R S R S R S R R S S R S 因为R S传递 R S所以R S传递 方法2用传递闭包证 证出t R S R S 即 R S R S 2 R S 3 R S 方法3用定理证 证出用方法2 方法3证明此题的传递性有很大难度 R S T R S R T 希望同学们灵活掌握证明关系性质的方法 P127 1 R的有向图如图所示 求r R s R t R P1273 9 5 设R1和R2是非空集合A上的关系 且R2 R1则 1 r R2 r R1 2 s R2 s R1 3 t R2 t R1 证明 1 R2 R1 R2 IA R1 IA r R2 r R1 2 R2 R1 R2C R1C R2 R2C R1 R1C s R2 s R1 3 R2 R1 R22 R12 R23 R13 R2 R22 R23 R1 R12 R13 t R2 t R1 因为R2 R1 而R1 t R1 所以R2 t R1 且又因为t R1 具有传递性 t R2 是包含R2的最小传递关系 所以t R2 t R1 集合与关系的结构图 枚举法有向图矩阵 等价关系 有向图 等价类 商集 划分 偏序关系 相容类 最大相容类 完全覆盖 简化图 全序 哈斯图 计算方法 运算性质 重要元素 第130页 1 X是集合 且 X 4 X有多少个不同的划分 解 第134页 2 X是集合 且 X 4 X上有多少个不同的等价关系 解 此题的答案与上题一样 因为每个划分对应一个等价关系 P134 4 R是A上关系 设S c A R R 求证若R是等价关系 则S也是等价关系 证明 a 证S自反 任取a A R是自反的 有 R 由S定义得 S S定义中c就是a S自反 b 证S对称 任取a b A 且有 S 由S定义得 c A R R 由R对称得 c A R R 由S定义得 S S对称 c 证S传递 任取a b c A 有 S S 由S定义得 d A R R e A R R 由于R传递 所以有 R R 由S定义得 S 所以S传递 所以S是A上等价关系 P135 6 R是A上对称和传递的关系 证明如果 a A b A 使得 R 则R是一个等价关系 证明 任取a A 由已知得 b A 使得 R 由R对称得 R 又由R的传递性得 R R是自反的 R是等价关系 P135 7 R和S都是A上等价关系 下面哪个是A上等价关系 证明或举反例说明 a R 即A A R b R Sc R2d r R S 解 a b d 不是 请看反例 R b b S b A A R b R2 b R S b r R S c 证R2自反 任取a A 因为R自反 所以 R 根据关系的复合得 R R 即 R2 R2自反 证R2对称 R2 c Rc 2 R2 由R对称得Rc R R2对称 证R2传递 任取a b c A 设有 R2 R2 根据关系的复合得 d A R R e A R R 由于R传递 所以有 R R R2所以R2传递 最后得R2是等价关系 相容关系1 定义 给定集合X上的关系r 若r是自反的 对称的 则r是A上相容关系 2 图的简化 不画环 两条对称边用一条无向直线代替 3 矩阵的简化 因为r的矩阵是对称阵且主对角线全是1 用下三角矩阵 不含主对角线 代替r的矩阵 4 相容类 设r是集合X上的相容关系 C A 如果对于C中任意两个元素x y有 r 称C是r的一个相容类 5 最大相容类 设r是集合X上的相容关系 C是r的一个相容类 如果C不能被其它相容类所真包含 则称C是一个最大相容类 最大完全多边形 6 完全覆盖 r是中的相容关系 由r的所有最大相容类为元素构成的集合 称之为X的完全覆盖 记作Cr X 第139页 2 X x1 x2 x3 x4 x5 x6 R是X上相容关系 其简化关系矩阵如下 求X的完全覆盖 解 R的简化图为 CR X x1 x2 x3 x1 x3 x6 x3 x4 x5 x3 x5 x6 o 偏序关系判断 会画Hasse图 会求一个子集的极小 大 元 最小 大 元 上界与下界 最小上界及最大下界 1 定义 R是A上自反 反对称和传递的关系 则称R是A上的偏序关系 并称是偏序集 2 x与y是可比较的 是偏序集 x y A 如果要么x y 要么y x 则称x与y是可比较的 3 定义 是偏序集 任何x y A 如果x与y都是可比较的 则称 是全序关系 线序 链 4 偏序集Hasse图的画法 令是偏序集 1 用 表示A中元素 2 如果x y 且x y 则结点y要画在结点x的上方 从最下层结点 全是射出的边与之相连 逐层向上画 直到最上层结点 全是射入的边与之相