關(guān)系習(xí)題解析

1、1,關(guān)系習(xí)題解析——經(jīng)典習(xí)題,2,1. 設(shè)A = {a, b}, B = {0,1}, 求: A2 ? B ， Ａ ? P(Ａ),解: (1) A2?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

2、)={(a, ?), (a, {a}), (a, ), (a, {a,b}), (b, ?), (b, {a}), (b, ), (b, {a,b})},3,,２ 設(shè)R是集合A上的關(guān)系（1）R是自反的，則R?R是自反的；（2）R是對(duì)稱的，則R?R是對(duì)稱的；（3）R是反自反和傳遞的，則R是反對(duì)稱的；,4,,/*證明思想：根據(jù)定義給出的性質(zhì)證明*/證明：（1）證明思想與（2）和（3）相同（2）設(shè)(a, b)?R?R

3、, 則存在c, (a, c)?R, (c, b)?R; 因?yàn)镽是對(duì)稱的，所以(b, c)?R, (c, a)?R; 所以(b, a)?R?R。則R?R是對(duì)稱的。（3）假設(shè)(a, b)?R, (b, a)?R。因?yàn)镽是傳遞的，所以(a, a)?R，(b, b)?R；因?yàn)镽是反自反的，所以導(dǎo)致矛盾。,5,,3 設(shè)R是A上的關(guān)系，若R是自反的和傳遞的，則R?R=R。 證明思想：證明：1）證明R?R?R； 2） 證明R?R?

4、R：,6,,證明：1）證明R?R?R： 設(shè)(a, b)?R?R，存在c?A, 使得(a, c)?R, (c, b)?R，因?yàn)镽是傳遞的，所以(a, b)?R；則R?R?R；2） 證明R?R?R： 設(shè)(a, b)?R，R是自反的，(b, b)?R，所以(a, b)?R?R；則R?R?R。所以R?R=R。,7,4 舉出A={1, 2, 3}上關(guān)系R的例子，使其具有下述性質(zhì)：a) 既是對(duì)稱的，又是反對(duì)稱的；

5、b) 既不是對(duì)稱的，又不是反對(duì)稱的；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 舉出一個(gè)集合上關(guān)系的例子，分別適合于自反、對(duì)稱、傳遞中的兩個(gè)且僅適合兩個(gè)。,10,,解：A={a, b, c}A)

6、R={(a, a)}對(duì)稱，傳遞, 不自反；B) R={(a, a), (b, b), (c, c), (a, b)}自反，傳遞，不對(duì)稱；C) R={(a, a), (b, b), (c, c), (a, b), (b, c), (b, a), (c, b)}自反，對(duì)稱，不傳遞,11,6 如果關(guān)系R和S是自反的、對(duì)稱的和傳遞的，證明R?S也是自反的、對(duì)稱的和傳遞的。證明：a）因?yàn)镽和S是自反的，對(duì)任意的a?A，(a, a)?R并

7、且(a, a)?S，則(a, a)?R?S。b）對(duì)任意的a, b?A, a?b，如果(a, b)?R?S，因?yàn)?a, b)?R?S，所以(a, b)?R并且(a, b)?S; 因?yàn)镽和S是對(duì)稱的，所以(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，因?yàn)镽和S是傳遞的，因此(a, c)?

8、R，(a, c)?S。所以(a, c)? R?S。,12,7 是非判斷：設(shè)R和S是A上的二元關(guān)系，確定下列命題是真還是假。如果命題為真，則證明之；如果命題為假，則給出一個(gè)反例。(1)若R和S是傳遞的，則R?S是傳遞的。(2)若R和S是傳遞的，則R?S是傳遞的。(3)若R是傳遞的，則R-1是傳遞的。(4)若R和S是對(duì)稱的，則R?S是對(duì)稱的。(5)若R是對(duì)稱的，則R-1是對(duì)稱的。(6) 若R和S是反對(duì)稱的，則R?S是反對(duì)稱

