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

《复合关系逆关系及闭包讲稿.ppt》由会员分享，可在线阅读，更多相关《复合关系逆关系及闭包讲稿.ppt（34页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2022-9-61第一页，讲稿共三十四页哦定义定义2逆逆(inverse)关系关系:设设R是是X到到Y的二元关系，则从的二元关系，则从Y到到X的二元的二元关系关系Rc定义为：定义为：Rc=|R.整数集合上的整数集合上的“”关系的逆关系是关系的逆关系是“”关系。关系。人群中的父子关系的逆关系是子父关系。人群中的父子关系的逆关系是子父关系。容易看出容易看出(Rc)c=R2022-9-62第二页，讲稿共三十四页哦例例1:设设 R=,S=,.求求:(1)Rc，Sc.(2)RS,SR解解:(1)Rc=,Sc=,.(2)RS=,SR=.例例2:（书上的例题（书上的例题2，第，第115页）页）2022-9-

2、63第三页，讲稿共三十四页哦定理定理1:设设R1,R2,R3为关系，为关系，R1 是是X到到Y的关系，的关系，R2是是Y到到Z的关系，的关系，R3是是Z到到W的关系则的关系则(R1R2)R3=R1(R2 R3)证明证明:,(R1 R2)R3 z(z Z x(R1R2)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(R2R3)w)xR1(R2R3)w R1(R2R3)(R1R2)R3=R

3、1(R2 R3).#说明说明:本定理说明复合运算满足结合律本定理说明复合运算满足结合律.2022-9-64第四页，讲稿共三十四页哦由复合关系满足结合律，可以把关系由复合关系满足结合律，可以把关系R本身所组成的复本身所组成的复合关系写成：合关系写成：RR，RRR，RRR(m个个)，分别记作分别记作 R(2)，R(3)，R(m)。可以证明复合关系不满足交换律。可以证明复合关系不满足交换律。R1R2 R2R12022-9-65第五页，讲稿共三十四页哦(1)MRc=(MR)T (T表示矩阵转置表示矩阵转置)(2)MR1 R2=MR1 MR2 (表示布尔乘法表示布尔乘法,其中加法使用逻辑其中加法使用逻辑

4、,乘法使用逻辑乘法使用逻辑 )2022-9-66第六页，讲稿共三十四页哦关系关系 Rc 的图形是将关系的图形是将关系R图形中弧的箭图形中弧的箭头方向反置。头方向反置。2022-9-67第七页，讲稿共三十四页哦定理定理2:设设R、R1、R2都是从都是从A到到B的二元关系，则有的二元关系，则有(1)(R1 R2)c=R1 c R2 c(2)(R1 R2)c=R1 c R2 c(3)(AB)c=B A(4)(R)c=Rc,这里这里R AB-R(5)(R1-R2)c=R1 c-R2 c 注：证明注：证明(1)(4)(5)见书见书117页。页。2022-9-68第八页，讲稿共三十四页哦定理定理3:设设R

5、,S为二元关系为二元关系,则则(RS)c=S c Rc.证明证明:,(RS)c (RS)z(yRz zSx)z(zRcy xScz)z(xScz zRcy)Sc Rc.2022-9-69第九页，讲稿共三十四页哦定理定理4:设设R为为X上的二元关系，则上的二元关系，则(1)R是对称的是对称的R=Rc（证明见书（证明见书118页）页）(2)是反对称的是反对称的R Rc IX定理定理5:P119(2)设设R为为X上的二元关系，则上的二元关系，则(1)R是传递的是传递的(RR)R(2)R是自反的是自反的 IX R2022-9-610第十页，讲稿共三十四页哦例题例题:设设 A=a,b,c,R1=,R2=

6、,用用MR1,MR2确定确定MR1c,MR2c,MR1R1,MR1R2,MR2R1,从而求出它们的集合表从而求出它们的集合表达式达式.2022-9-611第十一页，讲稿共三十四页哦 1 1 0 1 1 0MR1=1 0 1 MR1c=1 0 0 0 0 0 0 1 0 0 1 1 0 0 0MR2=0 0 1 MR2c=1 0 0 0 0 0 1 1 0 0 1 1MR1 R2=MR1 MR2=0 1 1 0 0 0R1R2=,.2022-9-612第十二页，讲稿共三十四页哦 1 1 0 1 1 0 1 1 1 MR1 R1=MR1 MR1=1 0 1 1 0 1 =1 1 0 0 0 0 0

