第三章復(fù)習(xí) (2)

1、第三章 集合與關(guān)系(1). 組織結(jié)構(gòu)是明確的，但是內(nèi)容比較多組織結(jié)構(gòu)是明確的，但是內(nèi)容比較多(2). 集合、直積、關(guān)系這些概念是簡(jiǎn)單的集合、直積、關(guān)系這些概念是簡(jiǎn)單的(3). 主要難點(diǎn)在于：復(fù)合、閉包和特殊關(guān)系主要難點(diǎn)在于：復(fù)合、閉包和特殊關(guān)系 （等價(jià)關(guān)系、相容關(guān)系、序關(guān)系）（等價(jià)關(guān)系、相容關(guān)系、序關(guān)系）習(xí)題習(xí)題3-1(p86)（6）確定）確定下列集合的冪集下列集合的冪集a) a,a b) 1,2,3解答：解答：a) a,a, a,a, b) , 1,2,3這種題目通常通過(guò)這種題目通常通過(guò)|P(A)|=2|A|來(lái)計(jì)算冪來(lái)計(jì)算冪集中元素的個(gè)數(shù)，然后驗(yàn)證解答是否正集中元素的個(gè)數(shù)，然后驗(yàn)證解答是否正

2、確，抓住這個(gè)，我們可以計(jì)算難題確，抓住這個(gè)，我們可以計(jì)算難題習(xí)題習(xí)題3-1(p86)（6）確定下列集合的冪集）確定下列集合的冪集d) P() e) P(P() (習(xí)題習(xí)題)解答：解答：d) 沒(méi)有元素，所以沒(méi)有元素，所以|P()|=20 =1， P() = ，P(P() = , (21)e) P(P(P() = P(P()=P(,) = , , (22)習(xí)題習(xí)題3-1(p86)(7) 設(shè)設(shè)A=, B= P(P(A)。問(wèn)：。問(wèn)：a) 是否是否 B ？是否是否 B ?b) 是否是否 B ？是否？是否 B ？c) 是否是否 B ? 是否是否 B ? 解答：由上題得到：解答：由上題得到： P(P() =

3、 , , 所以所以a) B ， B ；b) B , B ; c) B, B (拆括號(hào)法拆括號(hào)法) 習(xí)題習(xí)題3-2(p95)(5) 證明：證明： 對(duì)任意集合對(duì)任意集合A，B，C，有，有a) (A - B) - C = A - (BC)證明：證明：x (A - B) C x (A - B) x C x A x B x C x A x (BC) x A - (BC)所以所以 (A - B) - C = A - (BC)習(xí)題習(xí)題3-2(p95)8. a) 已知已知AB = AC，是否必須，是否必須B=C ？ b) 已知已知A B = A C，是否必須，是否必須B=C ？ c) 已知已知A B = A

4、C，是否必須，是否必須B=C ？a). A=1,2 , B=3, C=2,3為反例為反例b). A=1,2, B=1, C=2為反例為反例c). A B = A C A A B =A A C B= C B=C習(xí)題習(xí)題3-2(p95)a) A (B C) = (A B) (A C)左邊左邊= A (B-C)(C-B) = A(BC)(C B) = (ABC) (ABC)右邊右邊= (AB) (AC)(AC) (AB) = (ABA) (ABC) (ACA) (ACB) = (ABC) (ABC)習(xí)題習(xí)題3-3(p100)(5)A1: 學(xué)數(shù)學(xué)，學(xué)數(shù)學(xué)，A2：學(xué)物理，：學(xué)物理，A3：學(xué)生物：學(xué)生物

