第7講關系冪運算與關系閉包

北京大學內容提要關系冪(power)運算關系閉包(closure)2025/4/221《集合論與圖論》第7講第1頁關系冪運算

n次冪定義

指數律冪指數化簡2025/4/222《集合論與圖論》第7講第2頁關系n次冪關系n次冪(nthpower):設R

AA,nN,則

(1)R0

=IA;(2)Rn+1

=Rn○R,(n1).

Rn表示關系,是R關系圖中長度為n有向路徑起點與終點關系.12nn-12025/4/223《集合論與圖論》第7講第3頁關系冪運算(舉例)例:設A={a,b,c},R

AA,R={<a,b>,<b,a>,<a,c>},求R各次冪.解:bacbacG(R)G(R0)2025/4/224《集合論與圖論》第7講第4頁關系冪運算(舉例,續)解(續):R0

=IA,

R1

=R0○R=R={<a,b>,<b,a>,<a,c>},

R2

=R1○R={<a,a>,<b,b>,<b,c>},bacbacG(R)G(R2)2025/4/225《集合論與圖論》第7講第5頁關系冪運算(舉例,續2)解(續):R0

=IA,

R1

=R0○R=R={<a,b>,<b,a>,<a,c>},

R2

=R1○R={<a,a>,<b,b>,<b,c>},

R3

=R2○R={<a,b>,<a,b>,<a,c>}=R1,bacbacG(R)G(R3)2025/4/226《集合論與圖論》第7講第6頁關系冪運算(舉例,續3)解(續):

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,…,.#bacbacG(R)G(R5)bacG(R4)2025/4/227《集合論與圖論》第7講第7頁關系冪運算是否有指數律?指數律:(1)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.說明:對實數R來說,m,nN,Z,Q,R.對普通關系R來說,m,nN.對滿足IAR且AdomRranR關系R來說,m,nN,Z,比如R2○R-5=R-3,因為能夠定義R-n=(R-1)n=(Rn)-1

?2025/4/228《集合論與圖論》第7講第8頁定理17定理17:設R

AA,m,nN,則(1)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.說明:可讓m,nZ,只需IAdomRranR(此時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)22025/4/229《集合論與圖論》第7講第9頁定理17(證實(1))(1)Rm○Rn=Rm+n;證實:(1)給定m,對n歸納.n=0時,

Rm○Rn=Rm○R0=Rm○IA=Rm=Rm+0.假設Rm○Rn=Rm+n,

則Rm○Rn+1

=Rm○(Rn

○R1)=(Rm○Rn)○R1=Rm+n○R=R(m+n)+1=Rm+(n+1).(2)一樣對n歸納.#2025/4/2210《集合論與圖論》第7講第10頁R0,R1,R2,R3,…是否互不相等?R0R1R2R3R4R5R6R7R8R0R1R2R3R4R5=R19=R33=R47=…R6=R20=R34=R48=…R7=R21=R35=R49=…R8=R22=R36=…R15R9R10R11R14R16R172025/4/2211《集合論與圖論》第7講第11頁定理16定理16:設|A|=n,R

AA,則s,tN,而且,使得Rs=Rt.證實:P(AA)對冪運算是封閉,即

R,RP(AA)RkP(AA),

(kN).|P(AA)|=,在R0,R1,R2,…,

這個集合中,必有兩個是相同.所以s,tN,而且,使得Rs=Rt.#2025/4/2212《集合論與圖論》第7講第12頁鴿巢原理(pigeonholeprinciple)鴿巢原理(pigeonholeprinciple):若把n+1只鴿子裝進n只鴿巢,則最少有一只鴿巢裝2只以上鴿子.又名抽屜標準(Dirichletdrawerprinciple),(PeterGustavLejeuneDirichlet,1805~1859)推廣形式:若把m件物品裝進k只抽屜,則最少有一只抽屜裝只以上物品.1.8=2,1.8=1,-1.8=-1,-1.8=-2.2025/4/2213《集合論與圖論》第7講第13頁定理18定理18:設R

AA,若s,tN(s<t),使得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.2025/4/2214《集合論與圖論》第7講第14頁定理18(說明)spi泵(pumping):

Rs+kp+i

=

Rs+i2025/4/2215《集合論與圖論》第7講第15頁定理18(證實(1)(3))(1)Rs+k=Rt+k;(3)令S={R0,R1,…,Rt-1},則

qN,RqS.證實:(1)Rs+k=Rs○Rk=Rt○Rk=Rt+k;(3)若q>t-1s,則令q=s+kp+i,其中k,iN,p=t-s,s+i<t;于是Rq=Rs+kp+i=Rs+iS.2025/4/2216《集合論與圖論》第7講第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.#2025/4/2217《集合論與圖論》第7講第17頁冪指數化簡方法:利用定理16,定理18.例6:設R

AA,化簡R100指數.已知(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}.#2025/4/2218《集合論與圖論》第7講第18頁關系閉包自反閉包r(R)對稱閉包s(R)傳遞閉包t(R)閉包性質,求法,相互關系2025/4/2219《集合論與圖論》第7講第19頁什么是閉包閉包(closure):包含一些給定對象,含有指定性質最小集合“最小”:任何包含一樣對象,含有一樣性質集合,都包含這個閉包集合例:(平面上點凸包)2025/4/2220《集合論與圖論》第7講第20頁自反閉包(reflexiveclosure)自反閉包:包含給定關系R最小自反關系,稱為R自反閉包,記作r(R).(1)R

r(R);(2)r(R)是自反;(3)

