復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與工程系 吳永輝 離散數(shù)學(xué) 集合論 第二章 關(guān)系

1、第二章 關(guān)系2.1 二元關(guān)系2.2 關(guān)系的性質(zhì)2.3 關(guān)系的運(yùn)算2.4 關(guān)系數(shù)據(jù)庫的一個(gè)實(shí)例2.5 關(guān)系的閉包2.6 等價(jià)關(guān)系與劃分2.7 次序關(guān)系引言在現(xiàn)實(shí)生活中, 集合與集合之間還存在著某種聯(lián)系。現(xiàn)實(shí)世界中的二元關(guān)系1，同一個(gè)集合中的二元關(guān)系：同學(xué)關(guān)系、同桌關(guān)系2，兩個(gè)不同集合之間的二元關(guān)系：師生關(guān)系、學(xué)生和選修課程的關(guān)系現(xiàn)實(shí)世界中的多元關(guān)系學(xué)生、課程和任課教師的關(guān)系關(guān)系在現(xiàn)實(shí)世界和信息世界中的表示關(guān)系在現(xiàn)實(shí)世界中的表示： 表格 關(guān)系在信息世界中的表示 數(shù)據(jù)庫形式化和非形式化的描述形式化描述數(shù)學(xué)、精確無二義、難理解非形式化描述自然語言、不精確、易理解2.1 二元關(guān)系一 定義2.1（二元關(guān)系

2、） 設(shè)A和B是任意兩個(gè)集合，AB的子集R稱為從A到B的二元關(guān)系。當(dāng)A=B時(shí)，稱R為A上的二元關(guān)系。若(a, b)R，則稱a與b有關(guān)系R，記為aRb。 術(shù)語：(a, b)R：a與b沒有關(guān)系RR=：空關(guān)系R=AB：全關(guān)系由定義2.1，得出：1）二元關(guān)系是集合；2）二元關(guān)系的元素是有序?qū)Α?.1 二元關(guān)系例：設(shè)A=1, 2, 3, 4, 5，A上共有多少個(gè)二元關(guān)系？ 因?yàn)锳上的二元關(guān)系R是AA的子集，是AA的冪集中的元素。 西安交通大學(xué)1998考研解：因?yàn)锳上的二元關(guān)系R是AA的子集，|AA|=25，|P(AA)|=225所以A上的二元關(guān)系R的個(gè)數(shù)是225。 2.1 二元關(guān)系二 定義2.2（定義域，

3、值域） 設(shè)R是從A到B的二元關(guān)系，A的一個(gè)子集a|存在b，使得(a, b)R稱為R的定義域，記為Dom R。B的一個(gè)子集b|存在a，使得 (a, b)R稱為R的值域，記為Ran R。 A稱為R的前域，B稱為R的陪域，并且Dom RA，Ran RB。例2.1, 2.2, 2.3例2.1 整除關(guān)系 設(shè)A=2, 3, 4, B=3, 4, 5, 6, 7, 定義從A到B的二元關(guān)系R: (a, b)Ra整除b。 R=(2, 4), (2, 6), (3, 3), (3, 6), (4, 4) Dom R=2, 3, 4, Ran R=3, 4, 6.例2.2 A=1, 2, 3, 4上的小于關(guān)系R:

4、(a, b)R a0，RkRR2R3Rn。*/證明：/*分而治之*/對于kn，必有RkRR2R3Rn 。對于kn，若(a, b)Rk，則存在元素個(gè)數(shù)為k+1的元素序列c0, c1, , ck, c0=a, ck=b, 并且對1ik，(ci-1, ci)R。由于kn ，所以在元素序列中必有元素ci不止出現(xiàn)一次，即(a, c1), (c1, c2), , (ci-1, ci), (ci, cp), , (cq, ci), (ci, ci+1), , (ck-1, b) R，在刪去(ci, cp), , (cq, ci)這一段后，如果序列中元素個(gè)數(shù)仍大于n，則繼續(xù)上述過程，直到序列中元素個(gè)數(shù)kn為止