5、|A1|=67, |A2|=47, |A3|=95|A1 A3|=26, |A1 A2|=28, |A2 A3|=27N = 200， |(A1A2A3)|=50又又|A1A2A3|=|A1|+|A2|+|A3|- |A1 A3|- |A1 A2|- |A2 A3|+|A1 A2A3 |所以所以200-50 = 67+47+95-26-28-27+ |A1 A2A3|， 因此因此|A1 A2A3|=22習(xí)題習(xí)題3-4(p105)(3) 下列各式中哪些成立？哪些不成立？為下列各式中哪些成立？哪些不成立？為什么？什么？b) (A B)(C D) = (AC) (BD)d) (A B)C = (AC

6、) (BC)b) A = 1 ,2 , B = 1, C =1,2, D =1(A B)(C D) = (AC) (BD) = ,習(xí)題習(xí)題3-4(p105)d) (A B)C (x A x B y C )(x A y C y C )(x A y C ) (x B y C ) AC BC (AC ) (BC)所以所以(A B)C = (AC) (BC)習(xí)題習(xí)題3-4(p105)(4) 證明：若證明：若XX = YY，則，則X=Y證證：（：（1） XX，則，則 YY，所以，所以xY，X Y；（2）反之，設(shè)）反之，設(shè) YY,則則 XX，y X，Y X；所以所以X=Y 習(xí)題習(xí)題3-5(p110)(5)

7、 對(duì)式中所給出對(duì)式中所給出A上的二元關(guān)系，試給出上的二元關(guān)系，試給出關(guān)系圖關(guān)系圖 |0 x y 3，A=0,1,2,3,4R = , , , , , , , , , ,習(xí)題習(xí)題3-5(p110)(6) 對(duì)對(duì)0,1,2,3,4,5,6上的二元關(guān)系，上的二元關(guān)系，|xy x是質(zhì)數(shù)是質(zhì)數(shù)，寫(xiě)出關(guān)系矩陣。，寫(xiě)出關(guān)系矩陣。解：解：R =, , , , , , , , ,R011111100111111111111M = 1111111000001111111110000000習(xí)題習(xí)題3-5(p110)(7)設(shè)設(shè)P=,和和Q=,找出找出PQ , P Q , dom P, domQ ran P, ran Q

8、, dom(P Q), ran(P Q)解：解： PQ =,PQ = , domP = 1,2,3, domQ=1,2,4ran P=2,3,4, ran Q = 2,3,4dom(P Q )=2, ran(P Q)=4習(xí)題習(xí)題3-6(p113)(1) 分析集合分析集合A=1,2,3上的下述五個(gè)關(guān)系。上的下述五個(gè)關(guān)系。R=,S=,T=,判斷判斷A中的上述關(guān)系是不是中的上述關(guān)系是不是a)自反的，自反的，b)對(duì)稱(chēng)對(duì)稱(chēng)的，的，c)可傳遞的，可傳遞的，d)反對(duì)稱(chēng)的。反對(duì)稱(chēng)的。解答：（解答：（1）R滿(mǎn)足反對(duì)稱(chēng)性和傳遞性；滿(mǎn)足反對(duì)稱(chēng)性和傳遞性；（2）S滿(mǎn)足自反、對(duì)稱(chēng)和傳遞性滿(mǎn)足自反、對(duì)稱(chēng)和傳遞性（3）T滿(mǎn)

9、足反對(duì)稱(chēng)性。滿(mǎn)足反對(duì)稱(chēng)性。,破壞傳遞破壞傳遞習(xí)題習(xí)題3-6(p113)(2)給定給定A=1,2,3,4,考慮考慮A上的關(guān)系上的關(guān)系R，若，若R = ,a) 在在AA的坐標(biāo)圖中標(biāo)出的坐標(biāo)圖中標(biāo)出R，并繪出它的，并繪出它的關(guān)系圖；關(guān)系圖；b)R是自反的，對(duì)稱(chēng)的，可傳遞的，是自反的，對(duì)稱(chēng)的，可傳遞的，反對(duì)稱(chēng)的嗎？反對(duì)稱(chēng)的嗎？解答：解答：1234可傳遞的，可傳遞的，反對(duì)稱(chēng)反對(duì)稱(chēng)的的習(xí)題習(xí)題3-6(p114)(6)設(shè)設(shè)R是集合是集合X上的一個(gè)自反關(guān)系。求證：上的一個(gè)自反關(guān)系。求證：R是是對(duì)稱(chēng)和傳遞的，當(dāng)且僅當(dāng)對(duì)稱(chēng)和傳遞的，當(dāng)且僅當(dāng)和和在在R之之中則有中則有在在R之中。之中。證明：（證明：（1）若）若R是

