北大離散數(shù)學(xué).ppt

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è)R?A?A,n?N,則(1)R0=IA;(2)Rn+1=Rn○R,(n?1).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},R?A?A,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=R0○R=R={,,},R2=R1○R={,,},,,,,,,,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=R0○R=R={,,},R2=R1○R={,,},R3=R2○R={,,}=R1,,,,,,,,b,a,c,,,,b,a,c,G(R),G(R3),,,,2019/12/24,《集合論與圖論》第7講,7,關(guān)系冪運(yùn)算(舉例,續(xù)3),解(續(xù)):R4=R3○R=R1○R=R2,R5=R4○R=R2○R=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)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.說(shuō)明:對(duì)實(shí)數(shù)R來(lái)說(shuō),m,n?N,Z,Q,R.對(duì)一般關(guān)系R來(lái)說(shuō),m,n?N.對(duì)滿足IA?R且A?domR?ranR的關(guān)系R來(lái)說(shuō),m,n?N,Z,例如R2○R-5=R-3,因?yàn)榭梢远xR-n=(R-1)n=(Rn)-1?,2019/12/24,《集合論與圖論》第7講,9,定理17,定理17:設(shè)R?A?A,m,n?N,則(1)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.說(shuō)明:可讓m,n?Z,只需IA?domR?ranR(此時(shí)IA=R○R-1=R-1○R)并且定義R-n=(R-1)n=(Rn)-1.回憶:(F○G)-1=G-1○F-1(R2)-1=(R○R)-1=R-1○R-1=(R-1)2,2019/12/24,《集合論與圖論》第7講,10,定理17(證明(1)),(1)Rm○Rn=Rm+n;證明:(1)給定m,對(duì)n歸納.n=0時(shí),Rm○Rn=Rm○R0=Rm○IA=Rm=Rm+0.假設(shè)Rm○Rn=Rm+n,則Rm○Rn+1=Rm○(Rn○R1)=(Rm○Rn)○R1=Rm+n○R=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,R?A?A,則?s,t?N,并且,使得Rs=Rt.證明:P(A?A)對(duì)冪運(yùn)算是封閉的,即?R,R?P(A?A)?Rk?P(A?A),(k?N).|P(A?A)|=,在R0,R1,R2,…,這個(gè)集合中,必有兩個(gè)是相同的.所以?s,t?N,并且,使得Rs=Rt.#,2019/12/24,《集合論與圖論》第7講,13,鴿巢原理(pigeonholeprinciple),鴿巢原理(pigeonholeprinciple):若把n+1只鴿子裝進(jìn)n只鴿巢,則至少有一只鴿巢裝2只以上的鴿子.又名抽屜原則(Dirichletdrawerprinciple),(PeterGustavLejeuneDirichlet,1805~1859)推廣形式:若把m件物品裝進(jìn)k只抽屜,則至少有一只抽屜裝只以上的物品.?1.8?=2,?1.8?=1,?-1.8?=-1,?-1.8?=-2.,2019/12/24,《集合論與圖論》第7講,14,定理18,定理18:設(shè)R?A?A,若?s,t?N(st-1?s,則令q=s+kp+i,其中k,i?N,p=t-s,s+i<t;于是Rq=Rs+kp+i=Rs+i?S.,2019/12/24,《集合論與圖論》第7講,17,定理18(證明(2)),(2)Rs+kp+i=Rs+i,其中k,i?N,p=t-s;證明:(2)k=0時(shí),顯然;k=1時(shí),即(1);設(shè)k?2.則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è)R?A?A,化簡(jiǎn)R100的指數(shù).已知(1)R7=R15;(2)R3=R5;(3)R1=R3.解:(1)R100=R7+11?8+5=R7+5=R12?{R0,R1,…,R14};(2)R100=R3+48?2+1=R3+1=R4?{R0,R1,…,R4};(3)R100=R1+49?2+1=R1+1=R2?{R0,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)R?r(R);(2)r(R)是自反的;(3)?S((R?S?S自反)?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)R?s(R);(2)s(R)是對(duì)稱(chēng)的;(3)?S((R?S?S對(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)R?t(R);(2)t(R)是傳遞的;(3)?S((R?S?S傳遞)?t(R)?S).,,,,,,,,G(R),,,,,,G(t(R)),,,,,2019/12/24,《集合論與圖論》第7講,24,定理19,定理19:設(shè)R?A?A且A??,則(1)R自反?r(R)=R;(2)R對(duì)稱(chēng)?s(R)=R;(3)R傳遞?t(R)=R;證明:(1)R?R?R自反?r(R)?R又R?r(R),?r(R)=R.(2)(3)完全類(lèi)似.#,2019/12/24,《集合論與圖論》第7講,25,定理20,定理20:設(shè)R1?R2?A?A且A??,則(1)r(R1)?r(R2);(2)s(R1)?s(R2);(3)t(R1)?t(R2);證明:(1)R1?R2?r(R2)自反,?r(R1)?r(R2)(2)(3)類(lèi)似可證.#,2019/12/24,《集合論與圖論》第7講,26,定理21,定理21:設(shè)R1,R2?A?A且A??,則(1)r(R1?R2)=r(R1)?r(R2);(2)s(R1?R2)=s(R1)?s(R2);(3)t(R1?R2)?t(R1)?t(R2).證明:(1)利用定理20,r(R1?R2)?r(R1)?r(R2).r(R1)?r(R2)自反且包含R1?R2,所以r(R1?R2)?r(R1)?r(R2).?r(R1?R2)=r(R1)?r(R2),2019/12/24,《集合論與圖論》第7講,27,定理21(證明(2)),(2)s(R1?R2)=s(R1)?s(R2);證明(2):利用定理20,s(R1?R2)?s(R1)?s(R2).s(R1)?s(R2)對(duì)稱(chēng)且包含R1?R2,所以s(R1?R2)?s(R1)?s(R2).?s(R1?R2)=s(R1)?s(R2),2019/12/24,《集合論與圖論》第7講,28,定理21(證明(3)),(3)t(R1?R2)?t(R1)?t(R2).證明(3):利用定理20,t(R1?R2)?t(R1)?t(R2).反例:t(R1?R2)?t(R1)?t(R2).#,,,a,b,,,,,,,,,a,b,,,,a,b,,G(t(R1?R2)),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,定理22~24,定理22~24:設(shè)R?A?A且A??,則(1)r(R)=R?IA;(2)s(R)=R?R-1;(3)t(R)=R?R2?R3?….對(duì)比:R自反?IA?RR對(duì)稱(chēng)?R=R-1R傳遞?R2?R,2019/12/24,《集合論與圖論》第7講,31,定理22,定理22:設(shè)R?A?A且A??,則r(R)=R?IA;證明:(1)R?R?IA;(2)IA?R?IA?R?IA自反?r(R)?R?IA;(3)R?r(R)?r(R)自反?R?r(R)?IA?r(R)?R?IA?r(R)?r(R)=R?IA.,2019/12/24,《集合論與圖論》第7講,32,定理23,定理23:設(shè)R?A?A且A??,則s(R)=R?R-1;證明:(1)R?R?R-1;(2)(R?R-1)-1=R?R-1?R?R-1對(duì)稱(chēng)?s(R)?R?R-1;(3)R?s(R)?s(R)對(duì)稱(chēng)?R?s(R)?R-1?s(R)?R?R-1?s(R)?s(R)=R?R-1.,2019/12/24,《集合論與圖論》第7講,33,定理24,定理24:設(shè)R?A?A且A??,則t(R)=R?R2?R3?…;證明:(1)R?R?R2?R3?…;(2)(R?R2?R3?…)2=R2?R3?…?R?R2?R3?…?R?R2?R3?…傳遞?t(R)?R?R2?R3?…;(3)R?t(R)?t(R)傳遞?R?t(R)?R2?t(R)?R3?t(R)?…?R?R2?R3?…?t(R)?t(R)=R?R2?R3?….,2019/12/24,《集合論與圖論》第7講,34,定理24的推論,推論:設(shè)R?A?A且0<|A|<?,則?l?N,使得t(R)=R?R2?R3?…?Rl;證明:由定理16知?s,t?N,使得Rs=Rt.由定理18知R,R2,R3,…?{R0,R1,…,Rt-1}.取l=t-1,由定理24知t(R)=R?R2?R3?….=R?R2?R3?…?Rl?t(R)=R?R2?R3?…?Rl.#,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è)R?A?A且A??,則(1)R自反?s(R)和t(R)自反;(2)R對(duì)稱(chēng)?r(R)和t(R)對(duì)稱(chēng);(3)R傳遞?r(R)傳遞;證明:(1)IA?R?R-1=s(R)?s(R)自反.IA?R?R2?R3?…=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=(IA?R)-1=IA-1?R-1=IA?R-1=IA?R=r(R)?r(R)對(duì)稱(chēng).t(R)-1=(R?R2?R3?…)-1=R-1?(R2)-1?(R3)-1?…=R-1?(R-1)2?(R-1)3?…((F○G)-1=G-1○F-1)=R?R2?R3?…=t(R),?t(R)對(duì)稱(chēng).,2019/12/24,《集合論與圖論》第7講,43,定理25(證明(3)),(2)R傳遞?r(R)傳遞;證明:(2)r(R)○r(R)=(IA?R)○(IA?R)=(IA○IA)?(IA○R)?(R○IA)?(R○R)?IA?R?R?R=IA?R=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è)R?A?A且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(R?R-1)=IA?(R?R-1)=(IA?R)?(IA-1?R-1)=(IA?R)?(IA?R)-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(R?R2?R3?…)=IA?(R?R2?R3?…)=(IA?R)?(IA?R?R2)?(IA?R?R2?R3)?…=(IA?R)?(IA?R)2?(IA?R)3?…=r(R)?r(R)2?r(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,