第6章二元关系2

,主标题,主文本标题,二级标题,三级标题,四级标题,五级标题,*,*,离 散 数 学,电子科技大学,16 十一月 2024,2024/11/16,6.4,关系的性质,-,重点,本节涉及到的关系，如无特别声明，都是,假定其前域和后域相同,。即都为定义在集合,A,上的关系，且,A,是非空集合,。对于前后域不相同的关系，其性质无法加以定义。,6.4.1,关系性质的定义,1.,关系性质的定义,2024/11/16,定义,6.4.1-3,设,R,是集合,A,上的关系，,1.,如果对任意,x,A,，,都,有,R,，,那么,称,R,在,A,上是,自反的,，或称,R,具有,自反性,.,2.,如果对任意,xA,，都有,R,，那么称,R,在,A,上是,反自,反的,，或称,R,具有,反自反性,。,3.,对任意,x,yA,，,如果,R,，那么,R,，,则称关系,R,是,对称的,，或称,R,具有,对称性,；,4.,对任意,x,yA,，,如果,R,且,R,，那么,x,y,（,或者,若,x,y,则,与,不全属于,R,），,则称关系,R,是,反对称的,，或称,R,具有,反对称性,。,5.,对任意,x,y,zA,，如果,R,且,R,，那么,R,，则称关系,R,是,传递的,，或称,R,具有,传递性,。,2024/11/16,例,1,：,1.,整数集,I,上的,“,等于,”,关系是自反的、反对称的、对称的、传递的关系。,“,小于等于,”,关系是自反的、反对称的、传递的关系；,“,小于,”,关系是反自反的、反对称的、传递的关系,。,2.,幂集上的,“,包含,”,关系关系是自反的、反对称的、传递的关系,。,3.,命题公式集合上的蕴涵关系,“,”,具有,自反,性,、反对称,性和,传递,性。,4.,三角形的相似关系具有,自反,性,、对称,性和,传递,性。,5.,人的集合上的,朋友关系,具有,自反,性和,对称,性,;,父子关系,具有反,自反,性和,反对称性,.,2024/11/16,例,2,：,设,A是任意的,非空,集合,，,则,A,上的全关系,AA,是,自反的、对称的、传递的关系；,A,上的空关系,是,反自反的、反对称的、对称的、传,递的关系；,A,上的恒等关系,I,A,是 自反的、对称的、反对称的、传,递的关系。,例,3,：,设,A=1,2,3,，,A,上的关系：,（,1,）,R=,则,R,是自反的,反对称的,传递的,.,（,2,）,S=,则,S,是反自反的,对称的,.,2024/11/16,（,3,）,U=,则,U,是,对称的,反对称的,传递的,.,（,4,）,V=,则,V,是,反对称的,传递的,.,（,5,）,T=,则,T 5,个性质都没有,.,2,.,“,性质,”,在关系图和关系矩阵上的反应,（,1,）,关系,R,是自反的,关系图中,每个节点都有环,关系矩阵的主对角线上的元素全为,1,（,2,）,关系,R,是反自反的,关系图中,每个节点都无环,关系矩阵的主对角线上的元素全为,0,2024/11/16,(3),关系,R,是对称的,关系图中任何一对结点之间，,要么有方向相反的两条边，要么无边,关系矩阵为,对称矩阵,(4),关系,R,是反对称的,关系图中,任何一对结点之间，至多有一条边；,R,的关系矩阵满足,r,ij,r,ji,0,，,i,j=1,2,n,，,i,j,。,(5),关系,R,是,传递,的,图中,任何三个节点,x,y,z(,可以相同,),之间，若从,x,到,y,有一条边存在,从,y,到,z,有一条边存在,则从,x,到,z,一定有一条边存在,.,关系矩阵中,如,果,r,ij,1,且,r,jk,1,则,r,ik,1,2024/11/16,有,:,反自反性和反对称性,1,3,2,有,:,反自反性和反对称性,有,:,自反性,反对称性和,传递性,3,1,2,例,A=1,2,3,上关系,:,2024/11/16,设,A,a,b,c,试判断如下图所示,A,上关系的性质：,例,a,b,c,(a),a,b,c,(b),a,b,c,(c),a,b,c,(d),a,b,c,(e),a,b,c,(f),a,b,c,(g),a,b,c,(h),图,(a),的关系是自反的、对称的、反对称的、传递的关系,图,(b),的关系是具备反自反的、对称的、反对称的、传递的关系,图,(c),的关系是具备对称的、反对称的、传递的关系,图,(d),的关系是不具备任何的性质关系,图,(e),的关系是具备自反的、对称的、传递的关系,图,(f),的关系是具备反自反的、反对称的、传递的关系,图,(g),的关系是具备反自反的、反对称的关系,图,(h),的关系是具备反自反的、反对称的、传递的关系,2024/11/16,注,:,(3),存在既是对称也是反对称的关系；,(1),非空集合,A,上的关系,若有,自反性,则一定没有反自反性,;,反知,若有,反自反性,则一定没有自反性,;,(2),存在既不是对称也不是反对称的关系；,(4),非空,集合,A,上的,空关系,具有反自反性、对称性、,反对称性和传递性；,(5),空,集上的,空关系,5,个性质都具有,.,2024/11/16,总结,自反,反自反,对称,反对称,传递,定义,R,R,R,R,R,R,x,=,y,R,R,R,关系图,每个结点都有环,每个结点都无环,每对结点间或有方向相反的两条边，或无任何边,每对结点间至多有一条边存在,任三个结点,x,y,z,，若从,x,到,y,有边，从,y,到,z,有边，则从,x,到,z,一定有边,关系矩阵,对角线上全为,1,对角线上全为,0,对称矩阵,r,ij,r,ji,=0,i,j=1,2,n,i,j,如,r,ij,1,且,r,jk,1,则,r,ik,1,2024/11/16,反自反,关系性质的证明方法,自反,任取,x,A,，,中间过程,任取,x,A,，,中间过程,对称,任取,x,y,A,，,假设,R,，,中间过程,R,。,R,。,R,。,2024/11/16,关系性质的证明方法,(,续,),反对称,任取,x,y,A,，假设,R,，,R,，,中间过程,x,y,。,或者,任取,x,y,A,，,xy,，,假设,R,，,中间过程,R,。,传递,任取,x,y,z,A,，假设,R,，,R,，,中间过程,R,。,2024/11/16,定理,6.4.1,设,R,是集合,A,上的二元关系，则：,（,1,）,R,是自反的,I,A,R,；,（,2,）,R,是反自反的,RI,A,；,（,3,）,R,是对称的,RR,-1,；,（,4,）,R,是反对称的,RR,-1,I,A,；,（,5,）,R,是传递的,R,R,R,。,6.4.2,关系性质的判断定理,2024/11/16,证明,（,4,）,“,”,设,R,是反对称的。,对,任意,RR,-1,，则,R,且,R,-1,，,即：,R,且,R,由于,R,是反对称的,，则,ab,所以，I,A,，即,RR,-1,I,A,。,“,”,设,RR,-1,I,A,。,对,任意,a,b,A,，,若,R,且,R，,则有：,R,且,R,-1,，即：,RR,-1,。,又因,RR,-1,I,A,，所以，,I,A,，即,a,b,。,即,R,是反对称的。,2024/11/16,“,”,设,R,是传递的。,对任意,R,R,，,根据,“,”,的定义，,必存在,bA,，,使得,R,且R,，,由,R,的传递性，有,：R,。,所以，,R,R,R,。,“,”,设,R,R,R,。,对任意,a,b,c,A,，,若,R,并且R,，,则有：,R,R,，,因,R,R,R,，所以，,R,，,即,R,是传递的。,证明（,5,）,2024/11/16,定理6.4.2,设,R,S,是定义在,A,上的二元关系，则：,(1),若,R,S,是,自反,的，则,R,-1,RS,RS,R,S,也是,自反的,；,(2),若,R,S,是,反自反的,，则,R,-1,RS,RS,也是,反自反的。,(3),若,R,S,是,对称的,，则,R,-1,RS,RS,也是,对称的,。,(4),若,R,S,是,反对称的，,则,R,-1,RS,也是,反对称的,。,(5),若,R,S,是,传递的,，则,R,-1,RS,也是,传递的。,6.4.3,关系性质的保守性,注意：,（,1,）逆运算与交运算具有较好的保守性；,（,2,）并运算、差运算和复合运算的保守性较差。,2024/11/16,例,试举例说明,:,（,1,）,R,和,S,是反自反、反对称和传递的，,但是，,RoS,不一定具备反自反性，反对称性；,RS,不一定具有反对称性和传递性；,（,2,）,R,和,S,是自反、对称和传递的，,但是,RoS,不一定是对称和传递的，,R-S,不一定是自反和传递的。,解,（,1,）,“,不,”,的例：,设,A=1,2,3,A,上关系,R=,，,S=,。,显然,R,S,都是反自反的、反对称的、传递的。,2024/11/16,解（续）,则,RoS=,，,不具备反自反性和反对称性；,RS=,，,不具备传递性和反对称性；,（,2,）,“,不,”,的例：,设,A=1,2,3,A,上关系,R=,S=,显然,R,S,都是自反的、对称的、传递的。,此时，,RoS=,不具备对称性和传递性；,R-S=,不具备自反性和传递性；,2024/11/16,1.,闭包的定义,定义,6.5.1,设,R,是定义在,A,上的关系，若,存在,A,上的另一个关系,R,，满足：,（,1,）,R,是,自反的,(,对称的,、或,传递的,),；,（,2,）对任何,自反的,(,对称的,、或,传递的,),关系,R,，如果,R,R,，就有,R,R,，,则称为,R,的,自反闭包,(,对称闭包,、或,传递闭包,),，分别记为,r(R),(,s(R),或,t(R),),。,从定义可以看出，,关系的闭包是增加最少元素，使其具备所需性质的扩充。,6.5,关系的闭包运算,2024/11/16,2.,闭包的简单性质,关系,R,有自反性,r(R)=R,关系,R,有,对称,性,S(R)=R,关系,R,有,传递,性,t(R)=R,3.,闭包的计算,定理,6.5.1,设,R,是集合,A,上的二元关系，则：,（,1,）,r(R),RI,A,。,（,2,）,s(R),RR,-1,。,（,3,）,t(R),，若,|A|,n,，则,t(R),。,2024/11/16,例,:,设集合,A=1,2,3,4,，,A,上关系,R=,（,1,）画出,R,的关系图；,（,2,）求出,r(R),s(R),t(R),并画出其相应的关系图。,解,:,（,1,）,R,的关系图见下图；,2,4,1,3,2024/11/16,（续）,（,2,）,r(R)=,；,s(R)=,；,r(R),，,s(R),的关系图分别如下：,r(R)s(R),1,2,3,4,1,2,3,4,2024/11/16,（续）,（,2,）,R=,R,2,=,；,R,3,=,；,R,4,=,=,R,2,；,所以,t(R)=,。,t(R),的关系图分别如下：,t(R),1,2,3,4,2,4,1,3,2024/11/16,例,:,求下列关系的,r(R),s(R),和,t(R),。,（,1,）,定义在整数集,Z,上的“”关系；,（,2,）,定义在整数集,Z,上的“”关系。,解,:,（,1,）,定义在,Z,上的“”关系的,r(R),为“”，,s(R),为“”，,t(R),为“”；,（,2,）,定义在,Z,上的“,=”,关系的,r(R),为“,=”,，,s(R),为“,=”,，,t(R),为“,=”,。,2024/11/16,6.6,本章总结,序偶和笛卡儿积的概念,二元关系的概念和表示,关系的交、并、补、差运算、复合运算和逆运算,关系性质的定义、关系性质的判定、关系性质的证明和关系性质的保守性；,关系的自反、对称、和传递闭包的概念及计算。,2024/11/16,习 题,23,28,页,1-16,Thank You!,