第7讲关系幂运算与关系闭包 内容提要 秦关系幂(oWer)运算 关系闭包 closure) 《集合论与图论》第7讲
《集合论与图论》第7讲 1 第7讲 关系幂运算与关系闭包 内容提要 关系幂(power)运算 关系闭包(closure)
关系的幂运算 n次幂的定义 指数律 癱幂指数的化简 《集合论与图论》第7讲
《集合论与图论》第7讲 2 关系的幂运算 n次幂的定义 指数律 幂指数的化简
关系的n次幂 关系的n次幂( nth power):设 RCAXA, n∈N,则 (1)R0=I (2)R+=R"oR,(n≥1) R=RR6邛 n个R 秦R表示的关系,是R的关系图中长度为n 的有向路径的起点与终点的关系 ●0 →0 《集合论与图论》第7讲
《集合论与图论》第7讲 3 关系的n次幂 关系的n次幂(nth power): 设R⊆A×A, n∈N, 则 (1) R0 = IA; (2) Rn+1 = Rn○R, (n≥1). Rn表示的关系, 是R的关系图中长度为n 的有向路径的起点与终点的关系. 1 o4 2oL4 3o n R n R R R R 个 = 12 n n-1
关系幂运算(举例 例:设A={a,bc,RAxA, R={ab>,,}求R的各次幂 解 a C a G(R) G(RO) 《集合论与图论》第7讲
《集合论与图论》第7讲 4 关系幂运算(举例) 例: 设A={a,b,c}, R⊆A×A, R={,,}, 求R的各次幂. 解: b a c b a c G( R ) G( R0 )
关系幂运算(举例续) 解(续):R0=IA, R=ROR=R=, , a,c>), R2=RoR=, 1, a HC G(R) G(R2) 《集合论与图论》第7讲
《集合论与图论》第7讲 5 关系幂运算(举例,续) 解(续): R0 = IA, R1 = R0○R = R = {,,}, R2 = R1○R = {,,}, b a c b a c G( R ) G( R2 )
关系幂运算(举例续2) 静解(续):R0=IA R=ROR=R=a, b>, , 1. R2=RTOR= , I R3=R2R={ab>,a,b>,}=R1 a 心0C a G(R) G(R3) 《集合论与图论》第7讲
《集合论与图论》第7讲 6 关系幂运算(举例,续2) 解(续): R0 = IA, R1 = R0○R = R = {,,}, R2 = R1○R = {,,}, R3 = R2○R = {,,} = 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归纳. #