9、的。(7) 若R和S是反對(duì)稱的，則R ? S是反對(duì)稱的。(8) 若R是反對(duì)稱的，則R-1是反對(duì)稱的。,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；又因?yàn)镽是傳遞的，所以(c, a)?R。因此(a, c)?R-1。(4)假。

10、R={(1, 2), (2, 1)}, S={(2, 3), (3, 2)}。則R?S={(1, 3)}。,14,(5)真。根據(jù)對(duì)稱的性質(zhì)證明。對(duì)于任意的 (a, b)? R-1， (b, a)?R； 因?yàn)镽是對(duì)稱的， 則(a, b)?R，所以(b, a)? R-1。則R-1是對(duì)稱的。(6) 假。R={(1, 2)}，S={(2, 1)}，則R?S={(1, 2), (2, 1)}。(7) 假。R={(1, 3), (2, 4)},

11、 S={(3, 2), (4, 1)}, 則R?S={(1, 2), (2, 1)}，不是反對(duì)稱的。(8) 真。反證法證明。設(shè)R-1不是反對(duì)稱的。則存在(a, b)? R-1, (b, a)? R-1, a?b。則(a, b)?R, (b, a)?R, 與R是反對(duì)稱的矛盾。,15,,8 設(shè)R是A上的傳遞和自反關(guān)系, 設(shè)T是A上的二元關(guān)系：(a,b)?T當(dāng)且僅當(dāng)(a,b)和(b,a)都屬于R, 證明T是一個(gè)等價(jià)關(guān)系。,16,,證明:

12、(注意,T是A上的二元關(guān)系.)（1）自反: 對(duì)任意a?A,(關(guān)鍵證明(a,a)?T)；因?yàn)镽是A上的自反關(guān)系, 所以(a,a)?R, (a,a)?R, 因此根據(jù)T的定義,有(a,a)?T.（2）對(duì)稱:若(a,b)?T,則(a,b)和(b,a)都屬于R, 因此(b,a)和(a,b)都屬于R, 所以(b,a)?T.,17,,（3）傳遞: 若(a,b)?T,(b,c)?T(關(guān)鍵證明(a,c)?T,即要證明(a,c)?R,(c,a)?R)。

13、由于(a,b)?T,(b,c)?T,則(a,b)和(b,a)都屬于R,(b,c)和(c,b)都屬于R, 因?yàn)镽傳遞,所以當(dāng)(a,b)和(b,c)都屬于R時(shí),有(a,c)屬于R, 同樣當(dāng)(b,a)和(c,b)都屬于R時(shí),有(c,a)屬于R。因?yàn)?a,c)?R,(c,a)?R, 所以(a,c)?T。,18,9 設(shè)A={a,b,c,d},A上的二元關(guān)系R:R={(a,b), (b,a), (b,c),(c,d)}試求t(R), 并畫出它的

14、關(guān)系圖。,19,,20,10. 給定R={?a, b?,?b, c?,?d, e?}，RS ={?b, d?,?b, b?,?b,e?}，求一個(gè)滿足條件的基數(shù)最小的關(guān)系S 。一般地，若給定R和RS，S能被惟一地確定嗎？基數(shù)最小的S能被惟一地確定嗎？,解: S = {?c, d?, ?c, b?, ?c, e?}。一般地, 若給定R和RS, S不能被惟一地確定。如 S = {?c, d?, ?c, b?, ?c, e?, ?a,

15、b?}也滿足條件。基數(shù)最小的S不能被惟一地確定。例如, R = {?a, b?, ?a, c?}, RS = {?a, a?},基數(shù)最小的 S = {?b, a?} 或 S = {?c, a?}。,21,11. 下列關(guān)系中哪一個(gè)是自反的、對(duì)稱的、反對(duì)稱的或傳遞的?(1) 當(dāng)且僅當(dāng)|i - k|8(m, n?N)時(shí), 有mRn;(3) 當(dāng)且僅當(dāng)i≤k(i, k?N)時(shí), 有iRk。,解: (1) 是自反的|i - i

