北大离散数学07.ppt

《北大离散数学07.ppt》由会员分享，可在线阅读，更多相关《北大离散数学07.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020/10/24,集合论与图论第7讲,1,第7讲 关系幂运算与关系闭包北京大学,内容提要 关系幂(power)运算 关系闭包(closure),2020/10/24,集合论与图论第7讲,2,关系的幂运算,n次幂的定义 指数律 幂指数的化简,2020/10/24,集合论与图论第7讲,3,关系的n次幂,关系的n次幂(nth power): 设RAA, nN, 则 (1) R0 = IA; (2) Rn+1 = RnR, (n1). Rn表示的关系, 是R的关系图中长度为n的有向路径的起点与终点的关系.,1,2,n,n-1,2020/10/24,集合论与图论第7讲,4,关系幂运算(举例),例:

2、设A=a,b,c, RAA, R=, 求R的各次幂. 解:,b,a,c,b,a,c,G( R ),G( R0 ),2020/10/24,集合论与图论第7讲,5,关系幂运算(举例,续),解(续): R0 = IA, R1 = R0R = R = , R2 = R1R = ,b,a,c,b,a,c,G( R ),G( R2 ),2020/10/24,集合论与图论第7讲,6,关系幂运算(举例,续2),解(续): R0 = IA, R1 = R0R = R = , R2 = R1R = , R3 = R2R = , = R1,b,a,c,b,a,c,G( R ),G( R3 ),2020/10/24,

3、集合论与图论第7讲,7,关系幂运算(举例,续3),解(续): 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/10/24,集合论与图论第7讲,8,关系幂运算是否有指数律?,指数律: (1) RmRn = Rm+n ; (2) (Rm)n = Rmn. 说明: 对实数R来说, m,nN,Z,Q,R. 对一般关系R来说, m,nN. 对满足IAR且AdomRranR的关系R来

