幂的求法对于集合表示的关系R，计算Rn就是个复合矩阵表示就是个矩阵相乘，其中相加采用逻辑加例3设A=[a, b, c, d],R=[<a, b>,<b, a>,<b, c>, <c, d>] ,求的各次幂，分别用矩阵和关系图表示解与尺的关系矩阵分别为000001MM00016
16 幂的求法 对于集合表示的关系R，计算 R n 就是n个R左复合 . 矩阵表示就是n个矩阵相乘, 其中相加采用逻辑加. 例3 设A={a,b,c,d}, R={<a,b>,<b,a>,<b,c>,<c,d>}, 求R的各次幂, 分别用矩阵和关系图表示. 解 R与R 2的关系矩阵分别为 = 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 M = = 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 2 M
(续）幂幕的求法同理，R0=I4,R3和R4的矩阵分别是：0001111MMM因此M4=MP，即R4=R2.因此可以得到R2=R4=R6=..., R3=R5=R7=..17
17 同理，R0=IA, R3和R4的矩阵分别是： 因此M4=M2 , 即R4=R2 . 因此可以得到 R2=R4=R6=., R3=R5=R7=. = = 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 , 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 3 4 M M = 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 M 幂的求法（续）
(续）幂的求法R°RR2,R3...的关系图如下图所示R'=RROcR'=R"R'-R'18
18 R0 , R1 , R2 , R3 ,.的关系图如下图所示 幂的求法（续）
幂幕运算的性质定理3设A为n元集.R是A上的关系.则存在自然数s和t，使得Rs= Rt.证 R为A上的关系，由于IA|=n，A上的不同关系只有2n个。当列出R的各次幂R', R', R?, ....0必存在自然数s和t使得Rs=Rt19
19 幂运算的性质 定理3 设A为n元集, R是A上的关系, 则存在自然 数 s 和 t, 使得 Rs = Rt . 证 R为A上的关系, 由于|A|=n, A上的不同关系只 有 个. 当列出 R 的各次幂 R0 , R1 , R2 , ., , ., 必存在自然数 s 和 t 使得 Rs=Rt . 2 2 n
(续)幂运算的性质定理4i设R是A上的关系,m,nEN,则(1) RmoRn=Rm+n(2) (Rm)"=Rmn证用归纳法(1)对于任意给定的mEN，施归纳于n.若n=0,则有RmoR°=RmoI^=Rm=Rm+0假设RmoRn=Rm+n,则有RmoRn+1=Rmo(RnoR)=(RmoRn)oR=Rm+n+1所以对一切m,nEN有RmoRn=Rm+n20
20 定理4 设 R 是 A 上的关系, m, n∈N, 则 (1) Rm∘Rn=Rm+n (2) (Rm) n=Rmn 证 用归纳法 (1) 对于任意给定的m∈N, 施归纳于n. 若n=0, 则有 Rm∘R0=Rm∘IA=Rm=Rm+0 假设Rm∘Rn=Rm+n , 则有 Rm∘Rn+1=Rm∘(Rn∘R)=(Rm∘Rn )∘R=Rm+n+1 , 所以对一切m, n∈N有Rm∘Rn=Rm+n . 幂运算的性质（续）