2019/12/24,集合論與圖論第7講,1,第7講關(guān)系冪運(yùn)算與關(guān)系閉包北京大學(xué),內(nèi)容提要關(guān)系冪(power)運(yùn)算關(guān)系閉包(closure),2019/12/24,集合論與圖論第7講,2,關(guān)系的冪運(yùn)算,n次冪的定義指數(shù)律冪指數(shù)的化簡(jiǎn),2019/12/24,集合論與圖論第7講,3,關(guān)系的n次冪,關(guān)系的n次冪(nthpower):設(shè)RAA,nN,則(1)R0=IA;(2)Rn+1=RnR,(n1).Rn表示的關(guān)系,是R的關(guān)系圖中長(zhǎng)度為n的有向路徑的起點(diǎn)與終點(diǎn)的關(guān)系.,1,2,n,n-1,2019/12/24,集合論與圖論第7講,4,關(guān)系冪運(yùn)算(舉例),例:設(shè)A=a,b,c,RAA,R=,求R的各次冪.解:,b,a,c,b,a,c,G(R),G(R0),2019/12/24,集合論與圖論第7講,5,關(guān)系冪運(yùn)算(舉例,續(xù)),解(續(xù)):R0=IA,R1=R0R=R=,R2=R1R=,b,a,c,b,a,c,G(R),G(R2),2019/12/24,集合論與圖論第7講,6,關(guān)系冪運(yùn)算(舉例,續(xù)2),解(續(xù)):R0=IA,R1=R0R=R=,R2=R1R=,R3=R2R=,=R1,b,a,c,b,a,c,G(R),G(R3),2019/12/24,集合論與圖論第7講,7,關(guān)系冪運(yùn)算(舉例,續(xù)3),解(續(xù)):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),2019/12/24,集合論與圖論第7講,8,關(guān)系冪運(yùn)算是否有指數(shù)律?,指數(shù)律:(1)RmRn=Rm+n;(2)(Rm)n=Rmn.說(shuō)明:對(duì)實(shí)數(shù)R來(lái)說(shuō),m,nN,Z,Q,R.對(duì)一般關(guān)系R來(lái)說(shuō),m,nN.對(duì)滿足IAR且AdomRranR的關(guān)系R來(lái)說(shuō),m,nN,Z,例如R2R-5=R-3,因?yàn)榭梢远xR-n=(R-1)n=(Rn)-1?,2019/12/24,集合論與圖論第7講,9,定理17,定理17:設(shè)RAA,m,nN,則(1)RmRn=Rm+n;(2)(Rm)n=Rmn.說(shuō)明:可讓m,nZ,只需IAdomRranR(此時(shí)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,2019/12/24,集合論與圖論第7講,10,定理17(證明(1),(1)RmRn=Rm+n;證明:(1)給定m,對(duì)n歸納.n=0時(shí),RmRn=RmR0=RmIA=Rm=Rm+0.假設(shè)RmRn=Rm+n,則RmRn+1=Rm(RnR1)=(RmRn)R1=Rm+nR=R(m+n)+1=Rm+(n+1).(2)同樣對(duì)n歸納.#,2019/12/24,集合論與圖論第7講,11,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,2019/12/24,集合論與圖論第7講,12,定理16,定理16:設(shè)|A|=n,RAA,則s,tN,并且,使得Rs=Rt.證明:P(AA)對(duì)冪運(yùn)算是封閉的,即R,RP(AA)RkP(AA),(kN).|P(AA)|=,在R0,R1,R2,這個(gè)集合中,必有兩個(gè)是相同的.所以s,tN,并且,使得Rs=Rt.#,2019/12/24,集合論與圖論第7講,13,鴿巢原理(pigeonholeprinciple),鴿巢原理(pigeonholeprinciple):若把n+1只鴿子裝進(jìn)n只鴿巢,則至少有一只鴿巢裝2只以上的鴿子.又名抽屜原則(Dirichletdrawerprinciple),(PeterGustavLejeuneDirichlet,18051859)推廣形式:若把m件物品裝進(jìn)k只抽屜,則至少有一只抽屜裝只以上的物品.1.8=2,1.8=1,-1.8=-1,-1.8=-2.,2019/12/24,集合論與圖論第7講,14,定理18,定理18:設(shè)RAA,若s,tN(st-1s,則令q=s+kp+i,其中k,iN,p=t-s,s+i<t;于是Rq=Rs+kp+i=Rs+iS.,2019/12/24,集合論與圖論第7講,17,定理18(證明(2),(2)Rs+kp+i=Rs+i,其中k,iN,p=t-s;證明:(2)k=0時(shí),顯然;k=1時(shí),即(1);設(shè)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.#,2019/12/24,集合論與圖論第7講,18,冪指數(shù)的化簡(jiǎn),方法:利用定理16,定理18.例6:設(shè)RAA,化簡(jiǎn)R100的指數(shù).已知(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.#,2019/12/24,集合論與圖論第7講,19,關(guān)系的閉包,自反閉包r(R)對(duì)稱(chēng)閉包s(R)傳遞閉包t(R)閉包的性質(zhì),求法,相互關(guān)系,2019/12/24,集合論與圖論第7講,20,什么是閉包,閉包(closure):包含一些給定對(duì)象,具有指定性質(zhì)的最小集合“最小”:任何包含同樣對(duì)象,具有同樣性質(zhì)的集合,都包含這個(gè)閉包集合例:(平面上點(diǎn)的凸包),2019/12/24,集合論與圖論第7講,21,自反閉包(reflexiveclosure),自反閉包:包含給定關(guān)系R的最小自反關(guān)系,稱(chēng)為R的自反閉包,記作r(R).(1)Rr(R);(2)r(R)是自反的;(3)S(RSS自反)r(R)S).,G(R),G(r(R),2019/12/24,集合論與圖論第7講,22,對(duì)稱(chēng)閉包(symmetricclosure),對(duì)稱(chēng)閉包:包含給定關(guān)系R的最小對(duì)稱(chēng)關(guān)系,稱(chēng)為R的對(duì)稱(chēng)閉包,記作s(R).(1)Rs(R);(2)s(R)是對(duì)稱(chēng)的;(3)S(RSS對(duì)稱(chēng))s(R)S).,G(R),G(s(R),2019/12/24,集合論與圖論第7講,23,傳遞閉包(transitiveclosure),傳遞閉包:包含給定關(guān)系R的最小傳遞關(guān)系,稱(chēng)為R的傳遞閉包,記作t(R).(1)Rt(R);(2)t(R)是傳遞的;(3)S(RSS傳遞)t(R)S).,G(R),G(t(R),2019/12/24,集合論與圖論第7講,24,定理19,定理19:設(shè)RAA且A,則(1)R自反r(R)=R;(2)R對(duì)稱(chēng)s(R)=R;(3)R傳遞t(R)=R;證明:(1)RRR自反r(R)R又Rr(R),r(R)=R.(2)(3)完全類(lèi)似.#,2019/12/24,集合論與圖論第7講,25,定理20,定理20:設(shè)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)類(lèi)似可證.#,2019/12/24,集合論與圖論第7講,26,定理21,定理21:設(shè)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),2019/12/24,集合論與圖論第7講,27,定理21(證明(2),(2)s(R1R2)=s(R1)s(R2);證明(2):利用定理20,s(R1R2)s(R1)s(R2).s(R1)s(R2)對(duì)稱(chēng)且包含R1R2,所以s(R1R2)s(R1)s(R2).s(R1R2)=s(R1)s(R2),2019/12/24,集合論與圖論第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),2019/12/24,集合論與圖論第7講,29,如何求閉包?,問(wèn)題:(1)r(R)=R(2)s(R)=R(3)t(R)=R,?,?,?,2019/12/24,集合論與圖論第7講,30,定理2224,定理2224:設(shè)RAA且A,則(1)r(R)=RIA;(2)s(R)=RR-1;(3)t(R)=RR2R3.對(duì)比:R自反IARR對(duì)稱(chēng)R=R-1R傳遞R2R,2019/12/24,集合論與圖論第7講,31,定理22,定理22:設(shè)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.,2019/12/24,集合論與圖論第7講,32,定理23,定理23:設(shè)RAA且A,則s(R)=RR-1;證明:(1)RRR-1;(2)(RR-1)-1=RR-1RR-1對(duì)稱(chēng)s(R)RR-1;(3)Rs(R)s(R)對(duì)稱(chēng)Rs(R)R-1s(R)RR-1s(R)s(R)=RR-1.,2019/12/24,集合論與圖論第7講,33,定理24,定理24:設(shè)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.,2019/12/24,集合論與圖論第7講,34,定理24的推論,推論:設(shè)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.#,2019/12/24,集合論與圖論第7講,35,例8,例8:設(shè)A=a,b,c,d,R=,.求r(R),s(R),t(R).解:,a,b,c,d,2019/12/24,集合論與圖論第7講,36,例8(續(xù)),解(續(xù)):,a,b,c,d,a,b,c,d,a,b,c,d,2019/12/24,集合論與圖論第7講,37,例8(續(xù)2),解(續(xù)2):,a,b,c,d,2019/12/24,集合論與圖論第7講,38,例8(續(xù)3),解(續(xù)3):,a,b,c,d,2019/12/24,集合論與圖論第7講,39,例8(續(xù)4),解(續(xù)4):,a,b,c,d,a,b,c,d,#,2019/12/24,集合論與圖論第7講,40,閉包運(yùn)算是否保持關(guān)系性質(zhì)?,問(wèn)題:(1)R自反s(R),t(R)自反?(2)R對(duì)稱(chēng)r(R),t(R)對(duì)稱(chēng)?(3)R傳遞s(R),r(R)傳遞?,2019/12/24,集合論與圖論第7講,41,定理25,定理25:設(shè)RAA且A,則(1)R自反s(R)和t(R)自反;(2)R對(duì)稱(chēng)r(R)和t(R)對(duì)稱(chēng);(3)R傳遞r(R)傳遞;證明:(1)IARR-1=s(R)s(R)自反.IARR2R3=t(R)t(R)自反.,2019/12/24,集合論與圖論第7講,42,定理25(證明(2),(2)R對(duì)稱(chēng)r(R)和t(R)對(duì)稱(chēng);證明:(2)r(R)-1=(IAR)-1=IA-1R-1=IAR-1=IAR=r(R)r(R)對(duì)稱(chēng).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)對(duì)稱(chēng).,2019/12/24,集合論與圖論第7講,43,定理25(證明(3),(2)R傳遞r(R)傳遞;證明:(2)r(R)r(R)=(IAR)(IAR)=(IAIA)(IAR)(RIA)(RR)IARRR=IAR=r(R)r(R)傳遞.#,2019/12/24,集合論與圖論第7講,44,定理25(反例),反例:R傳遞,但是s(R)非傳遞.,G(R),G(s(R),小結(jié):閉包運(yùn)算保持下列關(guān)系性質(zhì).,2019/12/24,集合論與圖論第7講,45,閉包運(yùn)算是否可以交換順序?,問(wèn)題:(1)rs(R)=sr(R)?(2)rt(R)=tr(R)?(3)st(R)=ts(R)?說(shuō)明:rs(R)=r(s(R),2019/12/24,集合論與圖論第7講,46,定理26,定理26:設(shè)RAA且A,則(1)rs(R)=sr(R);(2)rt(R)=tr(R);(3)st(R)ts(R);,r(),s(),t(),可交換,可交換,2019/12/24,集合論與圖論第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).,2019/12/24,集合論與圖論第7講,48,定理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).rt(R)=tr(R).,2019/12/24,集合論與圖論第7講,49,定理26(證明(3),(3)st(R)ts(R);證明:(3)st(R)st(s(R)=sts(R)=s(ts(R)=ts(R)(ts(R)對(duì)稱(chēng),定理25(2)st(R)ts(R).#,2019/12/24,集合論與圖論第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),2019/12/24,集合論與圖論第7講,51,總結(jié),關(guān)系冪運(yùn)算關(guān)系閉包,2019/12/24,集合論與圖論第7講,52,作業(yè)(#5),p83,習(xí)題二,27,28,29今天交作業(yè)#1,#2,#3,#4,