5、。此時(shí)有(a, b)Rk，所以(a, b)RR2R3 Rn。2 .5 關(guān)系的閉包四 其他性質(zhì)定理2.11 設(shè)R是A上的二元關(guān)系。若R是自反的，則s(R)和t(R)都是自反的；若R是對稱的，則r(R)和t(R)都是對稱的；若R是傳遞的，則r(R)是傳遞的。證明思想：根據(jù)自反，對稱和傳遞定義所滿足的性質(zhì)進(jìn)行證明定理2.12 設(shè)R是A上的二元關(guān)系。rs(R)=sr(R)rt(R)=tr(R)ts(R) st(R)公式法：等式推導(dǎo)；基本法證明： （公式法：等式推導(dǎo)）（1）右式= sr(R)= s(RIA)= (RIA) (RIA) 1= RIA R-1IA-1 = RR-1IA = r(RR-1)=r

6、s(R)=左式證明： （公式法：等式推導(dǎo)）（2）右式=tr(R)=t(RIA)= (RIA) (RIA)2 (RIA)3 /*可以證明(RIA) n= IARR2 Rn*/= IARR2= IAt(R)=rt(R)=左式證明： （公式法：等式推導(dǎo)）（3）由于s(R)=RR-1R, 根據(jù)定理2.6，有ts(R)t(R)， sts(R)st(R)。而由定理 2.11可知，ts(R)是對稱的，所以sts(R)=ts(R)。因此ts(R)st(R)。2.6 等價(jià)關(guān)系與劃分一 等價(jià)關(guān)系與劃分1 定義2.12（劃分） 設(shè)A是一個(gè)集合。AiA, Ai , i=1, , n。若A1 A2 An=A， Ai A

7、j=（i, j=1, n, ij），則稱=A1, A2, , An是A的一個(gè)劃分。其中每個(gè)Ai稱為劃分的一個(gè)塊。/*物以類聚，人以群分*/例2.21 設(shè)A=a, b, c，A的子集組成的集合：P=a,b, cS=a, b, cT=a, b, cU=a, cV=a, b, b, cW=a, b, a, c, cP, S, T是A的劃分，其他不是A的劃分。2 劃分的塊數(shù)可以是無限的例2.22：整數(shù)I的劃分:1=E, O，其中E為偶數(shù)集，O為奇數(shù)集；2=0, -1, 1, -2, 2, -3, 3, 也是I的一個(gè)劃分。3 定義2.13（等價(jià)關(guān)系） 設(shè)R是A上的二元關(guān)系，若R是自反的、對稱的和傳遞的，

8、則稱R是A上的等價(jià)關(guān)系。若aRb，則稱a與b等價(jià)。例2.23 設(shè)A是一個(gè)學(xué)生集合, 定義A上二元關(guān)系R: (a, b)R當(dāng)且僅當(dāng)a與b同年齡. R是等價(jià)關(guān)系.2.6 等價(jià)關(guān)系與劃分二 術(shù)語1 定義2.14（等價(jià)類） 設(shè)R是A上的等價(jià)關(guān)系，對于每個(gè)aA，與a等價(jià)的元素全體所組成的集合稱為由a生成的關(guān)于R的等價(jià)類，記為aR，即 aR =x | xA，xRa，a稱為該等價(jià)類的代表元。 aR簡記為a。2 定義2.15（商集） 設(shè)R是A上的等價(jià)關(guān)系，關(guān)于R的等價(jià)類全體所組成的集合族稱為A上關(guān)于R的商集，記為A/R，即A/R=a| aA。2.6 等價(jià)關(guān)系與劃分三 性質(zhì)定理2.13 設(shè)R是A上的等價(jià)關(guān)系，則

9、（1）對任一aA，有aa；（2）對a, bA，如果aRb，則a=b;（3）對a, bA，如果(a, b)R，則ab=;（4）aAa=A。/*（1）根據(jù)定義的性質(zhì)進(jìn)行證明；*/證明：由于R是自反的，即aRa，所以aa。/*（2）基本法證明；*/證明：/*先證明ab*/ 對任一ca，有cRa，又由假設(shè)aRb，根據(jù)R是傳遞的，必有cRb，即cb，從而ab；/*再證明ba */ 對任一cb，有cRb，又由假設(shè)aRb，根據(jù)R是傳遞的，必有cRa，即ca，從而ba； 所以a=b。/*（3）反證法證明；*/證明：設(shè)(a, b)R，如果ab; 假設(shè)cab, 則ca且cb, 從定義可知cRa，cRb。由R的對稱

