离散数学关系的闭包ppt课件.ppt

1 4 4关系的闭包 闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质 2 一 闭包定义 定义设R是非空集合A上的关系 R的自反 对称或传递 闭包是A上的关系R 使得R 满足以下条件 1 R 是自反的 对称的或传递的 2 R R 3 对A上任何包含R的自反 对称或传递 关系R 有R R 一般将R的自反闭包记作r R 对称闭包记作s R 传递闭包记作t R 3 由闭包的定义可知 R的自反 对称 传递 闭包是含有R并且具有自反 对称 传递 性质的 最小 的关系 如果R已是自反的二元关系 显然有 R r R 同样 当R是对称的二元关系时R s R 当R是传递的二元关系时 R t R 且反之亦然 4 二 关系的闭包运算 1 已知一个集合中的二元关系R 则r R s R t R 是唯一的 它是包含R的最小的自反 对称 传递 关系 2 若R是自反 对称 传递 的 则r R s R t R 就是R本身 3 若R不是自反 对称 传递 的 则可以补上最少序偶 使之变为自反 对称 传递关系 从而得到r R s R t R 5 例 设 a b c R 求r R s R t R 解 r R s R t R 例 设 a b R 则r R s R t R R 6 设R是A上的二元关系 x A 将所有 x x R的有序对加到R上去 使其扩充成自反的二元关系 扩充后的自反关系就是R的自反闭包r R 例如 A a b c d R a a b d c c R的自反闭包r R a a b d c c b b d d 于是可得 定理 R是A上的二元关系 则R的自反闭包r R R IA 1 构造R的自反闭包的方法 三 闭包的构造方法 7 2 构造R的对称闭包的方法 每当 a b R 而 b a R时 将有序对 b a 加到R上去 使其扩充成对称的二元关系 扩充后的对称关系就是R的对称闭包s R 例如 A a b c d e R a a a b b a b c d e R的对称闭包s R a a a b b a b c c b d e e d 定理 R是A上二元关系 是其逆关系 则R的对称闭包s R R 由逆关系的定义可知 8 3 构造R的传递闭包的方法 设R是A上的二元关系 每当 a b R和 b c R而 a c R时 将有序对 a c 加到R上使其扩充成R1 并称R1为R的传递扩张 R1如果是传递关系 则R1是R的传递闭包 如果R1不是传递关系 继续求R1的的传递扩张R2 如果R2是传递关系时 则R2是R的传递闭包 如果R2不是传递关系时 继续求R2的的传递扩张R3 如果A是有限集 R经过有限次扩张后 定能得到R的传递闭包 扩张后的传递关系就是R的传递闭包t R 定理 设R为A上的关系 则有t R R R2 R3 说明 对于有穷集合A A n 上的关系 上式中的并最多不超过Rn 9 思考 设A a b c d R 求r R s R t R 解 r R R R0 s R R R 1 t R R R2 R3 R4 R2 R3 R4 R2 于是t R R R2 R3 10 闭包的构造方法 续 设关系R r R s R t R 的关系矩阵分别为M Mr Ms和Mt 则 Mr M EMs M M Mt M M2 M3 E是和M同阶的单位矩阵 M 是M的转置矩阵 注意在上述等式中矩阵的元素相加时使用逻辑加 11 闭包的构造方法 续 设关系R r R s R t R 的关系图分别记为G Gr Gs Gt 则Gr Gs Gt的顶点集与G的顶点集相等 除了G的边以外 以下述方法添加新边 考察G的每个顶点 如果没有环就加上一个环 最终得到Gr 考察G的每条边 如果有一条xi到xj的单向边 i j 则在G中加一条xj到xi的反方向边 最终得到Gs 考察G的每个顶点xi 找从xi出发的每一条路径 如果从xi到路径中任何结点xj没有边 就加上这条边 当检查完所有的顶点后就得到图Gt 12 实例 例1设A a b c d R R和r R s R t R 的关系图如下图所示 R r R s R t R 南宁空调回收南宁空调出租仧莒彾 MicrosoftOfficePowerPoint 是微软公司的演示文稿软件 用户可以在投影仪或者计算机上进行演示 也可以将演示文稿打印出来 制作成胶片 以便应用到更广泛的领域中 利用MicrosoftOfficePowerPoint不仅可以创建演示文稿 还可以在互联网上召开面对面会议 远程会议或在网上给观众展示演示文稿 MicrosoftOfficePowerPoint做出来的东西叫演示文稿 其格式后缀名为 ppt pptx 或者也可以保存为 pdf 图片格式等 14 定理R是A上关系 则 R是自反的 当且仅当r R R R是对称的 当且仅当s R R R是传递的 当且仅当t R R 证明略 因为由闭包定义即可得 定理R是A上关系 则 R是自反的 则s R 和t R 也自反 R是对称的 则r R 和t R 也对称 R是传递的 则r R 也传递 证明 因为R自反 得r R R 即R IA R r s R s R IA R R 1 IA R IA R 1 r R R 1 R R 1 s R s R 自反 15 类似可以证明t R 也自反 证明 证明t R 对称 t R 1 R R2 Rn 1 R 1 R2 1 Rn 1 R 1 R 1 2 R 1 n R R2 Rn R对称 R 1 R t R 所以t R 也对称 类似可以证明r R 也对称 证明 证明r R 传递 先用归纳法证明下面结论 R IA i IA R R2 Ri i 1时R IA IA R结论成立 假设i k时结论成立 即 R IA k IA R R2 Rk 16 当i k 1时 R IA k 1 R IA k R IA IA R R2 Rk IA R IA R R2 Rk R R2 Rk 1 IA R R2 Rk Rk 1所以结论成立 t r R t R IA R IA R IA 2 R IA 3 IA R IA R R2 IA R R2 R3 IA R R2 R3 IA t R IA R R传递t R R r R 所以r R 也传递 17 定理设R1 R2是A上关系 如果R1 R2 则 r R1 r R2 s R1 s R2 t R1 t R2 证明 r R1 IA R1 IA R2 r R2 类似可证 定理设R是A上关系 则 sr R rs R tr R rt R st R ts R 证明 sr R r R r R 1 R IA R IA 1 R IA R 1 IA 1 R IA R 1 IA R R 1 IA s R IA rs R 的证明用前边证明的结论 R IA k IA R R2 Rk很容易证明 这里从略 18 因R s R 得t R ts R