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

1、2020/9/2,集合論與圖論第7講,1,第7講 關(guān)系冪運(yùn)算與關(guān)系閉包北京大學(xué),內(nèi)容提要 關(guān)系冪(power)運(yùn)算 關(guān)系閉包(closure),2020/9/2,集合論與圖論第7講,2,關(guān)系的冪運(yùn)算,n次冪的定義 指數(shù)律 冪指數(shù)的化簡(jiǎn),2020/9/2,集合論與圖論第7講,3,關(guān)系的n次冪,關(guān)系的n次冪(nth power): 設(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,2020/9/2,集合論與圖論第7講,4,關(guān)系冪運(yùn)算(舉例),例: 設(shè)A=a,b,c

2、, RAA, R=, 求R的各次冪. 解:,b,a,c,b,a,c,G( R ),G( R0 ),2020/9/2,集合論與圖論第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 ),2020/9/2,集合論與圖論第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 ),2020/9/2,集合論與圖論第7講,7,關(guān)系

3、冪運(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 ),2020/9/2,集合論與圖論第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

4、-5=R-3,因?yàn)榭梢远x R-n = (R-1)n = (Rn)-1 ?,2020/9/2,集合論與圖論第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,2020/9/2,集合論與圖論第7講,10,定理17(證明(1),(1) RmRn = Rm+n ; 證明: (1) 給定m,

5、對(duì)n歸納. n=0時(shí), RmRn = RmR0 = RmIA = Rm = Rm+0. 假設(shè) RmRn = Rm+n, 則 RmRn+1 = Rm(Rn R1) = (RmRn)R1 = Rm+nR = R(m+n)+1 = Rm+(n+1). (2) 同樣對(duì)n歸納. #,2020/9/2,集合論與圖論第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

6、,R16,R17,2020/9/2,集合論與圖論第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. #,2020/9/2,集合論與圖論第7講,13,鴿巢原理(pigeonhole principle),鴿巢原理(pigeonhole principle): 若把n+1只鴿子裝進(jìn)n只鴿巢, 則至少有一只鴿巢裝2只

7、以上的鴿子. 又名抽屜原則(Dirichlet drawer principle), (Peter Gustav Lejeune Dirichlet,18051859) 推廣形式: 若把m件物品裝進(jìn)k只抽屜, 則至少有一只抽屜裝 只以上的物品. 1.8=2, 1.8=1, -1.8=-1, -1.8=-2.,2020/9/2,集合論與圖論第7講,14,定理18,定理18: 設(shè) RAA, 若 s,tN (st),使得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

8、.,2020/9/2,集合論與圖論第7講,15,定理18(說(shuō)明),s,p,i,泵(pumping): Rs+kp+i = Rs+i,2020/9/2,集合論與圖論第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.,2020/9/2,集合論與圖論第7講,17,定理18(證明(2),(2) Rs+kp

9、+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 . #,2020/9/2,集合論與圖論第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=R

10、7+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. #,2020/9/2,集合論與圖論第7講,19,關(guān)系的閉包,自反閉包r( R ) 對(duì)稱閉包s( R ) 傳遞閉包t( R ) 閉包的性質(zhì), 求法, 相互關(guān)系,2020/9/2,集合論與圖論第7講,20,什么是閉包,閉包(closure): 包含一些給定對(duì)象, 具有指定性質(zhì)的最小集合 “最小”: 任何包含同樣對(duì)象, 具有同樣性質(zhì)的集合, 都包含這個(gè)閉包集合 例: (平面上點(diǎn)的凸包),2020/9/2,集合

11、論與圖論第7講,21,自反閉包(reflexive closure),自反閉包: 包含給定關(guān)系R的最小自反關(guān)系, 稱為R的自反閉包, 記作r( R ). (1) R r( R ); (2) r( R )是自反的; (3) S( (RS S自反) r( R )S ).,G( R ),G(r( R ),2020/9/2,集合論與圖論第7講,22,對(duì)稱閉包(symmetric closure),對(duì)稱閉包: 包含給定關(guān)系R的最小對(duì)稱關(guān)系, 稱為R的對(duì)稱閉包, 記作s( R ). (1) R s( R ); (2) s( R )是對(duì)稱的; (3) S( (RS S對(duì)稱) s( R )S ).,G( R

12、),G(s( R ),2020/9/2,集合論與圖論第7講,23,傳遞閉包(transitive closure),傳遞閉包: 包含給定關(guān)系R的最小傳遞關(guān)系, 稱為R的傳遞閉包, 記作t( R ). (1) R t( R ); (2) t( R )是傳遞的; (3) S( (RS S傳遞) t( R )S ).,G( R ),G(t( R ),2020/9/2,集合論與圖論第7講,24,定理19,定理19: 設(shè)RAA且A,則 (1) R自反 r( R ) = R; (2) R對(duì)稱 s( R ) = R; (3) R傳遞 t( R ) = R; 證明: (1) RR R自反 r( R )R 又

13、R r( R ), r( R ) = R. (2)(3) 完全類似. #,2020/9/2,集合論與圖論第7講,25,定理20,定理20: 設(shè) R1R2AA 且 A, 則 (1) r( R1 ) r( R2 ); (2) s( R1 ) s( R2 ); (3) t( R1 ) t( R2 ); 證明: (1) R1R2 r( R2 )自反, r( R1 ) r( R2 ) (2)(3) 類似可證. #,2020/9/2,集合論與圖論第7講,26,定理21,定理21: 設(shè) R1,R2AA 且 A, 則 (1) r(R1R2) = r( R1 )r( R2 ); (2) s(R1R2) = s(

14、 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 ),2020/9/2,集合論與圖論第7講,27,定理21(證明(2),(2) s( R1R2) = s( R1 )s( R2 ); 證明(2): 利用定理20, s(R1R2)s(R1)s(R2). s(R1)s(R2)對(duì)稱且包含R1R2,所以 s(R1R2)s(R1)s(R2). s( R1R2) = s( R

15、1 )s( R2 ),2020/9/2,集合論與圖論第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),2020/9/2,集合論與圖論第7講,29,如何求閉包?,問題: (1) r( R ) = R (2) s( R ) = R (3) t( R ) = R ,?,?,?,2020/9/2,集合論與圖論第7講,30,定理2224,定

16、理2224: 設(shè) RAA 且 A, 則 (1) r( R ) = RIA; (2) s( R ) = RR-1; (3) t( R ) = RR2R3. 對(duì)比: R自反 IAR R對(duì)稱 R=R-1 R傳遞 R2R,2020/9/2,集合論與圖論第7講,31,定理22,定理22: 設(shè) 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.,2020/9/2,集合論與圖論第7講,32,定理23,

17、定理23: 設(shè) RAA 且 A, 則 s( R ) = RR-1; 證明: (1) R RR-1; (2) (RR-1)-1=RR-1 RR-1對(duì)稱 s( R )RR-1; (3) Rs( R ) s( R )對(duì)稱 Rs( R ) R-1s( R ) RR-1s( R ) s( R ) = RR-1.,2020/9/2,集合論與圖論第7講,33,定理24,定理24: 設(shè) RAA 且 A, 則 t( R ) = RR2R3; 證明: (1) R RR2R3; (2) (RR2R3)2 = R2R3 RR2R3 RR2R3傳遞 t( R )RR2R3; (3) Rt( R ) t( R )傳遞 R

18、t( R )R2t( R )R3t( R ) RR2R3 t( R ) t( R ) = RR2R3.,2020/9/2,集合論與圖論第7講,34,定理24的推論,推論: 設(shè) 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 . #,2020/9/2,集合論與圖論第7講,35,例8,例8: 設(shè) A = a,b,c,d , R = ,

19、. 求 r( R ), s( R ), t( R ). 解:,a,b,c,d,2020/9/2,集合論與圖論第7講,36,例8(續(xù)),解(續(xù)):,a,b,c,d,a,b,c,d,a,b,c,d,2020/9/2,集合論與圖論第7講,37,例8(續(xù)2),解(續(xù)2):,a,b,c,d,2020/9/2,集合論與圖論第7講,38,例8(續(xù)3),解(續(xù)3):,a,b,c,d,2020/9/2,集合論與圖論第7講,39,例8(續(xù)4),解(續(xù)4):,a,b,c,d,a,b,c,d,#,2020/9/2,集合論與圖論第7講,40,閉包運(yùn)算是否保持關(guān)系性質(zhì)?,問題: (1) R自反 s( R ), t( R

20、)自反 ? (2) R對(duì)稱 r( R ), t( R )對(duì)稱 ? (3) R傳遞 s( R ), r( R )傳遞 ?,2020/9/2,集合論與圖論第7講,41,定理25,定理25: 設(shè)RAA且A,則 (1) R自反 s( R )和t( R )自反; (2) R對(duì)稱 r( R )和t( R )對(duì)稱; (3) R傳遞 r( R )傳遞; 證明: (1) IA RR-1 = s( R ) s( R )自反. IA RR2R3 = t( R ) t( R )自反.,2020/9/2,集合論與圖論第7講,42,定理25(證明(2),(2) R對(duì)稱 r( R )和t( R )對(duì)稱; 證明: (2) r

21、( R )-1 =(IAR)-1 =IA-1R-1 =IAR-1 =IAR= r( R ) r( R )對(duì)稱. 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ì)稱.,2020/9/2,集合論與圖論第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 )傳遞. #,2020

22、/9/2,集合論與圖論第7講,44,定理25(反例),反例: R傳遞, 但是s( R )非傳遞.,G( R ),G(s( R ),小結(jié): 閉包運(yùn)算保持下列關(guān)系性質(zhì).,2020/9/2,集合論與圖論第7講,45,閉包運(yùn)算是否可以交換順序?,問題: (1) rs( R ) = sr( R ) ? (2) rt( R ) = tr( R ) ? (3) st( R ) = ts( R ) ? 說(shuō)明: rs( R ) = r(s( R ),2020/9/2,集合論與圖論第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( ),可交換,可交換,2020/9/2,集合論與圖論第7講,47,定理26(證明(1),(1) rs(