10、性和傳遞性，必有aRb，導(dǎo)致矛盾。所以ab= 。/*（4）基本法證明 */證明：對任一caAa，存在b使cb。而bA，從而cA，所以aAa=A 。定理2.13(1): A中每個(gè)元素所產(chǎn)生的等價(jià)類都是非空的；定理2.13(2)(3): 互相等價(jià)的元素屬于同一個(gè)等價(jià)類, 不等價(jià)的元素所屬的等價(jià)類沒有公共元素;定理2.13(4): A上關(guān)于R的商集A/R= a | aA 就是A的一個(gè)劃分, a是該劃分的一個(gè)塊.2.6 等價(jià)關(guān)系與劃分定理2.14 集合A上的任一劃分可以確定A上的一個(gè)等價(jià)關(guān)系R。由建立的等價(jià)關(guān)系R=(A1A1)(A2A2) (AnAn)證明R=(A1A1)(A2A2) (AnAn)是一

11、個(gè)等價(jià)關(guān)系，即證明R是自反、對稱和傳遞的。構(gòu)造性證明的思想例2.26 設(shè)A= a, b, c, d, e, f 的一個(gè)劃分=a, b, c, d, e, f,由確定A上的一個(gè)等價(jià)關(guān)系R: R=(a, ba, b) (c, d c, d)(e, f e, f)=(a, a), (a, b), (b, a), (b, b), (c, c), (c, d), (d, c), (d, d), (e, e), (e, f), (f, e), (f, f)定理2.15 設(shè)R1和R2是A上的等價(jià)關(guān)系， R1=R2 A/R1=A/R2 。定理2.13和定理2.15: 任一等價(jià)關(guān)系唯一確定一個(gè)劃分.定理2.14

12、和定理2.15: 任一劃分唯一確定一個(gè)等價(jià)關(guān)系.定理2.16 設(shè)R1和R2是A上的等價(jià)關(guān)系，則 R1R2是A上的等價(jià)關(guān)系。例：設(shè)A=1, 2, 3, 4, 5，A上的二元關(guān)系R中，有多少個(gè)是等價(jià)關(guān)系？ 因?yàn)榈葍r(jià)類劃分和等價(jià)關(guān)系是一一對應(yīng)的，所以A上的二元關(guān)系中等價(jià)關(guān)系的個(gè)數(shù)等于A的劃分個(gè)數(shù)。 西安交通大學(xué)1998考研解：對于A的劃分可分為如下幾種情況：（1） 劃分成5個(gè)都只含1個(gè)元素的塊，共有1種；（2） 劃分成1個(gè)都只含2個(gè)元素，3個(gè)都只含1個(gè)元素的塊，共有10種；（3） 劃分成2個(gè)都只含2個(gè)元素，1個(gè)都只含1個(gè)元素的塊，共有15種；（4） 劃分成1個(gè)都只含3個(gè)元素，2個(gè)都只含1個(gè)元素的塊，

13、共有10種；（5） 劃分成1個(gè)都只含3個(gè)元素，1個(gè)都只含2個(gè)元素的塊，共有10種；（6） 劃分成1個(gè)都只含4個(gè)元素，1個(gè)都只含1個(gè)元素的塊，共有5種；（7） 劃分成1個(gè)都只含5個(gè)元素的塊，共有1種；綜上所述，A上的等價(jià)關(guān)系共有1+10+15+10+10+5+1=52 2.6 等價(jià)關(guān)系與劃分四、劃分的積定義2.16 (劃分的積) 設(shè)R1和R2是A上的等價(jià)關(guān)系，由R1和R2確定A的劃分分別為1和2，A上的等價(jià)關(guān)系R1R2確定的劃分，稱為1與2劃分的積，記為12。例：A是學(xué)生集合, R1是A上的同年級(jí)關(guān)系，R2是A上的同專業(yè)關(guān)系。則R1R2是A上的同年級(jí)并且同專業(yè)的關(guān)系。定義2.17(細(xì)分) 設(shè)和是

