复合关系逆关系及闭包

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

1、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}.整数集合上的“>”关系的逆关系是“<”关系。人群中的父子关系的逆关系是子父关系。容易看出(Rc)c=R例1:设R={

4、,},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°R2)°R3z(zZx(R1°R2)zzR3w)z(zZy(yYxR

5、1y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本身所组成的复合关系写成：R°R，R°R°R，，R°R°°R(m个)，分别记作R(2)，R(3

6、)，，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)(~R)c=~Rc,这里~R＝A×B-R(5)(R1-R2)c=R1

7、c-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（证明见书118页）(2)是反对称的RRcIX定理5:[P119(2)]设R为X上的二元关系，则(1)R是传递的(R°R)R(2)R是自反的IXR例题:设A={a,b,c},R1={

8、,,,},R2={,,},用MR1,MR2确定MR1c,MR2c,MR1°R1,MR1°R2,MR2°R1,从而求出它们的集合表达式.110110MR1=101MR1c=100000010011000MR2=001MR2c=100000110011MR1R2=MR1MR2=011000R1°R2={,,,}.110110111MR1R1=MR1MR1=101101=110000000000R1°R1={

9、>,,,,}.011110101MR2R1=MR2MR1=001101=000000000000R2°R1={,}.解:R1c={,,,}R2c={,,}R1°R1={,,,,}.R1°R2={,,,}.R2°R1={,}.作业(3-7)：P118(1)(5)3-8关系的闭包运算自反闭包

10、r(R)(reflexivityclosure)对称闭包s(R)(symmetryclosure)传递闭包t(R)(transitivityclosure)闭包的性质,求法,相互关系3-8.1自反闭包(reflexiveclosure)定义1[自反闭包]:包含给