10、對(duì)稱(chēng)是對(duì)稱(chēng)的的，則由，則由和和在在R中，因此中，因此,在在R中，中，R是傳遞的，是傳遞的，因此因此在在R中，由對(duì)稱(chēng)，中，由對(duì)稱(chēng)，在在R中；（中；（2）a,b,c任意，任意，a取取c，、和和在在R中，中，故故R對(duì)稱(chēng)；因此由對(duì)稱(chēng)；因此由在在R中知道中知道在在R中，中，,在在R中，推出中，推出R傳遞。傳遞。習(xí)題習(xí)題3-7(p118)(1)設(shè)設(shè)R1和和R2是是A上的任意關(guān)系，說(shuō)明以下命上的任意關(guān)系，說(shuō)明以下命題的真假，并予以證明題的真假，并予以證明a) 若若R1和和R2是自反的是自反的,則則R1R2也是自反的也是自反的c) 若若R1和和R2是對(duì)稱(chēng)的是對(duì)稱(chēng)的,則則R1R2也是對(duì)稱(chēng)的也是對(duì)稱(chēng)的解答：解答：

11、a）成立，在）成立，在R1中有中有R1， 在在R2中有中有 R2, 因此因此 R1R2，有自反，有自反性。性。c）不成立，設(shè)）不成立，設(shè)R1=, R2=, 則則R1R2=, 無(wú)對(duì)稱(chēng)性。無(wú)對(duì)稱(chēng)性。 習(xí)題習(xí)題3-7(p119)(5) R是是A上的一個(gè)二元關(guān)系，如果上的一個(gè)二元關(guān)系，如果R是自反的，是自反的，則則Rc一定是自反的嗎？如果一定是自反的嗎？如果R是對(duì)稱(chēng)的，則是對(duì)稱(chēng)的，則Rc一定是對(duì)稱(chēng)的嗎？如果一定是對(duì)稱(chēng)的嗎？如果R是傳遞的，則是傳遞的，則Rc一定一定是傳遞的嗎？是傳遞的嗎？解答解答：（：（1）R自反，自反， R，所以，所以 Rc，Rc自反；（自反；（2）R對(duì)稱(chēng)，對(duì)稱(chēng)，Rc=R，也對(duì)稱(chēng)；，

12、也對(duì)稱(chēng)；（3）, R , Rc, 因此滿(mǎn)足傳遞性因此滿(mǎn)足傳遞性習(xí)題習(xí)題3-8(p127)(2)設(shè)集合設(shè)集合A=a,b,c,d, A上的關(guān)系上的關(guān)系R=,a) 用矩陣運(yùn)算和作圖方法求出用矩陣運(yùn)算和作圖方法求出R的自反閉包、的自反閉包、對(duì)稱(chēng)閉包和傳遞閉包。對(duì)稱(chēng)閉包和傳遞閉包。b) 用用Warshall算法求出算法求出R的傳遞閉包的傳遞閉包解答：解答：0100101000010000M圖略，直接解說(shuō)圖略，直接解說(shuō)傳遞性，要解說(shuō)傳遞性，要解說(shuō)一步邊、兩步邊、一步邊、兩步邊、三步邊、四步邊三步邊、四步邊abcd習(xí)題習(xí)題3-8(p127)矩陣運(yùn)算，矩陣運(yùn)算，(加法為析取加法為析取)自反自反M1 = M+I

