4.2关系的运算 ·4.关系的幂运算 ·定义4.13：设R是集合A上的二元关系，则R的n次 幂R”定义为：（①）R=I4={<x,x>x∈，(2).R1=R。R ·例4-5：设A={0,1,2,3,4},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>,<01>,<0,3>,<1,3>,<2,4>, <3,1>,4,4>}; 4={K0,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
4.2关系的运算 定理4.5：设R为A上的二元关系，m,n为自然数， 则（①）.R+1=R”oR=RoR”=RmoR”m+ (2)RmoR”=Rm+”,(3).(Rm)”=Rm,(4).(R1)”=(R) 证(4)：若n=0时，则有(R)°=I4,(R”)1=(I)1=I 假设n=k时，有(R)=(R),则n=k+1时，有 (R)+1=(R1)o(R1)=(R)1。R1=(RoR)1=(R+1) .命题成立。 ·定理4.6：设集合A的基数为n,R是A上的二元关系 ,那么存在自然数i,j使得R=R(0≤i<j≤2) 证明：我们知道，当A=n时，A上的二元关系共计 2”个，令k=2，因此在R,R,R2,,R+1这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
4.2关系的运算 系中，至少有两个是相同的（鸽巢原理），即有 i,j(0≤i<j≤2”)，使R=R 定理4.7：设A是有限集合，且A=n,R是A上的二 元关系，则0R=UR i=l i=1 证明：显然UR∈UR,下面证：UR'cUR。 1s1 i= 而UR=URUUR,为此，只要证明对任意的k>n i=n+l 有R*∈0R即可。对任意的<a,b>∈R,则由” 的定义知：存在a1,a2,…,ak-1∈A,使得： <a,41>∈R,<a,a2>∈R,,<ak-1,ak>∈R(令a=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
4.2关系的运算 由于|A=n,所以由鸽巢原理；k+1个元素ao,…,ak 中至少有两个元素相同，不妨设为a,=a,(i<),则可 在<a,41>∈R,<a,a,>∈R,…,<ak-1,ak>∈R中l删去 <a,a+1>∈R,<a+1,a+2>∈R,…,<aj-1,a,>∈R后仍有 <ao,a1>∈R,<a1,a2>∈R,…,<a-1,a>∈R,<aj,aj+1>∈R,<ak-1,ak>∈R 由关系的复合运算得：<a,b>=<a,ak>∈R,其中 k'=k-(j-i),此时：若K≤n,则a,b>∈UR';若 k'>n,则重复上述做法，最终总能找到k”<n,使 得<a,b>=<ao,a>∈R,即有<a,b>∈UR，由此 1= 有R∈UR, 由k的任意性( EUR,.UR=UR' =1 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 = =