离散数学关系的闭包.ppt

1 4.4 关系的闭包 闭包定义 闭包的构造方法 集合表示 矩阵表示 图表示 闭包的性质 2 一、闭包定义 定义 设R是非空集合A上的关系, R的自反（对称或传递）闭包是A上的关系R, 使得R满足以下条件：（1）R是自反的（对称的或传递的）（2）RR（3）对A上任何包含R的自反（对称或传递）关系 R 有 RR. 一般将 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={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,aa,b}， 则r(R)={a,aa,bb,b}, s(R)={a,aa,bb,a}, t(R)={a,aa,b}=R 6 设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的自反闭包的方法。 三、闭包的构造方法 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)}。 由逆关系的定义可知： 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) = R∪R2∪R3∪…说明： 对于有穷集合A (|A|=n) 上的关系, 上式中的并最多不超过 Rn. 9 思考：设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 }. 10 闭包的构造方法（续） 设关系R, r(R), s(R), t(R)的关系矩阵分别为M, Mr, Ms 和 Mt , 则  Mr = M + E Ms = M + M’ Mt = M + M2 + M3 + … E