復旦大學計算機科學與工程系 吳永輝 離散數(shù)學 集合論 第二章 關系

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

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

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

4、(a, b)R a0，RkRR2R3Rn。*/證明：/*分而治之*/對于kn，必有RkRR2R3Rn 。對于kn，若(a, b)Rk，則存在元素個數(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)這一段后，如果序列中元素個數(shù)仍大于n，則繼續(xù)上述過程，直到序列中元素個數(shù)kn為止

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

6、s(R)=左式證明： （公式法：等式推導）（2）右式=tr(R)=t(RIA)= (RIA) (RIA)2 (RIA)3 /*可以證明(RIA) n= IARR2 Rn*/= IARR2= IAt(R)=rt(R)=左式證明： （公式法：等式推導）（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 等價關系與劃分一 等價關系與劃分1 定義2.12（劃分） 設A是一個集合。AiA, Ai , i=1, , n。若A1 A2 An=A， Ai A

7、j=（i, j=1, n, ij），則稱=A1, A2, , An是A的一個劃分。其中每個Ai稱為劃分的一個塊。/*物以類聚，人以群分*/例2.21 設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的一個劃分。3 定義2.13（等價關系） 設R是A上的二元關系，若R是自反的、對稱的和傳遞的，

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

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

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

11、個等價關系，即證明R是自反、對稱和傳遞的。構造性證明的思想例2.26 設A= a, b, c, d, e, f 的一個劃分=a, b, c, d, e, f,由確定A上的一個等價關系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 設R1和R2是A上的等價關系， R1=R2 A/R1=A/R2 。定理2.13和定理2.15: 任一等價關系唯一確定一個劃分.定理2.14

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

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

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

15、推出xRa。因此x|xRax|xRa，即 aRZaR。的一塊包含在的一塊中，所以細分。定理2.18(12與1和2的聯(lián)系) 設1和2是A的劃分，則（1） 12細分1和2；（2）設是A的劃分，若細分1和2，則細分12。/* 12細分1和2；并且是同時細分1和2的最小劃分（劃分塊數(shù)最少）*/證明：（1）由R1R2R1, R1R2R2，即得。（2）若RR1，R R2則RR1R2即得。例2.27 設學生集合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。按同班級分為一組，得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)任兩個學生既在同年齡組中，又在同班級組中。 不在12同一組中的兩個學生，還可能在同一年齡組中或同一班級組中。五、劃分的和定理2.19 設R1和R2是A上的等價關系，則(R1R2)+是A上的等價關系。定義2.18 (劃分的和) 設R1和R2是A上的等價關系，由R1和R2確定A的劃分分別為1和2，A上的等價關系(R1R2)+所確定A的劃分稱為1和2劃分的和，記為1+2。定理2.20 設1和2是A的劃分，則（1） 1與2細分1+2；（2）設是A的劃分，

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

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

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

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

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

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

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

24、分析、表述、計算和推演，初步實現(xiàn)思維方式的數(shù)學化。實現(xiàn)思維方式數(shù)學化的步驟第二階段 數(shù)學學習轉向以計算機科學為背景的離散數(shù)學和理論計算機科學的學習，特別是通過對數(shù)理邏輯系統(tǒng)的學習，使學生思維方式逐步上升為系統(tǒng)的理性思維方式建議使用國內(nèi)外優(yōu)秀教材習題應全部作。習題解析（內(nèi)容一：關系的性質）關系的性質1）舉出A=1, 2, 3上關系R的例子，使其具有下述性質：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）舉出一個集合上關系的例子，分別適合于自反，對稱，傳遞中的兩個且僅適合兩個。解：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 是非判斷：設R和S是A上的二元關系，確定下列命題是真還是假。如果命題為真，則證明之；如果命題為假，則給出一個反例。（1）若R和S是傳遞的，則RS是傳遞的。假。R=(1, 2),

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

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

28、。真。同理，根據(jù)自反的性質證明。對于任意的aA, (a, a)R, 則(a, a)R-1。(9) 若R和S是對稱的，則RS是對稱的。真。根據(jù)對稱的性質證明。對于任意的 (a, b)RS, 則(a, b)R或(a, b)S；因為R和S是對稱的，所以(b, a)R或(b, a)S。因此(b, a) RS， RS是對稱的。(10)若R和S是對稱的，則RS是對稱的。真。同理，根據(jù)對稱的性質證明。對于任意的 (a, b)RS, 則(a, b)R并且(a, b)S；因為R和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ù)對稱的性質證明。對于任意的 (a, b) R-1, (b, a)R; 因為R是對稱的, 則(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是反對稱的。真。反證法證明。設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是反對稱的。真。反證法證明。設R-1不是反對稱的。則存在(a, b) R-1, (b, a) R-1, ab。則(a, b)R, (b, a)R, 與R是反對稱的矛盾。習題解析（內(nèi)容二：等價關系）1）設R1和R2是A上的等價關系，C1和C2分別是A中關于R1和R2的劃分。 證明： R1R2，當且僅當C1中的每個等價類是包含于C2的一些等價類之中。/*證明思想：劃

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

32、系,如果是等價關系, 請寫出它的等價類。(1)(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(1,5),(5,1),(3,5),(5,3)是等價類為: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);不是.因為(1,3),(3,4)R,而(1,4)R.(3)(1,1),(2,2),(3,3),(4,4);不是. 因為A=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;不是.因為A=1,2,3,4,5,而1+1不能被3整除,故(1,1)R(6)(a,b)|a整除2-b,a,bA。不是.因為A=1,2,3,4,5,而5不能整除2-5=-3,故(5,5)R2.22 設R是A上的傳遞和自反關系, 設T是A上的二元關系：(a,b)T當且僅當(a,b)和(b,a)都屬于R, 證明T是一個等價關系。證明:(注意,T是A上的二元關系.)（1）自反: 對任意aA,(關鍵證明(a,a)T)；因為R是A上的自反關系, 所以(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(關鍵證明(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。2.23 設R是一個二元關系,設S=(a,b)|存在某個c,使(a,c)R且(c,b)R。證明如果R是一個等價關系則S也是一個等價關系。證明: （1）自反:對任意aA

35、, (證明(a,a)S)。因為R是A上的自反關系, 所以(a,a)R, (a,a)R, 因此根據(jù)S的定義,有(a,a)S.（2）對稱:若(a,b)S,則存在cA,使得(a,c)和(c,b)都屬于R, 因為R對稱, 因此(c,a)和(b,c)都屬于R, 即(b,c)和(c,a)都屬于R, 故根據(jù)S的定義,有(b,a)S。（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傳遞

36、, 所以當(a,e)和(e,b)屬于R時,有(a,b)R, 當(b,f)和(f,c)屬于R時,有(b,c)R, 現(xiàn)在(a,b)和(b,c)屬于R, 根據(jù)S的定義,有(a,c)S。2.24 設R是A上的一個自反關系, 證明R是一個等價關系當且僅當若(a,b)R,(a,c)R則(b,c)R。證明:(1) R是一個等價關系,則當(a,b) R,(a,c)R必有(b,c)R(要說明的是,在(a,b)R,(a,c)R前提下導出(b,c)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

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

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