1、14.4 关系的闭包n 闭包定义n 闭包的构造方法 集合表示 矩阵表示 图表示n 闭包的性质 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(
2、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=，
3、则 r(R)=,s(R)=,t(R)=R6设 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的自反闭包的方法。 三、闭包的构造方法72.构造 R的对称闭包的方法。 每当 (a,b) R，而 (b,a)R时，将有序对 (b,a)加到 R上去，使其扩充成
4、对称的二元关系，扩充后的对称关系就是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 。 由逆关系的定义可知：83.构造 R的传递闭包的方法。 设 R 是 A上的二元关系，每当 (a,b) R和 (b,c) R而 (a,c)R时，将有序对 (a,c)加到 R上使其扩充成 R1，并称 R1 为 R的传递扩张， R1 如
5、果是传递关系 ，则 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. 9思考：设 A=a,b,c,d, R=, 求 r(R), s(R), t(R). 解 : r(R) = R R0=, , , , , , s(R) = R R1=, , t(R) = R R2 R3 R4 R2=, , , R3= , , , R4= , , , = R2于是 t(R) = R R2 R3= , , , , , , , , .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 的转置矩阵 . 注意在上述等式中矩阵的元素相加时使用逻辑加 .