16、| 8, 5?3 > 8 ? 2?3 > 8, 不可傳遞的。(3) 是自反的i≤i, 反對(duì)稱5≤8, 但8>5, 5≤8, 8≤18, 5≤18, 可傳遞的。,22,特殊關(guān)系,12 設(shè)S={1, 2, 3, 4}，并設(shè)A=S?S，在A上定義關(guān)系R為：(a, b)R(c, d)當(dāng)且僅當(dāng)a+b=c+d。（1）證明R是等價(jià)關(guān)系；（2）計(jì)算出A/R。,23,,（1）證明：1）對(duì)于任意的(a, b)?S?S，因

17、為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是對(duì)稱的。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

18、=c+d，所以根據(jù)和的數(shù)來(lái)劃分。,24,,13 設(shè)R、S是A上的等價(jià)關(guān)系，證明：R?S是A上的等價(jià)關(guān)系當(dāng)且僅當(dāng)R?S=S?R。,25,,證明思想：1）R?S是A上的等價(jià)關(guān)系?R?S=S?R；證明(i)R?S?S?R； (ii)S?R?R?S；2） R?S=S?R? R?S是A上的等價(jià)關(guān)系；證明R?S是(i)自反的；(ii)對(duì)稱的；(iii)傳遞的；,26,,證明：1）R?S是A上的等價(jià)關(guān)系?R?S=S?R：

19、 如果(a, b)?R?S, 因?yàn)镽?S是對(duì)稱的，所以(b, a)?R?S, 所以存在c?A, 使得(b, c)?R, (c, a)?S；因?yàn)镽和S是對(duì)稱的，所以(c, b)?R, (a, c)?S； 則(a, b)?S?R； 同理，S?R ? R?S；,27,2）自反性：由于R、S自反，因此R?S自反。對(duì)稱性：任意(a,b)?R?S，因R?S=S?R，因此(a,b)?S?R，則存在c?A, 使得(a, c

20、)?S, (c,b)?R；由R、S的對(duì)稱性，得(c, a)?S, (b,c)?R，所以(b,a)?R?S。,28,傳遞性：（方法一）因?yàn)镽,S為A上的等價(jià)關(guān)系，所以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     

21、;     因R?R?R，所以S?R?R?S?R =R?S                  即(R?S)?(R?S)?R?S，因此傳遞性得證。,29,傳遞性：（方法二）任意的(a,b)?R?S ，(b,c)?R?

22、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等價(jià)，因此(m,n) ?S，那么(a,c)?R?S?R=R?R?S；則存在p，q?A，使得(a,p)?R，(p,q)?R，(q,c)?S；由R等價(jià)，因此(a,q)?R；所以(a,c)?R?S

23、。傳遞性得證。,30,14 設(shè)R是一個(gè)二元關(guān)系,設(shè)S={(a,b)|存在某個(gè)c,使(a,c)?R且(c,b)?R}。證明：如果R是一個(gè)等價(jià)關(guān)系，則S也是一個(gè)等價(jià)關(guān)系。證明: (1) 自反:對(duì)任意a?A, (證明(a,a)?S)。因?yàn)镽是A上的自反關(guān)系, 所以(a,a)?R, (a,a)?R, 因此根據(jù)S的定義,有(a,a)?S.(2) 對(duì)稱:若(a,b)?S,則存在c?A,使得(a,c)和(c,b)都屬于R, 因?yàn)镽對(duì)稱,

