《关系习题解析》PPT课件.ppt

1,关系习题解析经典习题,2,1.设A=a,b,B=0,1,求:A2 B，P(),解:(1)A2B=(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)AP(A)=(a,),(a,a),(a,b),(a,a,b),(b,),(b,a),(b,b),(b,a,b),3,设R是集合A上的关系（1）R是自反的，则RR是自反的；（2）R是对称的，则RR是对称的；（3）R是反自反和传递的，则R是反对称的；,4,/*证明思想：根据定义给出的性质证明*/证明：（1）证明思想与（2）和（3）相同（2）设(a,b)RR,则存在c,(a,c)R,(c,b)R;因为R是对称的，所以(b,c)R,(c,a)R;所以(b,a)RR。则RR是对称的。（3）假设(a,b)R,(b,a)R。因为R是传递的，所以(a,a)R，(b,b)R；因为R是反自反的，所以导致矛盾。,5,3 设R是A上的关系，若R是自反的和传递的，则RR=R。证明思想：证明：1）证明RRR；2）证明RRR：,6,证明：1）证明RRR：设(a,b)RR，存在cA,使得(a,c)R,(c,b)R，因为R是传递的，所以(a,b)R；则RRR；2）证明RRR：设(a,b)R，R是自反的，(b,b)R，所以(a,b)RR；则RRR。所以RR=R。,7,4 举出A=1,2,3上关系R的例子，使其具有下述性质：a)既是对称的，又是反对称的；b)既不是对称的，又不是反对称的；c)是传递的。,8,解：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),9,5 举出一个集合上关系的例子，分别适合于自反、对称、传递中的两个且仅适合两个。,10,解：A=a,b,cA)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)自反，对称，不传递,11,6 如果关系R和S是自反的、对称的和传递的，证明RS也是自反的、对称的和传递的。证明：a）因为R和S是自反的，对任意的aA，(a,a)R并且(a,a)S，则(a,a)RS。b）对任意的a,bA,ab，如果(a,b)RS，因为(a,b)RS，所以(a,b)R并且(a,b)S;因为R和S是对称的，所以(b,a)R并且(b,a)S。则(b,a)RS。c）任意的(a,b)RS，(b,c)RS，则(a,b)R，(a,b)S，(b,c)R，(b,c)S，因为R和S是传递的，因此(a,c)R，(a,c)S。所以(a,c)RS。,12,7 是非判断：设R和S是A上的二元关系，确定下列命题是真还是假。如果命题为真，则证明之；如果命题为假，则给出一个反例。(1)若R和S是传递的，则RS是传递的。(2)若R和S是传递的，则RS是传递的。(3)若R是传递的，则R-1是传递的。(4)若R和S是对称的，则RS是对称的。(5)若R是对称的，则R-1是对称的。(6)若R和S是反对称的，则RS是反对称的。(7)若R和S是反对称的，则R S是反对称的。(8)若R是反对称的，则R-1是反对称的。,13,(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)。则RS=(1,3)。,14,(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)，则RS=(1,2),(2,1)。(7)假。R=(1,3),(2,4),S=(3,2),(4,1),则RS=(1,2),(2,1)，不是反对称的。(8)真。反证法证明。设R-1不是反对称的。则存在(a,b)R-1,(b,a)R-1,ab。则(a,b)R,(b,a)R,与R是反对称的矛盾。,15,8 设R是A上的传递和自反关系,设T是A上的二元关系：(a,b)T当且仅当(a,b)和(b,a)都属于R,证明T是一个等价关系。,16,证明:(注意,T是A上的二元关系.)（1）自反:对任意aA,(关键证明(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.,17,（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。,18,9 设A=a,b,c,d,A上的二元关系R:R=(a,b),(b,a),(b,c),(c,d)试求t(R),并画出它的关系图。,19,20,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。,21,11.下列关系中哪一个是自反的、对称的、反对称的或传递的?(1)当且仅当|i-k|8(m,nN)时,有mRn;(3)当且仅当ik(i,kN)时,有iRk。,解:(1)是自反的|i-i|8,53 8 23 8,不可传递的。(3)是自反的ii,反对称58,但85,58,818,518,可传递的。,22,特殊关系,12 设S=1,2,3,4，并设A=SS，在A上定义关系R为：(a,b)R(c,d)当且仅当a+b=c+d。（1）证明R是等价关系；（2）计算出A/R。,23,（1）证明：1）对于任意的(a,b)SS，因为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，所以根据和的数来划分。,24,13 设R、S是A上的等价关系，证明：RS是A上的等价关系当且仅当RS=SR。,25,证明思想：1）RS是A上的等价关系RS=SR；证明(i)RSSR；(ii)SRRS；2）RS=SR RS是A上的等价关系；证明RS是(i)自反的；(ii)对称的；(iii)传递的；,26,证明：1）RS是A上的等价关系RS=SR：如果(a,b)RS,因为RS是对称的，所以(b,a)RS,所以存在cA,使得(b,c)R,(c,a)S；因为R和S是对称的，所以(c,b)R,(a,c)S；则(a,b)SR；同理，SR RS；,27,2）自反性：由于R、S自反，因此RS自反。对称性：任意(a,b)RS，因RS=SR，因此(a,b)SR，则存在cA,使得(a,c)S,(c,b)R；由R、S的对称性，得(c,a)S,(b,c)R，所以(b,a)RS。,28,传递性：（方法一）因为R,S为A上的等价关系，所以RRR，SSS.下面证(RS)(RS)RS利用已知条件(RS=SR)，所以（RS)(RS)=(RS)(SR)=RSSR因SSS，所以RSSRRSR=SRR因RRR，所以SRRSR=RS 即(RS)(RS)RS，因此传递性得证。,29,传递性：（方法二）任意的(a,b)RS，(b,c)RS，又RS=SR，所以(a,c)(RS)(RS)=(RS)(SR)则存在kA，使得(a,k)RS，(k,c)SR；则存在m，nA，使得(a,m)R，(m,k)S，(k,n)S，(n,c)R；由S等价，因此(m,n)S，那么(a,c)RSR=RRS；则存在p，qA，使得(a,p)R，(p,q)R，(q,c)S；由R等价，因此(a,q)R；所以(a,c)RS。传递性得证。,30,14 设R是一个二元关系,设S=(a,b)|存在某个c,使(a,c)R且(c,b)R。证明：如果R是一个等价关系，则S也是一个等价关系。证明:(1)自反:对任意aA,(证明(a,a)S)。因为R是A上的自反关系,所以(a,a)R,(a,a)R,因此根据S的定义,有(a,a)S.(2)对称:若(a,b)S,则存在cA,使得(a,c)和(c,b)都属于R,因为R对称,因此(b,c)和(c,a)都属于R,故根据S的定义,有(b,a)S,31,(3)传递:若(a,b)S,(b,c)S(关键证明(a,c)S,即要证明存在dA,使得(a,d)和(d,c)都属于R)。由于(a,b)S,所以存在eA,使得(a,e)和(e,b)都属于R,同样因为(b,c)S,所以存在fA,使得(b,f)和(f,c)都属于R,因为R传递,所以当(a,e)和(e,b)属于R时,有(a,b)R,当(b,f)和(f,c)属于R时,有(b,c)R,现在(a,b)和(b,c)属于R,根据S的定义,有(a,c)S。,32,15 设R是A上的一个自反关系，证明：R是一个等价关系当且仅当若(a,b)R，(a,c)R则(b,c)R。证明:(1)R是一个等价关系，则当(a,b)R，(a,c)R必有(b,c)R。因为R对称，所以当(a,b)R时，有(b,a)R，因为R传递，所以当(b,a)R，(a,c)R时有(b,c)R。,33,(2)R是A上的一个自反关系，当(a,b)R，(a,c)R必有(b,c)R，证明R是等价关系。自反:条件已知；对称:若(a,b)R,因为R自反,故(a,a)R,现在(a,b)R,(a,a)R,则根据条件(b,a)R；传递:若(a,b)R,(b,c)R(关键证明(a,c)R,注意与条件不同,当(a,b)R,(a,c)R必有(b,c)R,而要证明的是(a,b)R,(b,c)R导出(a,c)R)证明:因为(a,b)R,(b,c)R,而R对称,所以(b,a)R,现在(b,a)R,(b,c)R,所以根据条件有(a,c)R,34,16 确定下列各式是不是A=1,2,3,4,5上的等价关系,如果是等价关系,请写出它的等价类。(1)(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(1,5),(5,1),(3,5),(5,3)(2)(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(3,4),(4,3);(3)(1,1),(2,2),(3,3),(4,4);(4)(a,b)|4整除a-b,a,bA;(5)(a,b)|3整除a+b,a,bA;(6)(a,b)|a整除2-b,a,bA。,35,(1)是，等价类为:1=3=5=1,3,52=24=4(2)不是.因为(1,3),(3,4)R,而(1,4)R.(3)不是.因为A=1,2,3,4,5,而(5,5)R(4)是，等价类为:1=5=1,5,2=2,3=3,4=4(5)不是.因为A=1,2,3,4,5,而1+1不能被3整除,故(1,1)R(6)不是.因为A=1,2,3,4,5,而5不能整除2-5=-3,故(5,5)R,36,证明:由题设 Rj=(x,y)|x=y(mod j)Rk=(x,y)|x=y(mod k)故(x,y)Rjxy=cj,(对某个cI)(x,y)Rkxy=dk,(对某个dI)a)假设I/Rk细分I/Rj,则RkRj；因此(k,0)Rk(k,0)Rj,故k0=1k=cj于是k是j的整数倍。b)若对某个rI,有 k=rj,则(x,y)Rkxy=ck,(对某个cI)x y=crj,(对某个c,rI)(x,y)Rj。因此Rk Rj,I/Rk细分I/Rj,17 设Rj表示I上模j等价关系,Rk表示I上模k等价关系,证明:I/Rk细分I/Rj当且仅当k是j的整数倍。,