离散数学-关系的闭包幻灯片.ppt

,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,4.4,关系的闭包,闭包定义,闭包的构造方法,集合表示,矩阵表示,图表示,闭包的性质,2,一、闭包定义,定义,设,R,是非空集合,A,上的关系,R,的,自反（对称,或,传递）闭包,是,A,上的关系,R,使得,R,满足以下条件：（,1,）,R,是自反的（对称的或传递的）（,2,）,R,R,（,3,）对,A,上任何包含,R,的自反（对称或传递）关系,R,有,R,R,.,一般将,R,的自反闭包记作,r,(,R,),对称闭包记作,s,(,R,),传递闭包记作,t,(,R,).,3,由闭包的定义可知，,R,的自反（对称，传递）闭包是含有,R,并且具有,自反（对称，传递）性质的“最小”的关系。,如果,R,已是自反的二元关系，显然有：,R=r(R),。,同样，当,R,是对称的二元关系时,R=s(R),；,当,R,是传递的二元关系时，,R=t(R),，且反之亦然。,4,二、关系的闭包运算,（,1,）已知一个集合中的二元关系,R,，则,r(R),s(R),t(R),是唯一的，它是包含,R,的,最小的自反（对称，传递）关系；,（,2,）若,R,是自反（对称，传递）的，则,r(R),s(R),t(R),就是,R,本身。,（,3,）若,R,不是自反（对称，传递）的，则,可以补上最少序偶，使之变为自反、对称、,传递关系，从而得到,r(R),s(R),t(R),；,5,例：设,=a,b,c,R=,，求,r(R),s(R),t(R,),。,解：,r(R)=,s(R)=,t(R)=,例：设,=a,b,R=,，,则,r(R)=,s(R)=,t(R)=R,6,设,R,是,A,上的二元关系，,x,A,，将所有,(,x,x),R,的有序对,加到,R,上去，使其扩充成自反的二元关系，扩充后的自反,关系就是,R,的自反闭包,r(R),。,例如，,A=a,b,c,d,R=(a,a),(b,d),(c,c),。,R,的自反闭包,r(R)=(a,a),(b,d),(c,c),(b,b),(d,d),。,于是可得：,定理,:R,是,A,上的二元关系，则,R,的自反闭包,r(R)=RI,A,。,1.,构造,R,的自反闭包的方法。,三、闭包的构造方法,7,2.,构造,R,的对称闭包的方法。,每当,(a,b),R,，而,(b,a),R,时，将有序对,(b,a),加到,R,上去，,使其扩充成对称的二元关系，扩充后的对称关系就是,R,的对称闭包,s(R),。,例如，,A=a,b,c,d,e,R=(a,a),(a,b),(b,a),(b,c),(d,e),。,R,的对称闭包,s(R)=(a,a),(a,b),(b,a),(b,c),(c,b),(d,e),(e,d),。,定理,:,R,是,A,上二元关系，是其逆关系，,则,R,的对称闭包,s(R)=R,。,由逆关系的定义可知：,8,3.,构造,R,的传递闭包的方法。,设,R,是,A,上的二元关系，每当,(a,b),R,和,(b,c)R,而,(a,c),R,时，将有序对,(a,c),加到,R,上使其扩充成,R,1,，并称,R,1,为,R,的传递扩张，,R,1,如果是传递关系,，则,R,1,是,R,的传递闭包；如果,R,1,不是传递关系，继续求,R,1,的的传递扩张,R,2,，如果,R,2,是传递关系时，则,R,2,是,R,的传递闭包；如果,R,2,不是传递关系时，继续求,R,2,的的传递扩张,R,3,，如果,A,是有限集，,R,经过有限次扩张后，定能得到,R,的传递闭包。,扩张后的传递关系就是,R,的传递闭包,t(R),。,定理,:,设,R,为,A,上的关系,则有,t,(,R,)=,R,R,2,R,3,说明：,对于有穷集合,A,(|,A,|=,n,),上的关系,上式中的并最多不超过,R,n,.,9,思考：设,A,=,a,b,c,d,R,=,求,r,(,R,),s,(,R,),t,(,R,).,解,:,r,(,R,)=,R,R,0,=,s,(,R,)=,R,R,1,=,t,(,R,)=,R,R,2,R,3,R,4,R,2,=,R,3,=,R,4,=,=,R,2,于是,t,(,R,)=,R,R,2,R,3,=,.,10,闭包的构造方法（续）,设关系,R,r,(,R,),s,(,R,),t,(,R,),的关系矩阵分别为,M,M,r,M,s,和,M,t,则,M,r,=,M,+,E,M,s,=,M,+,M,M,t,=,M,+,M,2,+,M,3,+,E,是和,M,同阶的单位矩阵,M,是,M,的转置矩阵,.,注意在上述等式中矩阵的元素相加时使用逻辑加,.,11,闭包的构造方法（续）,设关系,R,r,(,R,),s,(,R,),t,(,R,),的关系图分别记为,G,G,r,G,s,G,t,则,G,r,G,s,G,t,的顶点集与,G,的顶点集相等,.,除了,G,的边以外,以下述方法添加新边：考察,G,的每个顶点,如果没有环就加上一个环，最终得到,G,r,.,考察,G,的每条边,如果有一条,x,i,到,x,j,的单向边,i,j,则在,G,中加一条,x,j,到,x,i,的反方向边，最终得到,G,s,.,考察,G,的每个顶点,x,i,找从,x,i,出发的每一条路径，如果从,x,i,到路径中任何结点,x,j,没有边，就加上这条边,.,当检查完所有的顶点后就得到图,G,t,.,12,实例,例,1,设,A,=,a,b,c,d,R,=,R,和,r,(,R,),s,(,R,),t,(,R,),的关系图如下图所示,.,R,r,(,R,),s,(,R,),t,(,R,),南宁空调回收,南宁空调出租 仧莒彾,Microsoft Office PowerPoint,，是微软公司的演示文稿软件。用户可以在投影仪或者计算机上进行演示，也可以将演示文稿打印出来，制作成胶片，以便应用到更广泛的领域中。利用,Microsoft Office PowerPoint,不仅可以创建演示文稿，还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。,Microsoft Office PowerPoint,做出来的东西叫演示文稿，其格式后缀名为：,ppt,、,pptx,；或者也可以保存为：,pdf,、图片格式等,13,14,定理,R,是,A,上关系，则,R,是自反的，当且仅当,r(R)=R.,R,是对称的，当且仅当,s(R)=R.,R,是传递的，当且仅当,t(R)=R.,证明略，因为由闭包定义即可得。,定理,R,是,A,上关系，则,R,是自反的，则,s(R),和,t(R),也自反。,R,是对称的，则,r(R),和,t(R),也对称。,R,是传递的，则,r(R),也传递。,证明,:,因为,R,自反,得,r(R)=R,即,R,I,A,=R,r(s(R)=s(R),I,A,=(RR,-1,),I,A,=(R,I,A,)R,-1,=r(R)R,-1,=RR,-1,=s(R)s(R),自反,15,类似可以证明,t(R),也自反。,证明,.证明,t(R),对称:,(,t(R),-1,=(,RR,2,.R,n,.,),-1,=,R,-1,(R,2,),-1,.(R,n,),-1,.,=,R,-1,(R,-1,),2,.(R,-1,),n,.,=,RR,2,.R,n,.,(R,对称，,R,-1,=R),=t(R),所以,t(R),也对称。,类似可以证明,r(R),也对称。,证明,.证明,r(R),传递:先用归纳法证明下面结论:,(,R,I,A,),i,=I,A,RR,2,.R,i,i=1,时,R,I,A,=I,A,R,结论成立。,假设,ik,时结论成立，即,(,R,I,A,),k,=I,A,RR,2,.R,k,(R,2,),-1,=(R R),-1,=R,-1,R,-1,=(R,-1,),2,16,当,i=k+1,时,(,R,I,A,),k+1,=(,R,I,A,),k,(,R,I,A,),=(I,A,RR,2,.R,k,）,(I,A,R,),=(I,A,RR,2,.R,k,)(RR,2,.R,k+1,),=I,A,RR,2,.R,k,R,k+1,所以结论成立.,t(r(R)=t(,R,I,A,),=(,R,I,A,),(,R,I,A,),2,(,R,I,A,),3,.,=(I,A,R,),(I,A,RR,2,),(,I,A,RR,2,R,3,).,=I,A,RR,2,R,3,.,=I,A,t(R),=,I,A,R (R,传递,t(R)=R),=r(R),所以,r(R),也传递。,。,。,17,定理,设,R,1,、,R,2,是,A,上关系，如果,R,1,R,2,，则,r(R,1,),r(R,2,),s(R,1,),s(R,2,),t(R,1,),t(R,2,),证明,r(R,1,)=I,A,R,1,I,A,R,2,=,r(R,2,),，类似可证。,定理,设,R,是,A,上关系，则,sr(R)=rs(R),tr(R)=rt(R),st(R),ts(R),证明：,sr(R)=r(R)(r(R),-1,=(RI,A,)(RI,A,),-1,=(RI,A,)(R,-1,I,A,-1,)=RI,A,R,-1,I,A,=(RR,-1),I,A,=s(R)I,A,=rs(R),的证明用前边证明的结论：,(,R,I,A,),k,=I,A,RR,2,.R,k,很容易证明，这里从略。,18,因,R,s(R),，得,t(R),ts(R),；,st(R),sts(R),因,s(R),对称，得,ts(R),也对称，得,sts(R)=,ts(R),所以有,st(R),ts(R),。证明完毕。,通常将,t(R),记成,R,+,，,tr(R),记成,R*,，,即,t(R)=R,+,=,RR,2,.R,n,=,tr(R)=rt(R)=R*=R,0,RR,2,.R,n,=,R,i,i=1,R,i,i=0,