4、说, m,nN,Z, 例如R2R-5=R-3,因为可以定义 R-n = (R-1)n = (Rn)-1 ?,2020/10/24,集合论与图论第7讲,9,定理17,定理17: 设 RAA, m,nN, 则 (1) RmRn = Rm+n ; (2) (Rm)n = Rmn. 说明: 可让 m,nZ, 只需IAdomRranR (此时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/10/24,集合论与图论第7讲,10,定理17(证明(1),(1) RmRn =

5、Rm+n ; 证明: (1) 给定m, 对n归纳. n=0时, RmRn = RmR0 = RmIA = Rm = Rm+0. 假设 RmRn = Rm+n, 则 RmRn+1 = Rm(Rn R1) = (RmRn)R1 = Rm+nR = R(m+n)+1 = Rm+(n+1). (2) 同样对n归纳. #,2020/10/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=R3

6、6 =,R15,R9,R10,R11,R14,R16,R17,2020/10/24,集合论与图论第7讲,12,定理16,定理16: 设 |A|=n, RAA, 则 s,tN, 并且 , 使得 Rs = Rt. 证明: P(AA)对幂运算是封闭的, 即 R, RP(AA) RkP(AA), (kN). |P(AA)| = , 在R0,R1,R2, 这 个集合中, 必有两个是相同的. 所以 s,tN, 并且 , 使得 Rs = Rt. #,2020/10/24,集合论与图论第7讲,13,鸽巢原理(pigeonhole principle),鸽巢原理(pigeonhole principle): 若

7、把n+1只鸽子装进n只鸽巢, 则至少有一只鸽巢装2只以上的鸽子. 又名抽屉原则(Dirichlet drawer principle), (Peter Gustav Lejeune Dirichlet,18051859) 推广形式: 若把m件物品装进k只抽屉, 则至少有一只抽屉装 只以上的物品. 1.8=2, 1.8=1, -1.8=-1, -1.8=-2.,2020/10/24,集合论与图论第7讲,14,定理18,定理18: 设 RAA, 若 s,tN (st),使得Rs = Rt, 则 (1) Rs+k = Rt+k ; (2) Rs+kp+i = Rs+i, 其中k,iN, p=t-s;

8、 (3) 令S=R0,R1,Rt-1, 则qN, RqS.,2020/10/24,集合论与图论第7讲,15,定理18(说明),s,p,i,泵(pumping): Rs+kp+i = Rs+i,2020/10/24,集合论与图论第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/10/24

9、,集合论与图论第7讲,17,定理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 . #,2020/10/24,集合论与图论第7讲,18,幂指数的化简,方法: 利用定理16, 定理18. 例6: 设 RAA, 化简R100的指数. 已知 (1) R7 = R15; (2)

10、 R3 = R5; (3) R1 = R3. 解: (1) R100=R7+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/10/24,集合论与图论第7讲,19,关系的闭包,自反闭包r( R ) 对称闭包s( R ) 传递闭包t( R ) 闭包的性质, 求法, 相互关系,2020/10/24,集合论与图论第7讲,20,什么是闭包,闭包(closure): 包含一些给定对象, 具有指定性质的最小集合 “最小”: 任何包含同样对象, 具有同样性

11、质的集合, 都包含这个闭包集合 例: (平面上点的凸包),2020/10/24,集合论与图论第7讲,21,自反闭包(reflexive closure),自反闭包: 包含给定关系R的最小自反关系, 称为R的自反闭包, 记作r( R ). (1) R r( R ); (2) r( R )是自反的; (3) S( (RS S自反) r( R )S ).,G( R ),G(r( R ),2020/10/24,集合论与图论第7讲,22,对称闭包(symmetric closure),对称闭包: 包含给定关系R的最小对称关系, 称为R的对称闭包, 记作s( R ). (1) R s( R ); (2)

12、s( R )是对称的; (3) S( (RS S对称) s( R )S ).,G( R ),G(s( R ),2020/10/24,集合论与图论第7讲,23,传递闭包(transitive closure),传递闭包: 包含给定关系R的最小传递关系, 称为R的传递闭包, 记作t( R ). (1) R t( R ); (2) t( R )是传递的; (3) S( (RS S传递) t( R )S ).,G( R ),G(t( R ),2020/10/24,集合论与图论第7讲,24,定理19,定理19: 设RAA且A,则 (1) R自反 r( R ) = R; (2) R对称 s( R ) =

13、R; (3) R传递 t( R ) = R; 证明: (1) RR R自反 r( R )R 又 R r( R ), r( R ) = R. (2)(3) 完全类似. #,2020/10/24,集合论与图论第7讲,25,定理20,定理20: 设 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/10/24,集合论与图论第7讲,26,定理21,定理21: 设 R1,R2AA 且

14、 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/10/24,集合论与图论第7讲,27,定理21(证明(2),(2) s( R1R2) = s( R1 )s( R2 ); 证明(2): 利用定理20, s(R1R2)s(R1)s(R2). s(R

15、1)s(R2)对称且包含R1R2,所以 s(R1R2)s(R1)s(R2). s( R1R2) = s( R1 )s( R2 ),2020/10/24,集合论与图论第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/10/24,集合论与图论第7讲,29,如何求闭包?,问题: (1) r( R ) = R (2) s( R

16、) = R (3) t( R ) = R ,?,?,?,2020/10/24,集合论与图论第7讲,30,定理2224,定理2224: 设 RAA 且 A, 则 (1) r( R ) = RIA; (2) s( R ) = RR-1; (3) t( R ) = RR2R3. 对比: R自反 IAR R对称 R=R-1 R传递 R2R,2020/10/24,集合论与图论第7讲,31,定理22,定理22: 设 RAA 且 A, 则 r( R ) = RIA; 证明: (1) R RIA; (2) IARIA RIA自反 r( R )RIA; (3) Rr( R ) r( R )自反 Rr( R )

17、IA r( R ) RIA r( R ) r( R ) = RIA.,2020/10/24,集合论与图论第7讲,32,定理23,定理23: 设 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/10/24,集合论与图论第7讲,33,定理24,定理24: 设 RAA 且 A, 则 t( R ) = RR2R3; 证明: (1) R RR2R3; (2)

18、 (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/10/24,集合论与图论第7讲,34,定理24的推论,推论: 设 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

19、 ) = RR2R3Rl . #,2020/10/24,集合论与图论第7讲,35,例8,例8: 设 A = a,b,c,d , R = , . 求 r( R ), s( R ), t( R ). 解:,a,b,c,d,2020/10/24,集合论与图论第7讲,36,例8(续),解(续):,a,b,c,d,a,b,c,d,a,b,c,d,2020/10/24,集合论与图论第7讲,37,例8(续2),解(续2):,a,b,c,d,2020/10/24,集合论与图论第7讲,38,例8(续3),解(续3):,a,b,c,d,2020/10/24,集合论与图论第7讲,39,例8(续4),解(续4):,a

20、,b,c,d,a,b,c,d,#,2020/10/24,集合论与图论第7讲,40,闭包运算是否保持关系性质?,问题: (1) R自反 s( R ), t( R )自反 ? (2) R对称 r( R ), t( R )对称 ? (3) R传递 s( R ), r( R )传递 ?,2020/10/24,集合论与图论第7讲,41,定理25,定理25: 设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(

21、 R ) t( R )自反.,2020/10/24,集合论与图论第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 )对称. 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/10/24,集合论与图论第7讲,43,定理25(证明(3),(2) R传递 r( R )传递; 证明: (2

22、) r( R )r( R ) = (IAR)(IAR) = (IAIA)(IAR)(RIA)(RR) IARRR =IAR= r( R ) r( R )传递. #,2020/10/24,集合论与图论第7讲,44,定理25(反例),反例: R传递, 但是s( R )非传递.,G( R ),G(s( R ),小结: 闭包运算保持下列关系性质.,2020/10/24,集合论与图论第7讲,45,闭包运算是否可以交换顺序?,问题: (1) rs( R ) = sr( R ) ? (2) rt( R ) = tr( R ) ? (3) st( R ) = ts( R ) ? 说明: rs( R ) = r

23、(s( R ),2020/10/24,集合论与图论第7讲,46,定理26,定理26: 设 RAA 且 A, 则 (1) rs( R ) = sr( R ); (2) rt( R ) = tr( R ); (3) st( R ) ts( R );,r( ),s( ),t( ),可交换,可交换,2020/10/24,集合论与图论第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

24、 = s(r( R ) = sr( R ). rs( R ) = sr( R ).,2020/10/24,集合论与图论第7讲,48,定理26(证明(2),(2) rt( R ) = tr( R ); 证明:(2) rt( R ) = r(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/10/24,集合论与图论第7讲,49,定理26(证明(3),(3) st( R ) t

25、s( R ); 证明:(3) st( R ) st(s( R ) = sts( R ) = s(ts( R ) = ts( R ) ( ts( R )对称, 定理25(2) ) st( R ) ts( R ). #,2020/10/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 ),2020/10/24,集合论与图论第7讲,51,总结,关系幂运算 关系闭包,2020/10/24,集合论与图论第7讲,52,作业(#5),p83, 习题二, 27, 28, 29 今天交作业#1,#2,#3,#4,