42关系的运算 4.关系的幂运算 定义4.13:设R是集合A上的二元关系,则R的m次 幂定义为:(1)R=1={<x,x>x∈4},(2)R=R"。R 例4-5:设A={0,1,2,34},R={<0,0>,<0,1>, <1,3>,<2,4>,<3,1>,<4,4 则R={<0,0》,<0,1>,<0,3>,<1,1,<2,4 <3,3,<4,4》}; R=区0,0〉,<0,1>,<0,3>,<1,3>,<2,4> <3,1>,<4,4 R4={<0,0》,<0,1>,<0,3>,<1,1>,<2,4), <3,3>,<4,4>}=R2 16/57
16/57 4.2 关系的运算 • 4.关系的幂运算 •定义4.13：设R是集合A上的二元关系，则R的n次 幂 定义为： •例4-5：设A={0,1,2,3,4}，R={<0,0>，<0,1>， <1,3>，<2,4>，<3,1>，<4,4>}。 则 ={<0,0>，<0,1>，<0,3>，<1,1>，<2,4>， <3,3>，<4,4>}； ={<0,0>，<0,1>，<0,3>，<1,3>，<2,4>， <3,1>，<4,4>}； ={<0,0>，<0,1>，<0,3>，<1,1>，<2,4>， <3,3>，<4,4>}= n R R I x x x A R R R n n A = = = 0 +1 (1). { , | },(2). 2 R 3 R 4 R 2 R
42关系的运算 ·定理4.5:设R为A上的二元关系,m,n为自然数, R R"。R=RoR=Rm"oR (2)RmoR"=Rmn,、(3)(R")"=Rm,(4)(R)"=(R")h 证(4):若n=0时,则有(R)=1,(Ry)=(1)=1 假设n=时,有(R)=(R),则n=k+1时,有 (R-)=(R)°(R)=(R)R=(RoR)=(R+) 命题成立。 定理4.6:设集合A的基数为n,R是A上的二元关系 ,那么存在自然数i,j使得R'=R/(0≤i<j≤2 证明:我们知道,当|A|=n时,A上的二元关系共计 2个,令k=2”,因此在R,R,R2,…R这k+1个关 17/57
17/57 4.2 关系的运算 •定理4.5：设R为A上的二元关系，m，n为自然数， 则 证(4)：若n=0时，则有 假设n=k时，有 ，则n=k+1时，有 ∴命题成立。 • 定理4.6：设集合A的基数为n，R是A上的二元关系 ，那么存在自然数i，j使得 证明：我们知道，当|A|=n时，A上的二元关系共计 个，令k= ，因此在 这k+1个关 1 1 (1). + − + = = = n n n m n m R R R R R R R (2). ,(3).( ) ,(4).( ) ( ) . + −1 −1 = = = m n m n m n mn n n R R R R R R R A A n A R = I R = I = I −1 0 −1 −1 ( ) ,( ) ( ) 1 1 ( ) ( ) − − = k k R R 1 1 1 1 1 1 1 1 1 ( ) ( ) ( ) ( ) ( ) ( ) − + − − − − − + − = = = = k k k k k R R R R R R R R (0 2 ) 2 i j n R = R i j 2 2 n 2 2 n 0 1 2 1 , , , , k+ R R R R
42关系的运算 系中,至少有两个是相同的(鸽巢原理),即有 i,f(0≤i<j≤2”.使R=R 定理4.7:设A是有限集合,且|A|=n,R是A上的二 元关系,则UR=UR 证明:显然UR三UR,下面证: UR'CUR 而∪R'=∪R∪∪R,为此,只要证明对任意的kn 有RcUR即可。对任意的<a,b>∈R,则由“ 的定义知:存在a1,a2…ak∈A,使得: <an2a1>∈R,<a12a2>∈R…,<ak12ak>∈R(令a0=a,ak=b) 18/57
18/57 4.2 关系的运算 系中，至少有两个是相同的(鸽巢原理)，即有 • 定理4.7：设A是有限集合，且|A|=n，R是A上的二 元关系，则 证明：显然 ，下面证： 。 而 ，为此，只要证明对任意的k>n ，有 即可。对任意的 ，则由“” 的定义知：存在 ，使得： , (0 2 ), . 2 n i j i j i j 使R = R i n i i i R R 1 =1 = = i i i n i R R = = 1 1 i n i i i R R 1 =1 = i i n i n i i i R R R = = + = = 1 1 1 i n i k R R =1 k a,b R a1 ,a2 , ,ak−1 A , , , , , , ( , ) a0 a1 R a1 a2 R ak−1 ak R 令a0 = a ak = b
42关系的运算 由于|A=n,所以由鸽巢原理;k+1个元素a0…ak 中至少有两个元素相同,不妨设为a=a(<j),则可 在<40,a1>∈R<a,a2>∈R…<a-k>∈R中删去 <4124+1>∈R,<a41,4+2>∈R…,a1-12>∈R后仍有 <a0,a>∈R<a1,a2>∈R…,a1-1,a1>∈R<a1,a1+>∈R,<ak-1,ak>∈R 由关系的复合运算得:<ab>=<a0,4k>∈R,其中 k=k-(-),此时:若k≤n,则ab>∈UR';若 k>n,则重复上述做法,最终总能找到"<n,使 得<a,b><a。,ak>∈R,即有<a,b>∈∪R,由此 有R^∈UR,由k的任意性 URCUR,∴UR=UR i=1 19/57
19/57 4.2 关系的运算 由于|A|=n，所以由鸽巢原理；k+1个元素 中至少有两个元素相同，不妨设为 ，则可 在 中删去 后仍有 由关系的复合运算得： ，其中 ，此时：若 ，则 ；若 ，则重复上述做法，最终总能找到 ，使 得 ，即有 ，由此 有 ，由k的任意性 ，∴ a ak , , 0 a a (i j) i = j a0 ,a1 R, a1 ,a2 R, , ak−1 ,ak R ai ,ai+1 R, ai+1 ,ai+2 R, , aj−1 ,aj R a0 ,a1 R, a1 ,a2 R, , ai−1 ,ai R, aj ,aj+1 R, ak−1 ,ak R ' , , 0 k a b = a ak R k = k − ( j −i) k n i n i a b R 1 , = k n k n k a b a ak R , = 0 , i n i a b R 1 , = i n i k R R =1 i n i i i R R 1 =1 = i n i i i R R 1 =1 = =