离散数学：第5讲 关系的性质.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2025/5/16 周五,1,复习,复合关系和逆关系,关系的表示,2025/5/16 周五,2,逆,合成,(,复合,),对任意关系,F,G,可以定义,:,逆,(inverse):,F,-1,=|yFx,合成,(,复合,)(composite):,F,G=|,z,(xFz,zGy,),x,z,y,F,G,2025/5/16 周五,3,关系矩阵,(matrix),设,A=a,1,a,2,a,n,R,A,A,则,R,的关系,矩阵,M(R)=(r,ij,),n,n,其中,例如,A=a,b,c,R,1,=,R,2,=,2025/5/16 周五,4,关系矩阵的性质,R,的集合表达式与,R,的关系矩阵可以唯一相互确定,M(R,-1,)=(M(R),T,.(,T,表示矩阵转置,),M(R,1,R,2,)=M(R,1,),M(R,2,).(,表示这样的矩阵,“,乘法,”,其中加法使用逻辑,乘法使用逻辑,.,),2025/5/16 周五,5,例题,例题,:,设,A=a,b,c,R,1,=,R,2,=,用,M(R,1,),M(R,2,),确定,M(R,1,-1,),M(R,2,-2,),M(R,1,R,1,),M(R,1,R,2,),M(R,2,R,1,),从而求出它们的集合表达式,.,2025/5/16 周五,6,例题,(,解,),R,1,=,R,2,=,解,:,R,1,-1,=,R,2,-1,=,2025/5/16 周五,7,例题,(,解,续,),R,1,=,R,2,=,解,(,续,):,R,1,R,1,=,.,2025/5/16 周五,8,例题,(,解,续,),R,1,=,R,2,=,解,(,续,):,R,2,R,1,=,.#,2025/5/16 周五,9,关系图,(graph),设,A=a,1,a,2,a,n,R,A,A,则,A,中元素以,“,”,表示,(,称为顶点,),R,中元素以,“,”,表示,(,称为有向边,);,若,x,i,Rx,j,则从顶点,x,i,向顶点,x,j,引有向边,这样得到的图称为,R,的关系图,G(R).,例如,A=a,b,c,R,1,=,R,2,=,则,a,b,c,a,b,c,G(R,1,),G(R,2,),2025/5/16 周五,10,关系图,(,举例,),R,1,-1,=,R,2,-1,=,a,b,c,G(R,2,-1,),c,G(R,1,-1,),a,b,2025/5/16 周五,11,关系图,(,举例,续,),R,1,R,1,=,.,R,1,R,2,=,.,R,2,R,1,=,.,a,b,c,G(R,1,R,2,),c,G(R,1,R,1,),a,b,c,G(R,2,R,1,),a,b,2025/5/16 周五,12,关系矩阵,关系图,(,讨论,),当,A,中元素标定次序后,R,A,A,的关系图,G(R),与,R,的集合表达式可以互相确定（唯一）,R,的集合表达式,关系矩阵,关系图三者均可以互相确定,对于,R,AB,|A|=n,|B|=m,关系矩阵,M(R),是,nm,阶的,关系图,G(R),中的边都是从,A,中元素指向,B,中元素的,.,2025/5/16 周五,13,定理,1,定理,1:,设,F,是任意关系,则,(1)domF,-1,=ranF;,(2)ranF,-1,=domF;,(3)(F,-1,),-1,=F.,2025/5/16 周五,14,逆关系满足性质,定理：,设,R,、,R,1,和,R,2,都是从,A,到,B,的二元关系，则下列各式成立,.a)(R,1,R,2,),-1,R,1,-1,R,2,-1,b)(R,1,R,2,),-1,R,1,-1,R,2,-1,c)(AB),-1,BA d)(R),-1,R,-1,这里,R,AB-Re)(R,1,-R,2,),-1,R,1,-1,-R,2,-1,_,_,_,2025/5/16 周五,15,定理,2,定理,2(1):,设,R,1,R,2,R,3,为二元关系,则,(R,1,R,2,),R,3,=R,1,(R,2,R,3,),证明,:,(R,1,R,2,),R,3,z,(xR,3,z,z,(R,1,R,2,),y,),z,(xR,3,z,t,(zR,2,t t,R,1,y,),zt,(xR,3,z,(zR,2,t t,R,1,y,),tz,(xR,3,z,zR,2,t t,R,1,y,),2025/5/16 周五,16,定理,2(,续,),定理,2,（,2,）,:,设,F,G,为二元关系,则,(F,G),-1,=G,-1,F,-1,.,G,G,-1,F,F,-1,2025/5/16 周五,17,定理,3,定理,3:,设,R,为,A,上的二元关系,则,R,I,A,=I,A,R=R,2025/5/16 周五,18,复合关系的性质,定理,4:,设,R,1,R,2,R,3,是集合,则,(1)R,1,(,R,2,R,3,)=,(,R,1,R,2,),(,R,1,R,3,),(2)(R,1,R,2,),R,3,=,(,R,1,R,3,),(,R,2,R,3,),(3)R,1,(,R,2,R,3,),(,R,1,R,2,),(,R,1,R,3,),(4)(R,1,R,2,),R,3,(,R,1,R,3,),(,R,2,R,3,),2025/5/16 周五,19,定理,4(,证明,(1),(1)R,1,(,R,2,R,3,)=,(,R,1,R,2,),(,R,1,R,3,),证明,:,R,1,(,R,2,R,3,),z(x(,R,1,)z,z(,R,2,R,3,)y),z(x,R,1,z,(z,R,2,y,z,R,3,y),z(x,R,1,z,z,R,2,y),(x,R,1,z,z,R,3,y),z(x,R,1,z,z,R,2,y),z(x,R,1,z,z,R,3,y),（,对,可分配,）,x(,R,1,R,2,),y,x(,R,1,R,3,),y,x(,R,1,R,2,),(,R,1,R,3,)y,(,R,1,R,2,),(,R,1,R,3,),2025/5/16 周五,20,定理,4(,证明,(3),(3),R,1,(,R,2,R,3,),(,R,1,R,2,),(,R,1,R,3,),证明,:,R,1,(,R,2,R,3,),z(x,R,1,z,z(,R,2,R,3,),y),z(x,R,1,z,(z,R,2,y,z,R,3,y),z(x,R,1,z,z,R,2,y),(x,R,1,z,z,R,3,y),z(x,R,1,z,z,R,2,y),z(x,R,1,z,z,R,3,y),（,对,单向可分配,）,x(,R,1,R,2,),y,x(,R,1,R,3,),y,x(,R,1,R,2,),(,R,1,R,3,)y,(,R,1,R,2,),(,R,1,R,3,).#,2025/5/16 周五,21,定理,4(,讨论,(3),(3)R,1,(,R,2,R,3,),(,R,1,R,2,),(,R,1,R,3,),反例,(,说明,=,不成立,):,设,R,1,=,R,2,=,R,3,=.,则,R,1,(,R,2,R,3,)=R,1,=,R,1,R,2,=,R,1,R,3,=,(,R,1,R,2,),(,R,1,R,3,)=,.#,a,b,c,d,2025/5/16 周五,22,限制，像,设,R,为二元关系，,A,dom(R),，,R,在,A,上的限制记作,R|,A,=|xRy,x A,A,在,R,下的像记作,RA,，其中,RA=ran(R|,A,),A,RA,R,2025/5/16 周五,23,举例,设,关系,R,A,1,2,B=2,R|,A,=,R|,B,=,RA=1,2,4,RB=4,2025/5/16 周五,24,关系的幂运算,关系的,n,次幂,(,n,th power):,设,R,A,A,n,N,则,(1),R,0,=,I,A,;,(2),R,n+1,=,R,n,R,(,n,1,).,R,n,表示的关系,是,R,的关系图中长度为,n,的有向路径的起点与终点的关系,.,1,2,n,n-1,2025/5/16 周五,25,关系幂运算,(,举例,),例,:,设,A=a,b,c,R,A,A,R=,求,R,的各次幂,.,解,:,b,a,c,b,a,c,G(R),G(R,0,),2025/5/16 周五,26,关系幂运算,(,举例,续,),解,(,续,):R,0,=,I,A,R,1,=R,0,R=R=,a,c,R,2,=R,1,R=,b,c,b,a,c,b,a,c,G(R),G(R,2,),2025/5/16 周五,27,关系幂运算,(,举例,续,2),解,(,续,):R,0,=,I,A,R,1,=R,0,R=R=,R,2,=R,1,R=,R,3,=R,2,R=,=R,1,b,a,c,b,a,c,G(R),G(R,3,),2025/5/16 周五,28,关系幂运算,(,举例,续,3),解,(,续,):,R,4,=R,3,R=R,1,R=,R,2,R,5,=R,4,R=R,2,R=,R,3,=R,1,规律,:R,2k+1,=R,1,=R,k=0,1,2,R,2k,=R,2,k=1,2,.#,b,a,c,b,a,c,G(R),G(R,5,),b,a,c,G(R,4,),2025/5/16 周五,29,定理,7.6,定理,7.6:,设,|A|=n,R,A,A,则,s,tN,并且,使得,R,s,=R,t,.,2025/5/16 周五,30,关系幂运算满足,指数律,指数律,:,(1)R,m,R,n,=R,m+n,;,(2)(R,m,),n,=R,mn,.,说明,:,对实数来说,m,nN,Z,Q,R.,对一般关系来说,m,nN,Z,因为可以定义,R,-n,=(R,-1,),n,=(R,n,),-1,2025/5/16 周五,31,R,0,R,1,是否总满足泵规律,?,R,0,R,1,R,2,R,3,R,4,R,5,R,6,R,7,R,8,R,0,R,1,R,2,R,3,R,4,R,5,=R,19,=R,33,=R,47,=,R,6,=R,20,=R,34,=R,48,=,R,7,=R,21,=R,35,=R,49,=,R,8,=R,22,=R,36,=,R,15,R,9,R,10,R,11,R,14,R,16,R,17,2025/5/16 周五,32,鸽巢原理,(pigeonhole principle),鸽巢原理,:,若把,n+1,只鸽子装进,n,只鸽巢,则至少有一只鸽巢装,2,只以上的鸽子,.,又名,抽屉原则,(Dirichlet drawer principle),(Peter Gustav Lejeune Dirichlet,18051859),2025/5/16 周五,33,定理,7.6,定理,7.6:,设,|A|=n,R,A,A,则,s,tN,并且,使得,R,s,=R,t,.,证明,:P(,A,A),对,幂运算是封闭的,即,R,RP(,A,A)R,k,P(,A,A),(kN).,|P(,A,A)|=,在,R,0,R,1,R,2,这,个集合中,必有两个是相同的,.,所以,s,tN,并且,使得,R,s,=R,t,.#,2025/5/16 周五,34,定理,7.8,定理,7.8:,设,R,A,A,若,s,tN(st-1,s,则令,q=s+kp+i,其中,k,i,N,p=t-s,s+it;,于是,R,q,=R,s+kp+i,=R,s+i,S.,2025/5/16 周五,37,定理,7.8(,证明,(2),(2)R,s+kp+i,=R,s+i,其中,k,i,N,p=t-s;,证明,:(2)k=0,时,显然,;,k=1,时,即,(1);,设,k,2.,则,R,s+kp+i,=R,s+k(t-s)+i,=R,s+t-s+(k-1)(t-s)+i,=R,t+(k-1)(t-s)+i,=R,s+(k-1)(t-s)+i,=,=R,s+(t-s)+i,=R,t+i,=R,s+i,.#,2025/5/16 周五,38,幂指数的化简,方法,:,利用定理,7.6,定理,7.8.,例,6:,设,R,A,A,化简,R,100,的指数,.,已知,(1)R,7,=R,15,;(2)R,3,=R,5,;(3)R,1,=R,3,.,解,:,(1),R,100,=R,7+11,8+5,=R,7+,5,=R,12,R,0,R,1,R,14,;,(2)R,100,=R,3+48,2+1,=R,3+1,=R,4,R,0,R,1,R,4,;,(3)R,100,=R,1+49,2+1,=R,1+1,=R,2,R,0,R,1,R,2,.#,2025/5/16 周五,39,关系性质,自反性,(reflexivity),反自反性,(irreflexivity),对称性,(symmetry),反对称性,(antisymmetry),传递性,(transitivity),2025/5/16 周五,40,自反性,(reflexivity),设,R,A,A,说,R,是自反的,(reflexive),如果,x(xA xRx).,R,是非自反的,x(xA xRx),定理,9(1):R,是自反的,I,A,R,R,-1,是自反的,M(R),主对角线上的元素全为,1,G(R),的每个顶点处均有环,.#,2025/5/16 周五,41,自反性,(,举例,),2025/5/16 周五,42,反自反性,(irreflexivity),设,R,A,A,说,R,是反自反的,(irreflexive),如果,x(xA xRx).,R,是非反自反的,x(xA xRx),定理,9(2):R,是反自反的,I,A,R=,R,-1,是反自反的,M(R),主对角线上的元素全为,0,G(R),的每个顶点处均无环,.#,2025/5/16 周五,43,反自反性,(,举例,),2025/5/16 周五,44,自反性,&,反自反性,(,矩阵,),自反性与反自反性互斥，但不互补,2025/5/16 周五,45,自反,自反性,(,图,),自反,反自反,非自反,非反自反,自反且反自反,?,上的空关系,2025/5/16 周五,46,对称性,(symmetry),设,R,A,A,说,R,是对称的,(symmetric),如果,xy(xAyAxRyyRx).,R,非对称,xy(xAyAxRyyRx),定理,9(3):R,是对称的,R,-1,=R,R,-1,是对称的,M(R),是对称的,G(R),的任何两个顶点之间若有边,则必有两条方向相反的有向边,.#,2025/5/16 周五,47,对称性,(,举例,),2025/5/16 周五,48,反对称性,(antisymmetry),设,R,A,A,说,R,是反对称的,(antisymmetric),若,xy(xAyAxRyyRxx=y).,R,非反对称,xy(xAyAxRyyRxxy),定理,9(4):R,是反对称的,R,-1,R,I,A,R,-1,是反对称的,在,M(R),中,ij(ijr,ij,=1r,ji,=0),在,G(R),中,x,i,x,j,(ij),若有有向边,则必没有,.#,2025/5/16 周五,49,反对称性,(,举例,),2025/5/16 周五,50,对称性,&,反对称性,(,矩阵,),对称性与反对称性既不互斥，又不互补,恒等关系,:,既是对称的，又是反对称的；,而相关矩阵是,的二元关系，是,既不对称，又不是反对称的。,2025/5/16 周五,51,对称,反对称,(,图,),对称,反对称,非对称,非反对称,对称且反对称,?,2025/5/16 周五,52,传递性,(transitivity),设,R,A,A,说,R,是传递的,(transitive),如果,xyz(xAyAzAxRyyRzxRz).,R,非传递,xyz(xAyAzAxRyyRzxRz),定理,9(5):R,是传递的,RRR R,-1,是传递的,(r,ij,r,jk,)r,ik,设,M,R,=(r,ij,),n,n,在,G(R),中,x,i,x,j,x,k,若有有向边,则必有有向边,.#,2025/5/16 周五,53,传递性,(,举例,),2025/5/16 周五,54,注,:,r,ij,，,r,jk,中有一个不是,则,(r,ij,r,jk,),=1,a,ik,就可以任意。,即若,，,中有,1,个不属于,R,，,则讨论,是否属于,R,，无意义。,即没有传递的条件，也不需传递的结果。如,:,a,b,c,d,，,，,传递性解释,2025/5/16 周五,55,传递,(,分类,),非传递,传递,2025/5/16 周五,56,例,例,:A=a,b,c,R,1,=,R,2,=,R,3,=,R,4,=,R,5,=,R,6,=,2025/5/16 周五,57,例,(,续,),R,1,=,反对称,传递,R,2,=,反对称,G(R,1,),a,c,b,G(R,2,),a,c,b,2025/5/16 周五,58,例,(,续,),R,3,=,自反,对称,传递,R,4,=,对称,G(R,3,),a,c,b,G(R,4,),a,c,b,2025/5/16 周五,59,例,(,续,),R,5,=,自反,反对称,传递,R,6,=,.#,G(R,5,),a,c,b,G(R,6,),a,c,b,2025/5/16 周五,60,举例,在,N=0,1,2,上,:,=|xNyNxy,自反,反对称,传递,=|xNyNxy,自反,反对称,传递,|xNyNx=|xNyNxy,反自反,反对称,传递,|=|xNyNx|y,反对称,传递,(0|0),I,N,=|xNyNx=y,自反,对称,反对称,传递,E,N,=|xNyN=NN,自反,对称,传递,.#,2025/5/16 周五,61,1,2,，,1,，,2,（）其中（）是的幂集。,自反的，反对称的，传递的。,注：若,改为,，则为反自反性。,举例,P,gcd,（，）（互素），,对称的，不是反对称的，不是自反的，也不是反自反的，也无传递性,2025/5/16 周五,62,总结,(,r,ij,r,jk,),r,ik,2025/5/16 周五,63,关系运算是否保持关系性质,定理,:,设,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,1,-,R,2,R,2,-,R,1,(3),R,1,R,2,(3,),2025/5/16 周五,64,定理,(,证明,(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/5/16 周五,65,定理,(,证明,(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/5/16 周五,66,定理,(,证明,(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/5/16 周五,67,定理,(,证明,(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,yE,A,x y,R,1,x,y(E,A,-,R,1,)x y(,R,1,)x,R,1,对称,R,1,对称,.,#,2025/5/16 周五,68,定理,(,证明,(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/5/16 周五,69,定理,(,证明,(5),(5)R,1,R,2,传递,R,1,R,2,传递,.,证明,:x,y,zA,x(,R,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/5/16 周五,70,作业,P132-133:21-24,