离散数学-二元关系与运算.ppt

二元关系和运算 第四章 1 二元有序组 由两个元素x和y按一定顺序排成二元组 记作 4 1二元关系的概念 如 平面直角坐标系中点的坐标 一 二元关系的概念 二元有序组的性质 1 当x y时 2 当且仅当x u y v 1 2 说明有序组区别于集合 n元有序组 由n个元素x1 x2 xn 按一定顺序排成的n元组 记作 x1 x2 xn 2 一种新的集合运算 积运算 设A B为两集合 用A中元素为第一元素 B中元素作为第二元素构成的二元有序组的全体叫做A和B的笛卡儿积 记作 A B 符号化 A B x A y B 例4 1设A a b B 0 1 2 求A B B A 解 根据笛卡儿积的定义知 A B B A 一般地 如果 A m B n 则 A B B A mn 积运算的性质 1 若A B中有一个空集 则笛卡儿积是空集 即 B A 2 当A B 且A B都不是空集时 有A B B A 3 当A B C都不是空集时 有 A B C A B C 因为 A B C中的元素 z 而A B C 中的元素为 4 A B C A B A C 对 的分配律 B C A B A C A A B C A B A C B C A B A C A 我们证明 A B C A B A C 证明思想 要证明两个集合相等 通常有两种方法 一是证两个集合相互包含 二是利用已有的集合运算的性质 算律和已证明过的公式 仿照代数恒等式的证明方法 一步步从左 右 边推出右 左 边 或从左 右边分别推出同一个集合式子 一般说来 最基本的集合相等关系要用第一种证法 比较复杂的集合相等关系用第二种方法更好 但第二种方法的使用取决于我们对算律和常用公式的熟练程度 证明 用第一种方法 对于任意的 A B C x A y B C x A y B y C x A y B x A y C A B A C A B A C A B C A B A C 例4 2设A 1 2 求P A A 解 P A A 1 2 1 2 n阶笛卡儿积 x1 x2 xn x1 A1 x2 A2 xn An A1 A2 An 1 2 二元关系 如果一个集合的元素都是二元有序组 则这个集合称为一个二元关系 记作 R 如果 R 记作xRy 3 二元关系的数学定义 从A到B的二元关系 设A B为集合 A B的任何子集所定义的二元关系叫做从A到B的二元关系 若A B 叫做A上的二元关系 若 A n 则 A A n2 就是说 A上有个不同的二元关系 其中包括空关系 全域关系UA和恒等关系IA A A的所有子集有个 例4 3设A a b 写出P A 上的包含关系R 解 P A a b a b R A上关系的表示法 1 关系矩阵 设A x1 x2 xn R是A上的关系 则 rij nxn 是R的关系矩阵 令 二 二元关系的表示方法 2 关系图 以E xi A xj A xiRxj 为有向边集组成的有向图G 以V A x1 x2 xn 为顶点集 例4 4设A 1 2 3 4 R 是A上的关系 试写出R的关系矩阵并画出关系图 解 关系矩阵 0011 0000 0100 关系图 4 2关系的运算 关系R的定义域 domR x y R 即R中有序组的第一个元素构成的集合 关系R的值域 ranR y x R 即R中有序组的第二个元素构成的集合 一 关系的定义域与值域 例4 5下列关系都是整数集Z上的关系 分别求出它们的定义域和值域 1 R1 x y Z x y 2 R2 x y Z x2 y2 1 3 R3 x y Z y 2x 4 R4 x y Z x y 3 解 domR1 ranR1 Z 解 R2 domR2 ranR2 1 R1 x y Z x y 2 R2 x y Z x2 y2 1 解 domR3 Z ranR3 偶数 解 domR4 ranR4 3 R3 x y Z y 2x 4 R4 x y Z x y 3 二 关系的常用运算 F是任意关系 F的逆F 1 yFx F G是任意两个关系 F与G的合成记作 F G z xGz zFy 关系F在集A上的限制 记作 F A xFy x A 集A在关系F下的象F A ran F A 1 逆 2 合成 3 限制 4 象 例4 6设F G是N上的关系 其定义为 F x y N y x2 G x y N y x 1 求G 1 F G G F F 1 2 F 1 2 解 由定义知 G 1 y x N y x 1 列出G 1中的元素就是 G 1 为了求F G 可以先直观表示如下 对任何x N 即y x 1 2 因此F G x y N y x 1 2 同理可求G F 自己做 发现F G G F F 1 2 F 1 2 ran F 1 2 1 4 关系运算的性质 设F G H 为任意关系 则有 1 F 1 1 F 2 domF 1 ranF ranF 1 domF 3 F G H F G H 4 F G 1 G 1 F 1 5 F G H F G F H 对 的分配律 6 F G H F G F H 对 的半分配律 7 G H F G F H F 8 G H F G F H F 任取 F G 1 F G z G F z G 1 F 1 G 1 F 1 4 F G 1 G 1 F 1的证明 任取 F G H z G H F z G H F 注意对括号的顺序 z G F H F F G F H F G H F G F H 5 F G H F G F H的证明 4 3关系的性质 R的关系矩阵 主对角线元素全是1 R的关系图 每个顶点都有环 自反性 x A有 R R是A上的关系 关系矩阵 主对角线元素全是0 关系图 每个顶点都没有环 反自反性 x A R 对称性 若 R 则 R 关系矩阵 对称阵 关系图 如果两个顶点之间有边 一定是一对方向相反的边 反对称性 若 R且x y 则 R 关系矩阵 如果rij 1 且i j 则rji 0 关系图 如果两个顶点之间有边 一定是只有一条有向边 传递性 若 R且 R 则 R 关系图 如果顶点xi到xj有边 xj到xk有边 则从xi到xk有边 例4 7设A 1 2 10 对于A上的关系R x y 3 I I为整数集 问R有哪些性质 解 逐条性质加以验证R x y 3 I 任取A中元素x 由于 x x 3 0 所以R是自反的 又设A中任意两个元素x y 如果xRy 即x y可被3整除 则y x也一定可被3整除 即yRx 从而R是对称的 如果A中三个元素x y z满足xRy yRz 则x y y z被3整除 由于x z x y y z 所以x z被3整除 从而xRz即R具有传递性 4 4关系的闭包运算 闭包 设R A A 自反闭包记作r R 对称闭包记作s R 传递闭包记作t R 由A求r R s R t R 的过程叫闭包运算 那么 包含R而使之具有自反性质的最小关系 称之为R的自反闭包 包含R而使之具有对称性质 传递性质 的最小关系 称之为R的对称 传递 闭包 一 定义 幂运算 设R A A k N 约定 1 R0 IA x A 2 R1 R 3 Rk 1 Rk R 显然Rm Rn Rm n Rm n Rmn 二 计算方法 为了有效地计算关系R的各种闭包 先引进关系的幂运算概念 闭包运算的方法 设R是A上的任一关系 则 1 r R R IA 2 s R R R 3 t R R R2 R3 Rn 矩阵形式 M为R的关系矩阵 1 Mr M E 2 Ms M M M 是M的转置 3 Mt M M2 M3 其中 均表示 逻辑加 例4 8设A a b c d A上的关系 求r R s R 和t R 解 r R R IA R R 三 实例 s R R R t R R R2 R3 R 而R2 R R R3 R2 R R4 R3 R 实际上 看到当k 4时 已有R4 R R2 R3 故t R R R2 R3 四 闭包运算的性质 设A是有限集且 A n R A A 则 4 6等价关系和偏序关系 等价关系 集A上的关系R是自反的 对称的和传递的 等价类 R是集A上的等价关系 对于任一a A a R x aRx x A 被称为a的等价类 即A中所有和a有R关系的元素的集合 一 等价关系及用途 等价类的性质 R是非空集合 对任意的x y A 下面的结论成立 1 x 且 x A 等价类为A的子集 2 若xRy 则 x y 3 若x Ry 则 x y 集A在等价关系R下的商集 设R为非空集A上的等价关系 以R的不交的等价类为元素的集合叫做A在R下的商集 记作A R 即 A R x R x A 集A的划分 设A是非空集合 1 2 中任意两个元素不交 3 中所有元素的并集为A 则 为A的划分 如果存在一个A的子集族 P A 满足以下条件 由等价类的性质和商集的定义可知 商集A R是A的划分 称之为由R诱导的划分 反过来 给定A的任一划分 则A被分割成若干个划分块 若定义A上的二元关系R x y A且x y属 的同一块 则xRy 那么R是A上的等价关系 称之为由 诱导的等价关系 集A上的等价关系与划分是一一对应的 例4 9设A 1 2 3 求出A上所有的等价关系 解 先求A的各种划分 只有1个划分块的划分 1 具有两个划分块的划分 2 3 和 4 具有3个划分块 5 1 A 2 1 2 3 4 3 1 2 3 2 1 3 5 1 2 3 设对应于划分 i的等价关系Ri i 1 2 5 则有 R5 R1 R2 R3 R4 偏序关系 集A上的关系R是自反的 反对称的和传递的 记作 且称 A 为偏序集 二 偏序关系及用途 例4 10设A 2 4 6 8 A上关系R是通常意义下的小于或等于关系 试写出R并验证它是偏序关系 解 R 1 自反性 2 反对称性 3 传递性 均属于R 对任意的 R 必有x y 当x y时 y x 从而 R 对任意的 R R 由于x y y z 所以x z 从而 R 例4 11设C a b a b C上关系T是集合的 包含于 试写出T 并验证它是偏序关系 解 同例4 10类似 自己做 偏序集的哈斯图 1 用小圆圈表示偏序集的元素 称为结点 2 按每个元素在偏序中的次序从底向上列结点位置 3 对于偏序集中任意两个元素x和y 如果x y且不存在另一个元素a 使x a a y 则在x与y两结点之间划上一杠 即 x在下 y在上 全序关系 设是偏序集 x y x A y A x y y x 成立 则称 A 为全序集 这时的偏序关系叫全序关系 全序集 A 中全部元素可以排序 它的哈斯图为一条直线 如果 偏序集中的一些特殊元素 设是偏序集 B A 1 如果 y B 使得 x x B y x 为真 则y是B的最小元 小于 B中所有元 2 如果 y B 使得 x x B x y 为真 则y是B的最大元 大于 B中所有元 4 若 y B 使得 x x B x y 则称y是B的极大元 B中没有比y大的其他元 5 若 y A 使得 x x B x y 为真 则称y是B的上界 3 若 y B 使得 x x B x y 则称y是B的极小元 B中找不到x小于y 6 若 y A 使得 x x B y x 为真 则称y是B的下界 7 令C y y为B的上界 则称C的最小元为B的上确界或最小上界 8 令D y y为B的下界 则D的最大元为B的下确界或最大下界 例4 12画出和的哈斯图 并指出其中的特殊元 解 1 的哈斯图如下 由图可知1为最小元 没有最大元 7 8 9 10 11 12均为极大元 极小元为1 1为 1 2 12 的下界 也是下确界 1 2 12 中没有上确界或上界 2 的哈斯图如下 P a b c a b c a b a c b c a b c 由图可知 为P a b c 的最小元 a b c 为它的最大元 同时 a b c 也分别为它们的极小元和极大元 下确界和上确界 a b c d e 例4 13已知偏序集的哈斯图如下 h g f 试写出对应的A和A上的偏序关系R 并指出A中的特殊元 解 A a b c d e f g h 直接由哈斯图可知 A中没有最小元和最大元 e g和h均为A的极大元 a b f和h均为A的极小元 没有上确界和下确界 R a b c d e h g f 小结与学习要求 了解二元关系的定义和表示方法 熟练掌握关系的性质和运算 特别是复合和三种闭包运算 理解等价关系和偏序关系 明确它们在描述研究对象的结构和特点时重要作用 即分类和覆盖 它们在计算机科学中有重要应用