离散数学关系的闭包.ppt

1,4.4关系的闭包,闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质,2,一、闭包定义,定义设R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R,使得R满足以下条件：（1）R是自反的（对称的或传递的）（2）RR（3）对A上任何包含R的自反（对称或传递）关系R有RR.一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).,3,由闭包的定义可知，R的自反（对称，传递）闭包是含有R并且具有自反（对称，传递）性质的“最小”的关系。,如果R已是自反的二元关系，显然有：R=r(R)。同样，当R是对称的二元关系时R=s(R)；当R是传递的二元关系时，R=t(R)，且反之亦然。,4,二、关系的闭包运算,（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)；,5,例：设=a,b,c,R=,，求r(R),s(R),t(R)。,解：r(R)=,s(R)=,t(R)=,例：设=a,b,R=，,则r(R)=,s(R)=,t(R)=R,6,设R是A上的二元关系，xA，将所有(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)=RIA。,1.构造R的自反闭包的方法。,三、闭包的构造方法,7,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。,由逆关系的定义可知：,8,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)=RR2R3说明：对于有穷集合A(|A|=n)上的关系,上式中的并最多不超过Rn.,9,思考：设A=a,b,c,d,R=,求r(R),s(R),t(R).,解:r(R)=RR0=,s(R)=RR1=,t(R)=RR2R3R4,R2=,R3=,R4=,=R2,于是t(R)=RR2R3=,.,10,闭包的构造方法（续）,设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则Mr=M+EMs=M+MMt=M+M2+M3+E是和M同阶的单位矩阵,M是M的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加.,11,闭包的构造方法（续）,设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新边：考察G的每个顶点,如果没有环就加上一个环，最终得到Gr.考察G的每条边,如果有一条xi到xj的单向边,ij,则在G中加一条xj到xi的反方向边，最终得到Gs.考察G的每个顶点xi,找从xi出发的每一条路径，如果从xi到路径中任何结点xj没有边，就加上这条边.当检查完所有的顶点后就得到图Gt.,12,实例,例1设A=a,b,c,d,R=,R和r(R),s(R),t(R)的关系图如下图所示.,R,r(R),s(R),t(R),13,定理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,即RIA=R,r(s(R)=s(R)IA=(RR-1)IA=(RIA)R-1=r(R)R-1=RR-1=s(R)s(R)自反,14,类似可以证明t(R)也自反。证明.证明t(R)对称:(t(R)-1=(RR2.Rn.)-1=R-1(R2)-1.(Rn)-1.=R-1(R-1)2.(R-1)n.=RR2.Rn.(R对称，R-1=R)=t(R)所以t(R)也对称。类似可以证明r(R)也对称。证明.证明r(R)传递:先用归纳法证明下面结论:(RIA)i=IARR2.Rii=1时RIA=IAR结论成立。假设ik时结论成立，即(RIA)k=IARR2.Rk,15,当i=k+1时(RIA)k+1=(RIA)k(RIA)=(IARR2.Rk）(IAR)=(IARR2.Rk)(RR2.Rk+1)=IARR2.RkRk+1所以结论成立.t(r(R)=t(RIA)=(RIA)(RIA)2(RIA)3.=(IAR)(IARR2)(IARR2R3).=IARR2R3.=IAt(R)=IAR(R传递t(R)=R)=r(R)所以r(R)也传递。,。,。,16,定理设R1、R2是A上关系，如果R1R2，则r(R1)r(R2)s(R1)s(R2)t(R1)t(R2)证明r(R1)=IAR1IAR2=r(R2)，类似可证。定理设R是A上关系，则sr(R)=rs(R)tr(R)=rt(R)st(R)ts(R)证明：sr(R)=r(R)(r(R)-1=(RIA)(RIA)-1=(RIA)(R-1IA-1)=RIAR-1IA=(RR-1)IA=s(R)IA=rs(R)的证明用前边证明的结论：(RIA)k=IARR2.Rk很容易证明，这里从略。,17,因