关系幂运算与关系闭包ppt课件.ppt

第7讲关系幂运算与关系闭包北京大学,内容提要关系幂(power)运算关系闭包(closure),1,关系的幂运算,n次幂的定义指数律幂指数的化简,2,关系的n次幂,关系的n次幂(nthpower):设RAA,nN,则(1)R0=IA;(2)Rn+1=RnR,(n1).Rn表示的关系,是R的关系图中长度为n的有向路径的起点与终点的关系.,1,2,n,n-1,3,关系幂运算(举例),例:设A=a,b,c,RAA,R=,求R的各次幂.解:,b,a,c,b,a,c,G(R),G(R0),4,关系幂运算(举例,续),解(续):R0=IA,R1=R0R=R=,R2=R1R=,b,a,c,b,a,c,G(R),G(R2),5,关系幂运算(举例,续2),解(续):R0=IA,R1=R0R=R=,R2=R1R=,R3=R2R=,=R1,b,a,c,b,a,c,G(R),G(R3),6,关系幂运算(举例,续3),解(续):R4=R3R=R1R=R2,R5=R4R=R2R=R3=R1,一般地,R2k+1=R1=R,k=0,1,2,R2k=R2,k=1,2,.#,b,a,c,b,a,c,G(R),G(R5),b,a,c,G(R4),7,关系幂运算是否有指数律?,指数律:(1)RmRn=Rm+n;(2)(Rm)n=Rmn.说明:对实数R来说,m,nN,Z,Q,R.对一般关系R来说,m,nN.对满足IAR且AdomRranR的关系R来说,m,nN,Z,例如R2R-5=R-3,因为可以定义R-n=(R-1)n=(Rn)-1?,8,定理17,定理17:设RAA,m,nN,则(1)RmRn=Rm+n;(2)(Rm)n=Rmn.说明:可让m,nZ,只需IAdomRranR(此时IA=RR-1=R-1R)并且定义R-n=(R-1)n=(Rn)-1.回忆:(FG)-1=G-1F-1(R2)-1=(RR)-1=R-1R-1=(R-1)2,9,定理17(证明(1),(1)RmRn=Rm+n;证明:(1)给定m,对n归纳.n=0时,RmRn=RmR0=RmIA=Rm=Rm+0.假设RmRn=Rm+n,则RmRn+1=Rm(RnR1)=(RmRn)R1=Rm+nR=R(m+n)+1=Rm+(n+1).(2)同样对n归纳.#,10,R0,R1,R2,R3,是否互不相等?,R0,R1,R2,R3,R4,R5,R6,R7,R8,R0,R1,R2,R3,R4,R5=R19=R33=R47=,R6=R20=R34=R48=,R7=R21=R35=R49=,R8=R22=R36=,R15,R9,R10,R11,R14,R16,R17,11,定理16,定理16:设|A|=n,RAA,则s,tN,并且,使得Rs=Rt.证明:P(AA)对幂运算是封闭的,即R,RP(AA)RkP(AA),(kN).|P(AA)|=,在R0,R1,R2,这个集合中,必有两个是相同的.所以s,tN,并且,使得Rs=Rt.#,12,鸽巢原理(pigeonholeprinciple),鸽巢原理(pigeonholeprinciple):若把n+1只鸽子装进n只鸽巢,则至少有一只鸽巢装2只以上的鸽子.又名抽屉原则(Dirichletdrawerprinciple),(PeterGustavLejeuneDirichlet,18051859)推广形式:若把m件物品装进k只抽屉,则至少有一只抽屉装只以上的物品.1.8=2,1.8=1,-1.8=-1,-1.8=-2.,13,定理18,定理18:设RAA,若s,tN(st-1s,则令q=s+kp+i,其中k,iN,p=t-s,s+it;于是Rq=Rs+kp+i=Rs+iS.,16,定理18(证明(2),(2)Rs+kp+i=Rs+i,其中k,iN,p=t-s;证明:(2)k=0时,显然;k=1时,即(1);设k2.则Rs+kp+i=Rs+k(t-s)+i=Rs+t-s+(k-1)(t-s)+i=Rt+(k-1)(t-s)+i=Rs+(k-1)(t-s)+i=Rs+(t-s)+i=Rt+i=Rs+i.#,17,幂指数的化简,方法:利用定理16,定理18.例6:设RAA,化简R100的指数.已知(1)R7=R15;(2)R3=R5;(3)R1=R3.解:(1)R100=R7+118+5=R7+5=R12R0,R1,R14;(2)R100=R3+482+1=R3+1=R4R0,R1,R4;(3)R100=R1+492+1=R1+1=R2R0,R1,R2.#,18,关系的闭包,自反闭包r(R)对称闭包s(R)传递闭包t(R)闭包的性质,求法,相互关系,19,什么是闭包,闭包(closure):包含一些给定对象,具有指定性质的最小集合“最小”:任何包含同样对象,具有同样性质的集合,都包含这个闭包集合例:(平面上点的凸包),20,自反闭包(reflexiveclosure),自反闭包:包含给定关系R的最小自反关系,称为R的自反闭包,记作r(R).(1)Rr(R);(2)r(R)是自反的;(3)S(RSS自反)r(R)S).,G(R),G(r(R),21,对称闭包(symmetricclosure),对称闭包:包含给定关系R的最小对称关系,称为R的对称闭包,记作s(R).(1)Rs(R);(2)s(R)是对称的;(3)S(RSS对称)s(R)S).,G(R),G(s(R),22,传递闭包(transitiveclosure),传递闭包:包含给定关系R的最小传递关系,称为R的传递闭包,记作t(R).(1)Rt(R);(2)t(R)是传递的;(3)S(RSS传递)t(R)S).,G(R),G(t(R),23,定理19,定理19:设RAA且A,则(1)R自反r(R)=R;(2)R对称s(R)=R;(3)R传递t(R)=R;证明:(1)RRR自反r(R)R又Rr(R),r(R)=R.(2)(3)完全类似.#,24,定理20,定理20:设R1R2AA且A,则(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2);证明:(1)R1R2r(R2)自反,r(R1)r(R2)(2)(3)类似可证.#,25,定理21,定理21:设R1,R2AA且A,则(1)r(R1R2)=r(R1)r(R2);(2)s(R1R2)=s(R1)s(R2);(3)t(R1R2)t(R1)t(R2).证明:(1)利用定理20,r(R1R2)r(R1)r(R2).r(R1)r(R2)自反且包含R1R2,所以r(R1R2)r(R1)r(R2).r(R1R2)=r(R1)r(R2),26,定理21(证明(2),(2)s(R1R2)=s(R1)s(R2);证明(2):利用定理20,s(R1R2)s(R1)s(R2).s(R1)s(R2)对称且包含R1R2,所以s(R1R2)s(R1)s(R2).s(R1R2)=s(R1)s(R2),27,定理21(证明(3),(3)t(R1R2)t(R1)t(R2).证明(3):利用定理20,t(R1R2)t(R1)t(R2).反例:t(R1R2)t(R1)t(R2).#,a,b,a,b,a,b,G(t(R1R2),G(R1)=G(t(R1),G(R2)=G(t(R2),28,如何求闭包?,问题:(1)r(R)=R(2)s(R)=R(3)t(R)=R,?,?,?,29,定理2224,定理2224:设RAA且A,则(1)r(R)=RIA;(2)s(R)=RR-1;(3)t(R)=RR2R3.对比:R自反IARR对称R=R-1R传递R2R,30,定理22,定理22:设RAA且A,则r(R)=RIA;证明:(1)RRIA;(2)IARIARIA自反r(R)RIA;(3)Rr(R)r(R)自反Rr(R)IAr(R)RIAr(R)r(R)=RIA.,31,定理23,定理23:设RAA且A,则s(R)=RR-1;证明:(1)RRR-1;(2)(RR-1)-1=RR-1RR-1对称s(R)RR-1;(3)Rs(R)s(R)对称Rs(R)R-1s(R)RR-1s(R)s(R)=RR-1.,32,定理24,定理24:设RAA且A,则t(R)=RR2R3;证明:(1)RRR2R3;(2)(RR2R3)2=R2R3RR2R3RR2R3传递t(R)RR2R3;(3)Rt(R)t(R)传递Rt(R)R2t(R)R3t(R)RR2R3t(R)t(R)=RR2R3.,33,定理24的推论,推论:设RAA且0|A|,则lN,使得t(R)=RR2R3Rl;证明:由定理16知s,tN,使得Rs=Rt.由定理18知R,R2,R3,R0,R1,Rt-1.取l=t-1,由定理24知t(R)=RR2R3.=RR2R3Rlt(R)=RR2R3Rl.#,34,例8,例8:设A=a,b,c,d,R=,.求r(R),s(R),t(R).解:,a,b,c,d,35,例8(续),解(续):,a,b,c,d,a,b,c,d,a,b,c,d,36,例8(续2),解(续2):,a,b,c,d,37,例8(续3),解(续3):,a,b,c,d,38,例8(续4),解(续4):,a,b,c,d,a,b,c,d,#,39,闭包运算是否保持关系性质?,问题:(1)R自反s(R),t(R)自反?(2)R对称r(R),t(R)对称?(3)R传递s(R),r(R)传递?,40,定理25,定理25:设RAA且A,则(1)R自反s(R)和t(R)自反;(2)R对称r(R)和t(R)对称;(3)R传递r(R)传递;证明:(1)IARR-1=s(R)s(R)自反.IARR2R3=t(R)t(R)自反.,41,定理25(证明(2),(2)R对称r(R)和t(R)对称;证明:(2)r(R)-1=(IAR)-1=IA-1R-1=IAR-1=IAR=r(R)r(R)对称.t(R)-1=(RR2R3)-1=R-1(R2)-1(R3)-1=R-1(R-1)2(R-1)3(FG)-1=G-1F-1)=RR2R3=t(R),t(R)对称.,42,定理25(证明(3),(2)R传递r(R)传递;证明:(2)r(R)r(R)=(IAR)(IAR)=(IAIA)(IAR)(RIA)(RR)IARRR=IAR=r(R)r(R)传递.#,43,定理25(反例),反例:R传递,但是s(R)非传递.,G(R),G(s(R),小结:闭包运算保持下列关系性质.,44,闭包运算是否可以交换顺序?,问题:(1)rs(R)=sr(R)?(2)rt(R)=tr(R)?(3)st(R)=ts(R)?说明:rs(R)=r(s(R),45,定理26,定理26:设RAA且A,则(1)rs(R)=sr(R);(2)rt(R)=tr(R);(3)st(R)ts(R);,r(),s(),t(),可交换,可交换,46,定理26(证明(1),(1)rs(R)=sr(R);证明:(1)rs(R)=r(s(R)=r(RR-1)=IA(RR-1)=(IAR)(IA-1R-1)=(IAR)(IAR)-1=r(R)r(R)-1=s(r(R)=sr(R).rs(R)=sr(R).,47,定理26(证明(2),(2)rt(R)=tr(R);证明:(2)rt(R)=r(t(R)=r(RR2R3)=IA(RR2R3)=(IAR)(IARR2)(IARR2R3)=(IAR)(IAR)2(IAR)3=r(R)r(R)2r(R)3=t(r(R).r