關(guān)系習題解析

1、1,關(guān)系習題解析——經(jīng)典習題,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是對稱的，則R?R是對稱的；（3）R是反自反和傳遞的，則R是反對稱的；,4,,/*證明思想：根據(jù)定義給出的性質(zhì)證明*/證明：（1）證明思想與（2）和（3）相同（2）設(shè)(a, b)?R?R

3、, 則存在c, (a, c)?R, (c, b)?R; 因為R是對稱的，所以(b, c)?R, (c, a)?R; 所以(b, a)?R?R。則R?R是對稱的。（3）假設(shè)(a, b)?R, (b, a)?R。因為R是傳遞的，所以(a, a)?R，(b, b)?R；因為R是反自反的，所以導(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，因為R是傳遞的，所以(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) 既是對稱的，又是反對稱的；

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

6、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 如果關(guān)系R和S是自反的、對稱的和傳遞的，證明R?S也是自反的、對稱的和傳遞的。證明：a）因為R和S是自反的，對任意的a?A，(a, a)?R并

7、且(a, a)?S，則(a, a)?R?S。b）對任意的a, b?A, a?b，如果(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)?

8、R，(a, c)?S。所以(a, c)? R?S。,12,7 是非判斷：設(shè)R和S是A上的二元關(guān)系，確定下列命題是真還是假。如果命題為真，則證明之；如果命題為假，則給出一個反例。(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是反對稱

9、的。(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)假。

10、R={(1, 2), (2, 1)}, S={(2, 3), (3, 2)}。則R?S={(1, 3)}。,14,(5)真。根據(jù)對稱的性質(zhì)證明。對于任意的 (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)},

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

12、(注意,T是A上的二元關(guān)系.)（1）自反: 對任意a?A,(關(guān)鍵證明(a,a)?T)；因為R是A上的自反關(guān)系, 所以(a,a)?R, (a,a)?R, 因此根據(jù)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(關(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, 因為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 設(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?}，求一個滿足條件的基數(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)系中哪一個是自反的、對稱的、反對稱的或傳遞的?(1) 當且僅當|i - k|8(m, n?N)時, 有mRn;(3) 當且僅當i≤k(i, k?N)時, 有iRk。,解: (1) 是自反的|i - i

16、| 8, 5?3 > 8 ? 2?3 > 8, 不可傳遞的。(3) 是自反的i≤i, 反對稱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)當且僅當a+b=c+d。（1）證明R是等價關(guān)系；（2）計算出A/R。,23,,（1）證明：1）對于任意的(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是對稱的。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ù)來劃分。,24,,13 設(shè)R、S是A上的等價關(guān)系，證明：R?S是A上的等價關(guān)系當且僅當R?S=S?R。,25,,證明思想：1）R?S是A上的等價關(guān)系?R?S=S?R；證明(i)R?S?S?R； (ii)S?R?R?S；2） R?S=S?R? R?S是A上的等價關(guān)系；證明R?S是(i)自反的；(ii)對稱的；(iii)傳遞的；,26,,證明：1）R?S是A上的等價關(guān)系?R?S=S?R：

19、 如果(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；,27,2）自反性：由于R、S自反，因此R?S自反。對稱性：任意(a,b)?R?S，因R?S=S?R，因此(a,b)?S?R，則存在c?A, 使得(a, c

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

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

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, 同樣因為(b,c)?S, 所以存在f?A,使得(b,f)和(f,c)都屬于R, 因為R傳遞, 所以當(a,e)和(e,b)屬于R時,有(a,b)?R,

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

26、)?R時有(b,c)?R。,33,(2) R是A上的一個自反關(guān)系，當(a,b)?R，(a,c)?R必有(b,c)?R，證明R是等價關(guān)系。自反:條件已知；對稱:若(a,b)?R,因為R自反,故(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,注意與條件不同, 當(a,b)?R,(a,c)?R必有(b,c)?R,而要證明的是(a,b

27、)?R,(b,c)?R導(dǎo)出(a,c)?R)證明:因為(a,b)?R,(b,c)?R, 而R對稱,所以(b,a)?R, 現(xiàn)在(b,a)?R,(b,c)?R, 所以根據(jù)條件有(a,c)?R,34,16 確定下列各式是不是A={1,2,3,4,5}上的等價關(guān)系,如果是等價關(guān)系, 請寫出它的等價類。(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) 是，等價類為:[1]=[3]=[5]={1,3,5}[2]={2}[4]={4}

29、(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,證明: 由題設(shè) Rj={(

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