《北大离散数学课件.ppt》由会员分享，可在线阅读，更多相关《北大离散数学课件.ppt（52页珍藏版）》请在三一办公上搜索。
1、2023/5/26,集合论与图论第7讲,1,第7讲 关系幂运算与关系闭包北京大学,内容提要关系幂(power)运算关系闭包(closure),2023/5/26,集合论与图论第7讲,2,关系的幂运算,n次幂的定义 指数律 幂指数的化简,2023/5/26,集合论与图论第7讲,3,关系的n次幂,关系的n次幂(nth power):设RAA,nN,则(1)R0=IA;(2)Rn+1=RnR,(n1).Rn表示的关系,是R的关系图中长度为n的有向路径的起点与终点的关系.,1,2,n,n-1,2023/5/26,集合论与图论第7讲,4,关系幂运算(举例),例:设A=a,b,c,RAA,R=,求R的各次
2、幂.解:,b,a,c,b,a,c,G(R),G(R0),2023/5/26,集合论与图论第7讲,5,关系幂运算(举例,续),解(续):R0=IA,R1=R0R=R=,R2=R1R=,b,a,c,b,a,c,G(R),G(R2),2023/5/26,集合论与图论第7讲,6,关系幂运算(举例,续2),解(续):R0=IA,R1=R0R=R=,R2=R1R=,R3=R2R=,=R1,b,a,c,b,a,c,G(R),G(R3),2023/5/26,集合论与图论第7讲,7,关系幂运算(举例,续3),解(续):R4=R3R=R1R=R2,R5=R4R=R2R=R3=R1,一般地,R2k+1=R1=R,k
3、=0,1,2,R2k=R2,k=1,2,.#,b,a,c,b,a,c,G(R),G(R5),b,a,c,G(R4),2023/5/26,集合论与图论第7讲,8,关系幂运算是否有指数律?,指数律:(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?,2023/5/26,集合论与图论第7讲,9,定理17,定理17:设 RAA,m,nN,则(1)RmRn=Rm+n;(2)(Rm)n=Rmn.说明:可让
4、 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,2023/5/26,集合论与图论第7讲,10,定理17(证明(1),(1)RmRn=Rm+n;证明:(1)给定m,对n归纳.n=0时,RmRn=RmR0=RmIA=Rm=Rm+0.假设 RmRn=Rm+n,则 RmRn+1=Rm(Rn R1)=(RmRn)R1=Rm+nR=R(m+n)+1=Rm+(n+1).(2)同样对n归纳.#,2023/5/26,集合论与图论第7讲,11,R0,R1,R2,
5、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,2023/5/26,集合论与图论第7讲,12,定理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.#,
6、2023/5/26,集合论与图论第7讲,13,鸽巢原理(pigeonhole principle),鸽巢原理(pigeonhole principle):若把n+1只鸽子装进n只鸽巢,则至少有一只鸽巢装2只以上的鸽子.又名抽屉原则(Dirichlet drawer principle),(Peter Gustav Lejeune Dirichlet,18051859)推广形式:若把m件物品装进k只抽屉,则至少有一只抽屉装 只以上的物品.1.8=2,1.8=1,-1.8=-1,-1.8=-2.,2023/5/26,集合论与图论第7讲,14,定理18,定理18:设 RAA,若 s,tN(st),使
7、得Rs=Rt,则(1)Rs+k=Rt+k;(2)Rs+kp+i=Rs+i,其中k,iN,p=t-s;(3)令S=R0,R1,Rt-1,则qN,RqS.,2023/5/26,集合论与图论第7讲,15,定理18(说明),s,p,i,泵(pumping):Rs+kp+i=Rs+i,2023/5/26,集合论与图论第7讲,16,定理18(证明(1)(3),(1)Rs+k=Rt+k;(3)令S=R0,R1,Rt-1,则qN,RqS.证明:(1)Rs+k=RsRk=RtRk=Rt+k;(3)若 qt-1s,则令 q=s+kp+i,其中 k,iN,p=t-s,s+it;于是 Rq=Rs+kp+i=Rs+iS
8、.,2023/5/26,集合论与图论第7讲,17,定理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.#,2023/5/26,集合论与图论第7讲,18,幂指数的化简,方法:利用定理16,定理18.例6:设 RAA,化简R100的指数.已知(1)R7=R15;(2)R3=R5;(3)R1=R3.解:(1)R100=R7+11
9、8+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.#,2023/5/26,集合论与图论第7讲,19,关系的闭包,自反闭包r(R)对称闭包s(R)传递闭包t(R)闭包的性质,求法,相互关系,2023/5/26,集合论与图论第7讲,20,什么是闭包,闭包(closure):包含一些给定对象,具有指定性质的最小集合“最小”:任何包含同样对象,具有同样性质的集合,都包含这个闭包集合例:(平面上点的凸包),2023/5/26,集合论与图论第7讲,21,自反闭包(reflexive
10、 closure),自反闭包:包含给定关系R的最小自反关系,称为R的自反闭包,记作r(R).(1)R r(R);(2)r(R)是自反的;(3)S(RS S自反)r(R)S).,G(R),G(r(R),2023/5/26,集合论与图论第7讲,22,对称闭包(symmetric closure),对称闭包:包含给定关系R的最小对称关系,称为R的对称闭包,记作s(R).(1)R s(R);(2)s(R)是对称的;(3)S(RS S对称)s(R)S).,G(R),G(s(R),2023/5/26,集合论与图论第7讲,23,传递闭包(transitive closure),传递闭包:包含给定关系R的最小
11、传递关系,称为R的传递闭包,记作t(R).(1)R t(R);(2)t(R)是传递的;(3)S(RS S传递)t(R)S).,G(R),G(t(R),2023/5/26,集合论与图论第7讲,24,定理19,定理19:设RAA且A,则(1)R自反 r(R)=R;(2)R对称 s(R)=R;(3)R传递 t(R)=R;证明:(1)RR R自反 r(R)R 又 R r(R),r(R)=R.(2)(3)完全类似.#,2023/5/26,集合论与图论第7讲,25,定理20,定理20:设 R1R2AA 且 A,则(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2);证明:(1
12、)R1R2 r(R2)自反,r(R1)r(R2)(2)(3)类似可证.#,2023/5/26,集合论与图论第7讲,26,定理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),2023/5/26,集合论与图论第7讲,27,定理21(证明(2),(2)s(R1R2)=s(R1)s(R2);证明(
13、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),2023/5/26,集合论与图论第7讲,28,定理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),2023/5/26,集合论与图论第7讲,29,如何求闭包?,问题:(1)r(R)=R(2)s(R)=R(3
14、)t(R)=R,?,?,?,2023/5/26,集合论与图论第7讲,30,定理2224,定理2224:设 RAA 且 A,则(1)r(R)=RIA;(2)s(R)=RR-1;(3)t(R)=RR2R3.对比:R自反 IAR R对称 R=R-1 R传递 R2R,2023/5/26,集合论与图论第7讲,31,定理22,定理22:设 RAA 且 A,则r(R)=RIA;证明:(1)R RIA;(2)IARIA RIA自反 r(R)RIA;(3)Rr(R)r(R)自反 Rr(R)IA r(R)RIA r(R)r(R)=RIA.,2023/5/26,集合论与图论第7讲,32,定理23,定理23:设 RA
15、A 且 A,则s(R)=RR-1;证明:(1)R RR-1;(2)(RR-1)-1=RR-1 RR-1对称 s(R)RR-1;(3)Rs(R)s(R)对称 Rs(R)R-1s(R)RR-1s(R)s(R)=RR-1.,2023/5/26,集合论与图论第7讲,33,定理24,定理24:设 RAA 且 A,则t(R)=RR2R3;证明:(1)R RR2R3;(2)(RR2R3)2=R2R3 RR2R3 RR2R3传递 t(R)RR2R3;(3)Rt(R)t(R)传递 Rt(R)R2t(R)R3t(R)RR2R3 t(R)t(R)=RR2R3.,2023/5/26,集合论与图论第7讲,34,定理24
16、的推论,推论:设 RAA 且 0|A|,则l N,使得 t(R)=RR2R3Rl;证明:由定理16知 s,tN,使得 Rs=Rt.由定理18知 R,R2,R3,R0,R1,Rt-1.取l=t-1,由定理24知 t(R)=RR2R3.=RR2R3Rl t(R)=RR2R3Rl.#,2023/5/26,集合论与图论第7讲,35,例8,例8:设 A=a,b,c,d,R=,.求 r(R),s(R),t(R).解:,a,b,c,d,2023/5/26,集合论与图论第7讲,36,例8(续),解(续):,a,b,c,d,a,b,c,d,a,b,c,d,2023/5/26,集合论与图论第7讲,37,例8(续2
17、),解(续2):,a,b,c,d,2023/5/26,集合论与图论第7讲,38,例8(续3),解(续3):,a,b,c,d,2023/5/26,集合论与图论第7讲,39,例8(续4),解(续4):,a,b,c,d,a,b,c,d,#,2023/5/26,集合论与图论第7讲,40,闭包运算是否保持关系性质?,问题:(1)R自反 s(R),t(R)自反?(2)R对称 r(R),t(R)对称?(3)R传递 s(R),r(R)传递?,2023/5/26,集合论与图论第7讲,41,定理25,定理25:设RAA且A,则(1)R自反 s(R)和t(R)自反;(2)R对称 r(R)和t(R)对称;(3)R传递
18、 r(R)传递;证明:(1)IA RR-1=s(R)s(R)自反.IA RR2R3=t(R)t(R)自反.,2023/5/26,集合论与图论第7讲,42,定理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)对称.,2023/5/26,集合论与图论第7讲,43,定理25(证明(3),(2)R传递 r(R)传递;证明:(2)r(R)r(R
19、)=(IAR)(IAR)=(IAIA)(IAR)(RIA)(RR)IARRR=IAR=r(R)r(R)传递.#,2023/5/26,集合论与图论第7讲,44,定理25(反例),反例:R传递,但是s(R)非传递.,G(R),G(s(R),小结:闭包运算保持下列关系性质.,2023/5/26,集合论与图论第7讲,45,闭包运算是否可以交换顺序?,问题:(1)rs(R)=sr(R)?(2)rt(R)=tr(R)?(3)st(R)=ts(R)?说明:rs(R)=r(s(R),2023/5/26,集合论与图论第7讲,46,定理26,定理26:设 RAA 且 A,则(1)rs(R)=sr(R);(2)rt
20、(R)=tr(R);(3)st(R)ts(R);,r(),s(),t(),可交换,可交换,2023/5/26,集合论与图论第7讲,47,定理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).,2023/5/26,集合论与图论第7讲,48,定理26(证明(2),(2)rt(R)=tr(R);证明:(2)rt(R)=r(t(R)=r(RR2 R3)=IA(RR2 R3)=(IAR)(IARR2)(IAR
21、R2R3)=(IAR)(IAR)2(IAR)3=r(R)r(R)2 r(R)3=t(r(R).rt(R)=tr(R).,2023/5/26,集合论与图论第7讲,49,定理26(证明(3),(3)st(R)ts(R);证明:(3)st(R)st(s(R)=sts(R)=s(ts(R)=ts(R)(ts(R)对称,定理25(2)st(R)ts(R).#,2023/5/26,集合论与图论第7讲,50,定理26(3)反例),(3)st(R)=ts(R)?反例:st(R)ts(R),G(R),G(t(R),G(s(t(R),G(s(R),G(t(s(R),2023/5/26,集合论与图论第7讲,51,总结,关系幂运算关系闭包,2023/5/26,集合论与图论第7讲,52,作业(#5),p83,习题二,27,28,29今天交作业#1,#2,#3,#4,
