電大離散數學期末考試試題與答案ppt課件

1、離散數學期末考試2007年元月8日1. (6分分) 知知 A=a,a,b, B=b, a, 求求 AB, AB, P(A).解解: AB=(a,b), (a,a), (a, b), (a, a), (b, b), (b, a) AB=(A-B) (B-A)=a, b, b P(A)=, a, a, b, a, a, a,b, a,b, A.2. (4分分) 知知R1,R2是是A上的對稱關系上的對稱關系, R1 R2對稱嗎對稱嗎? 證明或證明或舉反例闡明舉反例闡明.解解: 普通地普通地, R1 R2 R1 R2. 反例反例: R1=(1,3), (3,1) 對稱對稱!R2=(3,2), (2,3

2、) 對稱對稱!R1 R2 =(1,2) 不對稱不對稱!3. (6分分) G是一個群是一個群, H是是G的子群的子群. g1,g2 G, (g1,g2) R g1g2-1 H. 證明證明R是是G上等價關系上等價關系.證明證明: 對于恣意的對于恣意的a G， aa-1=e H， (a,a) R，故，故R是自反的。是自反的。 對于恣意的對于恣意的a，b G，假設，假設(a,b) R， ab-1 H，(ab-1)-1=ba-1 H， (b,a) R，故，故R是對稱的。是對稱的。 對于恣意的對于恣意的a,b,c G，假設，假設(a,b) R，(b,c) R， ab-1 H且且 bc-1 H， (ab-1

3、)(bc-1)=ac-1 H， (a,c) R，故，故R是傳送的。是傳送的。4. (6分分) A=1,2,3,5,10,15,30, x,y A, x yx|y. (1) 畫出畫出(A, )的哈斯圖的哈斯圖 (2) 判別判別(A, )是格否是格否?分配格嗎分配格嗎?有補格有補格?布爾格嗎布爾格嗎?3010152531格格? 分配格分配格? ?有補格有補格? 布爾格布爾格 5. 知知 f: AB, g: BC, f是單射是單射,g是單射是單射,證明證明g f 是單射是單射. 假設假設g f是滿射是滿射,證明證明g是滿射是滿射.證明證明: (1) 對于恣意的對于恣意的x1,x2 A, 假設假設g

