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

《北大離散數(shù)學(xué)課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《北大離散數(shù)學(xué)課件.ppt（52頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、2020/8/20,集合論與圖論第7講,1,第7講 關(guān)系冪運(yùn)算與關(guān)系閉包北京大學(xué),內(nèi)容提要 關(guān)系冪(power)運(yùn)算 關(guān)系閉包(closure),2020/8/20,集合論與圖論第7講,2,關(guān)系的冪運(yùn)算,n次冪的定義 指數(shù)律 冪指數(shù)的化簡,2020/8/20,集合論與圖論第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)系圖中長度為n的有向路徑的起點(diǎn)與終點(diǎn)的關(guān)系.,,,,,,,,,,,,1,2,n,n-1,2020/8/20,集合論與圖論第7講,4,關(guān)系冪運(yùn)

2、算(舉例),例: 設(shè)A=a,b,c, RAA, R=,,, 求R的各次冪. 解:,,,,,,,b,a,c,,,,b,a,c,,,,,,,G( R ),G( R0 ),2020/8/20,集合論與圖論第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/8/20,集合論與圖論第7講,6,關(guān)系冪運(yùn)算(舉例,續(xù)2),解(續(xù)): R0 = IA, R1 = R0R = R = ,,, R2 = R1R = ,,, R3 = R2R

3、= ,, = R1,,,,,,,,b,a,c,,,,b,a,c,G( R ),G( R3 ),,,,2020/8/20,集合論與圖論第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 ),,2020/8/20,集合論與圖論第7講,8,關(guān)系冪運(yùn)算是否有指數(shù)律?,指數(shù)律: (1) RmRn =

4、 Rm+n ; (2) (Rm)n = Rmn. 說明: 對實(shí)數(shù)R來說, m,nN,Z,Q,R. 對一般關(guān)系R來說, m,nN. 對滿足IAR且AdomRranR的關(guān)系R來說, m,nN,Z, 例如R2R-5=R-3,因?yàn)榭梢远x R-n = (R-1)n = (Rn)-1 ?,2020/8/20,集合論與圖論第7講,9,定理17,定理17: 設(shè) RAA, m,nN, 則 (1) RmRn = Rm+n ; (2) (Rm)n = Rmn. 說明: 可讓 m,nZ, 只需IAdomRranR (此時(shí)IA=RR-1=R-1R)并且定義 R-n = (R-1)n = (Rn)-1. 回

5、憶: (FG)-1=G-1F-1 (R2)-1=(RR)-1=R-1R-1=(R-1)2,2020/8/20,集合論與圖論第7講,10,定理17(證明(1)),(1) RmRn = Rm+n ; 證明: (1) 給定m, 對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) 同樣對n歸納. #,2020/8/20,集合論與圖論第7講,11,R0,R1,R2,R3,是否互不相等?,,,,,,,,

6、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,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,2020/8/20,集合論與圖論第7講,12,定理16,定理16: 設(shè) |A|=n, RAA, 則 s,tN, 并且 , 使得 Rs = Rt. 證明: P(AA)對冪運(yùn)算是封閉的, 即 R, RP(AA) RkP(AA

7、), (kN). |P(AA)| = , 在R0,R1,R2,, 這 個(gè)集合中, 必有兩個(gè)是相同的. 所以 s,tN, 并且 , 使得 Rs = Rt. #,2020/8/20,集合論與圖論第7講,13,鴿巢原理(pigeonhole principle),鴿巢原理(pigeonhole principle): 若把n+1只鴿子裝進(jìn)n只鴿巢, 則至少有一只鴿巢裝2只以上的鴿子. 又名抽屜原則(Dirichlet drawer principle), (Peter Gustav Lejeune Dirichlet,18051859) 推廣形式: 若把m件物品裝進(jìn)k只抽屜,

8、 則至少有一只抽屜裝 只以上的物品. 1.8=2, 1.8=1, -1.8=-1, -1.8=-2.,2020/8/20,集合論與圖論第7講,14,定理18,定理18: 設(shè) RAA, 若 s,tN (s

9、: Rs+kp+i = Rs+i,2020/8/20,集合論與圖論第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+i

10、然; 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/8/20,集合論與圖論第7講,18,冪指數(shù)的化簡,方法: 利用定理16, 定理18. 例6: 設(shè) RAA, 化簡R100的指數(shù). 已知 (1) R7 = R15; (2) R3 = R5; (3) R1 = R3. 解: (1) R100=R7+118+5=R7+5=R12R0,R1,,R14;

11、 (2) R100=R3+482+1=R3+1=R4R0,R1,,R4; (3) R100=R1+492+1=R1+1=R2R0,R1,R2. #,2020/8/20,集合論與圖論第7講,19,關(guān)系的閉包,自反閉包r( R ) 對稱閉包s( R ) 傳遞閉包t( R ) 閉包的性質(zhì), 求法, 相互關(guān)系,2020/8/20,集合論與圖論第7講,20,什么是閉包,閉包(closure): 包含一些給定對象, 具有指定性質(zhì)的最小集合 “最小”: 任何包含同樣對象, 具有同樣性質(zhì)的集合, 都包含這個(gè)閉包集合 例: (平面上點(diǎn)的凸包),,,,,,,,,,,,,,,,2020/8/20,集合論與圖論第7講

12、,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/8/20,集合論與圖論第7講,22,對稱閉包(symmetric closure),對稱閉包: 包含給定關(guān)系R的最小對稱關(guān)系, 稱為R的對稱閉包, 記作s( R ). (1) R s( R ); (2) s( R )是對稱的; (3) S(

13、(RS S對稱) s( R )S ).,,,,,,,,,G( R ),,,,,,,,,G(s( R )),,,,,2020/8/20,集合論與圖論第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/8/20,集合論與圖論第7講,24,定理19,定理19: 設(shè)RAA且A,則 (1) R自反 r( R ) =

14、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) 完全類似. #,2020/8/20,集合論與圖論第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/8/20,集合論與圖論第7

