离散数学：第6讲 关系的幂与闭包.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,关系的闭包,*,2025/1/25 周六,关系的闭包,1,复习,复合关系和逆关系,自反性,对称性,传递性,反自反性,反对称性,2025/1/25 周六,关系的闭包,2,举例,在,N=0,1,2,上,:,=|xNyNxy,自反,反对称,传递,=|xNyNxy,自反,反对称,传递,|xNyNx=|xNyNxy,反自反,反对称,传递,|=|xNyNx|y,反对称,传递,(0|0),I,N,=|xNyNx=y,自反,对称,反对称,传递,E,N,=|xNyN=NN,自反,对称,传递,.#,2025/1/25 周六,关系的闭包,3,1,2,，,1,，,2,（）其中（）是的幂集。,自反的，反对称的，传递的。,注：若,改为，则为反自反性。,举例,P,gcd,（，）（互素），,对称的，不是反对称的，不是自反的，也不是反自反的，也无传递性,2025/1/25 周六,关系的闭包,4,总结,(,r,ij,r,jk,),r,ik,2025/1/25 周六,关系的闭包,5,关系运算是否保持关系性质,定理,:,设,R,1,R,2,AA,都具有某种性质,.,自反,反自反,对称,反对称,传递,R,1,-1,R,2,-1,(4),R,1,R,2,R,1,R,2,(2),(5),R,1,R,2,R,2,R,1,(1),矩阵,R,1R,2,R,2,-,R,1,(3),R,1,R,2,(3,),2025/1/25 周六,关系的闭包,6,定理,(,证明,(1),(1)R,1,R,2,自反,R,1,R,2,自反,.,证明,:x,xA,x,R,1,x x,R,2,x,x,R,1,R,2,x,R,1,R,2,自反,R,1,R,2,自反,.,#,2025/1/25 周六,关系的闭包,7,定理,(,证明,(2),(2)R,1,R,2,反,自反,R,1,R,2,反,自反,.,证明,:(,反证,),若,R,1,R,2,非反,自反,则,xA,x(,R,1,R,2,),x,x,R,1,x x,R,2,x,与,R,1,R,2,反,自反矛盾R,1,R,2,反,自反,R,1,R,2,反,自反,.#,2025/1/25 周六,关系的闭包,8,定理,(,证明,(3),(3)R,1,R,2,对称,R,1,-,R,2,对称,.,证明,:x,yA,x(,R,1,-,R,2,)y,x,R,1,y x,R,2,y,y,R,1,x y,R,2,x,y(,R,1,-,R,2,)x,R,1,R,2,对称,R,1,-,R,2,对称,.,#,2025/1/25 周六,关系的闭包,9,定理,(,证明,(3,),(3,)R,1,对称,R,1,对称,.,证明,:x,yA,x(,R,1,)y x(E,A,-,R,1,)y,xE,A,y x,R,1,y,yEA,x y,R,1,x,y(E,A,-,R,1,)x y(,R,1,)x,R,1,对称,R,1,对称,.,#,2025/1/25 周六,关系的闭包,10,定理,(,证明,(4),(4)R,1,反对称,R,1,-1,反对称,.,证明,:(,反证,),若,R,1,-1,非反对称,则,x,yA,x,R,1,-1,y y,R,1,-1,x xy,y,R,1,x x,R,1,y xy,与,R,1,反对称,矛盾,!,R,1,反对称,R,1,-1,反对称,.#,2025/1/25 周六,关系的闭包,11,定理,(,证明,(5),(5)R,1,R,2,传递,R,1,R,2,传递,.,证明,:x,y,zA,xR,1,R,2,)y y(,R,1,R,2,)z,x,R,1,y x,R,2,y y,R,1,z y,R,2,z,x,R,1,y y,R,1,z x,R,2,y y,R,2,z,x,R,1,z x,R,2,z x(,R,1,R,2,)z,R,1,R,2,传递,R,1,R,2,传递,.,#,2025/1/25 周六,关系的闭包,12,关系的闭包,自反闭包,r(R),对称闭包,s(R),传递闭包,t(R),闭包的性质,求法,相互关系,2025/1/25 周六,关系的闭包,13,什么是闭包,闭包(,closure):,包含一些给定对象,具有指定性质的最小集合,“最小”:任何包含同样对象,具有同样性质的集合,都包含这个闭包集合,例:(平面上点的凸包),2025/1/25 周六,关系的闭包,14,自反闭包(,reflexive closure),自反闭包:包含给定关系,R,的最小自反关系,称为,R,的自反闭包,记作,r(R).,(1)R,r(R);,(2)r(R),是自反的;,(3),S(RS S,自反),r(R)S).,G(R),G(r(R),2025/1/25 周六,关系的闭包,15,对称闭包(,symmetric closure),对称闭包:包含给定关系,R,的最小对称关系,称为,R,的对称闭包,记作,s(R).,(1)R,s,(R);,(2)s(R),是对称的;,(3),S(RS S,对称,),s(R)S).,G(R),G(s(R),2025/1/25 周六,关系的闭包,16,传递闭包(,transitive closure),传递闭包:包含给定关系,R,的最小传递关系,称为,R,的传递闭包,记作,t(R).,(1)R,t(R);,(2)t(R),是传递的;,(3),S(RS S,传递,),t(R)S).,G(R),G(t(R),2025/1/25 周六,关系的闭包,17,定理,7.11,定理,7.11:,设,R,A,A,且,A,则,(1),R,自反,r(R)=R,;,(2),R,对称,s(R)=R,;,(3),R,传递,t(R)=R,.,证明:(1),RR,R,自反r(R),R,又,R,r(R),r(R)=R.,(2)(3)完全类似.#,2025/1/25 周六,关系的闭包,18,定理,7.12,定理,7.12:,设,R,1,R,2,A,A,且,A,则,(1),r(R,1,),r(,R,2,),;,(2),s(R,1,),s(,R,2,),;,(3),t(R,1,),t(,R,2,),;,2025/1/25 周六,关系的闭包,19,性质,1,性质,1:,设,R,1,R,2,A,A,且,A,则,(1),r(R,1,R,2,)=,r(R,1,),r(,R,2,),;,(2),s(R,1,R,2,)=,s,(R,1,),s(,R,2,),;,(3),t(R,1,R,2,),t,(R,1,),t(,R,2,).,2025/1/25 周六,关系的闭包,20,如何求闭包?,问题:,(1),r(R)=,R,?,(2),s(R)=R,?,(3),t(R)=R,?,2025/1/25 周六,关系的闭包,21,定理,7.10,定理,7.10:,设,R,A,A,且,A,则,r(R)=,R,I,A,;,s(R)=R,R,-1,;,t(R)=R,R,2,R,3,.,对比:,R,自反,I,A,R,R,对称,R=R,-1,R,传递,R,2,R,2025/1/25 周六,关系的闭包,22,定理,7.10,（,1,）,定理,7.10,（,1,）,:,设,R,A,A,且,A,则,r(R)=,R,I,A,;,证明:(1),R,R,I,A,;,(2),I,A,R,I,A,R,I,A,自反,r(R),R,I,A,;,(3),R,r(R),r(R),自反,R,r(R),I,A,r(R),R,I,A,r(R),r(R)=,R,I,A,.,2025/1/25 周六,关系的闭包,23,定理,7.10,（,2,）,定理,7.10,（,2,）,:,设,R,A,A,且,A,则,s(R)=R,R,-1,;,证明:(1),R,R,R,-1,;,(2)(,R,R,-1,),-1,=,R,R,-1,R,R,-1,对称,s,(R),R,R,-1,;,(3),R,s,(R),s,(R),对称,Rs,(R),R,-1,s,(R),R,R,-1,s,(R),s,(R)=,R,R,-1,.,2025/1/25 周六,关系的闭包,24,定理,7.10,（,3,）,定理,7.10,（,3,）,:,设,R,A,A,且,A,则,t(R)=R,R,2,R,3,;,证明:(1),R,R,R,2,R,3,;,(2)(,R,R,2,R,3,),2,=,R,2,R,3,R,R,2,R,3,R,R,2,R,3,传递,t,(R),R,R,2,R,3,;,(3),R,t,(R),t,(R),传递,R,t,(R),R,2,t,(R),R,3,t,(R),R,R,2,R,3,t,(R),t(R)=R,R,2,R,32025/1/25 周六,关系的闭包,25,推论,推论,:,设,R,A,A,且 0,|A|,则,l,N,使得,t(R)=R,R,2,R,3,R,l,;,证明:由幂定理知,s,tN,(,不妨设,st),使得,R,s,=R,t,.,进一步知,R,R,2,R,3,R,0,R,1,R,t-1,.,取,l=t-1,由定理,7.10,（,3,）知,t(R)=R,R,2,R,3,.,=R,R,2,R,3,R,l,t(R)=R,R,2,R,3,R,l,.#,2025/1/25 周六,关系的闭包,26,例8,例8:设,A=a,b,c,d,R=,.,求,r(R),s(R),t(R).,解:,a,b,c,d,2025/1/25 周六,关系的闭包,27,例8(续),解(续):,a,b,c,d,a,b,c,d,a,b,c,d,2025/1/25 周六,关系的闭包,28,例8(续2),解(续2):,a,b,c,d,2025/1/25 周六,关系的闭包,29,例8(续3),解(续3):,a,b,c,d,2025/1/25 周六,关系的闭包,30,例8(续4),解(续4):,a,b,c,d,a,b,c,d,#,2025/1/25 周六,关系的闭包,31,闭包运算是否保持关系性质?,问题:,(1)R,自反,s(R),t(R),自反?,(2),R,对称,r(R),t(R),对称?,(3),R,传递,s(R),rR),传递?,2025/1/25 周六,关系的闭包,32,定理,7.13,定理,7.13,:设,R,A,A,且,A,则,(1),R,自反,s(R),和,t(R),自反;,(2),R,对称,r(R),和,t(R),对称;,(3),R,传递,r(R),传递;,证明:(1),I,A,R,R,-1,=s(R),s(,R),自反.,I,A,R,R,2,R,3,=t,(R),t(,R),自反.,2025/1/25 周六,关系的闭包,33,定理,7.13(,证明(2),(2),R,对称,r(R),和,t(R),对称;,证明:(2),r(,R),-1,=(,I,A,R),-1,=,I,A,-1,R,-1,=I,A,R,-1,=,I,A,R=,r(,R),r(R),对称.,t,(R),-1,=(,R,R,2,R,3,),-1,=,R,-1,(,R,2,),-1,(,R,3,),-1,=,R,-1,(,R,-1,),2,(,R,-1,),3,(,(,R,S),-1,=S,-1,R,-1,),=,R,R,2,R,3,=,t,(R),t(R),对称.,2025/1/25 周六,关系的闭包,34,定理,7.13(,证明(3),(2),R,传递,r(R),传递;,证明:(2),r(,R),r(,R),=(,I,A,R),(,I,A,R),=,(,I,A,I,A,),(,I,A,R),(,R,I,A,),(R,R),I,A,R,R,R,=,I,A,R=,r(,R),r(R),传递.#,2025/1/25 周六,关系的闭包,35,定理,7.13(,反例),反例:,R,传递,但是,s(R),非传递.,G(R),G(s(R),自反性,对称性,传递性,r(R),(定义),(性质3,(2),),(性质3,(3),),s(R),(性质3,(1),(定义),(反例),t(R),(性质3,(1),),(性质3,(2),),(定义),小结:,闭包运算保持下列关系性质.,2025/1/25 周六,关系的闭包,36,闭包运算是否可以交换顺序?,问题:,(1),rs(R)=sr(R)?,(2),rt(R)=tr(R)3),st(R)=ts(R)?,说明:,rs(R)=r(s(R),2025/1/25 周六,关系的闭包,37,性质,2,性质,2:,设,R,A,A,且,A,则,(1),rs(R)=sr(R),;,(2),rt(R)=tr(R),;,(3),st(R),ts(R),;,2025/1/25 周六,关系的闭包,38,性质,2(,证明(1),(1),rs(R)=sr(R),;,证明:(1),rs(R)=r(s(R)=r(,R,R,-1,),=,I,A,(,R,R,-1,)=(,I,A,R),(,I,A,-1,R,-1,),=(,I,A,R),(,I,A,R),-1,=r(R),r(R),-1,=s(r(R)=sr(R).,rs(R)=sr(R).,2025/1/25 周六,关系的闭包,39,性质,2(,证明(2),(2),rt(R)=tr(R),;,证明:(2),rt(R)=r(t(R)=r(,R,R,2,R,3,),=,I,A,(,R,R,2,R,3,),=(,I,A,R),(,I,A,R,R,2,),(,I,A,R,R,2,R,3,),=(,I,A,R),(,I,A,R),2,(,I,A,R),3,=r(R),r(R),2,r(R),3,=,t,(r(R).,rt(R)=tr(R).,2025/1/25 周六,关系的闭包,40,性质,2(,证明(3),(3),st(R),ts(R),;,证明:(3),st(R),st(s(R),=sts(R)=s(ts(R)=ts(R),(ts(R),对称,性质3(2),st(R),ts(R).#,2025/1/25 周六,关系的闭包,41,性质,2(3),反例),(3),st(R),=,ts(R)?,反例:,st(R),ts(R),G(R),G(t(R),G(s(t(R),G(s(R),G(t(s(R),2025/1/25 周六,关系的闭包,42,问题,rst(R),rts(R),str(R),srt(R),trs(R),tsr(R),是否相等？,2025/1/25 周六,关系的闭包,43,作业,P133:25,26,31,27,30,课堂上已证请参考。,