4、f (x1)= g f (x2), 即有即有 g(f(x1)= g(f(x2).由于由于g是單射是單射,故有故有f(x1)=f(x2). 由于由于f是單射是單射,故有故有x1=x2. 因此因此, g f 是單射是單射.(2) 對于恣意對于恣意z C, 存在存在x A, 使得使得g f (x)=z,即即 g(f(x)=z.故存在故存在 y=f(x) B, 使得使得g(y)=z.故故 g是滿射是滿射.6. (4分分) 知知: A是可數無限集，是可數無限集，B是有限集，是有限集， 且且AB=， 求證：求證：|A|=|AB|證明證明: 無妨記無妨記A=a1, a2, a3, ,an, B=b1, b2

5、, b3, , bm 作映射作映射 : AAB(ai)=bi (i=1,m)(ai)=ai-m (i=m+1,m+2,) 那么可以闡明那么可以闡明為為AAB的雙射，的雙射， 故結論得證。故結論得證。假設只用一句話說，假設只用一句話說， AB也是可數無限集，可以得也是可數無限集，可以得2分分7. (5分分) 畫出畫出5個頂點的自互補圖。證明當個頂點的自互補圖。證明當n=4k 或或4k+1時才時才有有. 假設一個圖和它的補圖同構，說它是自互補圖。假設一個圖和它的補圖同構，說它是自互補圖。解解: :1 12 2由于由于n n個頂點的無向完全圖有個頂點的無向完全圖有n(n-1)/2n(n-1)/2個邊

6、，所以自個邊，所以自互補圖各有互補圖各有n(n-1)/4n(n-1)/4個邊，因此，個邊，因此，n=4kn=4k或或4k+14k+1。8. (5分分) 證明證明: G或者或者G有一個是連通圖。有一個是連通圖。證明：由于證明：由于G不連通，那么不連通，那么G可以分為假設干連通子圖可以分為假設干連通子圖: G1=V1，E1，- ，Gn=Vn，En 根據根據G的補圖的構造過程知的補圖的構造過程知V1中每個頂點與其它中每個頂點與其它頂點集頂點集V2，- ，Vn中頂點有邊相連。中頂點有邊相連。 這樣，這樣， 在在G的補圖中，有的補圖中，有n 分別屬于兩個頂點子集分別屬于兩個頂點子集Vi與與Vj中的恣意兩

7、個頂點中的恣意兩個頂點之間有邊直接相連，之間有邊直接相連，n 屬于同一個頂點子集屬于同一個頂點子集Vi的恣意兩個頂點借助頂點的恣意兩個頂點借助頂點子集子集Vj的恣意一個頂點連通。的恣意一個頂點連通。n 所以，根據連通的定義知：所以，根據連通的定義知：G的補圖一定連通的補圖一定連通 。9. (4分) 一個有奇數條邊、偶數個頂點的歐拉圖，但不是哈密爾頓圖。10 (6分分) 畫出畫出K4,4，判別，判別K4,4能否平面圖能否平面圖.否!11. (5分分) 證明證明: 多于一個頂點的樹，至少有兩片樹葉。多于一個頂點的樹，至少有兩片樹葉。證明：設證明：設 T=(V,E)是一棵樹，假設是一棵樹，假設T中最

8、多只需一片樹葉，中最多只需一片樹葉，那么有那么有d(v) 1+2(|V|-1)=2|E|+1, 這與結論這與結論 d(v) =2|E| 矛盾矛盾! 矛盾闡明矛盾闡明 T 不止一不止一片樹葉。片樹葉。12. (8分分) (G, )是一個群，取定是一個群，取定u G. g1,g2 G，定義：，定義： g1*g2= g1u-1g2. 證明證明: (G,*)是群。是群。證明證明: (1) 封鎖性封鎖性 (2) 可以結合性可以結合性 (3) 幺元幺元 e*=u.現實上現實上, g*e*=g*u=gu-1u=ge=g e*g=u*g=uu-1g=eg=g(4) 逆元逆元 對于對于g G, 在代數運算在代數

9、運算*下的逆元記為下的逆元記為g*-1于是于是, g*-1=ug-1u這里這里, g-1是在代數運算是在代數運算下的逆元下的逆元13. (5分分) G是一個群是一個群,H,K是是G正規(guī)子群正規(guī)子群. 證明證明: HK是是G正規(guī)子群正規(guī)子群.證明證明: (1) (3分分) a,b HK,就有就有a,b H, a,b K， 由于由于H, K是群是群G的子群，的子群， 所以，所以，a*b-1H，a*b-1K，因此，因此a*b-1 HK。故故 HK是是G的子群。的子群。 (2) (2分分) 對于對于a HK, gG, 就有就有a H，aK。 由于由于H，K是群是群G的正規(guī)子群，所以的正規(guī)子群，所以g*

10、a*g-1H, g*a*g-1K, 從而有從而有g*a*g-1HK， 故故HK是是G的正規(guī)子群。的正規(guī)子群。14. (4分分) 知知(G, *)，(A, )是兩個群，是兩個群，f: GA是群同態(tài)的。是群同態(tài)的。 證明證明: (1) f(eG)=eA (eG G是幺元是幺元, eA A是幺元是幺元). (2) g G, f(g-1)=(f(g)-1.證明證明: (1) f(eGeG)f(eG)， 又又f(eGeG)f(eG) f(eG)，所以，所以 f(eG) f(eG)f(eG*eG) f(eG)f(eG)eA， 根據群的左消去律根據群的左消去律, 有有 f (eG) eA。 (2) 對于恣意

11、的對于恣意的g G，f(g*g-1)f(g) f(g-1)， 又又f(g*g-1)f(eG)eA，所以，所以 f(g) f(g-1)eA f(g) (f(g)-1， 由左消去律，由左消去律，f(g-1) (f(g)-1。15. (4分分) 以下哪些是循環(huán)群以下哪些是循環(huán)群:(Z，+) (N, +) (Q, +) (Z6, ) 16. (4分分) 試證明結合詞集合試證明結合詞集合，是完備的。是完備的。證明證明: PQ= P Q PQ= ( P Q) PQ = P Q P Q 即即 ， , , , 可以用可以用 ， 表示出來表示出來. 所以任何公式所以任何公式均可以由集合均可以由集合 ， 中的結合

12、詞表中的結合詞表達出來的公式與之等價。達出來的公式與之等價。 故集合故集合 ， 是完備的。是完備的。17. (4分分) 試求公式試求公式 (pq)(qr)p)的主析的主析取范式和主合取范式取范式和主合取范式.解解: (pq)(qr)p) = (pq)( qr)p) = (pq)( qr) p) ( ( qr) p) = (pq)( q p)(r p) (q r) p) = p q ( q p)(r p) (q rp) = p q (q rp) = ( pqr) ( pq r) ( p qr) ( p q r) (p qr) (p q r) (pq r) =(0,1,2,3,4,5,6) =(7

13、)= p q r18. (6分分) 將以下語句化為含有量詞的謂詞演算公式將以下語句化為含有量詞的謂詞演算公式不是每個人都能干不是每個人都能干,但一定有人能干但一定有人能干.有一種氣體可以腐蝕任何金屬有一種氣體可以腐蝕任何金屬. 凡是對頂角一定相等凡是對頂角一定相等.解解: ( x(P(x) A(x) (x(P(x) A(x) x(G(x) (y(M(y) R(x,y) xy(A(x,y) (x=y)19. (5分分) 知公理知公理 A: (pq) (qp) (pq) B: ppq C: pp D: (pr) (qr) (pq) r) E: pqp 證明定理證明定理: p(pp)證明證明:(1) ppq 公理公理B(2) ppp 代入代入(3) (pr) (qr) (pq) r) 公理公理D(4) (pp) (pp) (pp) p) 代入代入(5) p p 公理公理C(6) (pp) (pp) p) (4)(5)分別分別(7) (p