7、 0 0 0 0 0R1R1=,.0 1 1 1 1 0 1 0 1 MR2 R1=MR2 MR1=0 0 1 1 0 1 =0 0 0 0 0 0 0 0 0 0 0 0R2R1=,.2022-9-613第十三页，讲稿共三十四页哦解解:R1c=,R2c=,R1R1=,.R1R2=,.R2R1=,.2022-9-614第十四页，讲稿共三十四页哦P118(1)(5)2022-9-615第十五页，讲稿共三十四页哦自反闭包自反闭包r(R)(reflexivity closure)对称闭包对称闭包s(R)(symmetry closure)传递闭包传递闭包t(R)(transitivity closu

8、re)闭包的性质闭包的性质,求法求法,相互关系相互关系2022-9-616第十六页，讲稿共三十四页哦定义定义1自反闭包自反闭包:包含给定关系包含给定关系R的最小自反关系的最小自反关系,称为称为R的的自反闭包自反闭包,记作记作r(R).(1)r(R)是自反的是自反的;(2)R r(R);(3)(S)(R S S自反自反)r(R)S).2022-9-617第十七页，讲稿共三十四页哦定义定义2对称闭包对称闭包:包含给定关系包含给定关系R的最小的最小对称关系对称关系,称为称为R的对称闭包的对称闭包,记作记作s(R).(1)s(R)是对称的是对称的;(2)R s(R);(3)(S)(R S S对称对称)

9、s(R)S).2022-9-618第十八页，讲稿共三十四页哦定义定义3传递闭包传递闭包:包含给定关系包含给定关系R的最小的最小传递关系传递关系,称为称为R的传递闭包的传递闭包,记作记作t(R).(1)t(R)是传递的是传递的;(2)R t(R);(3)(S)(R S S传递传递)t(R)S).2022-9-619第十九页，讲稿共三十四页哦定理定理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)完全类似完全类似.2022-9-

10、620第二十页，讲稿共三十四页哦*（补充）定理（补充）定理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)类似可证类似可证.2022-9-621第二十一页，讲稿共三十四页哦*（补充）定理（补充）定理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

11、)r(R2).r(R1)r(R2)自反且包含自反且包含R1 R2,所以所以 r(R1 R2)r(R1)r(R2).r(R1 R2)=r(R1)r(R2)2022-9-622第二十二页，讲稿共三十四页哦证明证明(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).2022-9-623第二十三页，讲稿共三十四页哦定理定理2:设

12、设 R A A 且且 A,则则 (1)r(R)=R IA;(2)s(R)=R Rc;(3)t(R)=R R2 R3.对比对比:R自反自反 IA R R对称对称 R=Rc R传递传递 R2 R2022-9-624第二十四页，讲稿共三十四页哦证明证明:(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.2022-9-625第二十五页，讲稿共三十四页哦证明证明:(2)s(R)=R Rc;i)R R Rc;ii)(R Rc)c=R Rc R Rc 对称

13、对称 s(R)R Rc;iii)R s(R)s(R)对称对称R s(R)Rc s(R)R Rc s(R)s(R)=R Rc.2022-9-626第二十六页，讲稿共三十四页哦证明证明(3)之前，说明以下事实：之前，说明以下事实：复合运算对并运算满足分配律复合运算对并运算满足分配律lR1 (R2 R3)=(R1 R2)(R1 R3)l(R1 R2)R3=(R1 R3)(R2 R3)复合运算对交运算满足复合运算对交运算满足弱弱分配律分配律lR1 (R2 R3)(R1 R2)(R1 R3)(1)(R1 R2)R3 (R1 R2)(R1 R3)2022-9-627第二十七页，讲稿共三十四页哦证明证明:(

14、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.#2022-9-628第二十八页，讲稿共三十四页哦定理定理3：设设X是含有是含有n个元素的集合，个元素的集合，R是是X上的二元关系，则存在一个正整数上的二元关系，则存在一个正整数k n，使得使得t(R)=R R2 R3 Rk证明：见证明：见P12

15、2。2022-9-629第二十九页，讲稿共三十四页哦例题例题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=,见见P1232022-9-630第三十页，讲稿共三十四页哦当有限集当有限集X的元素较多时，矩阵运算很繁琐，的元素较多时，矩阵运算很繁琐，Warshall 在在1962年提出了年提出了R+的一个有效算法如的一个有效算法如下：下：（1）置新矩阵）置新矩阵A=M（2）置）置i=1（3）对所有）对所有j如果如果Aj,i=1，则对，则对k=1,2,nAj,k=Aj,k+Ai,k（4）i=

16、i+1（5）如果）如果 i n,则转到步骤（则转到步骤（3）,否则停止。否则停止。2022-9-631第三十一页，讲稿共三十四页哦引出下面定理：引出下面定理：闭包运算是否可以交换顺序闭包运算是否可以交换顺序?即：即：(1)rs(R)=sr(R)?(2)rt(R)=tr(R)?(3)st(R)=ts(R)?2022-9-632第三十二页，讲稿共三十四页哦定理定理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).2022-9-633第三十三页，讲稿共三十四页哦(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).2022-9-634第三十四页，讲稿共三十四页哦