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

离散数学,集合论,1,2/68,主要内容,集合代数二元关系函数,集合的基本概念集合的运算有穷集合的计数集合恒等式,有序对与笛卡儿积二元关系关系的运算关系的性质关系的闭包等价关系与划分偏序关系,函数的定义与性质函数的复合与反函数双射函数与集合的基数,3/68,7.5关系的闭包,一.闭包的定义定义7.14设R是非空集合A上的关系,R的自反闭包(对称闭包,传递闭包)是A上的关系R,它满足:(1)R是自反的(对称的,传递的)；(2)RR;(3)对A上任何包含R的自反关系(对称关系,传递关系)R都有RR.注: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=R0RR0知,RR0是自反的,且RRR0.设R是A上包含R的自反关系,则RR,IAR,因而RR0RIARR=R即RR0R.可见RR0满足自反闭包的定义,从而r(R)=RR0.(2)略.,5/68,闭包的计算,(3)先证RR2t(R),为此只需证明对任意正整数n都有Rnt(R).用归纳法.当n=1时,R1=Rt(R).假设Rnt(R),下证Rn+1t(R)事实上,由于Rn+1=RnRt(RnR)t(t(R)t(R)t(R)从而Rn+1t(R).由归纳法完成证明.,6/68,闭包的计算,下证RR2是传递的.事实上,对任意,(RR2)(RR2)t(Rt)s(Rs)ts(RtRs)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)RIAmxy=1exy=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=1Mkk+1,j=1,10/68,Warshall算法示例,设A=a,b,c,d,R=,求t(R).解,Mk+1i,j=1Mki,k+1=1Mkk+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+1RnRt(Rn)R)t(Rn)R)RRnRn+1故Rn+1是对称的.归纳法定成.现在来证t(R)的对称性.由于t(R)n(Rn)n(Rn)t(R)因此t(R)是对称的.注:由于对称闭包运算不保持传递性,故在运算顺序上它应放在传递闭包之前,即tsr(R)=t(s(r(R).,14/68,注,二元关系的闭包仍然是二元关系,还可以求它的闭包.例如,R是A上的二元关系,r(R)是它的自反闭包,还可以求r(R)的对称闭包.r(R)的对称闭包记为s(r(R),简记为sr(R),读做R的自反闭包的对称