13、x, 對(duì)稱(chēng)對(duì)稱(chēng)M2=M+Mc，傳遞傳遞M3=M1+M12+M13+M14b)0100010011101111101011101110111100010001000100010000000000000000習(xí)題習(xí)題3-8(p127)(7) 設(shè)設(shè)R1和和R2是是A上的關(guān)系，證明：上的關(guān)系，證明：a) r(R1R2) = r(R1)r(R2)b) s(R1R2) = s(R1)s(R2)解答：解答：a）左邊）左邊=R1 R2 I ， 右邊右邊=R1 I R2 I = R1 R2 I b）左邊）左邊=R1R2 (R1R2 )c = R1R2 R1cR2c 右邊右邊= R1R1cR2 R2c ，兩邊相等

14、，兩邊相等習(xí)題習(xí)題3-9(p130)(4)題略。題略。證明證明：（：（1）Ai不包含于不包含于Aj，因此，因此Ai不可能為不可能為空集；（空集；（2）有）有Ai Aj=，這是因?yàn)槿粲?，這是因?yàn)槿粲蠥i Aj不為空，設(shè)共同元素有不為空，設(shè)共同元素有x，因此，因此Ai中的元素中的元素ai和和Aj中的元素中的元素aj，由題意有，由題意有 R, R，由對(duì)稱(chēng)和傳遞，可以得到，由對(duì)稱(chēng)和傳遞，可以得到 R, 因此因此ai，aj在一個(gè)集合中，因此在一個(gè)集合中，因此Ai=Aj，這和這和Ai、Aj互不包含相排斥?；ゲ话嗯懦?。（3） a A，由自反性，由自反性， R, 因此因此a和和a在在某某個(gè)子集個(gè)子集As中

15、，由中，由a的任意性，遍歷的任意性，遍歷s，得，得到到a A1 A2 Ak 。（a A1 A2 Ak推出推出a A顯然，顯然， 上面可以證明上面可以證明a A 推推出出a A1 A2 Ak ），因此），因此A1 A2 Ak = A習(xí)題習(xí)題3-10(p134)(3) 給定集合給定集合S=1,2,3,4,5，找出，找出S上的等價(jià)關(guān)上的等價(jià)關(guān)系系R，此關(guān)系，此關(guān)系R能夠產(chǎn)生劃分能夠產(chǎn)生劃分1,2,3,4,5并畫(huà)出關(guān)系圖。并畫(huà)出關(guān)系圖。R = 1,22 32 4,52 = , ,關(guān)系關(guān)系圖分為三部分，為兩個(gè)完全圖分為三部分，為兩個(gè)完全2邊形和邊形和一一個(gè)個(gè)完全完全0邊形（用畫(huà)筆畫(huà)一下）邊形（用畫(huà)筆畫(huà)一

16、下）習(xí)題習(xí)題3-10(p135)(6) 設(shè)設(shè)R是集合是集合A上的對(duì)稱(chēng)和傳遞關(guān)系，證上的對(duì)稱(chēng)和傳遞關(guān)系，證明如果對(duì)于明如果對(duì)于A中的每一個(gè)元素中的每一個(gè)元素a，在，在A中同時(shí)中同時(shí)也存在一個(gè)也存在一個(gè)b，使，使在在R中，則中，則R是一個(gè)是一個(gè)等價(jià)關(guān)系。等價(jià)關(guān)系。證明：只需證明證明：只需證明R是自反的。對(duì)于任意的是自反的。對(duì)于任意的a，存在存在b，有，有 R，由對(duì)稱(chēng)性，由對(duì)稱(chēng)性 R；由傳遞性，由傳遞性， R，因此，因此R是自反的，是自反的，所以所以R是一個(gè)等價(jià)關(guān)系。是一個(gè)等價(jià)關(guān)系。習(xí)題習(xí)題3-11(p139)(1) 設(shè)設(shè)R是是X上的二元關(guān)系，試證明上的二元關(guān)系，試證明r=Ix R Rc是是X上的相

