关系幂运算(举例续2) 静解(续):R0=IA R=ROR=R=a, b>, <b, a>, <a, c>1. R2=RTOR=<a, a> <b,b>, <b, c>I R3=R2R={ab>,a,b>,<a,c>}=R1 a 心0C a G(R) G(R3) 《集合论与图论》第7讲
《集合论与图论》第7讲 6 关系幂运算(举例,续2) 解(续): R0 = IA, R1 = R0○R = R = {<a,b>,<b,a>,<a,c>}, R2 = R1○R = {<a,a>,<b,b>,<b,c>}, R3 = R2○R = {<a,b>,<a,b>,<a,c>} = R1, b a c b a c G( R ) G( R3 )
关系幂运算(举例续3) ●解(续):R4=R3oR=R1oR=R2 R5E ROR= R2OR=R3=R 般地,R2k+1=R1=R,k=0,112,, R2k=R2.k=12.# a a G(R) G(R4) G( R5 《集合论与图论》第7讲
《集合论与图论》第7讲 7 关系幂运算(举例,续3) 解(续): R4 = R3○R = R1○R = R2, R5 = R4○R = R2○R = R3 = R1, 一般地, R2k+1=R1=R, k=0,1,2,…, R2k=R2, k=1,2,…,. # b a c b a c G( R ) G( R5 ) b a c G( R4 )
关系幂运算是否有指数律? 指数律: (1)RmoRn= Rman 2)(Rm)=R 秦说明:对实数R来说,mn∈N,Z,Q,R 对一般关系R来说,m,n∈N 对满足IAcR且 AcdomRoranR的关系R来说, mn∈NZ,例如R2R5=R3,因为可以定义 Rn=(R-nE(Rn) 《集合论与图论》第7讲
《集合论与图论》第7讲 8 关系幂运算是否有指数律? 指数律: (1) Rm○Rn = 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, 例如R2○R-5=R-3,因为可以定义 R-n = (R-1)n = (Rn)-1 ?
定理17 定理17:设 RCAXA,m,neN,则 (1)RmORnE Rm (2)(R"n=R mn 说明:可让m,n∈乙,只需 IacdomRoranR (此时IA=RR=RoR)并且定义 Rn=(R-=(Rn-1 回忆:(FoG)1=G1oF (R2)1=(RR)R1R1=(R1)2 《集合论与图论》第7讲
《集合论与图论》第7讲 9 定理17 定理17: 设 R⊆A×A, m,n∈N, 则 (1) Rm○Rn = Rm+n ; (2) (Rm)n = Rmn. 说明: 可让 m,n∈Z, 只需IA⊆domR∩ranR (此时IA=R○R-1=R-1○R)并且定义 R-n = (R-1)n = (Rn)-1. 回忆: (F○G)-1=G-1○F-1 (R2)-1=(R○R)-1=R-1○R-1=(R-1)2
定理17(证明(1) 秦(1)RnoR"=Rmn 证明:(1)给定m,对n归纳。n=0时, RMORE RMOROE RI O=Rm=Rm+O 假设 MorN=Rmt,则RmoR+1 RmO(Rn ORt =(RmoRDOR=RmtnoR Rm+n)+1=Rm+(+1 (2)同样对n归纳.# 《集合论与图论》第7讲
《集合论与图论》第7讲 10 定理17(证明(1)) (1) Rm○Rn = Rm+n ; 证明: (1) 给定m, 对n归纳. n=0时, Rm○Rn = Rm○R0 = Rm○IA = Rm = Rm+0. 假设 Rm○Rn = Rm+n, 则 Rm○Rn+1 = Rm○(Rn ○R1) = (Rm○Rn)○R1 = Rm+n○R = R(m+n)+1 = Rm+(n+1). (2) 同样对n归纳. #