离散数学关系的闭包.ppt
离散数学,集合论,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的自反闭包记为 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)先证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)RR2.,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)=RIAr(R)R IA mxy=1 exy=1,8/68,通过关系图求闭包,设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,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+Mn2.Warshall算法考虑矩阵序列 M0,M1,Mn=Mt:k=0,1,nMki,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 是自反的当且仅当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）若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),简记为sr(R),读做R的自反闭包的对称闭包.类似的,R的对称闭包的自反闭包r(s(R)简记为rs(R),R的对称闭包的传递闭包t(s(R),简记为ts(R),通常用R*表示R的传递闭包的自反闭包rt(R),读作“R星”.在研究形式语言和计算模型时经常使用R*,该休息啦,