14、A的劃分，若的每一塊包含在的一塊中，稱細(xì)分，或稱加細(xì)。例： A是學(xué)生集合，是在A中按學(xué)院的劃分， 是在A中按專業(yè)的劃分。定理2.17 設(shè)和是A的劃分，它們確定A上的等價(jià)關(guān)系R和R，則細(xì)分當(dāng)且僅當(dāng)RR。例： A是學(xué)生集合，是在A中按學(xué)院的劃分， 是在A中按專業(yè)的劃分。和確定A上的等價(jià)關(guān)系R和R分別是同學(xué)院同學(xué)關(guān)系和同專業(yè)同學(xué)關(guān)系，RR。證明：/*細(xì)分 RR ，基本法*/對于任一(a, b)R，存在的某塊S，使a, bS。因?yàn)榧?xì)分，所以必存在一塊S，使SS。因此a, bS，從而(a, b)R。/* RR 細(xì)分 */設(shè)S是的一塊，aS則S=aR=x|xRa。對S中的每一個(gè)x，因?yàn)镽R，所以由xRa可

15、推出xRa。因此x|xRax|xRa，即 aRZaR。的一塊包含在的一塊中，所以細(xì)分。定理2.18(12與1和2的聯(lián)系) 設(shè)1和2是A的劃分，則（1） 12細(xì)分1和2；（2）設(shè)是A的劃分，若細(xì)分1和2，則細(xì)分12。/* 12細(xì)分1和2；并且是同時(shí)細(xì)分1和2的最小劃分（劃分塊數(shù)最少）*/證明：（1）由R1R2R1, R1R2R2，即得。（2）若RR1，R R2則RR1R2即得。例2.27 設(shè)學(xué)生集合A=a, b, c, d, e, f, g, h, i, j, k，按同年齡分為一組，得A的劃分：1 =a, b, c, d, e, f, g, h, i, j, k。按同班級(jí)分為一組，得A的劃分：2

16、 =a, b, c, h, d, i, e, f, j, k, g。 12 =a, b, c, d, e, f, g, h, i, j, k 同一組內(nèi)任兩個(gè)學(xué)生既在同年齡組中，又在同班級(jí)組中。 不在12同一組中的兩個(gè)學(xué)生，還可能在同一年齡組中或同一班級(jí)組中。五、劃分的和定理2.19 設(shè)R1和R2是A上的等價(jià)關(guān)系，則(R1R2)+是A上的等價(jià)關(guān)系。定義2.18 (劃分的和) 設(shè)R1和R2是A上的等價(jià)關(guān)系，由R1和R2確定A的劃分分別為1和2，A上的等價(jià)關(guān)系(R1R2)+所確定A的劃分稱為1和2劃分的和，記為1+2。定理2.20 設(shè)1和2是A的劃分，則（1） 1與2細(xì)分1+2；（2）設(shè)是A的劃分，

17、若1和2細(xì)分，則1+2細(xì)分。1+2被1與2細(xì)分，并且是同時(shí)被1與2細(xì)分的最大劃分（劃分的塊數(shù)最多）證明:(1)由R1(R1R2)+, R2(R1R2)+,即得.(2)若R1R , R2R 則R1R2R .由閉包定義的第三條件可知(R1R2)+R , 即(R1R2)+是包含R1R2的最小的等價(jià)關(guān)系.例2.28 在例2.27中, 學(xué)生集合的劃分為1, 2, 1+2=a, b, c, d, h, i, e, f, j, k在1+2同一組中的任兩個(gè)學(xué)生不是在1中，就是在2中，不在1+2同一組中的任兩個(gè)學(xué)生必定不在同一年齡組中，也不在同一班級(jí)組中。定理2.21 設(shè)集合A，對于a, bA，a, b在1+2

18、的同一塊中，當(dāng)且僅當(dāng)在A中存在元素序列a, c1, , ck, b，使得序列中每相鄰兩個(gè)元素在1的同一塊中或在2的同一塊中。證明：由1+2的定義可知， a, b在1+2的同一塊中，對應(yīng)于(a, b)(R1R2)+ ，由定理2.9知，存在正整數(shù)k+1，使a(R1R2)k+1b，即存在k個(gè)元素c1, , ckA， 使a(R1R2)c1, , ck(R1R2)b。因?yàn)镽1，R2是A 上的等價(jià)關(guān)系，所以a, c1在1或2的同一塊中，ck, b在1或2的同一塊中， a和b是鏈接的。反之亦然。 2.7 次序關(guān)系一 偏序關(guān)系、偏序集定義2.19(偏序關(guān)系) 設(shè)R是A上的二元關(guān)系，若 R是自反的、反對稱的和傳

