北大离散数学07
发布时间：2021-06-08
北大离散数学课件
第7讲 关系幂运算与关系闭包 北京大学内容提要 关系幂(power)运算 关系闭包(closure)
2013-8-14
《集合论与图论》第7讲
北大离散数学课件
关系的幂运算
n次幂的定义 指数律 幂指数的化简
2013-8-14
《集合论与图论》第7讲
北大离散数学课件
关系的n次幂 关系的n次幂(nth
power): 设R A A,
n N, 则 (1) R0 = IA; (2) Rn+1 = Rn○R, (n 1).
R R R R n n个R
Rn表示的关系,12013-8-14
是R的关系图中长度为n 的有向路径的起点与终点的关系.2 n-1《集合论与图论》第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
2013-8-14
《集合论与图论》第7讲
北大离散数学课件
关系幂运算(举例,续) 解(续):
R0 = I A , R1 = R0○R = R = {<a,b>,<b,a>,<a,c>}, R2 = R1○R = {<a,a>,<b,b>,<b,c>},b b
a
c
a
c
G( R )2013-8-14 《集合论与图论》第7讲
G( R2 )5
北大离散数学课件
关系幂运算(举例,续2) 解(续):
R0 = I A , 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,b b
a
c
a
c
G( R )2013-8-14
G( R3 )《集合论与图论》第7讲 6
北大离散数学课件
关系幂运算(举例,续3) 解(续):
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,…,. #b b b
a G( R )2013-8-14
c
a
c
a
c
G( R4 )《集合论与图论》第7讲
G( R5 )7
北大离散数学课件
关系幂运算是否有指数律?指数律: (1) Rm○Rn = 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, 例如R2○R-5=R-3,因为可以定义 R-n = (R-1)n = (Rn)-1 ? 2013-8-14 《集合论与图论》第7讲 8
北大离散数学课件
定理17 定理17:
设 R A A, m,n N, 则 (1) Rm○Rn = Rm+n ; (2) (Rm)n = Rmn. 说明: 可让 m,n Z, 只需IA domR ranR (此时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)22013-8-14 《集合论与图论》第7讲 9
北大离散数学课件
定理17(证明(1))Rm○Rn = Rm+n ; 证明: (1) 给定m, 对n归纳. n=0时, Rm○Rn = Rm○R0 = Rm○IA = Rm = Rm+0. 假设 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归纳. # (1)2013-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
R142013-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) Rk 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:2013-8-14 《集合论与图论》第7讲 12
北大离散数学课件
鸽巢原理(pigeonhole principle) 鸽巢原理(pigeonhole
principle): 若把n+1 只鸽子装进n只鸽巢, 则至少有一只鸽巢 装2只以上的鸽子. 又名抽屉原则(Dirichlet drawer principle), (Peter Gustav Lejeune Dirichlet,1805~1859) 推广形式: 若把m件物品装进k只抽屉, 则 m 至少有一只抽屉装 k 只以上的物品. 1.8 =2, 1.8 =1, -1.8 =-1, -1.8 =-2.2013-8-14 《集合论与图论》第7讲 13
北大离散数学课件
定理18 定理18:
设 R A A, 若 s,t N (s<t),使得 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.
2013-8-14
《集合论与图论》第7讲
北大离散数学课件
定理18(说明)s
泵(pumping):Rs+kp+i = Rs+ip
i
2013-8-14
《集合论与图论》第7讲
北大离散数学课件
定理18 (证明(1)(3))Rs+k = Rt+k ; (3) 令S={R0,R1,…,Rt-1}, 则 q N, Rq S. 证明: (1) Rs+k = Rs○Rk = Rt○Rk = Rt+k; (3) 若 q>t-1 s, 则令 q=s+kp+i, 其中 k,i N, p=t-s, s+i<t; 于是 Rq = Rs+kp+i = Rs+i S. (1)
2013-8-14
《集合论与图论》第7讲
北大离散数学课件
定理18(证明(2))Rs+kp+i = Rs+i, 其中k,i 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)2013-8-14 《集合论与图论》第7讲 17
北大离散数学课件
幂指数的化简 方法:
利用定理16, 定理18. 例6: 设 R A A, 化简R100的指数. 已知 (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}. #2013-8-14 《集合论与图论》第7讲 18
北大离散数学课件
关系的闭包 自反闭包r(
R) 对称闭包s( R ) 传递闭包t( R ) 闭包的性质, 求法, 相互关系
2013-8-14
《集合论与图论》第7讲
北大离散数学课件
什么是闭包 闭包(closure):
包含一些给定对象, 具有 指定性质的最小集合 “最小”: 任何包含同样对象, 具有同样 性质的集合, 都包含这个闭包集合 例: (平面上点的凸包)
2013-8-14
《集合论与图论》第7讲
北大离散数学课件
自反闭包(reflexive closure) 自反闭包:
包含给定关系R的最小自反关 系, 称为R的自反闭包, 记作r( R ). (1) R r( R ); (2) r( R )是自反的; (3) S( (R S S自反) r( R ) S ).
G( R )2013-8-14
G(r( R ))《集合论与图论》第7讲 21
北大离散数学07.doc
将本文的Word文档下载到电脑
上一篇：计算机工程与设计
下一篇：东海学校期末考试教学质量奖励办法
