离散数学 关系的闭包ppt课件.ppt

1、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=

2、 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

3、,设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)。,例如，

4、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

5、是传递关系时，则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) = RR2R3 R4,R2=, , , ,R3= , , , ,R4= , , , ,= R2,于是

6、 t(R) = RR2R3= , , , , , , , , .,10,闭包的构造方法（续）,设关系R, r(R), s(R), t(R)的关系矩阵分别为M, Mr, Ms 和 Mt , 则 Mr = M + E Ms = M + M Mt = 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的

7、每个顶点, 如果没有环就加上一个环，最终得到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),南宁空调回收 南宁空调出租 仧莒彾,Microsoft Office PowerPoint，是微软公司的演示文稿软件

8、。用户可以在投影仪或者计算机上进行演示，也可以将演示文稿打印出来，制作成胶片，以便应用到更广泛的领域中。利用Microsoft Office PowerPoint不仅可以创建演示文稿，还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。 Microsoft Office PowerPoint做出来的东西叫演示文稿，其格式后缀名为：ppt、pptx；或者也可以保存为：pdf、图片格式等,13,14,定理 R是A上关系，则 R是自反的，当且仅当 r(R)=R. R是对称的，当且仅当 s(R)=R. R是传递的，当且仅当 t(R)=R. 证明略，因为由闭包定义即可得。 定理 R是A上

9、关系，则 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)自反,15,类似可以证明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)也对称。 证明

10、. 证明r(R)传递:先用归纳法证明下面结论: (RIA)i= IARR2.Ri i=1时 RIA= IAR 结论成立。 假设ik 时结论成立，即 (RIA)k= IARR2.Rk,16,当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)也传递。,。,。,17,定理设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 很容易证