《《关系习题解析》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《关系习题解析》PPT课件.ppt(36页珍藏版)》请在三一办公上搜索。
1、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、(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
3、;则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
4、),(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 是非判
5、断:设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
6、。所以(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
7、,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
8、)。由于(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能被惟一地
9、确定吗?,解: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=
10、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上的等价
11、关系,证明: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,则存在
12、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,(
13、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对称,因此(
14、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,
15、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导出(
16、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)
17、|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的整数倍。,
链接地址:https://www.31ppt.com/p-5579074.html