关系习题解析

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,关系习题解析,经典习题,1,1.,设,A=a,b,B=0,1,求,:A,2,B,，,P(,),解,:,(1)A,2,B=(a,a),(a,b),(b,a),(b,b),0,1,=,(a,a,0),(a,b,0),(b,a,0),(b,b,0),(a,a,1),(a,b,1),(b,a,1),(b,b,1),(2),A,P(A)=(a,),(a,a),(a,b),(a,a,b,),(b,),(b,a),(b,b),(b,a,b,),2,设,R,是集合,A,上的关系,（,1,）,R,是自反的，则,R,R,是自反的；,（,2,）,R,是对称的，则,R,R,是对称的；,（,3,）,R,是反自反和传递的，则,R,是反对称的；,3,/*,证明思想：根据定义给出的性质证明*,/,证明：,（,1,）证明思想与（,2,）和（,3,）相同,（,2,）设,(a,b),R,R,则存在,c,(a,c),R,(c,b),R;,因为,R,是对称的，所以,(b,c),R,(c,a),R;,所以,(b,a),R,R,。则,R,R,是对称的。,（,3,）假,设,(a,b),R,(b,a)R,。,因为,R,是传递的，所以,(a,a)R,，,(b,b)R,；,因为,R,是反自反的，所以导致矛盾。,4,3,设,R,是,A,上的关系，若,R,是自反的和传递的，则,R,R=R,。,证明思想：,证明：,1,）,证明,R,R,R,；,2,）,证明,R,R,R,：,5,证明：,1,）证明,R,R,R,：,设,(a,b),R,R,，,存在,c,A,使得,(a,c),R,(c,b),R,，,因为,R,是传递的，所以,(a,b),R,；,则,R,R,R,；,2,）,证明,R,R,R,：,设,(a,b),R,，,R,是自反的，,(b,b),R,，,所以,(a,b),R,R,；则,R,R,R,。,所以,R,R=R,。,6,4,举出,A=1,2,3,上关系,R,的例子，使其具有下述性质：,a),既是对称的，又是反对称的；,b),既不是对称的，又不是反对称的；,c),是传递的。,7,解,：,a),R=(1,1),(2,2),(3,3),b),R=(1,2),(2,1),(2,3),c),R=(1,2),(2,1),(1,1),(2,2),(3,3),8,5,举出一个集合上关系的例子，分别适合于自反、对称、传递中的两个且仅适合两个。,9,解：,A=a,b,c,A),R=(a,a),对称，传递,不自反；,B),R=(a,a),(b,b),(c,c),(a,b),自反，传递，不对称；,C),R=(a,a),(b,b),(c,c),(a,b),(b,c),(b,a),(c,b),自反，对称，不传递,10,6,如果关系,R,和,S,是自反的、对称的和传递的，证明,R,S,也,是自反的、对称的和传递的。,证明,：,a,）,因为,R,和,S,是自反的，对任意的,a,A,，,(a,a),R,并且,(a,a)S,，则,(a,a),R,S,。,b,）,对任意的,a,b,A,ab,，,如果,(a,b),R,S,，,因为,(a,b),R,S,，,所以,(a,b),R,并且,(a,b)S,;,因为,R,和,S,是对称的，所以,(b,a),R,并且,(b,a)S,。则,(b,a),R,S,。,c,）,任意的,(a,b),R,S,，,(b,c),R,S,，则,(a,b),R,，,(a,b),S,，,(b,c),R,，,(b,c)S,，因为,R,和,S,是传递的，,因此,(a,c),R,，,(a,c)S,。所以,(a,c),R,S,。,11,7,是非判断：设,R,和,S,是,A,上的二元关系，确定下列命题是真还是假。如果命题为真，则证明之；如果命题为假，则给出一个反例。,(1),若,R,和,S,是传递的，则,R,S,是传递的。,(2),若,R,和,S,是传递的，则,R,S,是传递的。,(3),若,R,是传递的，则,R,-1,是传递的。,(4),若,R,和,S,是对称的，则,R,S,是对称的。,(5),若,R,是对称的，则,R,-1,是对称的。,(6),若,R,和,S,是反对称的，则,R,S,是反对称的。,(7),若,R,和,S,是反对称的，则,R,S,是反对称的。,(8),若,R,是反对称的，则,R,-1,是反对称的。,12,(1),假。,R=(1,2),S=(2,3),。,(2),假。,R=(1,4),(2,5),S=(4,2),(5,3),。,(3),真。任意,(a,b),R,-1,(b,c),R,-1,。所以,(,c,b),R,(b,a),R,；又因为,R,是传递的，所以,(c,a),R,。因此,(a,c),R,-1,。,(4),假。,R=(1,2),(2,1),S=(2,3),(3,2),。则,R,S=(1,3),。,13,(5),真。根据对称的性质证明。对于任意的,(a,b),R,-1,，,(b,a)R,；因为,R,是对称的，则,(a,b),R,，所以,(b,a),R,-1,。,则,R,-1,是对称的。,(6),假,。,R=(1,2),，,S=(2,1),，则,R,S=(1,2),(2,1),。,(7),假。,R=(1,3),(2,4),S=(3,2),(4,1),则,R,S=(1,2),(2,1),，不是反对称的。,(8),真。反证法证明。设,R,-1,不是反对称的。则存在,(a,b),R,-1,(b,a),R,-1,a,b,。则,(a,b),R,(b,a),R,与,R,是反对称的矛盾。,14,8,设,R,是,A,上的传递和自反关系,设,T,是,A,上的二元关系：,(a,b),T,当且仅当,(a,b),和,(b,a),都属于,R,证明,T,是一个等价关系。,15,证明,:(,注意,T,是,A,上的二元关系,.),（,1,）自反,:,对任意,a,A,(,关键证明,(a,a),T),；,因为,R,是,A,上的自反关系,所以,(a,a,),R,(,a,a),R,因此根据,T,的定义,有,(a,a,),T.,（,2,）,对称,:,若,(a,b),T,则,(a,b,),和,(,b,a),都属于,R,因此,(b,a,),和,(,a,b),都属于,R,所以,(b,a),T.,16,（,3,）传递,:,若,(a,b),T,(b,c),T(,关键证明,(a,c),T,即要证明,(a,c),R,(c,a),R),。,由于,(a,b),T,(b,c),T,则,(a,b),和,(b,a),都属于,R,(b,c),和,(c,b),都属于,R,因为,R,传递,所以当,(a,b),和,(b,c),都属于,R,时,有,(a,c),属于,R,同样当,(b,a),和,(c,b),都属于,R,时,有,(c,a),属于,R,。,因为,(a,c),R,(c,a),R,所以,(a,c),T,。,17,9,设,A=a,b,c,d,A,上的二元关系,R:R=(a,b),(b,a),(b,c),(c,d),试求,t(R),并画出它的关系图。,18,19,10.,给定,R=a,b,b,c,d,e,，,RS=b,d,b,b,b,e,，求一个满足条件的基数最小的关系,S,。一般地，若给定,R,和,RS,，,S,能被惟一地确定吗？基数最小的,S,能被惟一地确定吗？,解,:S=c,d,c,b,c,e,。,一般地,若给定,R,和,RS,S,不能被,惟一,地确定。,如,S=c,d,c,b,c,e,a,b,也满足条件。,基数最小的,S,不,能被,惟一,地确定。,例如,R=a,b,a,c,RS=a,a,基数最小的,S=b,a,或,S=c,a,。,20,11.,下列关系中哪一个是自反的、对称的、反对称的或传递的,?(1),当且仅当,|i-k|8(m,n,N,),时,有,mRn,;(3),当且仅当,ik(i,k,N,),时,有,iRk,。,解,:(1),是自反的,|i-i|11,对称的,|i-k|=|k-i|,|,2-10|11,|,10-18|11,|,2-18|,11,不可传递的。,(2),是非自反的,2,2 8,5,3 8,2,3 8,不可传递的。,(3),是自反的,ii,反对称,58,但,85,58,818,518,可传递的。,21,特殊关系,12,设,S=1,2,3,4,，,并设,A=S,S,，在,A,上定义关系,R,为：,(a,b)R(c,d),当且仅当,a+b=c+d,。,（,1,）,证明,R,是等价关系；,（,2,）计算出,A/R,。,22,（,1,）证明：,1,）对于任意的,(,a,b),S,S,，,因为,a+b=a+b,，,所以,(,a,b)R,(,a,b),，即,R,是自反的,。,2,）如果,(,a,b)R(c,d),，则,a+b=c+d,，,那么有,c+d=a+b,；,所以,(c,d)R(a,b),，即,R,是对称的,。,3,）如果,(,a,b)R(c,d),，,(c,d)R(e,f),，则,a+b=c+d,，,c+d=e+f,；,所以,a+b=e+f,，得,(,a,b)R(e,f),，即,R,是传递的。,（,2,）如果,(,a,b)R(c,d),，则,a+b,=,c+d,，所以根据和的数来划分。,23,13,设,R,、,S,是,A,上的等价关系，证明：,R,S,是,A,上的等价关系,当且仅当,R,S=S,R,。,24,证明思想：,1,）,R,S,是,A,上的等价关系,R,S=S,R,；,证明,(,i)R,S,S,R,；,(,ii)S,R,R,S,；,2,）,R,S=S,R,R,S,是,A,上的等价关系；,证明,R,S,是,(i),自反的；,(ii),对称的,；,(iii),传递的；,25,证明：,1,）,R,S,是,A,上的等价关系,R,S=S,R,：,如果,(a,b),R,S,因为,R,S,是对称的，所以,(b,a),R,S,所以存在,c,A,使得,(b,c),R,(c,a),S,；,因为,R,和,S,是对称的，所以,(c,b),R,(a,c),S,；,则,(a,b),S,R,；,同理，,S,R,R,S,；,26,2,）,自反性,：由于,R,、,S,自反，因此,R,S,自反。,对称性,：任意,(,a,b),R,S,，因,R,S=S,R,，因此,(,a,b),S,R,，则存在,c,A,使得,(a,c),S,(,c,b),R,；由,R,、,S,的对称性，得,(c,a),S,(,b,c),R,，所以,(,b,a),R,S,。,27,传递性,：（方法一）因为,R,S,为,A,上的等价关系，所以,R,R,R,，,S,S,S,.,下面证,(R,S)(R,S),R,S,利用已知条件,(R,S=S,R),，所以,（,R,S)(R,S)=(R,S)(S,R)=R,S,S,R,因,S,S,S,，所以,R,S,S,R,R,S,R=S,R,R,因,R,R,R,，所以,S,R,R,S,R=R,S,即,(R,S),(R,S),R,S,，因此传递性得证。,28,传递性,：（方法二）,任意的,(,a,b),R,S,，,(,b,c),R,S,，又,R,S=S,R,，所以,(,a,c),(,R,S,),(,R,S)=(R,S),(S,R),则存在,k,A,，使得,(,a,k),R,S,，,(,k,c),S,R,；,则存在,m,，,n,A,，使得,(,a,m),R,，,(,m,k),S,，,(,k,n),S,，,(,n,c,),R,；,由,S,等价，因此,(,m,n,),S,，那么,(,a,c),R,S,R,=R,R,S,；,则存在,p,，,q,A,，使得,(,a,p),R,，,(,p,q),R,，,(,q,c),S,；,由,R,等价，因此,(,a,q),R,；,所以,(,a,c),R,S,。,传递性得证。,29,14,设,R,是一个二元关系,设,S=(a,b)|,存在某个,c,使,(a,c),R,且,(c,b),R,。证明：如果,R,是一个等价关系，则,S,也是一个等价关系。,证明,: