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

《复合关系与关系的闭包.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、集合与关系3-4复合关系与关系的闭包湖北汽车工业学院计算机工程系彭彬3-7复合关系和逆关系3-7.1复合关系定义1[复合(合成)(composite)关系]:设R为X到Y的关系，S为从Y到Z上的关系，则R°S称为R和S的复合关系，表示为：R°S={

2、xXzZ(y)(yYRS)}.注意：从左到右依次复合，不同教材处理方式不同。3-7.2逆关系定义2[逆(inverse)关系]:设R是X到Y的二元关系，则从Y到X的二元关系Rc定义为：Rc={

3、R}.整数集合上的“>”关系的

4、逆关系是“<”关系。人群中的父子关系的逆关系是子父关系。容易看出(Rc)c=R例1:设R={,},S={,}.求:(1)Rc，Sc.(2)R°S,S°R解:(1)Rc={,}Sc={,}.(2)R°S={,}S°R={}.例2:（书上的例题2，第115页）定理1:设R1,R2,R3为关系，R1是X到Y的关系，R2是Y到Z的关系，R3是Z到W的关系则(R1°R2)°R3=R1°(R2°R3)．证明:,(R1°R

5、2)°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R1°(R2°R3)(R1°R2)°R3=R1°(R2°R3).#说明:本定理说明复合运算满足结合律.由复合关系满足结合律，可以把关系R本身所组成的复合关系

6、写成：R°R，R°R°R，，R°R°°R(m个)，分别记作R(2)，R(3)，，R(m)。特别可以证明复合关系不满足交换律。R1°R2R2°R17-3.3关系矩阵的性质：(1)MRc=(MR)T.(T表示矩阵转置)(2)MR1°R2=MR1MR2(表示布尔乘法,其中加法使用逻辑,乘法使用逻辑)3-7.4逆关系关系图的性质：关系Rc的图形是将关系R图形中弧的箭头方向反置。定理2:设R、R1、R2都是从A到B的二元关系，则有(1)(R1R2)c=R1cR2c(2)(R1R2)c=R1cR2c(3)(A×B)c=B×A(4

7、)(~R)c=~Rc,这里~R＝A×B-R(5)(R1-R2)c=R1c-R2c注：证明(1)(4)(5)见书117页。定理3:设R,S为二元关系,则(R°S)c=Sc°Rc.证明:,(R°S)c(R°S)z(yRzzSx)z(zRcyxScz)z(xSczzRcy)Sc°Rc.定理4:设R为X上的二元关系，则(1)R是对称的R=Rc证明：设R是对称的，则RRRc,即R=Rc反之：若R=Rc，RRC<

8、y,x>R，故R是对称的(2)是反对称的RRcIX证明：设R是反对称的，RRc，则R且Rc，即R且R。由反对称定义，则x=y，从而=IX,故RRcIX。反之:RRc,则IX，从而x=y，故R，即R是反对称的。定理5:[P119(2)]设R为X上的二元关系，则R是传递的(R°R)R证明：R°R,则c满足R且R。由R的传递性，R，故(R°R)R。反之，

9、R，R，则R°R。由于R是传递的，故R，从而(R°R)R(2)R是自反的IXR证明：xA,则IXRR是自反的。反之，IX，若R是自反的，则xA,且R，从而IXR例题:设A={a,b,c},R1={,,,},R2={,,},用MR1,MR2确定MR1c,MR2c,MR1°R1,MR1°R2,MR2°R1,从而求出它们的集合表达式.110110MR1=101M

10、R1c=100000010011000MR2=001MR2c=100000110011MR1R2=MR1MR2=011000R1°R2={,,,