北大离散数学07

北大离散数学课件

第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

本文来源：https://www.bwwdw.com/article/1v2j.html