离散数学 ch2.二元关系(3,4节)

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,2-3,关系的性质,本节将研究关系的一些性质，它们在关系的研究,中起着重要的作用。,这是本章最重要的一节,。,本节中所讨论的关系都是集合,A,中的关系。,关系的性质主要有：自反性、反自反性、对称,性、反对称性和传递性。,一,.,自反性（,反身性）,定义,:,设,R,是集合,A,中的关系，如果,对于任意,x,都有（,x,x,）,R (,即,xRx),，,则称,R,是,A,中自反关系。,例如：在实数集合中,“,”,是自反关系，因为，对任意实数,x,，有,x,x,。,是自反，,不是反自反,充分必要条件：,R,是,A,中自反的,A,R,从关系有向图看自反性,:,每个结点都有环。,从关系矩阵看自反性：主对角线都为,1,。,令,A=1,2,3,给定,A,上八个关系如下：,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,3,3,3,3,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,3,3,3,3,R,2,R,1,R,3,R,4,R,5,R,6,R,7,R,8,二,.,反自反性,定义,：设,R,是集合,A,中的关系，如果对于任,意的,xA,都有（,x,x,）,R,，,则称,R,为,A,中的非,自反关系。 （逆否说法,）,充分必要条件：,R,是,A,中非自反的,A,R,F,从关系有向图看非自反性,:,每个结点都无环。,从关系矩阵看非自反性：主对角线都为,0,。,如实数的小于关系,，父子关系是非自反的。,注意,：,1,）,自反和非自反不是互补的,，,一个不是自反的 关系，不一定就是非自反的，如前边,R,6,、,R,7,不是自反,也不是非自反。,2,）若在矩阵中当,r,ii,中既有,0,又有,1,，则,R,既不是自反的也不是反自反的,。,下面,R,2,、,R,5,、,R,8,、,均是反自反关系,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,3,3,3,3,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,3,3,3,3,R,2,R,1,R,3,R,4,R,5,R,6,R,7,R,8,例,1,设,R,是,A,中非自反的,A,R,F,R,是,A,中自反的,A,R,（,1,）,.,自反与反自反,三,.,对称性,定义,:R,是集合,X,中关系,若,对任何,x,yX,如,果有,(x,y),R,必有,(y,x),R,则称,R,为,A,中的,对称关系。,充分必要条件：,R,是,A,上对称的,=,R,C,从关系有向图看对称性,:,在两个不同的结点,之间，,若有,边的话,，,则有方向相反的两条边,从关系矩阵看对称性,：,以主对角线为对称,的矩阵。,如邻居关系，朋友关系，同学关系是对称关,系。,下边,R,3,、,R,4,、,R,6,、,R,8,均是对称关系。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,3,3,3,3,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,3,3,3,3,R,2,R,1,R,3,R,4,R,5,R,6,R,7,R,8,四,.,反对称性,定义,:,设,R,为集合,X,中关系,若对任何,x,yX,如果有,（,x,y),R,和,(y ,x),R,就,有,x=y,则称,R,为,A,中反对称关系 。,如实数的小于关系,，,，均是反对称的。父子关系是反,对称的。,充分必要条件：,R,是,X,上反对称的,R,C,A,由,R,的关系图看非对称性,：,两个不同的结点之间最多有一条边。,从关系矩阵看非对称性,：,以主对角线为对称的两个元素中最多有一个,1,。,1,）的相关矩阵是对称矩阵的转置,2,）若,r,ij,，则,r,ji,=,，但,r,ij,时，,不要求,r,ji,，即,r,ij,r,ji,是允许的。,3,）另外,对称与反对称不是完全对立的，,有些关系,它既是对称也是反对称的，例如,空关系和恒等关系,。,下边,R,1,、,R,2,、,R,4,、,R,5,、,R,8,均是反对称关系。,R,4,、,R,8,既是对称也是反对称的。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,3,3,3,3,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,3,3,3,3,R,2,R,1,R,3,R,4,R,5,R,6,R,7,R,8,（,2,）,对称与反对称,R,是,X,上反对称的,R,C,A,R,是,A,上对称的,=,R,C,五,.,传递性,定义,:R,是,X,中关系，对任何,x,y,zX,如果有（,x,y,）,R,且,(y,z),R,就,有,(x,z),R,则称,R,为,X,中传递关系。,实数集中的、，集合,、,是传递的。,*,从关系关系图和关系矩阵中不易看清是否有传递性。,有时，必须直接根据传递的定义来检查。,检查时要特别注意：,没有传递的条件也不需传递的结果。,即使得传递定义表达式的前件为,F,的时候，此表达式为,T,，,即若（,x,y,）,R,与（,y,z,）,R,有一个是,F,时,(,即定义的前件为假,),，,R,是传递的。,例如,：,若,(,，,),(,，,),中有,1,个不属于,R,，,则讨论,（,a,c),是否属于,R,，,无意义。设,a,b,c,d,，,（，）,（，）,即是传递的。,问题：由对称性与传递性是否可推出自反性,下边,R,1,、,R,3,、,R,4,、,R,5,、,R,8,均是传递的关系,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,3,3,3,3,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,1,。,2,。,。,3,3,3,3,R,2,R,1,R,3,R,4,R,5,R,6,R,7,R,8,（,3,）,可传递与不可传递,自反性,反自反性,对称性,传递性,反对称性,每个结点都有环 主对角线全是,1,每个结点都无环 主对角线全是,0,不同结点间如果有边,则有方向相反的两条边,.,是以对角线为对称 的矩阵,不同结点间,最多有一条边,.,以主对角线为对称的位置不会同时为,1,如果有边（,a,b),（,b,c,）,则也有边（,a,c,）,.,或者定义的前件为假.,如果,a,ij,=1,且,a,jk,=1,则,a,ik,=1,从关系的矩阵,从关系的有向图,性质 判定,例：,1,（，）， ，,自反的，,r,ii,=1;,不对称的，,(1,2) R,1,而,(2,1),R,1,反对称的，传递的。,注：,将改为，则无自反性，且是反自反的。,例：,2,（，），,自反的，不对称的，反对称的，传递的。,例：,3,（,1,，,2,）,1,2,，,1,，,2,（）其中（）是的幂集。,自反的，不对称的，反对称的，传递的。,注：,若,改为，则无自反性。,例：,4,（，）偶数， ，,自反的，对称的，传递的，,因：偶，偶，,则：,（）（,C,）,偶数与偶数之差偶数。,例：,5,（，）（，）（互素），,对称的，但不是自反的，也无传递性。,本节要求：,1.,准确掌握这五个性质的定义。,2.,熟练掌握五个性质的判断和证明。,注意：,判断关系,R,性质时要特别注意使得性质定义表达式的前件为,F,的时候此表达式为,T,，即,R,是满足此性质的。,(,自反和非自反性除外,),2-4,关系的闭包运算,给定,A,中关系,R,，,有时候我们希望,R,具有一些有用的性质，如自反（对称、传递）性，,为此需要在,R,中添加一些序偶而构成新的关系,R,使得,R,具有所需要的性质,但又不希望,R,变得“太大”即希望添加的序偶尽可能的少,满足这些要求的就是的自反（对称、传递）闭包。,关系的闭包是个很有用的概念，特别是传递闭,包。关系的闭包是通过关系的复合和求逆构成的,一个新的关系。这里要介绍关系的自反闭包、对,称闭包和传递闭包。,这里要介绍关系的自反闭包、对称闭包和传递闭包。,一,.,例子,给定,A,中关系,R,，,如图所示，,分别求,A,上另一个关系,R,，,使,得它是包含,R,的,“,最小的,”,(,序偶,尽量少,),分别具有,自反,(,对称、,传递,),性的关系。,这个,R,就分别是,R,的,自反,(,对称、传递,),闭包。,1,。,2,。,。,3,这三个关系图分别是,R,的,自反、对称、传递闭包。,二,.,定义,：,给定,A,中关系,R,若,A,上另一个关系,R,，,满足：,RR,；,R,是自反的,(,对称的、传递的,),；,R,是,“,最小的,”,，即对于任何,A,上自反,(,对称、,传递,),的关系,R”,如果,RR”,就有,RR”,。,则称,R,是,R,的,自反,(,对称、传递,),闭包。记作,r(R),、,(s(R),、,t(R) (,r,eflexive,、,s,ymmetric,、,t,ransitive,),1,。,2,。,。,3,1,。,2,。,。,3,1,。,2,。,。,3,实际上,r(R),、,(s(R),、,t(R),就是包含,R,的,“,最小,”,的,自反,(,对称、,传递,),关系。,三,.,计算方法,定理,1.,给定,A,中关系,R,则,r(R)=R,I,A,。,证明：令,R=R,I,A,显然,R,是自反的和,RR,，,下,面证明,R,是,“,最小的,”,：如果有,A,上自反关系,R”,且,RR”,又,I,A,R”,所以,R,I,A,R”,即,RR”,。,所以,R,就是,R,的自反闭包。即,r(R)=R,I,A,。,定理,2.,给定,A,中关系,R,则,s(R)=R,。,证明方法与,1.,类似。（集合法）,定理,3.,给定,A,中关系,R,则,t(R)=RR,2,R,3,.,。,证明：令,R= RR,2,R,3,.,显然有,RR,；,证,R,是传递的：任取,x,y,zA,设有（,x,y)R,（,y,z)R,由,R,定义得必存在整数,i,j,和,y,使得,(,x,y),R,i,(,y,z)R,j,根据关系的复合得,(,x,z)R,i+j,又因,R,i+j,R,所以R, R,传递,。,证,R,是,“,最小的,”,：如果有,A,上传递关系,R”,且,RR”,（,证出,RR”,即可,）任取,(x,y)R,则由,R,定义得必存在整数,i,使得,(,x,y)R,i,根据关系的复合得,A,中必存在,i-1,个元素,e,1, e,2,.,e,i-1,，,使得,(见,3,4页),（,x, e,1,)R,（,e,1,e,2,）,R,.,（,e,i-1,y,）,R,。,因,RR”,有,(x ,e,1,),R”(e,1,e,2,)R”,.R”,。,由于,R”,传递，所以有,(x,y)R”,。,RR”,。,综上所述，,R,就是,R,的传递闭包，即,t(R)=RR,2,R,3,=,R,i,i=1,用上述,公式计算,t(R),，,要计算,R,的,无穷大次幂,好,象无法实现似的。其实则不然，请看下例:,A=1,2,3 A,中关系,R,1,R,2,如下：,R,1,=(1,2),(1,3),(3,2),R,2,=(1,2),(2,3),(3,1),R,1,2,= ,R,1,3,= ,所以,t(R,1,)=,R,1,R,1,2,R,1,3,= R,1,R,2,2,=,R,2,3,=, =I,A,R,2,4,= R,2,.,t(R,2,)= R,2,R,2,3,R,2,4,定理,4.,给定,A,中关系,R,如果,A,是有限集合，,|,A|=n,则,t(R)=RR,2,.,R,n,。,证明,：,令,R,=RR,2,R,3,.,R,n,，,已知,t(R),R R,2,.,R,n,R,要证,R= t(R) ,只要证,R,R,即可,显然,R R,成立下证,R, R,。,只证对于任意的,k,有,R,k, R,即可,显然当,kn,时,成立,下面证明,k,n,时有,R,k, t(R),成立,：,由,R,定义得,(a,b)R,k,k=1,2, . .,根据关系的复合得,A,中必存在,k-1,个元素,c,1, c,2,.,c,k-1,，,使得 （,a,c,1,)R,且,(c,1,c,2,)R,且,.(c,k-1,b)R,成立,。,上述元素序列:,a=c,0, c,1, c,2,.,c,k-1,b=c,k,中共有,k+1,个元,素，,k+1n ,而,A,中只有,n,个元素，所以上述元素中,至少有两个相同，设,c,j,=,c,i,(i,j),，,于是,R,的关系图中会有下面这些边：,从此图中删去回路中,j-i(,j-i1,),条边后得,(a,b)R,k-(j-i),，,k-(j-i)n,。即,R,k,=,R,k-(j-i),，,所以,(a,b),t(R),于是,对于任意的,k,，,R,k, R ,于是,t(R),R,。,最后得,R,=,t(R),，,所以,t(R)=RR,2,.,R,n,定理证毕。,。,。,。,。,。,。,。,。,a,c,1,c,i,-1,c,i,=,c,j,c,i,+1,。,。,。,。,.,。,c,i,+2,c,j-1,c,j-2,c,j+1,c,j+2,.,.,c,k-1,b,四,.,性质,定理,5,. R,是,A,上关系，则,R,是自反的，当且仅当,r(R)=R., R,是对称的，当且仅当,s(R)=R., R,是传递的,，,当且仅当,t(R)=R.,证明略，因为由,(,三种,),闭包定义即可得。,定理,6,(,作业,P,34,.8),：,设,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,),证明：用定义,练习,：给定,A,中关系,R,如图所示：分别画出,r(R),、,s(R),、,t(R),、,sr(R,),、,rs(R,),、,tr(R,),、,rt(R,),、,st(R,),、,ts(R,),的图。,本节重点掌握闭包的定义、计算方法和性质。,练习,：利用关系图求闭包,给定,A,中关系,R,，,如图所示：分别画,出,r(R),、,s(R),、,t(R),、,sr(R,),、,rs(R,),、,tr(R,),、,rt(R,),、,st(R,),、,ts(R,),的图。,1,。,2,。,。,。,4,3,1,。,2,。,。,。,4,3,1,。,2,。,。,。,4,3,1,。,2,。,。,。,4,3,1,。,2,。,。,。,4,3,1,。,2,。,。,。,4,3,1,。,2,。,。,。,4,3,1,。,2,。,。,。,4,3,1,。,2,。,。,。,4,3,1,。,2,。,。,。,4,3,r(R),s(R),t(R),sr(R,),rs(R,),tr(R,),rt(R,),st(R,),ts(R,),