《集合论与图论》第 7讲 1 第 7讲 关系幂运算与关系闭包 内容提要 ?关系幂 (power)运算 ?关系闭包 (closure) 《集合论与图论》第 7讲 2 关系的幂运算 ? n次幂 的定义 ? 指数律 ? 幂指数的 化简 《集合论与图论》第 7讲 3 关系的 n次幂 ?关系的 n次幂 (nth power): 设 R?A×A, n∈N, 则 (1) R 0 = I A ; (2) R n+1 = R n ○R, (n≥1). ? ?R n 表示的关系 , 是 R的关系图中 长度为 n 的有向路径的 起点 与 终点 的关系 . 43421 oLoo Rn n RRRR 个 = 12 nn-1 《集合论与图论》第 7讲 4 关系幂运算 (举例 ) ?例 : 设 A={a,b,c}, R?A×A, R={<a,b>,<b,a>,<a,c>}, 求 R的各次幂 . ?解 : b a c b a c G( R ) G( R 0 ) 《集合论与图论》第 7讲 5 关系幂运算 (举例 ,续 ) ?解 (续 ): R 0 = I A , R 1 = R 0 ○R = R = {<a,b>,<b,a>,<a,c>}, R 2 = R 1 ○R = {<a,a>,<b,b>,<b,c>}, b a c b a c G( R ) G( R 2 ) 《集合论与图论》第 7讲 6 关系幂运算 (举例 ,续 2) ?解 (续 ): R 0 = I A , R 1 = R 0 ○R = R = {<a,b>,<b,a>,<a,c>}, R 2 = R 1 ○R = {<a,a>,<b,b>,<b,c>}, R 3 = R 2 ○R = {<a,b>,<a,b>,<a,c>} = R 1 , b a c b a c G( R ) G( R 3 ) 《集合论与图论》第 7讲 7 关系幂运算 (举例 ,续 3) ?解 (续 ): R 4 = R 3 ○R = R 1 ○R = R 2 , R 5 = R 4 ○R = R 2 ○R = R 3 = R 1 , 一般地 , R 2k+1 =R 1 =R, k=0,1,2,…, R 2k =R 2 , k=1,2,…,. # b ac b ac G( R ) G( R 5 ) b ac G( R 4 ) 《集合论与图论》第 7讲 8 关系幂运算是否有指数律 ? ? 指数律 : (1) R m ○R n = R m+n ; (2) (R m ) n = R mn . ? 说明 : 对实数 R来说 , m,n∈N,Z,Q,R. 对一般关系 R来说 , m,n∈N. 对满足 I A ?R且 A?domR∩ranR的关系 R来说 , m,n∈N,Z, 例如 R 2 ○R -5 =R -3 ,因为可以定义 R -n = (R -1 ) n = (R n ) -1 ? 《集合论与图论》第 7讲 9 定理 17 ?定理 17: 设 R?A×A, m,n∈N, 则 (1) R m ○R n = R m+n ; (2) (R m ) n = R mn . ?说明 : 可让 m,n∈Z, 只需 I A ?domR∩ranR (此时 I A =R○R -1 =R -1 ○R)并且定义 R -n = (R -1 ) n = (R n ) -1 . ?回忆 : (F○G) -1 =G -1 ○F -1 (R 2 ) -1 =(R○R) -1 =R -1 ○R -1 =(R -1 ) 2 《集合论与图论》第 7讲 10 定理 17(证明 (1)) ?(1) R m ○R n = R m+n ; ?证明 : (1) 给定 m, 对 n归纳 . n=0时 , R m ○R n = R m ○R 0 = R m ○I A = R m = R m+0 . 假设 R m ○R n = R m+n , 则 R m ○R n+1 = R m ○(R n ○R 1 ) = (R m ○R n )○R 1 = R m+n ○R = R (m+n)+1 = R m+(n+1) . ?(2) 同样对 n归纳 . # 《集合论与图论》第 7讲 11 R 0 ,R 1 ,R 2 ,R 3 ,…是否互不相等 ? R 0 R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 0 R 1 R 2 R 3 R 4 R 5 =R 19 =R 33 =R 47 =… R 6 =R 20 =R 34 =R 48 =… R 7 =R 21 =R 35 =R 49 =… R 8 =R 22 =R 36 =… R 15 R 9 R 10 R 11 R 14 R 16 R 17 《集合论与图论》第 7讲 12 定理 16 ?定理 16: 设 |A|=n, R?A×A, 则 ?s,t∈N, 并 且 , 使得 R s = R t . ?证明 : P(A×A)对幂运算是封闭的 , 即 ?R, R∈P(A×A) ? R k ∈P(A×A), (k∈N). |P(A×A)| = , 在 R 0 ,R 1 ,R 2 ,…, 这 个集合中 , 必有两个是相同的 . 所以 ?s,t∈N, 并且 , 使得 R s = R t . # 2 n 2ts0 ≤<≤ 2 n 2 2 n 2 R 12 2 n + 2 n 2ts0 ≤<≤ 《集合论与图论》第 7讲 13 鸽巢原理 (pigeonhole principle) ?鸽巢原理 (pigeonhole principle): 若把 n+1 只鸽子装进 n只鸽巢 , 则至少有一只鸽巢 装 2只以上的鸽子 . ?又名 抽屉原则 (Dirichlet drawer principle), (Peter Gustav Lejeune Dirichlet,1805~1859) ?推广形式 : 若把 m件物品装进 k只抽屉 , 则 至少有一只抽屉装 只以上的物品 . ? ?1.8?=2, ?1.8?=1, ?-1.8?=-1, ?-1.8?=-2. ? ? ? ? ? ? k m 《集合论与图论》第 7讲 14 定理 18 ?定理 18: 设 R?A×A, 若 ?s,t∈N (s<t),使得 R s = R t , 则 (1) R s+k = R t+k ; (2) R s+kp+i = R s+i , 其中 k,i∈N, p=t-s; (3) 令 S={R 0 ,R 1 ,…,R t-1 }, 则 ?q∈N, R q ∈S. 《集合论与图论》第 7讲 15 定理 18(说明 ) s p i 泵 (pumping): R s+kp+i = R s+i 《集合论与图论》第 7讲 16 定理 18 (证明 (1)(3)) ?(1) R s+k = R t+k ; (3) 令 S={R 0 ,R 1 ,…,R t-1 }, 则 ?q∈N, R q ∈S. ?证明 : (1) R s+k = R s ○R k = R t ○R k = R t+k ; (3) 若 q>t-1≥s, 则令 q=s+kp+i, 其中 k,i∈N, p=t-s, s+i<t; 于是 R q = R s+kp+i = R s+i ∈S. 《集合论与图论》第 7讲 17 定理 18(证明 (2)) ?(2) R s+kp+i = R s+i , 其中 k,i∈N, p=t-s; ?证明 : (2) k=0时 ,显然 ; k=1时 ,即 (1); 设 k≥2. 则 R s+kp+i = R s+k(t-s)+i = R s+t-s+(k-1)(t-s)+i = R t+(k-1)(t-s)+i = R s+(k-1)(t-s)+i = … = R s+(t-s)+i = R t+i = R s+i . # 《集合论与图论》第 7讲 18 幂指数的化简 ?方法 : 利用定理 16, 定理 18. ?例 6: 设 R?A×A, 化简 R 100 的指数 . 已知 (1) R 7 = R 15 ; (2) R 3 = R 5 ; (3) R 1 = R 3 . ?解 : (1) R 100 =R 7+11×8+5 =R 7+5 =R 12 ∈{R 0 ,R 1 ,…,R 14 }; (2) R 100 =R 3+48×2+1 =R 3+1 =R 4 ∈{R 0 ,R 1 ,…,R 4 }; (3) R 100 =R 1+49×2+1 =R 1+1 =R 2 ∈{R 0 ,R 1 ,R 2 }. # 《集合论与图论》第 7讲 19 关系的闭包 ?自反闭包 r( R ) ?对称闭包 s( R ) ?传递闭包 t( R ) ?闭包的 性质 , 求法 , 相互关系 《集合论与图论》第 7讲 20 什么是闭包 ?闭包 (closure): 包含一些给定对象 , 具有 指定性质的最小集合 ?“最小 ”: 任何包含同样对象 , 具有同样性 质的集合 , 都包含这个闭包集合 ?例 : (平面上 点 的 凸包 ) 《集合论与图论》第 7讲 21 自反闭包 (reflexive closure) ?自反闭包 : 包含给定关系 R的最小自反关 系 , 称为 R的自反闭包 , 记作 r( R ). (1) R ? r( R ); (2) r( R )是自反的 ; (3) ?S( (R?S ∧ S自反 ) → r( R )?S ). G( R ) G(r( R )) 《集合论与图论》第 7讲 22 对称闭包 (symmetric closure) ?对称闭包 : 包含给定关系 R的最小 对称 关 系 , 称为 R的 对称 闭包 , 记作 s( R ). (1) R ? s( R ); (2) s( R )是对称的 ; (3) ?S( (R?S ∧ S对称 ) → s( R )?S ). G( R ) G(s( R )) 《集合论与图论》第 7讲 23 传递闭包 (transitive closure) ?传递闭包 : 包含给定关系 R的最小 传递 关 系 , 称为 R的 传递 闭包 , 记作 t( R ). (1) R ? t( R ); (2) t( R )是 传递 的 ; (3) ?S( (R?S ∧ S传递 ) → t( R )?S ). G( R ) G(t( R )) 《集合论与图论》第 7讲 24 定理 19 ?定理 19: 设 R?A×A且 A≠?,则 (1) R自反 ? r( R ) = R; (2) R对称 ? s( R ) = R; (3) R传递 ? t( R ) = R; 证明 : (1) R?R ∧ R自反 ? r( R )?R 又 R ? r( R ), ∴ r( R ) = R. (2)(3) 完全类似 . # 《集合论与图论》第 7讲 25 定理 20 ?定理 20: 设 R 1 ?R 2 ?A×A 且 A≠?, 则 (1) r( R 1 ) ? r( R 2 ); (2) s( R 1 ) ? s( R 2 ); (3) t( R 1 ) ? t( R 2 ); 证明 : (1) R 1 ?R 2 ? r( R 2 )自反 , ∴ r( R 1 ) ? r( R 2 ) (2)(3) 类似可证 . # 《集合论与图论》第 7讲 26 定理 21 ? 定理 21: 设 R 1 ,R 2 ?A×A 且 A≠?, 则 (1) r(R 1 ∪R 2 ) = r( R 1 )∪r( R 2 ); (2) s(R 1 ∪R 2 ) = s( R 1 )∪s( R 2 ); (3) t(R 1 ∪R 2 ) ? t( R 1 )∪t( R 2 ). 证明 : (1) 利用定理 20, r(R 1 ∪R 2 )?r(R 1 )∪r(R 2 ). r(R 1 )∪r(R 2 )自反且包含 R 1 ∪R 2 ,所以 r(R 1 ∪R 2 )?r(R 1 )∪r(R 2 ). ∴ r( R 1 ∪R 2 ) = r( R 1 )∪r( R 2 ) 《集合论与图论》第 7讲 27 定理 21(证明 (2)) ?(2) s( R 1 ∪R 2 ) = s( R 1 )∪s( R 2 ); ?证明 (2): 利用定理 20, s(R 1 ∪R 2 )?s(R 1 )∪s(R 2 ). s(R 1 )∪s(R 2 )对称且包含 R 1 ∪R 2 ,所以 s(R 1 ∪R 2 )?s(R 1 )∪s(R 2 ). ∴ s( R 1 ∪R 2 ) = s( R 1 )∪s( R 2 ) 《集合论与图论》第 7讲 28 定理 21(证明 (3)) ? (3) t( R 1 ∪R 2 ) ? t( R 1 )∪t( R 2 ). ?证明 (3): 利用定理 20, t(R 1 ∪R 2 )?t(R 1 )∪t(R 2 ). 反例 : t(R 1 ∪R 2 )?t(R 1 )∪t(R 2 ) . # ab ab ab G(t(R 1 ∪R 2 )) G(R 1 )= G(t(R 1 )) G(R 2 )= G(t(R 2 )) 《集合论与图论》第 7讲 29 如何求闭包 ? ?问题 : (1) r( R ) = R ∪ (2) s( R ) = R ∪ (3) t( R ) = R ∪ ? ? ? 《集合论与图论》第 7讲 30 定理 22~24 ?定理 22~24: 设 R?A×A 且 A≠?, 则 (1) r( R ) = R∪I A ; (2) s( R ) = R∪R -1 ; (3) t( R ) = R∪R 2 ∪R 3 ∪…. ?对比 : R自反 ? I A ?R R对称 ? R=R -1 R传递 ? R 2 ?R 《集合论与图论》第 7讲 31 定理 22 ?定理 22: 设 R?A×A 且 A≠?, 则 r( R ) = R∪I A ; ?证明 : (1) R ? R∪I A ; (2) I A ?R∪I A ? R∪I A 自反 ? r( R )?R∪I A ; (3) R?r( R ) ∧ r( R )自反 ? R?r( R ) ∧ I A ? r( R ) ? R∪I A ?r( R ) ∴ r( R ) = R∪I A . 《集合论与图论》第 7讲 32 定理 23 ? 定理 23: 设 R?A×A 且 A≠?, 则 s( R ) = R∪R -1 ; ? 证明 : (1) R ? R∪R -1 ; (2) (R∪R -1 ) -1 =R∪R -1 ? R∪R -1 对称 ? s( R )?R∪R -1 ; (3) R?s( R ) ∧ s( R )对称 ? R?s( R ) ∧ R -1 ?s( R ) ? R∪R -1 ?s( R ) ∴ s( R ) = R∪R -1 . 《集合论与图论》第 7讲 33 定理 24 ? 定理 24: 设 R?A×A 且 A≠?, 则 t( R ) = R∪R 2 ∪R 3 ∪…; ? 证明 : (1) R ? R∪R 2 ∪R 3 ∪…; (2) (R∪R 2 ∪R 3 ∪…) 2 = R 2 ∪R 3 ∪… ? R∪R 2 ∪R 3 ∪… ? R∪R 2 ∪R 3 ∪…传递 ? t( R )?R∪R 2 ∪R 3 ∪…; (3) R?t( R ) ∧ t( R )传递 ? R?t( R )∧R 2 ?t( R )∧R 3 ?t( R )∧… ? R∪R 2 ∪R 3 ∪… ? t( R ) ∴ t( R ) = R∪R 2 ∪R 3 ∪…. 《集合论与图论》第 7讲 34 定理 24的推论 ?推论 : 设 R?A×A 且 0<|A|<∞, 则 ?l ∈N, 使 得 t( R ) = R∪R 2 ∪R 3 ∪…∪R l ; ?证明 : 由定理 16知 ?s,t∈N, 使得 R s = R t . 由定理 18知 R,R 2 ,R 3 ,…∈{ R 0 ,R 1 ,…,R t-1 }. 取 l =t-1, 由定理 24知 t( R ) = R∪R 2 ∪R 3 ∪…. = R∪R 2 ∪R 3 ∪…∪R l ∴ t( R ) = R∪R 2 ∪R 3 ∪…∪R l . # 《集合论与图论》第 7讲 35 例 8 ? 例 8: 设 A = { a,b,c,d }, R = { <a,b>,<b,a>,<b,c>,<c,d> }. 求 r( R ), s( R ), t( R ). ? 解 : . ? ? ? ? ? ? ? ? ? ? ? ? = 0000 1000 0101 0010 M(R) . 1000 1100 0111 0011 M(r(R)) ? ? ? ? ? ? ? ? ? ? ? ? = . 0100 1010 0101 0010 M(s(R)) ? ? ? ? ? ? ? ? ? ? ? ? = a bc d 《集合论与图论》第 7讲 36 例 8(续 ) ?解 (续 ): . 0000 1000 0101 0010 M(R) ? ? ? ? ? ? ? ? ? ? ? ? = . 1000 1100 0111 0011 M(r(R)) ? ? ? ? ? ? ? ? ? ? ? ? = . 0100 1010 0101 0010 M(s(R)) ? ? ? ? ? ? ? ? ? ? ? ? = a bc d a bc d a bc d 《集合论与图论》第 7讲 37 例 8(续 2) ?解 (续 2): . 0000 1000 0101 0010 M(R) ? ? ? ? ? ? ? ? ? ? ? ? = a bc d . 0000 0000 1010 0101 0000 1000 0101 0010 0000 1000 0101 0010 )M(R 2 ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = . 0000 0000 0101 1010 0000 0000 1010 0101 0000 1000 0101 0010 )M(R 3 ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 《集合论与图论》第 7讲 38 例 8(续 3) ?解 (续 3): . 0000 1000 0101 0010 M(R) ? ? ? ? ? ? ? ? ? ? ? ? = a bc d . 0000 0000 1010 0101 )M(R 2 ? ? ? ? ? ? ? ? ? ? ? ? = . 0000 0000 0101 1010 )M(R 3 ? ? ? ? ? ? ? ? ? ? ? ? = ).M(R 0000 0000 1010 0101 0000 0000 0101 1010 0000 1000 0101 0010 )M(R 24 = ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 《集合论与图论》第 7讲 39 例 8(续 4) ?解 (续 4): a bc d . 0000 1000 1111 1111 )M(R)M(RM(R)M(t(R)) 32 ? ? ? ? ? ? ? ? ? ? ? ? =∨∨= a bc d # 《集合论与图论》第 7讲 40 闭包运算是否保持关系性质 ? ?问题 : (1) R自反 ? s( R ), t( R )自反 ? (2) R对称 ? r( R ), t( R )对称 ? (3) R传递 ? s( R ), r( R )传递 ? 《集合论与图论》第 7讲 41 定理 25 ?定理 25: 设 R?A×A且 A≠?,则 (1) R自反 ? s( R )和 t( R )自反 ; (2) R对称 ? r( R )和 t( R )对称 ; (3) R传递 ? r( R )传递 ; 证明 : (1) I A ? R∪R -1 = s( R ) ∴ s( R )自反 . I A ? R∪R 2 ∪R 3 ∪… = t( R ) ∴ t( R )自反 . 《集合论与图论》第 7讲 42 定理 25(证明 (2)) ?(2) R对称 ? r( R )和 t( R )对称 ; ?证明 : (2) r( R ) -1 =(I A ∪R) -1 =I A -1 ∪R -1 =I A ∪R -1 =I A ∪R= r( R ) ∴ r( R )对称 . t( R ) -1 = (R∪R 2 ∪R 3 ∪…) -1 = R -1 ∪(R 2 ) -1 ∪(R 3 ) -1 ∪… = R -1 ∪(R -1 ) 2 ∪(R -1 ) 3 ∪…( (F○G) -1 =G -1 ○F -1 ) =R∪R 2 ∪R 3 ∪…=t( R ), ∴ t( R )对称 . 《集合论与图论》第 7讲 43 定理 25(证明 (3)) ?(2) R传递 ? r( R )传递 ; ?证明 : (2) r( R )○r( R ) = (I A ∪R)○(I A ∪R) = (I A ○I A )∪(I A ○R)∪(R○I A )∪(R○R) ? I A ∪R∪R∪R=I A ∪R= r( R ) ∴ r( R )传递 . # 《集合论与图论》第 7讲 44 定理 25(反例 ) ?反例 : R传递 , 但是 s( R )非传递 . G( R ) G(s( R )) √ (定义 ) √ (定理 25(2)) √ (定理 25(1)) t( R ) ×(反例 )√ (定义 ) √ (定理 25(1)) s( R ) √ (定理 25(3)) √ (定理 25(2)) √ (定义 ) r( R ) 传递性对称性自反性 ?小结 : 闭包运算保持下列关系性质 . 《集合论与图论》第 7讲 45 闭包运算是否可以交换顺序 ? ?问题 : (1) rs( R ) = sr( R ) ? (2) rt( R ) = tr( R ) ? (3) st( R ) = ts( R ) ? ?说明 : rs( R ) = r(s( R )) 《集合论与图论》第 7讲 46 定理 26 ?定理 26: 设 R?A×A 且 A≠?, 则 (1) rs( R ) = sr( R ); (2) rt( R ) = tr( R ); (3) st( R ) ? ts( R ); r( ) s( ) t( ) 可交换 可交换 《集合论与图论》第 7讲 47 定理 26(证明 (1)) ? (1) rs( R ) = sr( R ); 证明 : (1) rs( R ) = r(s( R )) = r(R∪R -1 ) = I A ∪(R∪R -1 ) = (I A ∪R)∪(I A -1 ∪R -1 ) = (I A ∪R)∪(I A ∪R) -1 = r( R )∪r( R ) -1 = s(r( R )) = sr( R ). ∴ rs( R ) = sr( R ). 《集合论与图论》第 7讲 48 定理 26(证明 (2)) ? (2) rt( R ) = tr( R ); 证明 :(2) rt( R ) = r(t( R )) = r(R∪R 2 ∪R 3 ∪…) = I A ∪(R∪R 2 ∪R 3 ∪…) = (I A ∪R)∪(I A ∪R∪R 2 )∪(I A ∪R∪R 2 ∪R 3 )∪… = (I A ∪R)∪(I A ∪R) 2 ∪(I A ∪R) 3 ∪… = r( R )∪r( R ) 2 ∪r( R ) 3 ∪…=t(r( R )). ∴ rt( R ) = tr( R ). 《集合论与图论》第 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 ). # 《集合论与图论》第 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 ))) 《集合论与图论》第 7讲 51 总结 ?关系幂运算 ?关系闭包 《集合论与图论》第 7讲 52 作业 (#5) ? p83, 习题二 , 27, 28, 29 ?今天交作业 #1,#2,#3,#4