離散數(shù)學(xué)試卷及答案

1、.離散數(shù)學(xué)試題（ A 卷答案）一、（10 分）求 (P Q)(P(QR)的主析取范式解： (P Q)(P(QR)( PQ)(PQR)(PQ)(PQR)(PQP)(PQQ)(PQR)(PQ)(PQR)(PQ(RR)(PQR)(PQR)(PQR)(PQR)M0M1m2 m3 m4 m5 m6 m7二、（10 分）在某次研討會(huì)的休息時(shí)間， 3 名與會(huì)者根據(jù)王教授的口音分別作出下述判斷：甲說：王教授不是蘇州人，是上海人。乙說：王教授不是上海人，是蘇州人。丙說：王教授既不是上海人，也不是杭州人。王教授聽后說：你們 3 人中有一個(gè)全說對(duì)了，有一人全說錯(cuò)了，還有一個(gè)人對(duì)錯(cuò)各一半。試判斷王教授是哪里人？解設(shè)設(shè)

2、 P：王教授是蘇州人； Q：王教授是上海人； R：王教授是杭州人。則根據(jù)題意應(yīng)有：甲：PQ乙：QP丙：QR王教授只可能是其中一個(gè)城市的人或者 3 個(gè)城市都不是。所以，丙至少說對(duì)了一半。因此，可得甲或乙必有一人全錯(cuò)了。 又因?yàn)?，若甲全錯(cuò)了， 則有 Q P，因此，乙全對(duì)。同理，乙全錯(cuò)則甲全對(duì)。所以丙必是一對(duì)一錯(cuò)。故王教授的話符號(hào)化為：;.(PQ) ( QR) (QR) (QP) (QR)(PQQR) (PQQR) (QPQR)(PQR) ( PQR)PQRT因此，王教授是上海人。三、（10 分）證明 tsr( R) 是包含 R 的且具有自反性、對(duì)稱性和傳遞性的最小關(guān)系。證明設(shè) R 是非空集合 A

3、上的二元關(guān)系，則由定理4.19 知， tsr( R) 是包含 R 的且具有自反性、對(duì)稱性和傳遞性的關(guān)系。若 R' 是包含 R 的且具有自反性、 對(duì)稱性和傳遞性的任意關(guān)系，則由閉包的定義知 r ( R)R' 。由定理4.15 和由定理4.16 得 sr( R)s( R' ) R' ，進(jìn)而有tsr( R)t( R' ) R' 。綜上可知， tsr( R) 是包含 R 的且具有自反性、對(duì)稱性和傳遞性的最小關(guān)系。四、（15 分）集合 A a，b，c，d，e 上的二元關(guān)系R 為 R< a，a>，<a，b>，<a，c>，&

4、lt;a，d>， <a，e>，<b，b>，<b，c>，<b，e>，<c，c>，<c，d>，<c，e>，<d，d>，<d，e>，<e，e> ，(1) 寫出 R 的關(guān)系矩陣。(2) 判斷 R 是不是偏序關(guān)系，為什么？解 (1) R 的關(guān)系矩陣為：1111101101M(R) 001010001100001(2) 由關(guān)系矩陣可知， 對(duì)角線上所有元素全為1，故 R 是自反的； rij r ji 1，故 R 是反對(duì)稱的；可計(jì)算對(duì)應(yīng)的關(guān)系矩陣為：;.1111101101M(R2)

5、00101M (R)0001100001由以上矩陣可知R 是傳遞的。五、（10 分）設(shè) A、B、C 和 D 為任意集合，證明 ( AB) ×C( A×C) ( B×C) 。證明：因?yàn)?lt; x ， y >( AB) ×Cx ( AB) y C( x A xB) y C( x A y C xB) ( x A y Cy C)( x A y C) ( xB yC)( x A y C) ( x B y C)< x ， y >( A×C) < x ， y > ( B×C)< x ， y >( A

6、15;C) ( B×C)所以， ( AB) ×C( A×CB×C) 。六、（10 分）設(shè) f：AB，g：BC，h：CA，證明：如果 h g fIA ，f h g I B，g f h IC，則 f、g、h 均為雙射，并求出 f1 、g 1 和 h 1。解 因 IA 恒等函數(shù)，由 h g fIA 可得 f 是單射，h 是滿射；因 I B 恒等函數(shù)，由 f h gIB 可得 g 是單射， f 是滿射；因 IC 恒等函數(shù)，由 g f hI C 可得 h 是單射， g 是滿射。從而 f、g、h 均為雙射。由 h g fI A，得 f1h g；由 f h gI B，

7、得 g1f h；由 g f hI C，得 h1g f。七、（ 15 分）設(shè) <G，*> 是一代數(shù)系統(tǒng)，運(yùn)算 *滿足交換律和結(jié)合律，且 a* x a* y xy，證明：若 G 有限，則 G 是一群。;.證明 因 G 有限，不妨設(shè) G a1 ， a2 ， ， an 。由 a* xa* y xy 得，若 xy，則 a* xa*y。于是可證，對(duì)任意的 aG，有 aGG。又因?yàn)檫\(yùn)算 * 滿足交換律， 所以 aGGGa。令 eG 使得 a* ea。對(duì)任意的 b G，令 c* a b，則 b* e(c* a)* ec*( a* e)c* ab，再由運(yùn)算 * 滿足交換律得 e* b b，所以 e

8、是關(guān)于運(yùn)算 * 的幺元。對(duì)任意 aG，由 aGG 可知，存在 bG 使得 a* b e，再由運(yùn)算 *滿足交換律得 b* ae，所以 b 是 a 的逆元。由 a 的任意性知，G 中每個(gè)元素都存在逆元。故G 是一群。八、（20 分）（1）證明在 n 個(gè)結(jié)點(diǎn)的連通圖 G 中，至少有 n1 條邊。證明 不妨設(shè) G 是無向連通圖（若 G 為有向圖，可略去邊的方向討論對(duì)應(yīng)的無向圖）。設(shè) G 中結(jié)點(diǎn)為 v1 、 v2 、 、 vn 。由連通性，必存在與 v1 相鄰的結(jié)點(diǎn)，不妨設(shè)它為 v2（否則可重新編號(hào)），連接 v1 和 v2 ，得邊 e1 ，還是由連通性， 在 v3 、v4 、 、vn 中必存在與 v1

9、或 v2 相鄰的結(jié)點(diǎn)，不妨設(shè)為 v3 ，將其連接得邊 e2 ，續(xù)行此法， vn 必與 v1 、 v2 、 、 vn 1 中的某個(gè)結(jié)點(diǎn)相鄰，得新邊 en 1 ，由此可見 G 中至少有 n1條邊。（2）給定簡單無向圖 G<V，E>，且 | V| m，| E| n。試證：若 n Cm212，則 G 是哈密爾頓圖。證明 若 n Cm21，則23m6（1）。22nm若存在兩個(gè)不相鄰結(jié)點(diǎn)、 使得 d() d() m，則有 2nd (w) uvuvm ( mw V2)( m3) m m23m6，與（ 1）矛盾。所以，對(duì)于G 中任意兩個(gè)不相鄰結(jié)點(diǎn) u 、 v 都有 d( u ) d( v ) m。

10、由定理10.26 可知， G 是哈密爾頓圖。;.離散數(shù)學(xué)試題（ B 卷答案）一、（ 10 分）使用將命題公式化為主范式的方法，證明( PQ)( PQ) (Q P)(PQ)。證明：因?yàn)?( PQ)( PQ)(PQ) ( PQ)( PQ)(PQ)( QP) ( PQ)(QP) ( PQ)( PQ) (QQ) ( PP) ( PQ);.(PQ)P( PQ) ( P( QQ)( PQ) ( PQ) ( PQ)( PQ) ( PQ)所以，( PQ)( PQ)(QP)( PQ)。二、（10 分）證明下述推理： 如果 A 努力工作，那么 B 或 C 感到愉快；如果 B 愉快，那么 A 不努力工作；如果 D

11、愉快那么 C 不愉快。所以，如果 A 努力工作，則 D 不愉快。解設(shè) A：A 努力工作； B、C、D 分別表示 B、C、D 愉快；則推理化形式為：A BC，BA，DCA D(1)A附加前提(2)ABCP(3)BCT(1)(2)，I(4)BAP(5)ABT(4) ，E(6)BT(1)(5)，I(7)CT(3)(6)，I(8)DCP(9)DT(7)(8)，I(10) ADCP三、（10 分）證明x y( P( x)Q( y) ( xP( x)yQ( y) 。xy( P( x)Q( y)x y(P( x) Q( y)x(P( x) yQ( y)xP( x) yQ( y)xP( x) yQ( y);.

12、(xP( x)yQ( y)四、（10 分）設(shè) A，1，1 ，B0 ，0 ，求 P( A) 、P( B) 0 、P( B)B。解P( A) ， ，1 ，1，1 ，1 ，1 ，1 ，1，1P( B) 0 ，0 ，0，0 ，0 0 ，0 ，0，0 ，0P( B)B，0 ，0，0 ，00 ，0 ，0，0，0 ，0五、（15 分）設(shè) X1 ，2，3，4 ，R 是 X 上的二元關(guān)系， R<1 ，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>(1)

13、 畫出 R 的關(guān)系圖。(2) 寫出 R 的關(guān)系矩陣。(3) 說明 R 是否是自反、反自反、對(duì)稱、傳遞的。解 (1) R 的關(guān)系圖如圖所示：(2) R 的關(guān)系矩陣為：11100000M (R)11101110(3) 對(duì)于 R 的關(guān)系矩陣，由于對(duì)角線上不全為 1，R 不是自反的；由于對(duì)角線上存在非 0 元，R 不是反自反的；由于矩陣不對(duì)稱， R 不是對(duì)稱的；經(jīng)過計(jì)算可得11100000M (R2)11M ( R) ，所以 R 是傳遞的。101110六、（15 分）設(shè)函數(shù) f：R×RR×R，f 定義為： f(< x，y>) <xy，xy>。(1) 證明 f

14、 是單射。;.(2) 證明 f 是滿射。(3) 求逆函數(shù) f1 。(4) 求復(fù)合函數(shù) f1 f 和 f f。證明 (1)對(duì)任意的 x，y，x1，y1R，若 f(< x，y>) f(< x1，y1>) ，則<xy，xy><x1y1，x1y1>，xyx1y1，xy x1y1，從而 xx1，yy1，故 f是單射。(2)對(duì)任意的 <u，w>R×R，令 x uw ，y uw ，則 f(< x，y>) < u w222 uw ， u w uw ><u，w>，所以 f 是滿射。222(3)f1(<

15、 u，w>) < u w ， uw >。22(4)f 1 f(< x， y>) f 1( f(< x， y>) f 1(< x y，x y>) < xy x y ，2x y (x y) ><x，y> 2f f(< x，y>) f( f(< x，y>) f(< xy，xy>) <xyxy，xy( xy)> <2x，2y>。七、（15 分）給定群 <G，*> ，若對(duì) G 中任意元 a 和 b，有 a3* b3( a* b) 3， a4* b4 ( a

16、* b) 4，a5* b5( a* b) 5，試證 <G，*>是 Abel 群。證明對(duì) G 中任意元 a 和 b。因?yàn)?a3* b3 ( a* b) 3 ，所以 a 1 *a3* b3* b 1 a 1 *( a* b) 3* b 1 ，即得 a2*b2 ( b* a) 2。同理，由 a4* b4( a* b) 4 可得， a3*b3( b*a) 3。由 a5* b5( a* b) 5 可得， a4* b4 ( b* a) 4。于是 ( a3*b3)*( b*a) ( b* a) 4a4* b4，即 b4* aa* b4。同理可得，( a2* b2)*( b* a) ( b*a) 3a3* b3，即 b3* aa* b3。344333由于 ( a* b)* b a* b b * ab* (b * a)b* (a* b )(b* a)* b ，故 a*bb* a。證明不妨設(shè) G 是無向連通圖（若 G 為有向圖，可略去邊的方向討論對(duì)應(yīng);.的無向圖）。設(shè) G 中結(jié)點(diǎn)為 v1 、 v2 、