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

1、第三章 集合與關(guān)系(1). 組織結(jié)構(gòu)是明確的，但是內(nèi)容比較多組織結(jié)構(gòu)是明確的，但是內(nèi)容比較多(2). 集合、直積、關(guān)系這些概念是簡單的集合、直積、關(guān)系這些概念是簡單的(3). 主要難點在于：復(fù)合、閉包和特殊關(guān)系主要難點在于：復(fù)合、閉包和特殊關(guān)系 （等價關(guān)系、相容關(guān)系、序關(guān)系）（等價關(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這種題目通常通過這種題目通常通過|P(A)|=2|A|來計算冪來計算冪集中元素的個數(shù)，然后驗證解答是否正集中元素的個數(shù)，然后驗證解答是否正

2、確，抓住這個，我們可以計算難題確，抓住這個，我們可以計算難題習(xí)題習(xí)題3-1(p86)（6）確定下列集合的冪集）確定下列集合的冪集d) P() e) P(P() (習(xí)題習(xí)題)解答：解答：d) 沒有元素，所以沒有元素，所以|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)。問：。問：a) 是否是否 B ？是否是否 B ?b) 是否是否 B ？是否？是否 B ？c) 是否是否 B ? 是否是否 B ? 解答：由上題得到：解答：由上題得到： P(P() =

3、 , , 所以所以a) B ， B ；b) B , B ; c) B, B (拆括號法拆括號法) 習(xí)題習(xí)題3-2(p95)(5) 證明：證明： 對任意集合對任意集合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、 對式中所給出對式中所給出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) 對對0,1,2,3,4,5,6上的二元關(guān)系，上的二元關(guān)系，|xy x是質(zhì)數(shù)是質(zhì)數(shù)，寫出關(guān)系矩陣。，寫出關(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上的下述五個關(guān)系。上的下述五個關(guān)系。R=,S=,T=,判斷判斷A中的上述關(guān)系是不是中的上述關(guān)系是不是a)自反的，自反的，b)對稱對稱的，的，c)可傳遞的，可傳遞的，d)反對稱的。反對稱的。解答：（解答：（1）R滿足反對稱性和傳遞性；滿足反對稱性和傳遞性；（2）S滿足自反、對稱和傳遞性滿足自反、對稱和傳遞性（3）T滿

9、足反對稱性。滿足反對稱性。,破壞傳遞破壞傳遞習(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是自反的，對稱的，可傳遞的，是自反的，對稱的，可傳遞的，反對稱的嗎？反對稱的嗎？解答：解答：1234可傳遞的，可傳遞的，反對稱反對稱的的習(xí)題習(xí)題3-6(p114)(6)設(shè)設(shè)R是集合是集合X上的一個自反關(guān)系。求證：上的一個自反關(guān)系。求證：R是是對稱和傳遞的，當(dāng)且僅當(dāng)對稱和傳遞的，當(dāng)且僅當(dāng)和和在在R之之中則有中則有在在R之中。之中。證明：（證明：（1）若）若R是

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

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

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

13、x, 對稱對稱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=，這是因為若有，這是因為若有Ai Aj不為空，設(shè)共同元素有不為空，設(shè)共同元素有x，因此，因此Ai中的元素中的元素ai和和Aj中的元素中的元素aj，由題意有，由題意有 R, R，由對稱和傳遞，可以得到，由對稱和傳遞，可以得到 R, 因此因此ai，aj在一個集合中，因此在一個集合中，因此Ai=Aj，這和這和Ai、Aj互不包含相排斥。互不包含相排斥。（3） a A，由自反性，由自反性， R, 因此因此a和和a在在某某個子集個子集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上的等價關(guān)上的等價關(guān)系系R，此關(guān)系，此關(guān)系R能夠產(chǎn)生劃分能夠產(chǎn)生劃分1,2,3,4,5并畫出關(guān)系圖。并畫出關(guān)系圖。R = 1,22 32 4,52 = , ,關(guān)系關(guān)系圖分為三部分，為兩個完全圖分為三部分，為兩個完全2邊形和邊形和一一個個完全完全0邊形（用畫筆畫一下）邊形（用畫筆畫一

16、下）習(xí)題習(xí)題3-10(p135)(6) 設(shè)設(shè)R是集合是集合A上的對稱和傳遞關(guān)系，證上的對稱和傳遞關(guān)系，證明如果對于明如果對于A中的每一個元素中的每一個元素a，在，在A中同時中同時也存在一個也存在一個b，使，使在在R中，則中，則R是一個是一個等價關(guān)系。等價關(guān)系。證明：只需證明證明：只需證明R是自反的。對于任意的是自反的。對于任意的a，存在存在b，有，有 R，由對稱性，由對稱性 R；由傳遞性，由傳遞性， R，因此，因此R是自反的，是自反的，所以所以R是一個等價關(guān)系。是一個等價關(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是對稱的。是對稱的。因此因此r是相容關(guān)系。是相容關(guān)系。習(xí)題習(xí)題3-11(p139)(2) 題目省略。題目省略。解答：完全覆蓋為解答：完全覆蓋為(最大相容類集合最大相容類集合)：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上的一個相容關(guān)系。并說明上的一個相容關(guān)系。并說明在什么條件下，此相容關(guān)系

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

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