离散数学关系的闭包

离散数学关系的闭包由闭包得定义可知,R得自反(对称,传递)闭包就是含有R并且具有自反(对称,传递)性质得“最小”得关系。如果R已就是自反得二元关系,显然有:R=r(R)。同样,当R就是对称得二元关系时R=s(R);当R就是传递得二元关系时,R=t(R),且反之亦然。二、关系得闭包运算(1)已知一个集合中得二元关系R,则

r(R),s(R),t(R)就是唯一得,她就是包含R得最小得自反(对称,传递)关系;(2)若R就是自反(对称,传递)得,则

r(R),s(R),t(R)就就是R本身。(3)若R不就是自反(对称,传递)得,则可以补上最少序偶,使之变为自反、对称、传递关系,从而得到r(R),s(R),t(R);例:设Ａ={a,b,c},R={<a,b>,<b,c>,<c,a>},求r(R),s(R),t(R)。解:r(R)=s(R)=t(R)={<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>,<a,a>,<b,b>,<c,c>}例:设Ａ={a,b},R={<a,a><a,b>},则r(R)={<a,a><a,b><b,b>},s(R)={<a,a><a,b><b,a>},t(R)={<a,a><a,b>}=R

设R就是A上得二元关系,x∈A,将所有(x,x)

R得有序对加到R上去,使其扩充成自反得二元关系,扩充后得自反关系就就是R得自反闭包r(R)。

例如,A={a,b,c,d},R={(a,a),(b,d),(c,c)}。R得自反闭包r(R)={(a,a),(b,d),(c,c),(b,b),(d,d)}。

于就是可得:定理:R就是A上得二元关系,则R得自反闭包r(R)=R∪IA。1、构造R得自反闭包得方法。

三、闭包得构造方法2、构造R得对称闭包得方法。

每当(a,b)∈R,而(b,a)

R时,将有序对(b,a)加到R上去,使其扩充成对称得二元关系,扩充后得对称关系就就是R得对称闭包s(R)。

例如,A={a,b,c,d,e},R={(a,a),(a,b),(b,a),(b,c),(d,e)}。R得对称闭包s(R)={(a,a),(a,b),(b,a),(b,c),(c,b),(d,e),(e,d)}。

定理:R是A上二元关系，是其逆关系，则R的对称闭包s(R)=R∪

。

由逆关系得定义可知:3、构造R得传递闭包得方法。

设R就是A上得二元关系,每当(a,b)∈R与(b,c)∈R而(a,c)

R时,将有序对(a,c)加到R上使其扩充成R1,并称R1

为R得传递扩张,R1

如果就是传递关系,则R1就是R得传递闭包;如果R1不就是传递关系,继续求R1得得传递扩张R2,如果R2就是传递关系时,则R2就是R得传递闭包;如果R2不就是传递关系时,继续求R2得得传递扩张R3…,如果A就是有限集,R经过有限次扩张后,定能得到R得传递闭包。扩张后得传递关系就就是R得传递闭包t(R)。

定理:设R为A上得关系,则有t(R)=R∪R2∪R3∪…

说明:对于有穷集合A(|A|=n)上得关系,上式中得并最多不超过Rn、思考:设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求r(R),s(R),t(R)、解:r(R)=R∪R0={<a,a>,<a,b>,<b,a>,<b,b>,<b,c>,<c,c>,<c,d>,<d,d>},s(R)=R∪R

1={<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>},

t(R)=R∪R2∪R3∪R4

R2={<a,a>,<a,c>,<b,b>,<b,d>}R3={<a,b>,<a,d>,<b,a>,<b,c>}R4={<a,b>,<a,c>,<b,b>,<b,d>}=R2于就是t(R)=R∪R2∪R3=

{<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}、闭包得构造方法(续)设关系R,r(R),s(R),t(R)得关系矩阵分别为M,Mr,Ms与Mt,则

Mr=M+EMs=M+M’

Mt=M+M2+M3+…E就是与M同阶得单位矩阵,M’就是M得转置矩阵、注意在上述等式中矩阵得元素相加时使用逻辑加、闭包得构造方法(续)设关系R,r(R),s(R),t(R)得关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt得顶点集与G得顶点集相等、除了G得边以外,以下述方法添加新边:

考察G得每个顶点,如果没有环就加上一个环,最终得到Gr、考察G得每条边,如果有一条xi到xj得单向边,i≠j,则在G中加一条xj到xi得反方向边,最终得到Gs、考察G得每个顶点xi,找从xi出发得每一条路径,如果从xi到路径中任何结点xj没有边,就加上这条边、当检查完所有得顶点后就得到图Gt、实例例1设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R与r(R),s(R),t(R)得关系图如下图所示、Rr(R)s(R)t(R)大家学习辛苦了，还是要坚持继续保持安静定理R就是A上关系,则⑴R就是自反得,当且仅当r(R)=R、⑵R就是对称得,当且仅当s(R)=R、⑶R就是传递得,当且仅当t(R)=R、证明略,因为由闭包定义即可得。定理

R就是A上关系,则⑴R就是自反得,则s(R)与t(R)也自反。⑵R就是对称得,则r(R)与t(R)也对称。⑶R就是传递得,则r(R)也传递。证明:⑴因为R自反,得r(R)=R,即R∪IA=R,r(s(R))=s(R)∪IA=(R∪R-1)∪IA=(R∪IA)∪R-1=r(R)∪R-1=R∪R-1=s(R)∴s(R)自反

类似可以证明t(R)也自反。证明⑵、证明t(R)对称:(t(R))-1=(R∪R2∪、、、∪Rn∪、、、)-1

=R-1∪(R2)-1∪、、、∪(Rn)-1∪、、、

=R-1∪(R-1)2∪、、、∪(R-1)n∪、、、=R∪R2∪、、、∪Rn∪、、、(∵R对称,∴R-1=R)=t(R)所以t(R)也对称。类似可以证明r(R)也对称。证明⑶