《細菌》教學(xué)課件37-人教版

第7講關(guān)系冪運算與關(guān)系閉包

北京大學(xué)內(nèi)容提要關(guān)系冪(power)運算關(guān)系閉包(closure)2024/4/11精選可編輯ppt第7講關(guān)系冪運算與關(guān)系閉包

北京大學(xué)內(nèi)容提要2024/3/關(guān)系的冪運算

n次冪的定義

指數(shù)律冪指數(shù)的化簡2024/4/12精選可編輯ppt關(guān)系的冪運算n次冪的定義2024/3/312精選可編輯pp關(guān)系的n次冪關(guān)系的n次冪(nthpower):設(shè)R

AA,nN,則

(1)R0

=IA;(2)Rn+1

=Rn○R,(n1).

Rn表示的關(guān)系,是R的關(guān)系圖中長度為n的有向路徑的起點與終點的關(guān)系.12nn-12024/4/13精選可編輯ppt關(guān)系的n次冪關(guān)系的n次冪(nthpower):設(shè)RA關(guān)系冪運算(舉例)例:設(shè)A={a,b,c},R

AA,R={<a,b>,<b,a>,<a,c>},求R的各次冪.解:bacbacG(R)G(R0)2024/4/14精選可編輯ppt關(guān)系冪運算(舉例)例:設(shè)A={a,b,c},RAA,關(guān)系冪運算(舉例,續(xù))解(續(xù)):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)2024/4/15精選可編輯ppt關(guān)系冪運算(舉例,續(xù))解(續(xù)):R0=IA,bacba關(guān)系冪運算(舉例,續(xù)2)解(續(xù)):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)2024/4/16精選可編輯ppt關(guān)系冪運算(舉例,續(xù)2)解(續(xù)):R0=IA,bacb關(guā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,…,.#bacbacG(R)G(R5)bacG(R4)2024/4/17精選可編輯ppt關(guān)系冪運算(舉例,續(xù)3)解(續(xù)):R4=R3○R=關(guān)系冪運算是否有指數(shù)律?指數(shù)律:(1)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.說明:對實數(shù)R來說,m,nN,Z,Q,R.對一般關(guān)系R來說,m,nN.對滿足IAR且AdomRranR的關(guān)系R來說,m,nN,Z,例如R2○R-5=R-3,因為可以定義R-n=(R-1)n=(Rn)-1

?2024/4/18精選可編輯ppt關(guān)系冪運算是否有指數(shù)律?指數(shù)律:2024/3/318精選可編定理17定理17:設(shè)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)22024/4/19精選可編輯ppt定理17定理17:設(shè)RAA,m,nN,則202定理17(證明(1))(1)Rm○Rn=Rm+n;證明:(1)給定m,對n歸納.n=0時,

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)同樣對n歸納.#2024/4/110精選可編輯ppt定理17(證明(1))(1)Rm○Rn=Rm+n;R0,R1,R2,R3,…是否互不相等?R0R1R2R3R4R5R6R7R8R0R1R2R3R4R5=R19=R33=R47=…R6=R20=R34=R48=…R7=R21=R35=R49=…R8=R22=R36=…R15R9R10R11R14R16R172024/4/111精選可編輯pptR0,R1,R2,R3,…是否互不相等?R0R1R2R3R定理16定理16:設(shè)|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.#2024/4/112精選可編輯ppt定理16定理16:設(shè)|A|=n,RAA,則s鴿巢原理(pigeonholeprinciple)鴿巢原理(pigeonholeprinciple):若把n+1只鴿子裝進n只鴿巢,則至少有一只鴿巢裝2只以上的鴿子.又名抽屜原則(Dirichletdrawerprinciple),(PeterGustavLejeuneDirichlet,1805~1859)推廣形式:若把m件物品裝進k只抽屜,則至少有一只抽屜裝只以上的物品.1.8=2,1.8=1,-1.8=-1,-1.8=-2.2024/4/113精選可編輯ppt鴿巢原理(pigeonholeprinciple)鴿巢原理定理18定理18:設(shè)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.2024/4/114精選可編輯ppt定理18定理18:設(shè)RAA,若s,tN(s定理18(說明)spi泵(pumping):

Rs+kp+i

=

Rs+i2024/4/115精選可編輯ppt定理18(說明)spi泵(pumping):2024定理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.2024/4/116精選可編輯ppt定理18(證明(1)(3))(1)Rs+k=Rt+定理18(證明(2))(2)Rs+kp+i=Rs+i,其中k,iN,p=t-s;證明:(2)k=0時,顯然;k=1時,即(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.#2024/4/117精選可編輯ppt定理18(證明(2))(2)Rs+kp+i=Rs+i冪指數(shù)的化簡方法:利用定理16,定理18.例6:設(shè)R

AA,化簡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}.#2024/4/118精選可編輯ppt冪指數(shù)的化簡方法:利用定理16,定理18.2024/3/關(guān)系的閉包自反閉包r(R)對稱閉包s(R)傳遞閉包t(R)閉包的性質(zhì),求法,相互關(guān)系2024/4/119精選可編輯ppt關(guān)系的閉包自反閉包r(R)2024/3/3119精選可編什么是閉包閉包(closure):包含一些給定對象,具有指定性質(zhì)的最小集合“最小”:任何包含同樣對象,具有同樣性質(zhì)的集合,都包含這個閉包集合例:(平面上點的凸包)2024/4/120精選可編輯ppt什么是閉包閉包(closure):包含一些給定對象,具自反閉包(reflexiveclosure)自反閉包:包含給定關(guān)系R的最小自反關(guān)系,稱為R的自反閉包,記作r(R).(1)R

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

