离散数学-3-7 复合关系和逆关系.ppt

1,第三章 集合与关系,3-7 复合关系和逆关系授课人：李朔,2,一关系的复合,二元关系是以序偶为元素的集合，可以进行集合运算，产生新的集合，本课介绍关系的一种新的运算，关系的复合。设R为X到Y的关系，S为从Y到Z的关系，则RS称为R和S的复合关系，表示为 RSxXzZy(yYRS)易见RS是从X到Z的关系。*从R和S，求RS称为关系的合成运算。合成运算由两个关系生成一个新的关系*P114例如：R1是关系“是兄弟”，R2是关系“是父亲”，那么R1R2是关系“是的叔伯”若R1是关系“是的父亲”，那么R1R2是关系“是的祖父”,3,一关系的复合,例题1：R=,S=,则 RS=,SR=,(RS)R=?R(SR)=?SS=RR=,RRR=,可以证明，关系的复合运算满足结合律，即：（RS）TR（ST）故可记为 RSTP115 例题2*当R与自己复合时，记RRR2。一般定义 Rn+1=RnR,4,一关系的复合,例：设X=0,1,2,3,则 R=,R2=RR=?,R3=R2R=?,*关系可用矩阵表示，故复合关系亦可用矩阵表示。（类似矩阵乘法，但采用逻辑加）P115,5,例,例题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试求MR S和MR MS，它们是否相等?解：按照R 和S的定义，求出 RS=1,5,2,5,3,2 写出R、S和R S关系矩阵如下：MR=MS=MR S=,6,例,MR MS=,所以MR S=MR MS,7,二、关系的逆,关系是序偶的集合，由于序偶的有序性，关系还有一些特殊的运算。P117 设R为X到y的二元关系，如将R中每一序偶的元素顺序互换，所得的集称为R的逆关系，记为Rc，即：Rc=R例如：R=,则 Rc=,易见(Rc)c=R 又如集合Z上，关系“”,8,二、关系的逆,P117 设R，S，T都是从A到B的二元关系，则1）(ST)C=SCTC2）(ST)C=SCTC3）(AB)C=BA4）(R)C=RC(R=AB-R,RC=BA-RC)5）(S-T)C=SCTC,9,二、关系的逆,证：1)(ST)CSTSTS C T c S C T C4)(R)CRRR C(R)C5)因STST，故(S-T)C=(ST)C=S C(T)C=S C T C=S C-T C,10,二、关系的逆,P117 设T为从X到Y的关系，S为从Y到Z的关系，则（TS）CS CT C证：（TS）CTSy(yYTS)y(yYT C S C)S CT C,11,二、关系的逆,设R为X上的二元关系，则：1）R是对称的，当且仅当RR C；2）R是反对称的，当且仅当RR C IX。证：1）R对称，故RRR C,故RR C反之R CR，则RR CR，即R对称。,12,二、关系的逆,设R为X上的二元关系，则：1）R是对称的，当且仅当RR C；2）R是反对称的，当且仅当RR C IX。证：2）设R反对称RR C 则 R且 R C 故有Rx=y 即 IXRRC IX,反之设RR C IX R且R则 R C RR C即有IX x=y R是反对称的。,13,二、关系的逆,*关于R C的图形，是R的图形中将其弧线的箭头反置即得，而R C的关系矩阵是R的关系矩阵的转置。例：X=a,b,c其上二元关系R关系阵为则R C的关系阵为,14,例,例 设X=1,2,3,4，Y=a,b,c，X到Y二元关系 R=1,a,2,b,4,c，试求RC，写出MR和，验证=MRT 画出R和RC的关系图，验证将R关系图中的弧线的箭头反置可得到RC关系图。解：RC=a,1,b,2,c,4 R和RC的关系矩阵是：MR=显然，=MRT,15,例,R和RC的关系图分别是图1和图2，它们中的弧线的方向是相反的。,16,本课小结,关系的复合关系的逆,17,作业,P119(6)(7),