北大离散数学

第7讲关系幂运算与关系闭包

北京大学内容提要关系幂(power)运算关系闭包(closure)2025/4/221《集合论与图论》第7讲第1页关系幂运算

n次幂定义

指数律幂指数化简2025/4/222《集合论与图论》第7讲第2页关系n次幂关系n次幂(nthpower):设R

AA,nN,则

(1)R0

=IA;(2)Rn+1

=Rn○R,(n1).

Rn表示关系,是R关系图中长度为n有向路径起点与终点关系.12nn-12025/4/223《集合论与图论》第7讲第3页关系幂运算(举例)例:设A={a,b,c},R

AA,R={<a,b>,<b,a>,<a,c>},求R各次幂.解:bacbacG(R)G(R0)2025/4/224《集合论与图论》第7讲第4页关系幂运算(举例,续)解(续):R0

=IA,

R1

=R0○R=R={<a,b>,<b,a>,<a,c>},

R2

=R1○R={<a,a>,<b,b>,<b,c>},bacbacG(R)G(R2)2025/4/225《集合论与图论》第7讲第5页关系幂运算(举例,续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,bacbacG(R)G(R3)2025/4/226《集合论与图论》第7讲第6页关系幂运算(举例,续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,…,.#bacbacG(R)G(R5)bacG(R4)2025/4/227《集合论与图论》第7讲第7页关系幂运算是否有指数律?指数律:(1)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.说明:对实数R来说,m,nN,Z,Q,R.对普通关系R来说,m,nN.对满足IAR且AdomRranR关系R来说,m,nN,Z,比如R2○R-5=R-3,因为能够定义R-n=(R-1)n=(Rn)-1

?2025/4/228《集合论与图论》第7讲第8页定理17定理17:设R

AA,m,nN,则(1)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.说明:可让m,nZ,只需IAdomRranR(此时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)22025/4/229《集合论与图论》第7讲第9页定理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归纳.#2025/4/2210《集合论与图论》第7讲第10页R0,R1,R2,R3,…是否互不相等?R0R1R2R3R4R5R6R7R8R0R1R2R3R4R5=R19=R33=R47=…R6=R20=R34=R48=…R7=R21=R35=R49=…R8=R22=R36=…R15R9R10R11R14R16R172025/4/2211《集合论与图论》第7讲第11页定理16定理16:设|A|=n,R

AA,则s,tN,而且,使得Rs=Rt.证实:P(AA)对幂运算是封闭,即

R,RP(AA)RkP(AA),

(kN).|P(AA)|=,在R0,R1,R2,…,

这个集合中,必有两个是相同.所以s,tN,而且,使得Rs=Rt.#2025/4/2212《集合论与图论》第7讲第12页鸽巢原理(pigeonholeprinciple)鸽巢原理(pigeonholeprinciple):若把n+1只鸽子装进n只鸽巢,则最少有一只鸽巢装2只以上鸽子.又名抽屉标准(Dirichletdrawerprinciple),(PeterGustavLejeuneDirichlet,1805~1859)推广形式:若把m件物品装进k只抽屉,则最少有一只抽屉装只以上物品.1.8=2,1.8=1,-1.8=-1,-1.8=-2.2025/4/2213《集合论与图论》第7讲第13页定理18定理18:设R

AA,若s,tN(s<t),使得Rs=Rt,则(1)Rs+k=Rt+k;(2)Rs+kp+i=Rs+i,其中k,iN,p=t-s;(3)令S={R0,R1,…,Rt-1},则

qN,RqS.2025/4/2214《集合论与图论》第7讲第14页定理18(说明)spi泵(pumping):

Rs+kp+i

=

Rs+i2025/4/2215《集合论与图论》第7讲第15页定理18(证实(1)(3))(1)Rs+k=Rt+k;(3)令S={R0,R1,…,Rt-1},则

qN,RqS.证实:(1)Rs+k=Rs○Rk=Rt○Rk=Rt+k;(3)若q>t-1s,则令q=s+kp+i,其中k,iN,p=t-s,s+i<t;于是Rq=Rs+kp+i=Rs+iS.2025/4/2216《集合论与图论》第7讲第16页定理18(证实(2))(2)Rs+kp+i=Rs+i,其中k,iN,p=t-s;证实:(2)k=0时,显然;k=1时,即(1);设k2.则

Rs+kp+i=Rs+k(t-s)+i=Rs+t-s+(k-1)(t-s)+i

=Rt+(k-1)(t-s)+i=Rs+(k-1)(t-s)+i=…=Rs+(t-s)+i=Rt+i=Rs+i.#2025/4/2217《集合论与图论》第7讲第17页幂指数化简方法:利用定理16,定理18.例6:设R

AA,化简R100指数.已知(1)R7=R15;(2)R3=R5;(3)R1=R3.解:(1)R100=R7+11

8+5=R7+5=R12{R0,R1,…,R14};(2)R100=R3+48

2+1=R3+1=R4{R0,R1,…,R4};(3)R100=R1+49

2+1=R1+1=R2{R0,R1,R2}.#2025/4/2218《集合论与图论》第7讲第18页关系闭包自反闭包r(R)对称闭包s(R)传递闭包t(R)闭包性质,求法,相互关系2025/4/2219《集合论与图论》第7讲第19页什么是闭包闭包(closure):包含一些给定对象,含有指定性质最小集合“最小”:任何包含一样对象,含有一样性质集合,都包含这个闭包集合例:(平面上点凸包)2025/4/2220《集合论与图论》第7讲第20页自反闭包(reflexiveclosure)自反闭包:包含给定关系R最小自反关系,称为R自反闭包,记作r(R).(1)R

r(R);(2)r(R)是自反;(3)

S((RSS自反)r(R)S).G(R)G(r(R))2025/4/2221《集合论与图论》第7讲第21页对称闭包(symmetricclosure)对称闭包:包含给定关系R最小对称关系,称为R对称闭包,记作s(R).(1)Rs(R);(2)s(R)是对称;(3)

S((RSS对称)s(R)S).G(R)G(s(R))2025/4/2222《集合论与图论》第7讲第22页传递闭包(transitiveclosure)传递闭包:包含给定关系R最小传递关系,称为R传递闭包,记作t(R).(1)R

t(R);(2)t(R)是传递;(3)

S((RSS传递)t(R)S).G(R)G(t(R))2025/4/2223《集合论与图论》第7讲第23页定理19定理19:设R

A

A且A

,则(1)R自反

r(R)=R;(2)R对称

s(R)=R;(3)R传递

t(R)=R;证实:(1)RR

R自反

r(R)

R

又R

r(R),

r(R)=R.(2)(3)完全类似.#2025/4/2224《集合论与图论》第7讲第24页定理20定理20:设R1

R2

A

A且A

,则(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2);证实:(1)R1

R2r(R2)自反,

r(R1)r(R2)(2)(3)类似可证.#2025/4/2225《集合论与图论》第7讲第25页定理21定理21:设R1,R2

A

A且A

,则(1)r(R1

R2)=

r(R1)r(R2);(2)s(R1

R2)=s(R1)s(R2);(3)t(R1

R2)

t(R1)t(R2).证实:(1)利用定理20,r(R1

R2)

r(R1)r(R2).r(R1)r(R2)自反且包含R1

R2,所以

r(R1

R2)

r(R1)r(R2).

r(R1

R2)=

r(R1)r(R2)2025/4/2226《集合论与图论》第7讲第26页定理21(证实(2))(2)s(R1

R2)=s(R1)s(R2);证实(2):利用定理20,s(R1

R2)s(R1)s(R2).s(R1)s(R2)对称且包含R1

R2,所以

s(R1

R2)s(R1)s(R2).s(R1

R2)=s(R1)s(R2)2025/4/2227《集合论与图论》第7讲第27页定理21(证实(3))(3)t(R1

R2)

t(R1)t(R2).证实(3):利用定理20,t(R1

R2)t(R1)t(R2).

反例:t(R1

R2)t(R1)t(R2).#abababG(t(R1

R2))G(R1)=G(t(R1))G(R2)=G(t(R2))2025/4/2228《集合论与图论》第7讲第28页怎样求闭包?问题:(1)r(R)=R

