北大离散数学07

1、北大离散数学07 北大离散数学课件 第7讲 关系幂运算与关系闭包 北京高校内容提要 关系幂(power)运算 关系闭包(closure) 2021-8-14 集合论与图论第7讲 北大离散数学课件 关系的幂运算 n次幂的定义 指数律 幂指数的化简 2021-8-14 集合论与图论第7讲 北大离散数学课件 关系的n次幂 关系的n次幂(nth power): 设r a a, n n, 则 (1) r0 = ia; (2) rn+1 = rnr, (n 1). r r r r n n个r rn表示的关系,12021-8-14 是r的关系图中长度为n 的有向路径的起点与终点的关系.2 n-1集合论与图论

2、第7讲 n3 北大离散数学课件 关系幂运算(举例) 例: 设a=a,b,c, r a a, r=a,b,b,a,a,c, 求r的各次幂. b 解: bc g( r ) a g( r0 ) c a 2021-8-14 集合论与图论第7讲 北大离散数学课件 关系幂运算(举例,续) 解(续): r0 = i a , r1 = r0r = r = a,b,b,a,a,c, r2 = r1r = a,a,b,b,b,c,b b a c a c g( r )2021-8-14 集合论与图论第7讲 g( r2 )5 北大离散数学课件 关系幂运算(举例,续2) 解(续): r0 = i a , r1 = r0

3、r = r = a,b,b,a,a,c, r2 = r1r = a,a,b,b,b,c, r3 = r2r = a,b,a,b,a,c = r1,b b a c a c g( r )2021-8-14 g( r3 )集合论与图论第7讲 6 北大离散数学课件 关系幂运算(举例,续3) 解(续): r4 = r3r = r1r = r2, r5 = r4r = r2r = r3 = r1, 一般地, r2k+1=r1=r, k=0,1,2, r2k=r2, k=1,2,. #b b b a g( r )2021-8-14 c a c a c g( r4 )集合论与图论第7讲 g( r5 )7 北大

4、离散数学课件 关系幂运算是否有指数律?指数律: (1) rmrn = rm+n ; (2) (rm)n = rmn. 说明: 对实数r来说, m,n n,z,q,r. 对一般关系r来说, m,n n. 对满意ia r且a domr ranr的关系r来说, m,n n,z, 例如r2r-5=r-3,由于可以定义 r-n = (r-1)n = (rn)-1 ? 2021-8-14 集合论与图论第7讲 8 北大离散数学课件 定理17 定理17: 设 r a a, m,n n, 则 (1) rmrn = rm+n ; (2) (rm)n = rmn. 说明: 可让 m,n z, 只需ia domr r

5、anr (此时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)22021-8-14 集合论与图论第7讲 9 北大离散数学课件 定理17(证明(1)rmrn = 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归纳. # (1

6、)2021-8-14 集合论与图论第7讲 10 北大离散数学课件 0,r1,r2,r3,是否互不相等? rr0r0 r1r1 r2r2 r3r3 r4r4 r5 r6 r7 r8 r5=r19=r33=r47= r6=r20=r34=r48= r7=r21=r35=r49= r8=r22=r36 = r9 r17 r16r15 r142021-8-14 集合论与图论第7讲 r10 r1111 北大离散数学课件 定理16设 |a|=n, r a a, 则 s,t n, 并 n2 且 0 s t 2 , 使得 rs = rt. 证明: p(a a)对幂运算是封闭的, 即 r, r p(a a) r

7、k p(a a), (k n). n2 n2 |p(a a)| = 2 , 在r0,r1,r2, r 2 这 n2 个集合中, 必有两个是相 同的. 2 1 n2 所以 s,t n, 并且 0 s t 2 , 使得 rs = rt. # 定理16:2021-8-14 集合论与图论第7讲 12 北大离散数学课件 鸽巢原理(pigeonhole principle) 鸽巢原理(pigeonhole principle): 若把n+1 只鸽子装进n只鸽巢, 则至少有一只鸽巢 装2只以上的鸽子. 又名抽屉原则(dirichlet drawer principle), (peter gustav lej

8、eune dirichlet,18051859) 推广形式: 若把m件物品装进k只抽屉, 则 m 至少有一只抽屉装 k 只以上的物品. 1.8 =2, 1.8 =1, -1.8 =-1, -1.8 =-2.2021-8-14 集合论与图论第7讲 13 北大离散数学课件 定理18 定理18: 设 r a a, 若 s,t n (st),使得 rs = rt, 则 (1) rs+k = rt+k ; (2) rs+kp+i = rs+i, 其中k,i n, p=t-s; (3) 令s=r0,r1,rt-1, 则 q n, rq s. 2021-8-14 集合论与图论第7讲 北大离散数学课件 定理1

9、8(说明)s 泵(pumping):rs+kp+i = rs+ip i 2021-8-14 集合论与图论第7讲 北大离散数学课件 定理18 (证明(1)(3)rs+k = rt+k ; (3) 令s=r0,r1,rt-1, 则 q n, rq s. 证明: (1) rs+k = rsrk = rtrk = rt+k; (3) 若 qt-1 s, 则令 q=s+kp+i, 其中 k,i n, p=t-s, s+it; 于是 rq = rs+kp+i = rs+i s. (1) 2021-8-14 集合论与图论第7讲 北大离散数学课件 定理18(证明(2)rs+kp+i = rs+i, 其中k,i

10、 n, p=t-s; 证明: (2) k=0时,明显; k=1时,即(1); 设 k 2. 则 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 . # (2)2021-8-14 集合论与图论第7讲 17 北大离散数学课件 幂指数的化简 方法: 利用定理16, 定理18. 例6: 设 r a a, 化简r100的指数. 已知 (1) r7 = r15; (2) r3 = r5; (3) r1 = r3. 解: (1) r100=

11、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. #2021-8-14 集合论与图论第7讲 18 北大离散数学课件 关系的闭包 自反闭包r( r) 对称闭包s( r ) 传递闭包t( r ) 闭包的性质, 求法, 相互关系 2021-8-14 集合论与图论第7讲 北大离散数学课件 什么是闭包 闭包(closure): 包含一些给定对象, 具有 指定性质的最小集合 “最小”: 任何包含同样对象, 具有同样 性质的集合, 都包含这个闭包集合 例: (平面上点的凸包) 2021-8-14 集合论与图论第7讲 北大离散