复合关系与关系的闭包.pptVIP

*（补充）定理2:设R1,R2?A?A且A??,则(1)r(R1?R2)=r(R1)?r(R2);(2)s(R1?R2)=s(R1)?s(R2);(3)t(R1?R2)?t(R1)?t(R2).证明:(1)由R1?R1?R2,R2?R1?R2则r(R1)?r(R1?R2),r(R2)?r(R1?R2)从而r(R1)?r(R2)?r(R1?R2)另一方面，r(R1)?r(R2)自反且包含R1?R2,所以r(R1?R2)?r(R1)?r(R2).?r(R1?R2)=r(R1)?r(R2)构造闭包的方法定理2:设R?A?A且A??,则r(R)=R?IA;（证明用定义）s(R)=R?Rc;（证明用定义）t(R)=R?R2?R3?….对比:R自反?IA?RR对称?R=RcR传递?R2?R定理3：设X是含有n个元素的集合，R是X上的二元关系，则存在一个正整数k?n，使得t(R)=R?R2?R3?…?Rk集合与关系3-4

复合关系与关系的闭包湖北汽车工业学院计算机工程系彭彬定义1[复合(合成)(composite)关系]:01设R为X到Y的关系，S为从Y到Z上的关系，则R°S称为R和S的复合关系，表示为：02R°S={x,z|03x?X?z?Z?(?y)(y?Y?x,y?R?y,z?S)}.04注意：从左到右依次复合，不同教材处理方式不同。053-7.1复合关系3-7复合关系和逆关系3-7.2逆关系STEP5STEP4STEP3STEP2STEP1定义2[逆(inverse)关系]:设R是X到Y的二元关系，则从Y到X的二元关系Rc定义为：Rc={y,x|x,y?R}.整数集合上的“”关系的逆关系是“”关系。人群中的父子关系的逆关系是子父关系。容易看出(Rc)c=R例1:设R={a,b,c,d},S={b,e,d,c}.求:(1)Rc，Sc.(2)R°S,S°R解:(1)Rc={b,a,d,c}Sc={e,b,c,d}.(2)R°S={a,e,c,c}S°R={d,d}.例2:（书上的例题2，第115页）定理1:设R1,R2,R3为关系，R1是X到Y的关系，R2是Y到Z的关系，R3是Z到W的关系则(R1°R2)°R3=R1°(R2°R3)．证明:?x,w,x,w?(R1°R2)°R3??z(z?Z?x(R1°R2)z?zR3w)??z(z?Z??y(y?Y?xR1y?yR2z)?zR3w)??z?y(z?Z?y?Y?xR1y?yR2z?zR3w)??yt?z(z?Z?y?Y?xR1y?(yR2z?zR3w))??y(y?Y?xR1y??z(z?Z?yR2z?zR3w))??y(y?Y?xR1y?y(R2°R3)w)?xR1°(R2°R3)w?x,w?R1°(R2°R3)?(R1°R2)°R3=R1°(R2°R3).#说明:本定理说明复合运算满足结合律.由复合关系满足结合律，可以把关系R本身所组成的复合关系写成：R°R，R°R°R，?，R°R°?°R(m个)，分别记作R(2)，R(3)，?，R(m)。特别可以证明复合关系不满足交换律。R1°R2?R2°R17-3.3关系矩阵的性质：MR1°R2=MR1?MR2(?表示布尔乘法,其中加法使用逻辑?,乘法使用逻辑?)(T表示矩阵转置)MRc=(MR)T.014逆关系关系图的性质：02关系Rc的图形是将关系R图形中弧的箭头方向反置。定理2:设R、R1、R2都是从A到B的二元关系，则有(R1?R2)c=R1c?R2c(R1?R2)c=R1c?R2c(A×B)c=B×A(~R)c=~Rc,这里~R＝A×B-R(R1-R2)c=R1c-R2c注：证明(1)(4