复合关系逆关系及闭包.ppt

3 7复合关系和逆关系 3 7 1复合关系定义1 复合 合成 composite 关系 设R为X到Y的关系 S为从Y到Z上的关系 则R S称为R和S的复合关系 表示为 R S x X z Z y y Y R S 3 7 2逆关系 定义2 逆 inverse 关系 设R是X到Y的二元关系 则从Y到X的二元关系Rc定义为 Rc R 整数集合上的 关系的逆关系是 关系 人群中的父子关系的逆关系是子父关系 容易看出 Rc c R 例1 设R S 求 1 Rc Sc 2 R S S R解 1 Rc Sc 2 R S S R 例2 书上的例题2 第115页 定理1 设R1 R2 R3为关系 R1是X到Y的关系 R2是Y到Z的关系 R3是Z到W的关系则 R1 R2 R3 R1 R2 R3 证明 R1 R2 R3 z z Z x R1 R2 z zR3w z z Z y y Y xR1y yR2z zR3w z y z Z y Y xR1y yR2z zR3w yt z z Z y Y xR1y yR2z zR3w y y Y xR1y z z Z yR2z zR3w y y Y xR1y y R2 R3 w xR1 R2 R3 w R1 R2 R3 R1 R2 R3 R1 R2 R3 说明 本定理说明复合运算满足结合律 由复合关系满足结合律 可以把关系R本身所组成的复合关系写成 R R R R R R R R m个 分别记作R 2 R 3 R m 可以证明复合关系不满足交换律 R1 R2 R2 R1 7 3 3关系矩阵的性质 1 MRc MR T T表示矩阵转置 2 MR1 R2 MR1 MR2 表示布尔乘法 其中加法使用逻辑 乘法使用逻辑 3 7 4逆关系关系图的性质 关系Rc的图形是将关系R图形中弧的箭头方向反置 定理2 设R R1 R2都是从A到B的二元关系 则有 1 R1 R2 c R1c R2c 2 R1 R2 c R1c R2c 3 A B c B A 4 R c Rc 这里 R A B R 5 R1 R2 c R1c R2c注 证明 1 4 5 见书117页 定理3 设R S为二元关系 则 R S c Sc Rc 证明 R S c R S z yRz zSx z zRcy xScz z xScz zRcy Sc Rc 定理4 设R为X上的二元关系 则 1 R是对称的 R Rc 证明见书118页 2 是反对称的 R Rc IX定理5 P119 2 设R为X上的二元关系 则 1 R是传递的 R R R 2 R是自反的 IX R 例题 设A a b c R1 R2 用MR1 MR2确定MR1c MR2c MR1 R1 MR1 R2 MR2 R1 从而求出它们的集合表达式 110110MR1 101MR1c 100000010011000MR2 001MR2c 100000110011MR1 R2 MR1 MR2 011000R1 R2 110110111MR1 R1 MR1 MR1 101 101 110000000000R1 R1 011110101MR2 R1 MR2 MR1 001 101 000000000000R2 R1 解 R1c R2c R1 R1 R1 R2 R2 R1 作业 3 7 P118 1 5 3 8关系的闭包运算 自反闭包r R reflexivityclosure 对称闭包s R symmetryclosure 传递闭包t R transitivityclosure 闭包的性质 求法 相互关系 3 8 1自反闭包 reflexiveclosure 定义1 自反闭包 包含给定关系R的最小自反关系 称为R的自反闭包 记作r R 1 r R 是自反的 2 R r R 3 S R S S自反 r R S 3 8 2对称闭包 symmetricclosure 定义2 对称闭包 包含给定关系R的最小对称关系 称为R的对称闭包 记作s R 1 s R 是对称的 2 R s R 3 S R S S对称 s R S 3 8 3传递闭包 transitiveclosure 定义3 传递闭包 包含给定关系R的最小传递关系 称为R的传递闭包 记作t R 1 t R 是传递的 2 R t R 3 S R S S传递 t R S 定理1 设R A A且A 则 1 R自反 r R R 2 R对称 s R R 3 R传递 t R R 证明 1 R R R自反 r R R又R r R r R R 2 3 完全类似 补充 定理1 设R1 R2 A A且A 则 1 r R1 r R2 2 s R1 s R2 3 t R1 t R2 证明 1 R1 R2 r R2 自反 r R1 r R2 2 3 类似可证 补充 定理2 设R1 R2 A A且A 则 1 r R1 R2 r R1 r R2 2 s R1 R2 s R1 s R2 3 t R1 R2 t R1 t R2 证明 1 利用定理20 r R1 R2 r R1 r R2 r R1 r R2 自反且包含R1 R2 所以r R1 R2 r R1 r R2 r R1 R2 r R1 r R2 证明 2 利用定理20 s R1 R2 s R1 s R2 s R1 s R2 对称且包含R1 R2 所以s R1 R2 s R1 s R2 s R1 R2 s R1 s R2 证明 3 利用定理20 t R1 R2 t R1 t R2 反例 t R1 R2 t R1 t R2 定理2 设R A A且A 则 1 r R R IA 2 s R R Rc 3 t R R R2 R3 对比 R自反 IA RR对称 R RcR传递 R2 R 证明 1 r R R IA i R R IA ii IA R IA R IA自反 r R R IA iii R r R r R 自反 R r R IA r R R IA r R r R R IA 证明 2 s R R Rc i R R Rc ii R Rc c R Rc R Rc对称 s R R Rc iii R s R s R 对称 R s R Rc s R R Rc s R s R R Rc 证明 3 之前 说明以下事实 复合运算对并运算满足分配律R1 R2 R3 R1 R2 R1 R3 R1 R2 R3 R1 R3 R2 R3 复合运算对交运算满足弱分配律R1 R2 R3 R1 R2 R1 R3 R1 R2 R3 R1 R2 R1 R3 证明 3 t R R R2 R3 证明 i 先证t R R R2 R3 R R R2 R3 R R2 R3 2 R2 R3 R R2 R3 R R2 R3 传递 t R R R2 R3 ii 再证R R2 R3 t R R t R t R 传递 R t R R2 t R R3 t R R R2 R3 t R t R R R2 R3 定理3 设X是含有n个元素的集合 R是X上的二元关系 则存在一个正整数k n 使得t R R R2 R3 Rk证明 见P122 例题1 设A a b c d R 求r R s R t R 解 r R R IA s R R Rc t R R R2 R3 R4 见P123 求传递闭包的另一种方法 当有限集X的元素较多时 矩阵运算很繁琐 Warshall在1962年提出了R 的一个有效算法如下 1 置新矩阵A M 2 置i 1 3 对所有j如果A j i 1 则对k 1 2 nA j k A j k A i k 4 i i 1 5 如果i n 则转到步骤 3 否则停止 引出下面定理 闭包运算是否可以交换顺序 即 1 rs R sr R 2 rt R tr R 3 st R ts R 定理4 设R A A且A 则 1 rs R sr R 2 rt R tr R 3 st R ts R 证明 1 rs R r s R r R Rc IA R Rc IA R IAc Rc IA R IA R c r R r R c s r R sr R rs R sr R 2 证明 rt R r t R r R R2 R3 IA R R2 R3 IA R IA R R2 IA R R2 R3 IA R IA R 2 IA R 3 r R r R 2 r R 3 t r R rt R tr R 3 st R ts R 证明 st R st s R sts R s ts R ts R 对称 ts R st R ts R 本次课小结及要求 关系的运算除集合运算外还有复合关系 逆关系及闭包运算 要求会做复合关系 逆关系及闭包运算 会做相应的证明 作业 3 8 P127 1 2 a 7 选作