17、容關(guān)系。上的相容關(guān)系。證明證明：（：（1） Ix，因此，因此 r，r自反；（自反；（2） R , 則則 Rc，因此因此 r并且并且 r, r是對(duì)稱(chēng)的。是對(duì)稱(chēng)的。因此因此r是相容關(guān)系。是相容關(guān)系。習(xí)題習(xí)題3-11(p139)(2) 題目省略。題目省略。解答：完全覆蓋為解答：完全覆蓋為(最大相容類(lèi)集合最大相容類(lèi)集合)：x1,x2,x3,x1,x3,x6x3,x5,x6,x3,x4,x5x3x5x4x2x6x1習(xí)題習(xí)題3-11(p139)(4) 設(shè)設(shè)C=A1,A2,An為集合為集合A的覆蓋，試的覆蓋，試由此覆蓋確定由此覆蓋確定A上的一個(gè)相容關(guān)系。并說(shuō)明上的一個(gè)相容關(guān)系。并說(shuō)明在什么條件下，此相容關(guān)系

18、為等價(jià)關(guān)系。在什么條件下，此相容關(guān)系為等價(jià)關(guān)系。R = A1A1 A2A2 AnAn當(dāng)當(dāng)R滿(mǎn)足傳遞性，此相容關(guān)系為等價(jià)關(guān)系，滿(mǎn)足傳遞性，此相容關(guān)系為等價(jià)關(guān)系，一般的，只要一般的，只要C不僅是一個(gè)覆蓋，還是一個(gè)不僅是一個(gè)覆蓋，還是一個(gè)劃分的時(shí)候，劃分的時(shí)候，R就能滿(mǎn)足傳遞性，就能滿(mǎn)足傳遞性，R就是等就是等價(jià)關(guān)系。價(jià)關(guān)系。習(xí)題習(xí)題3-12(p145)(1) 設(shè)集合為設(shè)集合為3,5,15, 1,2,3,6,12, 3,9,27,54，偏序關(guān)系為整除，畫(huà)出這些集合，偏序關(guān)系為整除，畫(huà)出這些集合的偏序關(guān)系圖，并指出哪些是全序關(guān)系。的偏序關(guān)系圖，并指出哪些是全序關(guān)系。第第3個(gè)圖代表全序個(gè)圖代表全序習(xí)題習(xí)題

19、3-12(p146)(6)題見(jiàn)書(shū)本題見(jiàn)書(shū)本 極大元極大元 最大元最大元 極小元極小元 最小元最小元 P x1 x1 x4、x5 無(wú)無(wú) 上界上界 上確界上確界 下界下界 下確界下確界x2,x3,x4 x1 x1 x4 x4x3,x4,x5 x1,x3 x3 無(wú)無(wú) 無(wú)無(wú) x1,x2,x3 x1 x1 x4 x4習(xí)題習(xí)題3-12(p146)(7)題目省略題目省略畫(huà)哈斯圖，注意先看出射點(diǎn)和入射點(diǎn)，全畫(huà)哈斯圖，注意先看出射點(diǎn)和入射點(diǎn)，全序和良序只為（序和良序只為（c）圖）圖習(xí)題習(xí)題4-1 (p151)(1) 題目省略題目省略解答：解答：(a)都不是；都不是；(b)都不是都不是; (c)是滿(mǎn)射是滿(mǎn)射(d)都不是都不是, (i=-1和和i=1,值相同值相同)(e) 是雙射是雙射習(xí)題習(xí)題4-1 (p151)(5) 假定假定X和和Y是有窮集合是有窮集合, 找出從找出從X到到Y(jié)存在存在入射的必要條件是什么入射的必要條件是什么?解答解答：1）x1x2,