15、講,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 ),2020/8/20,集合論與圖論第7講,27,定理21(證明(2)),(2) s( R1R2) = s( R1 )s( R2 ); 證明(2

16、): 利用定理20, s(R1R2)s(R1)s(R2). s(R1)s(R2)對稱且包含R1R2,所以 s(R1R2)s(R1)s(R2). s( R1R2) = s( R1 )s( R2 ),2020/8/20,集合論與圖論第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)),202

17、0/8/20,集合論與圖論第7講,29,如何求閉包?,問題: (1) r( R ) = R (2) s( R ) = R (3) t( R ) = R ,?,?,?,2020/8/20,集合論與圖論第7講,30,定理2224,定理2224: 設(shè) RAA 且 A, 則 (1) r( R ) = RIA; (2) s( R ) = RR-1; (3) t( R ) = RR2R3. 對比: R自反 IAR R對稱 R=R-1 R傳遞 R2R,2020/8/20,集合論與圖論第7講,31,定理22,定理22: 設(shè) RAA 且 A, 則 r( R ) = RIA; 證

18、明: (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/8/20,集合論與圖論第7講,32,定理23,定理23: 設(shè) RAA 且 A, 則 s( R ) = RR-1; 證明: (1) R RR-1; (2) (RR-1)-1=RR-1 RR-1對稱 s( R )RR-1; (3) Rs( R ) s( R )對稱 Rs( R ) R-1s( R ) RR-1s( R ) s( R ) = RR-1.,2020/8/20,集

19、合論與圖論第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 )傳遞 Rt( R )R2t( R )R3t( R ) RR2R3 t( R ) t( R ) = RR2R3.,2020/8/20,集合論與圖論第7講,34,定理24的推論,推論: 設(shè) RAA 且 0<|A|<, 則l N, 使得 t( R ) = RR2R3Rl ; 證明: 由定理16知 s,tN, 使得 Rs = Rt.

20、由定理18知 R,R2,R3, R0,R1,,Rt-1 . 取l =t-1, 由定理24知 t( R ) = RR2R3. = RR2R3Rl t( R ) = RR2R3Rl . #,2020/8/20,集合論與圖論第7講,35,例8,例8: 設(shè) A = a,b,c,d , R = ,,, . 求 r( R ), s( R ), t( R ). 解:,,,,,a,b,c,d,,,,,2020/8/20,集合論與圖論第7講,36,例8(續(xù)),解(續(xù)):,,,,,a,b,c,d,,,,,,,,,a,b,c,d,,,,,,,,,a,b,c,d,,,,,,,,,,,,,,,202

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

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

23、)對稱. 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 )對稱.,2020/8/20,集合論與圖論第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/8/20,集合論與圖論第7講,44,定理25(反例),反例: R傳遞, 但是s( R )非

24、傳遞.,,,,G( R ),,,,G(s( R )),,小結(jié): 閉包運(yùn)算保持下列關(guān)系性質(zhì).,2020/8/20,集合論與圖論第7講,45,閉包運(yùn)算是否可以交換順序?,問題: (1) rs( R ) = sr( R ) ? (2) rt( R ) = tr( R ) ? (3) st( R ) = ts( R ) ? 說明: rs( R ) = r(s( R )),2020/8/20,集合論與圖論第7講,46,定理26,定理26: 設(shè) RAA 且 A, 則 (1) rs( R ) = sr( R ); (2) rt( R ) = tr( R ); (3) st( R ) ts( R );,r(

25、),s( ),t( ),,,可交換,可交換,,,2020/8/20,集合論與圖論第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 ).,2020/8/20,集合論與圖論第7講,48,定理26(證明(2)),(2) rt( R ) = tr( R ); 證明:(2) rt( R ) = r(

26、t( R )) = r(RR2 R3 ) = IA(RR2 R3 ) = (IAR)(IARR2)(IARR2R3) = (IAR)(IAR)2 (IAR)3 = r( R )r( R )2 r( R )3 =t(r( R )). rt( R ) = tr( R ).,2020/8/20,集合論與圖論第7講,49,定理26(證明(3)),(3) st( R ) ts( R ); 證明:(3) st( R ) st(s( R )) = sts( R ) = s(ts( R )) = ts( R ) ( ts( R )對稱, 定理25(2) ) st( R ) ts( R ). #,2020/8/20,集合論與圖論第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 ))),,,,,,2020/8/20,集合論與圖論第7講,51,總結(jié),關(guān)系冪運(yùn)算 關(guān)系閉包,2020/8/20,集合論與圖論第7講,52,作業(yè)(#5),p83, 習(xí)題二, 27, 28, 29 今天交作業(yè)#1,#2,#3,#4,