24、因此 (b,c)和(c,a)都屬于R, 故根據(jù)S的定義,有(b,a)?S,31,,(3) 傳遞: 若(a,b)?S,(b,c)?S(關(guān)鍵證明(a,c)?S,即要證明存在d?A,使得(a,d)和(d,c)都屬于R)。由于(a,b)?S, 所以存在e?A,使得(a,e)和(e,b)都屬于R, 同樣因?yàn)?b,c)?S, 所以存在f?A,使得(b,f)和(f,c)都屬于R, 因?yàn)镽傳遞, 所以當(dāng)(a,e)和(e,b)屬于R時(shí),有(a,b)?R,

25、 當(dāng)(b,f)和(f,c)屬于R時(shí),有(b,c)?R, 現(xiàn)在(a,b)和(b,c)屬于R, 根據(jù)S的定義,有(a,c)?S。,32,,15 設(shè)R是A上的一個(gè)自反關(guān)系，證明：R是一個(gè)等價(jià)關(guān)系當(dāng)且僅當(dāng)若(a,b)?R，(a,c)?R則(b,c)?R。證明:(1) R是一個(gè)等價(jià)關(guān)系，則當(dāng)(a,b)?R，(a,c)?R必有(b,c)?R。因?yàn)镽對(duì)稱，所以當(dāng)(a,b)?R時(shí)，有(b,a)?R， 因?yàn)镽傳遞，所以當(dāng)(b,a)?R，(a,c

26、)?R時(shí)有(b,c)?R。,33,(2) R是A上的一個(gè)自反關(guān)系，當(dāng)(a,b)?R，(a,c)?R必有(b,c)?R，證明R是等價(jià)關(guān)系。自反:條件已知；對(duì)稱:若(a,b)?R,因?yàn)镽自反,故(a,a)?R, 現(xiàn)在(a,b)?R,(a,a)?R,則根據(jù)條件(b,a)?R；傳遞: 若(a,b)?R,(b,c)?R (關(guān)鍵證明(a,c)?R,注意與條件不同, 當(dāng)(a,b)?R,(a,c)?R必有(b,c)?R,而要證明的是(a,b

27、)?R,(b,c)?R導(dǎo)出(a,c)?R)證明:因?yàn)?a,b)?R,(b,c)?R, 而R對(duì)稱,所以(b,a)?R, 現(xiàn)在(b,a)?R,(b,c)?R, 所以根據(jù)條件有(a,c)?R,34,16 確定下列各式是不是A={1,2,3,4,5}上的等價(jià)關(guān)系,如果是等價(jià)關(guān)系, 請(qǐng)寫出它的等價(jià)類。(1){(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(1,5),(5,1),(3,5),(5,3)}

28、(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,b?A;(5){(a,b)|3整除a+b},a,b?A;(6){(a,b)|a整除2-b},a,b?A。,35,(1) 是，等價(jià)類為:[1]=[3]=[5]={1,3,5}[2]={2}[4]={4}

29、(2)不是.因?yàn)?1,3),(3,4)?R,而(1,4)?R.(3)不是. 因?yàn)锳={1,2,3,4,5},而(5,5)?R(4)是，等價(jià)類為:　[1]=[5]={1,5},[2]={2},[3]={3},[4]={4}(5)不是.因?yàn)锳={1,2,3,4,5},而1+1不能被3整除,故(1,1)?R(6)不是.因?yàn)锳={1,2,3,4,5},而5不能整除2-5=-3,故(5,5)?R,36,證明: 由題設(shè) Rj={(

30、x, y)|x=y(mod j)}Rk={(x, y)|x=y(mod k)}故 (x, y)?Rj?x–y=cj, (對(duì)某個(gè)c?I) (x, y)?Rk?x–y=dk, (對(duì)某個(gè)d?I) a) 假設(shè)I/Rk細(xì)分I/Rj, 則Rk?Rj ；因此(k, 0)?Rk?(k, 0)?Rj , 故k–0=1k=cj于是k是j的整數(shù)倍。 b) 若對(duì)某個(gè)r?I, 有 k = rj, 則(x, y)?Rk?x–y