S((RSS自反)r(R)S).G(R)G(r(R))2024/4/121精選可編輯ppt自反閉包(reflexiveclosure)自反閉包:包對稱閉包(symmetricclosure)對稱閉包:包含給定關(guān)系R的最小對稱關(guān)系,稱為R的對稱閉包,記作s(R).(1)Rs(R);(2)s(R)是對稱的;(3)

S((RSS對稱)s(R)S).G(R)G(s(R))2024/4/122精選可編輯ppt對稱閉包(symmetricclosure)對稱閉包:包傳遞閉包(transitiveclosure)傳遞閉包:包含給定關(guān)系R的最小傳遞關(guān)系,稱為R的傳遞閉包,記作t(R).(1)R

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

S((RSS傳遞)t(R)S).G(R)G(t(R))2024/4/123精選可編輯ppt傳遞閉包(transitiveclosure)傳遞閉包:定理19定理19:設(shè)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)完全類似.#2024/4/124精選可編輯ppt定理19定理19:設(shè)RAA且A,則2024/3/3定理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

R2r(R2)自反,

r(R1)r(R2)(2)(3)類似可證.#2024/4/125精選可編輯ppt定理20定理20:設(shè)R1R2AA且A,則定理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)2024/4/126精選可編輯ppt定理21定理21:設(shè)R1,R2AA且A,則定理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)2024/4/127精選可編輯ppt定理21(證明(2))(2)s(R1R2)=s(定理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))2024/4/128精選可編輯ppt定理21(證明(3))(3)t(R1R2)t(如何求閉包?問題:(1)r(R)=R

(2)s(R)=R

(3)t(R)=R

???2024/4/129精選可編輯ppt如何求閉包?問題:???2024/3/3129精選可編定理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

….對比:R自反

IARR對稱

R=R-1R傳遞

R2R2024/4/130精選可編輯ppt定理22~24定理22~24:設(shè)RAA且A,定理22定理22:設(shè)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.2024/4/131精選可編輯ppt定理22定理22:設(shè)RAA且A,則2024定理23定理23:設(shè)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.2024/4/132精選可編輯ppt定理23定理23:設(shè)RAA且A,則2024定理24定理24:設(shè)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….2024/4/133精選可編輯ppt定理24定理24:設(shè)RAA且A,則2024定理24的推論推論:設(shè)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.#2024/4/134精選可編輯ppt定理24的推論推論:設(shè)RAA且0<|A|<,例8例8:設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}.求r(R),s(R),t(R).解:abcd2024/4/135精選可編輯ppt例8例8:設(shè)A={a,b,c,d},abcd20例8(續(xù))解(續(xù)):abcdabcdabcd2024/4/136精選可編輯ppt例8(續(xù))解(續(xù)):abcdabcdabcd2024/例8(續(xù)2)解(續(xù)2):abcd2024/4/137精選可編輯ppt例8(續(xù)2)解(續(xù)2):abcd2024/3/3137例8(續(xù)3)解(續(xù)3):abcd2024/4/138精選可編輯ppt例8(續(xù)3)解(續(xù)3):abcd2024/3/3138例8(續(xù)4)解(續(xù)4):abcdabcd#2024/4/139精選可編輯ppt例8(續(xù)4)解(續(xù)4):abcdabcd#2024/3閉包運算是否保持關(guān)系性質(zhì)?問題:(1)R自反

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

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

s(R),r(R)傳遞?2024/4/140精選可編輯ppt閉包運算是否保持關(guān)系性質(zhì)?問題:2024/3/3140精選可定理25定理25:設(shè)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)自反.2024/4/141精選可編輯ppt定理25定理25:設(shè)RAA且A,則2024/3/3定理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)對稱.2024/4/142精選可編輯ppt定理25(證明(2))(2)R對稱r(R)和t(定理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)傳遞.#2024/4/143精選可編輯ppt定理25(證明(3))(2)R傳遞r(R)傳遞;定理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))

(定義)小結(jié):閉包運算保持下列關(guān)系性質(zhì).2024/4/144精選可編輯ppt定理25(反例)反例:R傳遞,但是s(R)非傳遞.閉包運算是否可以交換順序?問題:(1)rs(R)=sr(R)?(2)rt(R)=tr(R)?(3)st(R)=ts(R)?說明:rs(R)=r(s(R))2024/4/145精選可編輯ppt閉包運算是否可以交換順序?問題:2024/3/3145精選定理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()可交換可交換2024/4/146精選可編輯ppt