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

1、1,第三章 集合与关系,3-7 复合关系和逆关系 授课人：李朔 Email:,2,一关系的复合,二元关系是以序偶为元素的集合，可以进行集合运算，产生新的集合，本课介绍关系的一种新的运算，关系的复合。 定义3.7.1 设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：

2、R=,S=,则 RS=, SR=, (RS)R=? R(SR)=? SS= RR=, RRR=, 可以证明，关系的复合运算满足结合律，即： （RS）TR（ST） 故可记为 RST P115 例题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和

3、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 定义3.7.2 设R为X到y的二元关系，如将R中每一序偶的元素顺序互换，所得的集称为R的逆关系，记为Rc，即：Rc=R 例如：R=, 则 Rc =, 易见 (Rc)c = R 又如集合Z上，关系“”,8,二、关系的逆,P117 定理3.7.1 设R，S，T都是从A到B的二元关系，则 1）(ST)C=S

4、CTC 2）(ST)C =SCTC 3）(AB)C =BA 4）(R)C =RC (R=AB-R, RC=BA-RC) 5）(S-T)C =SCTC,9,二、关系的逆,证： 1)(ST)CST ST S C T c S C T C 4)(R) CR RR C (R) C 5)因STST，故 (S-T) C =( ST) C =S C (T) C =S C T C =S C -T C,10,二、关系的逆,P117 定理3.7.2 设T为从X到Y的关系，S为从Y到Z的关系，则（TS）CS CT C 证：（TS）C TS y(yYTS) y(yYT C S C) S CT C,11,二、关系的逆,定

5、理3.7.3 设R为X上的二元关系，则： 1）R是对称的，当且仅当RR C； 2）R是反对称的，当且仅当RR C IX。 证：1）R对称，故 RRR C, 故RR C 反之R CR，则 RR CR，即R对称。,12,二、关系的逆,定理3.7.3 设R为X上的二元关系，则： 1）R是对称的，当且仅当RR C； 2）R是反对称的，当且仅当RR C IX。 证：2）设R反对称 RR C 则 R且 R C 故有R x=y 即 IX RRC 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的关系矩阵是：