19、遞的，則稱R是A上的偏序關(guān)系。又記為。（并不意味小于等于）常見的偏序關(guān)系：, 定義2.20(偏序集) 若集合A具有偏序關(guān)系R（或 ），則稱A為偏序集，記為（A, R）或（A, ）。哈斯圖：表示偏序集。若a b，則結(jié)點(diǎn)a在b之下；若a與b之間不存在其他元素c，使a c，c b則在a與b之間用一線相連。2.7 次序關(guān)系例2.29例2.30題目類型：給出集合和集合上的二元關(guān)系，畫出哈斯圖。判斷是否正確，并說明理由。設(shè)A和B為集合，R是A的冪集P(A)上的二元關(guān)系，對所有S, TP(A)，(S, T)R。當(dāng)且僅當(dāng)|S|T|，R是偏序關(guān)系。/*復(fù)旦大學(xué)1999考研*/證明整除關(guān)系是正整數(shù)集合上的偏序關(guān)系

20、。/*北京師范大學(xué)1999考研*/2.7 次序關(guān)系二 擬序關(guān)系定義2.21（擬序關(guān)系） A上的二元關(guān)系 R是反自反的和傳遞的，稱R為A上的擬序關(guān)系。稱(A, R)為擬序集，或記為(A, )。（不意味著小于）定理2.22 A上的二元關(guān)系 R是擬序的，則R必為反對稱的。證明：反證法2.7 次序關(guān)系定理2.23 設(shè)R是A上的二元關(guān)系，則(1)若R是A上的擬序關(guān)系，則r(R)=RIA是A上的偏序關(guān)系；(2) R是A上的偏序關(guān)系，則R-IA是A上的擬序關(guān)系；證明方法：根據(jù)定義給出的性質(zhì)證明。2.7 次序關(guān)系三 全序關(guān)系定義2.22（全序關(guān)系） 設(shè)是集合A 上的二元關(guān)系，如果對于A中任意兩個(gè)元素a, bA

21、，必有a b或b a，則稱 是A上的全序關(guān)系（或線性次序關(guān)系）。定義2.23（全序集） 若集合A具有全序關(guān)系 或R，則稱A為全序集或線性次序集，記為(A, )或(A, R) 。實(shí)例：字典序2.7 次序關(guān)系四 最大元、最小元、極大元、極小元定義2.22（最大元、最小元、極大元、極小元）設(shè)偏序集(A, )，BA，(1)最大元、最小元 若存在一個(gè)元素bB，對所有bB都有b b，則稱b是B的最大元；若都有b b，則稱b是B的最小元；(2)極大元、極小元 若存在一個(gè)元素bB，且在B中不存在元素b使bb，b b，則稱b是B的極大元；若在B中不存在元素b使bb，b b ，則稱b是B的極小元；2.7 次序關(guān)系

22、(3)上界、下界 若存在一個(gè)元素aA，對所有bB都有ba，則稱a是B的上界；對所有bB都有ab，則稱a是B的下界；(4)上確界、下確界 若aA是B的上界且對B的每個(gè)上界a都有a a，則稱a是B的上確界（最小上界）；若aA是B的下界且對B的每個(gè)下界a都有aa，則稱a是B的下確界（最大下界）。2.7 次序關(guān)系定理2.24 設(shè)偏序集(A, )，BA，若在B中存在最大元（最小元），則必唯一。證明： （反證）定理2.25 設(shè)偏序集（A, ）, BA，在B中存在最大元（最小元）必為極大元（極小元）。例2.32, 2.33(題目類型)寫出集合A=a, b, c的冪集P(A)，并畫出偏序集(P(A), )的哈