(2)s(R)=R

(3)t(R)=R

???2025/4/2229《集合论与图论》第7讲第29页定理22~24定理22~24:设R

A

A且A

,则(1)r(R)=R

IA;(2)s(R)=R

R-1;(3)t(R)=R

R2

R3

….对比:R自反

IARR对称

R=R-1R传递

R2R2025/4/2230《集合论与图论》第7讲第30页定理22定理22:设R

A

A且A

,则r(R)=R

IA;证实:(1)RR

IA;(2)IAR

IA

R

IA自反

r(R)R

IA;(3)R

r(R)

r(R)自反

R

r(R)

IA

r(R)R

IA

r(R)

r(R)=R

IA.2025/4/2231《集合论与图论》第7讲第31页定理23定理23:设R

A

A且A

,则s(R)=R

R-1;证实:(1)RR

R-1;(2)(R

R-1)-1=R

R-1

R

R-1对称s(R)R

R-1;(3)Rs(R)

s(R)对称

Rs(R)

R-1s(R)R

R-1s(R)s(R)=R

R-1.2025/4/2232《集合论与图论》第7讲第32页定理24定理24:设R

A

A且A

,则t(R)=R

R2

R3…;证实:(1)RR

R2

R3…;(2)(R

R2

R3…)2=R2