S((RSS自反)r(R)S).G(R)G(r(R))2025/4/2221《集合論與圖論》第7講第21頁對稱閉包(symmetricclosure)對稱閉包:包含給定關系R最小對稱關系,稱為R對稱閉包,記作s(R).(1)Rs(R);(2)s(R)是對稱;(3)

S((RSS對稱)s(R)S).G(R)G(s(R))2025/4/2222《集合論與圖論》第7講第22頁傳遞閉包(transitiveclosure)傳遞閉包:包含給定關系R最小傳遞關系,稱為R傳遞閉包,記作t(R).(1)R

t(R);(2)t(R)是傳遞;(3)

S((RSS傳遞)t(R)S).G(R)G(t(R))2025/4/2223《集合論與圖論》第7講第23頁定理19定理19:設R

A

A且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)完全類似.#2025/4/2224《集合論與圖論》第7講第24頁定理20定理20:設R1

R2

A

A且A

,則(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2);證實:(1)R1

R2r(R2)自反,

r(R1)r(R2)(2)(3)類似可證.#2025/4/2225《集合論與圖論》第7講第25頁定理21定理21:設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)2025/4/2226《集合論與圖論》第7講第26頁定理21(證實(2))(2)s(R1

R2)=s(R1)s(R2);證實(2):利用定理20,s(R1

R2)s(R1)s(R2).s(R1)s(R2)對稱且包含R1

R2,所以

s(R1

R2)s(R1)s(R2).s(R1

R2)=s(R1)s(R2)2025/4/2227《集合論與圖論》第7講第27頁定理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).#abababG(t(R1

R2))G(R1)=G(t(R1))G(R2)=G(t(R2))2025/4/2228《集合論與圖論》第7講第28頁怎樣求閉包?問題:(1)r(R)=R

(2)s(R)=R

(3)t(R)=R

???2025/4/2229《集合論與圖論》第7講第29頁定理22~24定理22~24:設R

A

A且A

,則(1)r(R)=R

IA;(2)s(R)=R

R-1;(3)t(R)=R

R2

R3

….對比:R自反

IARR對稱

R=R-1R傳遞

R2R2025/4/2230《集合論與圖論》第7講第30頁定理22定理22:設R

A

A且A

,則r(R)=R

IA;證實:(1)RR

IA;(2)IAR

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.2025/4/2231《集合論與圖論》第7講第31頁定理23定理23:設R

A

A且A

,則s(R)=R

R-1;證實:(1)RR

R-1;(2)(R

R-1)-1=R

R-1

R

R-1對稱s(R)R

R-1;(3)Rs(R)

s(R)對稱

Rs(R)

R-1s(R)R

R-1s(R)s(R)=R

R-1.2025/4/2232《集合論與圖論》第7講第32頁定理24定理24:設R

A

A且A

,則t(R)=R

R2

R3…;證實:(1)RR

R2

R3…;(2)(R

R2

R3…)2=R2

R3…R

R2

R3…

R

R2

R3…傳遞t(R)R

R2

R3…;(3)Rt(R)

t(R)傳遞

Rt(R)

R2t(R)

R3t(R)…R

R2

R3…t(R)

t(R)=R

R2

R3….2025/4/2233《集合論與圖論》第7講第33頁定理24推論推論:設R

A

A且0<|A|<,則

lN,使得t(R)=R

R2

R3…Rl;證實:由定理16知

s,tN,使得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.#2025/4/2234《集合論與圖論》第7講第34頁例8例8:設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}.求r(R),s(R),t(R).解:abcd2025/4/2235《集合論與圖論》第7講第35頁例8(續)解(續):abcdabcdabcd2025/4/2236《集合論與圖論》第7講第36頁例8(續2)解(續2):abcd2025/4/2237《集合論與圖論》第7講第37頁例8(續3)解(續3):abcd2025/4/2238《集合論與圖論》第7講第38頁例8(續4)解(續4):abcdabcd#2025/4/2239《集合論與圖論》第7講第39頁閉包運算是否保持關系性質?問題:(1)R自反

s(R),t(R)自反?(2)R對稱

r(R),t(R)對稱?(3)R傳遞

s(R),r(R)傳遞?2025/4/2240《集合論與圖論》第7講第40頁定理25定理25:設R

A

A且A

,則(1)R自反

s(R)和t(R)自反;(2)R對稱

r(R)和t(R)對稱;(3)R傳遞

r(R)傳遞;證實:(1)

IA

R

R-1=s(R)

s(R)自反.

IAR

R2

R3…=t(R)

t(R)自反.2025/4/2241《集合論與圖論》第7講第41頁定理25(證實(2))(2)R對稱

r(R)和t(R)對稱;證實:(2)r(R)-1=(IA

R)-1=IA-1

R-1=IA

R-1

=IA

R=r(R)

r(R)對稱.

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)對稱.2025/4/2242《集合論與圖論》第7講第42頁定理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)傳遞.#2025/4/2243《集合論與圖論》第7講第43頁定理25(反例)反例:R傳遞,不過s(R)非傳遞.G(R)G(s(R))自反性對稱性傳遞性r(R)

(定義)

(定理25(2))

(定理25(3))s(R)

(定理25(1))

(定義)(反例)t(R)

(定理25(1))

(定理25(2))

(定義)小結:閉包運算保持以下關系性質.2025/4/2244《集合論與圖論》第7講第44頁閉包運算是否能夠交換次序?問題:(1)rs(R)=sr(R)?(2)rt(R)=tr(R)?(3)st(R)=ts(R)?說明:rs(R)=r(s(R))2025/4/2245《集合論與圖論》第7講第45頁定理26定理26:設R

A

A且A

,則(1)rs(R)=sr(R);(2)rt(R)=tr(R);(3)st(R)

ts(R);r()s()t