23、斯圖。/*北京航空航天大學(xué)1996考研試題*/數(shù)學(xué)教育對計(jì)算機(jī)科學(xué)專業(yè)人才的培養(yǎng)目的通過教學(xué)使學(xué)生掌握進(jìn)一步學(xué)習(xí)這一學(xué)科所需要的數(shù)學(xué)知識(shí)；通過嚴(yán)格的數(shù)學(xué)訓(xùn)練，使學(xué)生實(shí)現(xiàn)思維方式或思維過程的數(shù)學(xué)化。思維方式的數(shù)學(xué)化從普通人的思維方式轉(zhuǎn)向數(shù)學(xué)家工作的思維方式： 通過對事物的抽象，運(yùn)用特殊的符號(hào)或語言系統(tǒng)，研究事物在空間中的數(shù)量關(guān)系、位置關(guān)系、結(jié)構(gòu)關(guān)系和變換規(guī)律，研究具有共同抽象概念、性質(zhì)的一類事物的某些內(nèi)在規(guī)律，以此指導(dǎo)人們從另一個(gè)側(cè)面去認(rèn)識(shí)事物。實(shí)現(xiàn)思維方式數(shù)學(xué)化的步驟第一階段 通過對數(shù)學(xué)分析、高等代數(shù)、概率統(tǒng)計(jì)等數(shù)學(xué)課程的學(xué)習(xí)，使學(xué)生熟悉和習(xí)慣于使用數(shù)學(xué)語言和符號(hào)系統(tǒng)對研究的數(shù)學(xué)對象進(jìn)行嚴(yán)格的

24、分析、表述、計(jì)算和推演，初步實(shí)現(xiàn)思維方式的數(shù)學(xué)化。實(shí)現(xiàn)思維方式數(shù)學(xué)化的步驟第二階段 數(shù)學(xué)學(xué)習(xí)轉(zhuǎn)向以計(jì)算機(jī)科學(xué)為背景的離散數(shù)學(xué)和理論計(jì)算機(jī)科學(xué)的學(xué)習(xí)，特別是通過對數(shù)理邏輯系統(tǒng)的學(xué)習(xí)，使學(xué)生思維方式逐步上升為系統(tǒng)的理性思維方式建議使用國內(nèi)外優(yōu)秀教材習(xí)題應(yīng)全部作。習(xí)題解析（內(nèi)容一：關(guān)系的性質(zhì)）關(guān)系的性質(zhì)1）舉出A=1, 2, 3上關(guān)系R的例子，使其具有下述性質(zhì)：a) 既是對稱的，又是反對稱的；b) 既不是對稱的，又不是反對稱的；c) 是傳遞的。解：a) R=(1, 1), (2, 2), (3, 3) b) R=(1, 2), (2, 1), (2, 3) c) R=(1, 2), (2, 1),

25、(1, 1), (2, 2), (3, 3)2）舉出一個(gè)集合上關(guān)系的例子，分別適合于自反，對稱，傳遞中的兩個(gè)且僅適合兩個(gè)。解：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)自反，對稱，不傳遞2.4 是非判斷：設(shè)R和S是A上的二元關(guān)系，確定下列命題是真還是假。如果命題為真，則證明之；如果命題為假，則給出一個(gè)反例。（1）若R和S是傳遞的，則RS是傳遞的。假。R=(1, 2),

26、S=(2, 3)。（2）若R和S是傳遞的，則RS是傳遞的。真。反證法證明。假設(shè)RS不是傳遞的，則(a, b)RS, (b, c)RS, 而(a, c)RS。所以(a, b)R, (b, c)R；(a, b)S, (b, c)S；因?yàn)镽和S是傳遞的，則(a, c)R, (a, c)S；就有(a, c)RS。導(dǎo)致矛盾。(3)若R和S是傳遞的，則RoS是傳遞的。假。R=(1, 4), (2, 5), S=(4, 2), (5, 3)。(4)若R是傳遞的，則R-1是傳遞的。真。反證法證明。假設(shè)R-1不是傳遞的，則(a, b)R-1, (b, c)R-1, 而(a, c)R-1。所以(c, b)R, (

27、b, a)R；又因?yàn)镽是傳遞的，所以(c, a)R。因此(a, c)R-1。所以導(dǎo)致矛盾。(5) 若R和S是自反的，則RS是自反的。真。根據(jù)自反的性質(zhì)證明。對于任意的aA, (a, a)R, 所以(a, a)RS。則RS是自反的。(6)若R和S是自反的，則RS是自反的。真。同理，根據(jù)自反的性質(zhì)證明。對于任意的aA, (a, a)R, (a, a)S, 所以(a, a) RS。則RS是自反的。(7)若R和S是自反的，則RoS是自反的。真。同理，根據(jù)自反的性質(zhì)證明。對于任意的aA, (a, a)R, (a, a)S, 所以(a, a) RoS。則RoS是自反的。(8)若R是自反的，則R-1是自反的

