北大离散数学课件.ppt

《北大离散数学课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7讲关系幂运算与关系闭包北京大学内容提要关系幂(power)运算关系闭包(closure)2021/10/41《集合论与图论》第7讲关系的幂运算n次幂的定义指数律幂指数的化简2021/10/42《集合论与图论》第7讲关系的n次幂关系的n次幂(nthpower):设RAA,nN,则(1)R0=IA;(2)Rn+1=Rn○R,(n1).Rn表示的关系,是R的关系图中长度为n的有向路径的起点与终点的关系.12nn-12021/10/43《集合论与图论》第7讲关系幂运算(举例)例:设A={a,b

2、,c},RAA,R={,,},求R的各次幂.解:bacbacG(R)G(R0)2021/10/44《集合论与图论》第7讲关系幂运算(举例,续)解(续):R0=IA,R1=R0○R=R={,,},R2=R1○R={,,},bacbacG(R)G(R2)2021/10/45《集合论与图论》第7讲关系幂运算(举例,续2)解(续):R0=IA,R1=R0○R=R={,,},R2=R1○

3、R={,,},R3=R2○R={,,}=R1,bacbacG(R)G(R3)2021/10/46《集合论与图论》第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,…,.#bacbacG(R)G(R5)bacG(R4)2021/10/47《集合论与图论》第7讲关系幂运算是否有指数律?指数律:(1)Rm○Rn=

4、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?2021/10/48《集合论与图论》第7讲定理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

5、)n=(Rn)-1.回忆:(F○G)-1=G-1○F-1(R2)-1=(R○R)-1=R-1○R-1=(R-1)22021/10/49《集合论与图论》第7讲定理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归纳.#2021/10/410《集合论与图论》第7讲R

6、0,R1,R2,R3,…是否互不相等?R0R1R2R3R4R5R6R7R8R0R1R2R3R4R5=R19=R33=R47=…R6=R20=R34=R48=…R7=R21=R35=R49=…R8=R22=R36=…R15R9R10R11R14R16R172021/10/411《集合论与图论》第7讲定理16定理16:设

7、A

8、=n,RAA,则s,tN,并且,使得Rs=Rt.证明:P(AA)对幂运算是封闭的,即R,RP(AA)RkP(AA),(kN).

9、P(AA)

10、=,在R0,R

11、1,R2,…,这个集合中,必有两个是相同的.所以s,tN,并且,使得Rs=Rt.#2021/10/412《集合论与图论》第7讲鸽巢原理(pigeonholeprinciple)鸽巢原理(pigeonholeprinciple):若把n+1只鸽子装进n只鸽巢,则至少有一只鸽巢装2只以上的鸽子.又名抽屉原则(Dirichletdrawerprinciple),(PeterGustavLejeuneDirichlet,1805~1859)推广形式:若把m件物品装进k只抽屉,则至少有一只抽屉装只以上的物

12、品.1.8=2,1.8=1,-1.8=-1,-1.8=-2.2021/10/413《集合论与图论》第7讲定理18定理18:设RAA,若s,tN(s