离散数学-关系的闭包

1、离散数学,集合论,2 / 68,主要内容,集合代数 二元关系 函数,集合的基本概念 集合的运算 有穷集合的计数 集合恒等式,有序对与笛卡儿积 二元关系 关系的运算 关系的性质 关系的闭包 等价关系与划分 偏序关系,函数的定义与性质 函数的复合与反函数 双射函数与集合的基数,3 / 68,7.5 关系的闭包,一. 闭包的定义 定义7.14 设R是非空集合A上的关系,R的自反闭包(对称闭包,传递闭包)是 A上的关系 R ,它满足: (1) R 是自反的 (对称的,传递的)； (2) R R ; (3) 对A上任何包含 R 的自反关系 (对称关系,传递关系) R 都有R R . 注:R的自反闭包记为

2、 r(R),对称闭包记为 s(R),传递闭包记 为 t(R).,Reflexive, Symmetric, Transtive: r(R), s(R), t(R).,4 / 68,闭包的计算,定理 7.10 设R是A上的关系,则 (1) r(R)=RR0; (2) s(R)= RR-1; (3) t(R)= RR2R3. 证明：(1) 由IA= R0 RR0 知, RR0 是自反的,且R RR0. 设R是A上包含R的自反关系,则 R R , IA R, 因而 RR0 RIA RR = R 即 RR0 R .可见RR0满足自反闭包的定义,从而 r(R)= RR0. (2) 略.,5 / 68,闭

3、包的计算,(3)先证RR2 t(R),为此只需证明对任意正整数n都有 Rnt(R). 用归纳法. 当n=1时, R1 = R t(R). 假设 Rn t(R), 下证 Rn+1t(R) 事实上,由于 Rn+1 = Rn R t(Rn R) t(t(R) t(R) t(R) 从而 Rn+1 t(R) . 由归纳法完成证明.,6 / 68,闭包的计算,下证 RR2 是传递的. 事实上,对任意 , ( RR2)( RR2) t (Rt) s(Rs) ts( Rt Rs) ts( Rt+s) RR2 从而 RR2 是传递的. 因t(R)是传递闭包, 故t(R) RR2. 由以上两方面知, t(R) R

4、R2 .,7 / 68,通过关系矩阵求闭包,证:由定理7.6和定理7.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的转置矩阵,矩阵元素相加时使用逻辑加.,推论 设R是有限集合A上的关系，则存在正整数r使得 t(R)= RR2Rr.,r(R) = RIA r(R) R IA mxy = 1 exy = 1,8 / 68,通过关系图求闭包,设关系R, r(R), s(R), t(R)的关系图分别记为G, Gr

5、, Gs, Gt, 则Gr, Gs, Gt的顶点集与G的顶点集相同.除了G的边外,依下述方法添加新边: (1)对G的每个顶点,如果无环,则添加一条环,由此得到Gr; (2)对G的每条边,如果它是单向边,则添加一条反方向的边.由此得到Gs;,(3) 对G的每个顶点xi ,找出从xi 出发的所有2步, 3步, , n步长的有向路 (n为G的顶点数).设路的终点分别为 ,如果从 xi 到 xj 无边,则添上这条边.如上处理完所有顶点后得到 Gt,9 / 68,Warshall算法,设A=x1,x2,xn,R为A上的二元关系,R的关系矩阵为M: 1. Mt = M+M2+Mn 2. Warshall算

6、法 考虑矩阵序列 M0,M1,Mn= Mt : k=0,1,n Mki,j=1 当且仅当 在GR中存在一条从xi到xj的路径并且除端点外中间只经过x1,x2,xk中的顶点. Mk+1i,j=1 当且仅当 在GR中存在一条从xi到xj的路径并且除端点外中间只经过x1,x2,xk,xk+1中的顶点 Mki,j=1 或者 Mki,k+1=1 Mkk+1,j=1,10 / 68,Warshall算法示例,设 A=a,b,c,d, R=,求 t( R ). 解,Mk+1i,j=1 Mki,k+1=1 Mkk+1,j=1,11 / 68,闭包的性质,定理7.11 设R是非空集合A上的关系,则 (1) R

7、是自反的当且仅当r(R)=R (2) R 是对称的当且仅当 s(R)=R (3) R 是传递的当且仅当 t(R)=R 证:(1) 充分性显然.下证必要性. 因 R 是包含了 R 的自反关系,故r(R)R. 另一方面,显然 Rr(R). 从而,r(R)=R. (2), (3)略. 定理7.12 设 R1 和 R2 是非空集合A上的关系,且 R1R2 , 则 (1)r(R1)r(R2); (2)s(R1) s(R2); (3)t(R1) t(R2) 证明略,12 / 68,闭包的性质,定理7.13 设 R 是非空集合A上的关系 （1）若R是自反的,则 s(R) 和 t(R) 也是自反的. （2）若

8、R是对称的,则 r(R) 和 t(R) 也是自反的. （3）若R是传递的,则 r(R) 也是传递的. 证明:只证 (2) . 先考虑r(R). 因R是 A上的对称关系。故R=R-1 , 同时 IA = IA-1 ,于是 (RIA)-1=R-1IA-1 (根据习题7.20). 从而 r(R)-1 = (RR0)-1 = (RIA)-1 = R-1IA-1 = RIA = r(R) . 这便说明 r(R) 是对称的. 下面证明t(R)的对称性.为此,先用数学归纳法证明: 若R是对称的, 则对任何正整数n, Rn也是对称的. 事实上,当n=1时,R=R 显然是对称的.,13 / 68,闭包的性质,假设Rn是对称的,下证Rn+1 的对称性.由于 Rn+1 Rn R t (Rn)R) t (Rn)R) R Rn Rn+1 故 Rn+1 是对称的.归纳法定成. 现在来证 t(R)的对称性.由于 t(R) n(Rn) n(Rn) t(R) 因此t(R)是对称的. 注:由于对称闭包运算不保持传递性,故在运算顺序 上它应放在传递闭包之前,即 t s r(R)=t(s(r(R).,14 / 68,注,二元关系的闭包仍然是二元关系,还可以求它的闭包. 例如,R是A上的二元关系, r(R)是它的自反闭包,还可以求r(R)的对称闭包.r(R)的对称闭包记为s(r(R