离散数学-3-7复合关系和逆关系省名师优质课获奖课件市赛课一等奖课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,第三章 集合与关系,3-7 复合关系和逆关系,讲课人：李朔,Email:chn.nj.ls,第1页,1,一关系复合,二元关系是以序偶为元素集合，能够进行集合运算，产生新集合，本课介绍关系一个新运算，关系复合。,定义3.7.1,设,R,为,X,到,Y,关系，,S,为从,Y,到,Z,关系，则,RS,称为,R,和,S,复合关系,，表示为,RS,x,X,z,Z,y(y,Y,R,S),易见,RS,是从,X,到,Z,关系,。,*从,R,和,S，,求,RS,称为,关系合成运算,。,合成运算由两个关系生成一个新关系,*,P114,比如：,R,1,是关系“是弟兄”，,R,2,是关系“是父亲”，那么,R,1,R,2,是关系“是叔伯”,若,R1,是关系“是父亲”，那么,R,1,R,2,是关系“是祖父”,第2页,2,一关系复合,例题1：,R=,S=,则,RS=,SR=,(RS)R=?R(SR)=?,SS=,RR=,RRR=,能够证实，关系复合运算,满足结合律,，即：,（,RS）TR（ST）,故可记为 ,RST,P115,例题2,*当,R,与自己复合时，,记,RRR,2,。,普通定义,R,n+1,=R,n,R,第3页,3,一关系复合,例：设,X=0,1,2,3,则,R=,R,2,=RR=?,R,3,=R,2,R=?,*关系可用矩阵表示，故复合关系亦可用矩阵表示。（类似矩阵乘法，但采取逻辑加）,P115,第4页,4,例,例题3,A,=,1,2,3,4,5,，,A,上二元关系,R,和,S,定义以下：,R,=,1,2,2,2,3,4,S,=,1,3,2,5,3,1,4,2,试求,M,R,S,和,M,R,M,S,，,它们是否相等,?,解：,按照,R,和,S,定义，求出,R,S,=,1,5,2,5,3,2,写出,R,、,S,和,R,S,关系矩阵以下：,M,R,=,M,S,=,M,R,S,=,第5页,5,例,M,R,M,S,=,=,所以,M,R,S,=,M,R,M,S,第6页,6,二、关系逆,关系是序偶集合，因为序偶有序性，关系还有一些特殊运算。,P117,定义3.7.2,设,R,为,X,到,y,二元关系，如将,R,中每一序偶元素次序交换，所得集称为,R,逆关系,，记为,R,c,，,即：,R,c,=,R,比如：,R=,则,R,c,=,易见(,R,c,),c,=R,又如集合,Z,上，关系“”,第7页,7,二、关系逆,P117,定理3.7.1,设,R，S，T,都是从,A,到,B,二元关系，则,1）(,S,T),C,=S,C,T,C,2）(S,T),C,=S,C,T,C,3）(A,B),C,=B,A,4）(,R),C,=,R,C,(,R=A,B-R,R,C,=B,A-R,C,),5）(S-T),C,=S,C,T,C,第8页,8,二、关系逆,证：,1),(S,T),C,S,T,S,T,S,C,T,c,S,C,T,C,4),(,R),C,R,R,R,C,(,R),C,5),因,STS,T，,故,(,S-T),C,=(S,T),C,=S,C,(,T),C,=S,C,T,C,=S,C,-T,C,第9页,9,二、关系逆,P117,定理3.7.2,设,T,为从,X,到,Y,关系，,S,为从,Y,到,Z,关系，则,（,TS）,C,S,C,T,C,证：,（TS）,C,TS,y(y,Y,T,S),y(y,Y,T,C,S,C,),S,C,T,C,第10页,10,二、关系逆,定理3.7.3,设,R,为,X,上二元关系，则：,1）,R,是对称，当且仅当,RR,C,；,2）R,是反对称，当且仅当,R,R,C,I,X,。,证,：1）,R,对称，故,R,R,R,C,故,RR,C,反之,R,C,R，,则,R,R,C,R，,即,R,对称。,第11页,11,二、关系逆,定理3.7.3,设,R,为,X,上二元关系，则：,1）,R,是对称，当且仅当,RR,C,；,2）R,是反对称，当且仅当,R,R,C,I,X,。,证,：2）设,R,反对称,R,R,C,则,R,且,R,C,故有,R,x=y,即,I,X,R,R,C,I,X,反之设,R,R,C,I,X,R,且,R,则,R,C,R,R,C,即有,I,X,x=y,R,是反对称。,第12页,12,二、关系逆,*关于,R,C,图形，是,R,图形中将其弧线箭头反置即得，而,R,C,关系矩阵是,R,关系矩阵转置。,例：,X=a,b,c,其上二元关系,R,关系阵为,则,R,C,关系阵为,第13页,13,例,例,设,X,=,1,2,3,4,，,Y,=,a,b,c,，,X,到,Y,二元关系,R,=,1,a,2,b,4,c,，,试求,R,C,，,写出,M,R,和 ，验证,=,M,R,T,画出,R,和,R,C,关系图，验证将,R,关系图中弧线箭头反置可得到,R,C,关系图。,解：,R,C,=,a,1,b,2,c,4,R,和,R,C,关系矩阵是：,M,R,=,显然，,=,M,R,T,第14页,14,例,R,和,R,C,关系图分别是图,1,和图,2,，它们中弧线方向是相反。,第15页,15,本课小结,关系复合,关系逆,第16页,16,作业,P119(6)(7),第17页,17,