R3…R

R2

R3…

R

R2

R3…传递t(R)R

R2

R3…;(3)Rt(R)

t(R)传递

Rt(R)

R2t(R)

R3t(R)…R

R2

R3…t(R)

t(R)=R

R2

R3….2025/4/2233《集合论与图论》第7讲第33页定理24推论推论:设R

A

A且0<|A|<,则

lN,使得t(R)=R

R2

R3…Rl;证实:由定理16知

s,tN,使得Rs=Rt.由定理18知R,R2,R3,…

{R0,R1,…,Rt-1}.取l=t-1,由定理24知t(R)=R

R2

R3….=R

R2

R3…Rl

t(R)=R

R2

R3…Rl.#2025/4/2234《集合论与图论》第7讲第34页例8例8:设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}.求r(R),s(R),t(R).解:abcd2025/4/2235《集合论与图论》第7讲第35页例8(续)解(续):abcdabcdabcd2025/4/2236《集合论与图论》第7讲第36页例8(续2)解(续2):abcd2025/4/2237《集合论与图论》第7讲第37页例8(续3)解(续3):abcd2025/4/2238《集合论与图论》第7讲第38页例8(续4)解(续4):abcdabcd#2025/4/2239《集合论与图论》第7讲第39页闭包运算是否保持关系性质?问题:(1)R自反

s(R),t(R)自反?(2)R对称

r(R),t(R)对称?(3)R传递

s(R),r(R)传递?2025/4/2240《集合论与图论》第7讲第40页定理25定理25:设R

A

A且A

,则(1)R自反

s(R)和t(R)自反;(2)R对称

r(R)和t(R)对称;(3)R传递

r(R)传递;证实:(1)

IA

R

R-1=s(R)

s(R)自反.

IAR

R2

R3…=t(R)

t(R)自反.2025/4/2241《集合论与图论》第7讲第41页定理25(证实(2))(2)R对称

r(R)和t(R)对称;证实:(2)r(R)-1=(IA

R)-1=IA-1

R-1=IA

R-1

=IA

R=r(R)

r(R)对称.

t(R)-1=(R

R2

R3…)-1=R-1(R2)-1(R3)-1…=R-1(R-1)2(R-1)3…((F○G)-1=G-1○F-1)=

R

R2

R3…=t(R),

t(R)对称.2025/4/2242《集合论与图论》第7讲第42页定理25(证实(3))(2)R传递

r(R)传递;证实:(2)r(R)○r(R)=(IA

R)○(IA

R)=(IA○IA)(IA○R)(R○IA)(R○R)

IA

R

R

R

=IA

R=r(R)

r(R)传递.#2025/4/2243《集合论与图论》第7讲第43页定理25(反例)反例:R传递,不过s(R)非传递.G(R)G(s(R))自反性对称性传递性r(R)

(定义)

(定理25(2))

(定理25(3))s(R)

(定理25(1))

(定义)(反例)t(R)

(定理25(1))

(定理25(2))

(定义)小结:闭包运算保持以下关系性质.2025/4/2244《集合论与图论》第7讲第44页闭包运算是否能够交换次序?问题:(1)rs(R)=sr(R)?(2)rt(R)=tr(R)?(3)st(R)=ts(R)?说明:rs(R)=r(s(R))2025/4/2245《集合论与图论》第7讲第45页定理26定理26:设R

A

A且A

,则(1)rs(R)=sr(R);(2)rt(R)=tr(R);(3)st(R)

ts(R);r()s()t