28、。真。同理，根據(jù)自反的性質(zhì)證明。對于任意的aA, (a, a)R, 則(a, a)R-1。(9) 若R和S是對稱的，則RS是對稱的。真。根據(jù)對稱的性質(zhì)證明。對于任意的 (a, b)RS, 則(a, b)R或(a, b)S；因?yàn)镽和S是對稱的，所以(b, a)R或(b, a)S。因此(b, a) RS， RS是對稱的。(10)若R和S是對稱的，則RS是對稱的。真。同理，根據(jù)對稱的性質(zhì)證明。對于任意的 (a, b)RS, 則(a, b)R并且(a, b)S；因?yàn)镽和S是對稱的，所以(b, a)R并且(b, a)S。因此(b, a) RS， R S是對稱的。(11)若R和S是對稱的，則RoS是對稱的

29、。假。R=(1, 2), (2, 1), S=(2, 3), (3, 2)。則RoS=(1, 3)。(12)若R是對稱的，則R-1是對稱的。真。根據(jù)對稱的性質(zhì)證明。對于任意的 (a, b) R-1, (b, a)R; 因?yàn)镽是對稱的, 則(a, b)R; 所以(b, a) R-1。則R-1是對稱的。(13) 若R和S是反對稱的，則RS是反對稱的。假。R=(1, 2), S=(2, 1),則RS=(1, 2), (2, 1)。(14) 若R和S是反對稱的，則RS是反對稱的。真。反證法證明。設(shè)RS不是反對稱的。則存在(a, b)RS, (b, a)RS, ab。則(a, b)R, (b, a)R,

30、 與R是反對稱的矛盾。(15) 若R和S是反對稱的，則RoS是反對稱的。假。R=(1, 3), (2, 4), S=(3, 2), (4, 1), 則RoS=(1, 2), (2, 1)，不是反對稱的。(16) 若R是反對稱的，則R-1是反對稱的。真。反證法證明。設(shè)R-1不是反對稱的。則存在(a, b) R-1, (b, a) R-1, ab。則(a, b)R, (b, a)R, 與R是反對稱的矛盾。習(xí)題解析（內(nèi)容二：等價(jià)關(guān)系）1）設(shè)R1和R2是A上的等價(jià)關(guān)系，C1和C2分別是A中關(guān)于R1和R2的劃分。 證明： R1R2，當(dāng)且僅當(dāng)C1中的每個(gè)等價(jià)類是包含于C2的一些等價(jià)類之中。/*證明思想：劃

31、分與等價(jià)關(guān)系：由建立的等價(jià)關(guān)系R=(A1A1)(A2A2) (AnAn)*/習(xí)題解析（內(nèi)容二）2）設(shè)R是A上的二元關(guān)系，S=(a, b) | 對于某一c，有(a, b)R, (b, c)R，證明如果 R是A上的等價(jià)關(guān)系，則S是A上的等價(jià)關(guān)系。/*證明思想： 證明S是等價(jià)關(guān)系，即證明S是自反的，對稱的和傳遞的。*/習(xí)題解析（內(nèi)容二）3）設(shè)R1和R2是A上的等價(jià)關(guān)系，試確定以下各式，哪些是A上的等價(jià)關(guān)系，對不是的式子，提供反例。a) (AA)-R1;b) R1- R2;c) R12;d) r(R1- R2).思想：判斷是否自反、對稱和傳遞2.19 確定下列各式是不是A=1,2,3,4,5上的等價(jià)關(guān)

32、系,如果是等價(jià)關(guān)系, 請寫出它的等價(jià)類。(1)(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(1,5),(5,1),(3,5),(5,3)是等價(jià)類為:1=3=5=1,3,52=24=4(2)(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(3,4),(4,3);不是.因?yàn)?1,3),(3,4)R,而(1,4)R.(3)(1,1),(2,2),(3,3),(4,4);不是. 因?yàn)锳=1,2,3,4,5,而(5,5)R(4)(a,b)|4整除a-b,a,bA;是1=5=1,5,2=2,3=3,4=4(5)(a,b)|3整除a

