《离散数学 关系3》由会员分享，可在线阅读，更多相关《离散数学 关系3（51页珍藏版）》请在金锄头文库上搜索。
1、*集合论与图论第7讲1第7讲 关系幂运算与关系闭包内容提要关系幂(power)运算关系闭包(closure)*集合论与图论第7讲2关系的幂运算 n次幂的定义 指数律 幂指数的化简*集合论与图论第7讲3关系的n次幂关系的n次幂(nth power): 设R A A, n N, 则 (1) R0 = IA;(2) Rn+1 = RnR, (n 1). Rn表示的关系, 是R的关系图中长度为n 的有向路径的起点与终点的关系. 12nn-1*集合论与图论第7讲4关系幂运算(举例)例: 设A=a,b,c, R A A, R=, 求R的各次幂.解:bacbacG( R )G( R0 )*集合论与图论第7讲
2、5关系幂运算(举例,续)解(续): R0 = IA,R1 = R0R = R = ,R2 = R1R = ,bacbacG( R )G( R2 )*集合论与图论第7讲6关系幂运算(举例,续2)解(续): R0 = IA,R1 = R0R = R = ,R2 = R1R = ,R3 = R2R = , = R1,bacbacG( R )G( R3 )*集合论与图论第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,. # bacbacG(
3、 R ) G( R5 )bacG( R4 )*集合论与图论第7讲8关系幂运算是否有指数律?指数律:(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 ?*集合论与图论第7讲9定理17定理17: 设 R A A, m,n N, 则(1) RmRn = Rm+n ;(2) (Rm)n = Rmn.说明: 可让 m,n Z, 只需 IA domR ran
4、R (此时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*集合论与图论第7讲10定理17(证明(1)(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归纳 . #*集合论与图论第7讲11R0,R1,R2,
5、R3,是否互不相等?R0R1R2R3R4R5R6R7R8R0R1R2R3R4R5=R19=R33=R47= R6=R20=R34=R48= R7=R21=R35=R49=R8=R22=R36 =R15R9R10 R11R14R16R17*集合论与图论第7讲12定理16定理16: 设 |A|=n, R A A, 则 s,t N, 并且 , 使得 Rs = Rt. 证明: P(A A)对幂运算是封闭的, 即 R, R P(A A) Rk P(A A), (k N). |P(A A)| = , 在R0,R1,R2, 这个集合中, 必有两个是相同的. 所以 s,t N, 并且 , 使得 Rs = Rt
6、. #*集合论与图论第7讲13鸽巢原理(pigeonhole principle)鸽巢原理(pigeonhole principle): 若把 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.*集合论与图论第7讲14定理18定理18: 设 R A A, 若 s,t N (st-1
7、s, 则令 q=s+kp+i,其中 k,i N, p=t-s, s+i, .求 r( R ), s( R ), t( R ).解: abcd*集合论与图论第7讲36例8(续)解(续): abcdabcdabcd*集合论与图论第7讲37例8(续2)解(续2): abcd*集合论与图论第7讲38例8(续3)解(续3): abcd*集合论与图论第7讲39例8(续4)解(续4): abcdabcd#*集合论与图论第7讲40闭包运算是否保持关系性质?问题 :(1) R自反 s( R ), t( R )自反 ?(2) R对称 r( R ), t( R )对称 ?(3) R传递 s( R ), r( R )
8、传递 ?*集合论与图论第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) IA R R-1 = s( R ) s( R )自反.IA R R2 R3 = t( R ) t( R )自反.*集合论与图论第7讲42定理25(证明(2)(2) R对称 r( R )和t( R )对称;证明: (2) r( R )-1 =(IA R)-1 =IA-1 R-1 =IA R-1 =IA R= r( R ) r( R )对称.t( R )-1 = (R R2 R
9、3 )-1 = R-1 (R2)-1 (R3)-1 = R-1 (R-1)2 (R-1)3 ( (FG)-1=G-1F-1 ) = R R2 R3 =t( R ), t( R )对称.*集合论与图论第7讲43定理25(证明(3)(2) R传递 r( R )传递 ;证明: (2) r( R )r( R ) = (IA R)(IA R) = (IAIA) (IAR) (RIA) (RR) IA R R R =IA R= r( R ) r( R )传递 . #*集合论与图论第7讲44定理25(反例)反例: R传递 , 但是s( R )非传递 . G( R )G(s( R )自反性对称性传递性 r(
10、R ) (定义)(定理25(2)(定理25(3)s( R ) (定理25(1)(定义) (反例)t( R ) (定理25(1)(定理25(2)(定义)小结: 闭包运算保持下列关系性质. *集合论与图论第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) s
11、t( 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) = IA (R R-1) = (IA R) (IA-1 R-1) = (IA R) (IA 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 ) =
12、r(R R2 R3 ) = IA (R R2 R3 ) = (IA R) (IA R R2) (IA R R2 R3) = (IA R) (IA R)2 (IA 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总结关系幂运算关系闭包