33、+b,a,bA;不是.因?yàn)锳=1,2,3,4,5,而1+1不能被3整除,故(1,1)R(6)(a,b)|a整除2-b,a,bA。不是.因?yàn)锳=1,2,3,4,5,而5不能整除2-5=-3,故(5,5)R2.22 設(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)系。證明:(注意,T是A上的二元關(guān)系.)（1）自反: 對任意aA,(關(guān)鍵證明(a,a)T)；因?yàn)镽是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

34、)和(a,b)都屬于R, 所以(b,a)T.（3）傳遞: 若(a,b)T,(b,c)T(關(guān)鍵證明(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, 因?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。2.23 設(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）自反:對任意aA

35、, (證明(a,a)S)。因?yàn)镽是A上的自反關(guān)系, 所以(a,a)R, (a,a)R, 因此根據(jù)S的定義,有(a,a)S.（2）對稱:若(a,b)S,則存在cA,使得(a,c)和(c,b)都屬于R, 因?yàn)镽對稱, 因此(c,a)和(b,c)都屬于R, 即(b,c)和(c,a)都屬于R, 故根據(jù)S的定義,有(b,a)S。（3）傳遞: 若(a,b)S,(b,c)S(關(guān)鍵證明(a,c)S,即要證明存在dA,使得(a,d)和(d,c)都屬于R)。由于(a,b)S, 所以存在eA,使得(a,e)和(e,b)都屬于R, 同樣因?yàn)?b,c)S, 所以存在fA,使得(b,f)和(f,c)都屬于R, 因?yàn)镽傳遞

36、, 所以當(dāng)(a,e)和(e,b)屬于R時(shí),有(a,b)R, 當(dāng)(b,f)和(f,c)屬于R時(shí),有(b,c)R, 現(xiàn)在(a,b)和(b,c)屬于R, 根據(jù)S的定義,有(a,c)S。2.24 設(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(要說明的是,在(a,b)R,(a,c)R前提下導(dǎo)出(b,c)R)。若當(dāng)(a,b)R,(a,c)R,(要證明(b,c)R)，因?yàn)镽對稱, 所以當(dāng)(a,b)R時(shí),有(b,a)R, 因?yàn)镽傳遞, 所以當(dāng)(b,a)R,(a,c)R時(shí)有(b

37、,c)R.(2) R是A上的一個(gè)自反關(guān)系, 當(dāng)(a,b)R,(a,c)R必有(b,c)R,證明R是等價(jià)關(guān)系自反:條件已知；對稱:若(a,b)R,因?yàn)镽自反S,故(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)R,(b,c)R導(dǎo)出(a,c)R)證明:因?yàn)?a,b)R,(b,c)R, 而R對稱,所以(b,a)R, 現(xiàn)在(b,a)R,(b,c)R, 所以根據(jù)條件有(a,c)R習(xí)題解析（內(nèi)容三：序關(guān)系）序關(guān)系1）設(shè)R是A上的自反和傳

38、遞關(guān)系，證明A上存在一個(gè)等價(jià)關(guān)系S，且在A/S上存在偏序關(guān)系R，使得(x, y)R (x, y) R。習(xí)題解析（內(nèi)容三）2）設(shè)R是A上的二元關(guān)系，A是A的子集，定義A上的關(guān)系R如下：R=R(AA)確定下述命題真假并證明：a)如果R在A上是傳遞的，則R在A上是傳遞的；b)如果R是A上的偏序關(guān)系，則R是A上的偏序關(guān)系；c)如果R是A上的擬序關(guān)系，則R是A上的擬序關(guān)系；d)如果R是A上的全序關(guān)系，則R是A上的全序關(guān)系；習(xí)題解析（內(nèi)容三）3）畫出集合A=1, 2, 3, 4, 5, 6在偏序關(guān)系“整除”下的哈斯圖，并討論：a) 寫出1, 2, 3, 4, 5, 6的極大元，極小元，最大元，最小元；b) 分別寫出2, 3, 6和2, 3, 5的上界，下界，上確界，下確界。習(xí)題解析（內(nèi)容四：閉包）2.13 設(shè)R1和R2是集合A上的二元關(guān)系,(3) t(R1)t(R2)t(R1R2)。證明方法1：（公式法）因?yàn)镽1