離散數(shù)學(xué)期末考試試題及答案

1、離散數(shù)學(xué)試題 (B 卷答案 1）一、證明題（10 分）1)(P (Q R) (Q R) (P R)R證明: 左端(PQR)(QP)R)(PQ)R)(QP)R)(PQ)R)(QP)R)(PQ)(QP)R(PQ)(PQ)RTR(置換)R2)x (A(x)B(x)xA(x)xB(x)證明 ：x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)二、求命題公式(P (Q R)(P QR)的主析取范式和主合取范式（證明： (P (QR)(P Q R)(P (Q R) (P Q R)10 分）。（P (QR) ） (P Q R)(PPQ)(PQ R) (R)P

2、 (P Q R)QR) (P QR) (PQR) (P Q R)m0m1 m2 m7M3M4 M5 M6三、推理證明題（10 分）1） C D， (C D)E，E (A B)， (A B) (R S) RS證明： (1) (CD)EP(2)E (A B)P(3)(C D)(AB)T(1)(2)，I(4)(A B)(R S)P(5)(C D)(R S)T(3)(4)， I(6)C DP(7) R ST(5)， I2)x(P(x)Q(y) R(x) ，xP(x)Q(y) x(P(x) R(x)證明 (1)xP(x)P(2)P(a)T(1)， ES(3)x(P(x)Q(y) R(x)P(4)P(a)

3、Q(y) R(a)T(3)，US(5)Q(y) R(a)T(2)(4)， I(6)Q(y)T(5)，I(7)R(a)T(5)，I(8)P(a) R(a)T(2)(7)， I(9)x(P(x) R(x)T(8)， EG(10)Q(y)x(P(x) R(x)T(6)(9)， I四、某班有25 名學(xué)生，其中 14 人會(huì)打籃球，12 人會(huì)打排球，6 人會(huì)打籃球和排球， 5人會(huì)打籃球和網(wǎng)球，還有2 人會(huì)打這三種球。而6 個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)（10 分）。解：A，B，C 分別表示會(huì)打排球、 網(wǎng)球和籃球的學(xué)生集合。則 |A|=12 ，|B|=6 ，|C|=14 ，|A C|

4、=6 ，|B C|=5， |A BC|=2 。先求 |A B| 。 6=| （ A C） B|=| （ A B）（ B C） |=| （ A B） |+| （ B C） |-|A B C|=|（ A B） |+5-2 ， | （ A B） |=3 。于是 |A B C|=12+6+14-6-5-3+2=20。不會(huì)打這三種球的人數(shù)25-20=5 。五、已知 A、 B、 C 是三個(gè)集合，證明A-(B C)=(A-B) (A-C)（ 10 分）。證明： x A- （ B C） xA x （ BC）xA （ xBx C）（ xA xB）（ xA xC）x （ A-B） x （ A-C）x（ A-B）（

5、 A-C） A- （B C） =（ A-B）（ A-C）六、已知 R、S 是 N 上的關(guān)系，其定義如下：R=|x，y2N y=x ， S=| x，y N y=x+1 。求 R-1 、 R*S、 S*R、R 1 ， 2 、S1 ，2（ 10分）。解： R-1 =| x， y N y=x 2R*S=| x ， y2N y=x +1S*R=| x，yN y=（x+1）2 ，R 1 ， 2=， ，S1 ，2=1，4 。七、設(shè) R=， ，求 r(R) 、 s(R) 和 t(R)（ 15 分）。解： r(R)=， ， ， ， ， s(R)=， ， R2= R 5=， ， R3=， ， R4=， ， t(R

6、)=， ，八、證明整數(shù)集I 上的模 m同余關(guān)系R=|xy(mod m) 是等價(jià)關(guān)系。 其中，xy(modm)的含義是x-y 可以被 m整除（ 15 分）。證明： 1） xI ，因?yàn)椋?x-x 2） x， y I ，若 xRy，則 x） /m=0，所以 x x(mod m) ，即 xRx。y(mod m) ，即（ x-y ） /m=k I ，所以（ y - x） /m=-k I ，所以 y x(mod m) ，即 yRx。3）x， y， zI ，若 xRy， yRz，則（ x-y ）/m=u I ，（ y-z ）/m=v I ，于是（ x-z ）/m=（ x-y+y-z ） /m=u+v I ，

7、因此 xRz。九、若 f:A B 和 g:B C 是雙射，則（gf ） -1 =f -1 g-1 （ 10 分）。證明：因?yàn)閒 、 g 是雙射，所以gf ： AC是雙射，所以gf 有逆函數(shù)（ gf ） -1 ：C A。同理可推 f -1 g-1 ： C A 是雙射。因?yàn)?f -1 g-1存在 z（ g-1f -1 ） 存在 z（ f g） gf（ gf ） -1 ，所以（ gf ） -1 =f -1 g-1 。一、證明題（10 分）離散數(shù)學(xué)試題 (B 卷答案 2）1)(P Q)(P (Q R) ( PQ) ( P R) T證明 : 左端(P Q) (P (Q R) (P Q)(P R)( 摩根

8、律 )(P Q) (P Q) (P R) (P Q) (P R)( 分配律 )(P Q) (P R) (P Q) (P R) ( 等冪律 )T( 代入 )2)xy( P( x)Q( y)(xP( x)yQ( y)證明：xy( P( x)Q( y)xy(P( x) Q( y)x(P( x) yQ( y)xP(x) yQ( y)xP( x) yQ( y)(xP( x)yQ( y)二、求命題公式 (P Q)(P Q)的主析取范式和主合取范式（10 分）解： ( P Q)(P Q)(PQ) (P Q)(P Q) (P Q)(PQ) (P Q)(P P Q) ( Q P Q)(P Q)M1m0 m2m3

9、三、推理證明題（10 分）1)(P(QS) (R P) QRS證明： (1)R(2) R P(3)P(4)P (Q S)(5)Q S(6)Q(7)S(8)R S2)x( A( x)yB( y)，x( B( x)yC( y)xA( x)yC( y) 。證明： (1)x( A( x)yB( y)(2)A( a)yB( y)T(1)， ES(3)x( B( x)yC( y)P(4)x( B( x)C( c )T(3)， ES(5)B( b )C( c )T(4)， US(6)A( a)B( b )T(2)， US(7)A( a) C( c )T(5)(6)， I(8)xA( x) C( c )T(7

10、)， UG(9)xA( x)yC( y)T(8)， EG四、只要今天天氣不好，就一定有考生不能提前進(jìn)入考場(chǎng)，當(dāng)且僅當(dāng)所有考生提前進(jìn)入考場(chǎng)，考試才能準(zhǔn)時(shí)進(jìn)行。所以，如果考試準(zhǔn)時(shí)進(jìn)行，那么天氣就好（15 分）。解設(shè) P：今天天氣好，Q：考試準(zhǔn)時(shí)進(jìn)行，A( e) ： e 提前進(jìn)入考場(chǎng)，個(gè)體域：考生的集合，則命題可符號(hào)化為：Px() ，()Q。A xxA xQ P(1)Px()PA x(2)P()(1) ，ExA xT(3)()P(2)，ExA xT(4)()QPxA x(5)(xA( x)Q) ( QxA( x)T(4)， E(6)QxA( x)T(5)， I(7) QPT(6)(3)，I五、已知A

11、、 B、 C 是三個(gè)集合，證明證明： xA（ B C）xA(B C)=(A B) (A C) （ 10 分）A x（B C）xA（ xB xC）（xA xB）（ xA xC）x（ A B） xA Cx（ A B）（AC） A（ B C）=（ A B）（ A C）六、 A= x 1,x 2,x 3 ， B= y 1,y 2 ， R=, ，求其關(guān)系矩陣及關(guān)系圖（ 10 分）。七、設(shè)R=,，求r(R)、 s(R) 和t(R)，并作出它們及R 的關(guān)系圖（15 分）。解： r(R)=,s(R)=,R2=R5=,R3=,R4=,t(R)=,八、設(shè) R1 是 A 上的等價(jià)關(guān)系， R2 是 B 上的等價(jià)關(guān)系，

12、 A且 B。關(guān)系 R滿足： ， 1 且 2，證明R是 上的等價(jià)關(guān)系（10 分）。xyR x xRyyRA B證明 對(duì)任意的 ，由1 是A上的等價(jià)關(guān)系可得 1，由2 是BxyA BRxxRR上的等價(jià)關(guān)系可得 2。再由R的定義，有 ， ，所以R是自反yRxxyR的。對(duì)任意的 、A B，若 R，則 R1 且 R2。由 R1 對(duì)稱得 R1，由 R2 對(duì)稱得 R2。再由 R 的定義，有 ， R，即 R，所以 R是對(duì)稱的。對(duì)任意的 、 、 A B，若 R且 R，則 R1 且 R2， R1 且 R2。由 R1、 R1 及 R1 的傳遞性得 R1，由 R2、 R2 及 R2 的傳遞性得 R1。再由 R的定義，

13、有 ， R，即 R，所以 R是傳遞的。綜上可得， R是 A B 上的等價(jià)關(guān)系。九、設(shè) f ：A B，g：BC，h：C A，證明：如果hogof I A，f ohogI B， gof oh I C，則f 、 g、 h 均為雙射，并求出f 1、 g1 和 h1（ 10 分）。解 因 I A 恒等函數(shù)， 由 hogof I A 可得 f 是單射， h 是滿射；因 I B 恒等函數(shù)， 由 f ohog I B 可得 g 是單射， f 是滿射；因 I C恒等函數(shù)，由gof oh I C可得 h 是單射， g 是滿射。從而 f 、 g、 h 均為雙射。由 hogof I ，得 f 1 1 1 hog；由

14、f ohog I ，得 g f oh；由 gof oh I ，得 h gof 。ABC離散數(shù)學(xué)試題 (B 卷答案 3）一、（ 10 分）判斷下列公式的類型（永真式、永假式、可滿足式）( 寫(xiě)過(guò)程)1)P(P Q R)2)(QP) P) (P R)3)(P Q)R)(P Q) R)解： 1) 重言式； 2) 矛盾式； 3) 可滿足式二、（ 10 分）求命題公式（P (Q R)(P Q R)的主析取范式，并求成真賦值。解：（ P (Q R)(P Q R)(P (Q R) P QR(P ( PQ Q) (R) P Q RPR)(P Q)R(P Q) (P Q) (PR) R1 (PR) R)1m0 m

15、1 m2 m3m4 m5 m6 m7該式為重言式，全部賦值都是成真賦值。三、（ 10 分）證明 (P QA) C)(A(P Q C)(A (PQ)C證明： (P QA)C) (A(P Q C)(P Q A) C) (A(P QC)(PQA) C) (A P Q) C)(PQA) (A P Q) C(PQA) (A PQ)C( (PQA) ( A P Q)C(P Q A) (A PQ)C(A (P Q) (PQ)C(A (P Q) (PQ)C(A (QP) (PQ)C(A (PQ)C四、（ 10 分）個(gè)體域?yàn)?1 ， 2 ，求xy（ x+y=4）的真值。解：xy（ x+y=4）x（ x+1=4）

16、（ x+2=4）（ 1+1=4）（ 1+2=4）（ 2+1=4）（ 2+2=4）（ 0 0）（ 0 1） 0 1 0五、（ 10 分）對(duì)于任意集合A，B，試證明： P(A) P(B)=P(A B)解：xP(A) P(B) ，xP(A) 且 xP(B) ，有 xA 且 xB，從而 B) ，由于上述過(guò)程可逆，故P(A) P(B)=P(A B)xAB，xP(A六、（ 10 分）已知 A=1，2，3，4，5 和 R=， ，求 r(R) 、 s(R) 和 t(R) 。解： r(R)=， ， ， ， ， ， ， s(R)=， ，t(R)=， ， ， ， ， ， 七、（ 10 分）設(shè)函數(shù)f ： R RR R

17、， R 為實(shí)數(shù)集， f 定義為： f()= 。1) 證明 f 是雙射。解：1）， R R，若 f()=f() ，即=，則 x1+y1=x2+y2 且 x1-y 1=x2-y 2 得 x1=x2， y1=y2 從而 f 是單射。2） RR，由 f()=，通過(guò)計(jì)算可得x=(p+q)/2 ；y=(p-q)/2；從而 的原象存在， f 是滿射。八、（10 分） 是個(gè)群， u G，定義 G中的運(yùn)算“ ”為 ab=a*u -1 *b ，對(duì)任意 a，b G，求證： 也是個(gè)群。證明： 1）a，b G， ab=a*u -1 *b G，運(yùn)算是封閉的。2）a， b， c G，（ a b） c=（ a*u -1*b

18、） *u -1*c=a*u -1* （ b*u -1*c ） =a （ bc），運(yùn)算是可結(jié)合的。3）a G，設(shè) E 為的單位元，則 aE=a*u-1 *E=a，得 E=u，存在單位元 u。4）a G， a x=a*u-1 *x=E ， x=u*a -1 *u ，則 xa=u*a -1 *u*u -1 *a=u=E，每個(gè)元素都有逆元。所以 也是個(gè)群。九、（ 10 分）已知： D=，V=1 ， 2， 3， 4， 5 ， E=， ， ， ， ，求 D 的鄰接距陣A 和可達(dá)距陣P。解： 1） D 的鄰接距陣A 和可達(dá)距陣P 如下：01010111110010011111A= 0 0 0 1 1P= 1

19、 1 1 1100000000001000011111十、（ 10 分）求葉的權(quán)分別為2、 4、 6、8、 10、 12、 14 的最優(yōu)二叉樹(shù)及其權(quán)。解：最優(yōu)二叉樹(shù)為權(quán) (2+4) 4+6 3+12 2+(8+10) 3+142 148離散數(shù)學(xué)試題 (B 卷答案 4）一、證明題（10 分）1)(P Q)(P (QR) (P Q) (P R) T證明 : 左端(P Q) (P (Q R) (P Q) (P R)(摩根律 )(P Q) (P Q) (P R) (P Q) (P R)( 分配律 )(P Q) (P R) (P Q) (P R) (等冪律 )T ( 代入 )2) x(P(x)Q(x)

20、xP(x)x(P(x) Q(x)證明：x(P(x)Q(x) xP(x)x(P(x)Q(x) P(x)x(P(x) Q(x) P(x)x(P(x) Q(x)xP(x) xQ(x)x(P(x) Q(x)二、求命題公式(PQ)(P Q) 的主析取范式和主合取范式（10 分）解： (PQ)(P Q)(PQ) (P Q)(P Q) (P Q)(PQ) (P Q)(P PQ) (Q PQ)(P Q)M1m0 m2 m3三、推理證明題（10 分）1)(P(QS) (R P) Q RS證明：（ 1） R附加前提(2)R PP(3)PT(1)(2),I(4)P(QS)P(5)QST(3)(4),I(6)QP(7

21、)ST(5)(6),I(8)RSCP2)x(P(x) Q(x)，x P(x)x Q(x)證明： (1)xP(x)P(2)P(c)T(1),US(3)x(P(x) Q(x)P(4)P(c) Q(c)T(3),US(5)Q(c)T(2)(4),I(6)x Q(x)T(5),EG四、例 5 在邊長(zhǎng)為1 的正方形內(nèi)任意放置九個(gè)點(diǎn)，證明其中必存在三個(gè)點(diǎn)，使得由它們組成的三角形（可能是退化的）面積不超過(guò)1/8 （ 10 分）。證明：把邊長(zhǎng)為1 的正方形分成四個(gè)全等的小正方形，則至少有一個(gè)小正方形內(nèi)有三個(gè)點(diǎn)，它們組成的三角形（可能是退化的）面積不超過(guò)小正方形的一半，即1/8。五、已知A、 B、 C 是三個(gè)集

22、合，證明A(B C)=(A B) (A C)（ 10 分）證明：xA（ B C）xA x（B C）xA（ xB xC）（xA xB）（ xA xC）x（ A B） xA C（ A B）（AC） A（ B C）=（ A B）（A C）六、=A 1，A2，An是集合A 的一個(gè)劃分，定 R=|a 、 b Ai ，I=1 ， 2，n ， R是A 上的等價(jià)關(guān)系（15 分）。 明：a A 必有 i 使得 a Ai ，由定 知aRa，故 R 自反。a,b A，若 aRb ， a,b Ai ，即 b,a Ai ，所以 bRa，故 R 稱。a,b,c A，若 aRb 且 bRc， a,b Ai 及 b,c Aj

23、 。因 i j 時(shí) Ai Aj =，故i=j，即 a,b,c Ai ，所以 aRc，故 R 。 之 R是 A 上的等價(jià)關(guān)系。七、若 f:A B 是雙射， f -1 :B A 是雙射（ 15 分）。 明 : 任意的 x A，因 f是從 A 到 B 的函數(shù)，故存在yB，使 f ， f -1 。所以 ,f-1 是 射。 任意的x A，若存在y1,y 2 B，使得 f -1 且 f -1 , 有 f且 f 。因 f 是函數(shù)， y1=y2。所以， f -1 是 射。因此 f -1 是雙射。八、 是群， 和 是 的子群， 明：若 ， G或BGABGA B GA G（ 10 分）。 明假 AG且 B G，

24、存在aA， aB，且存在 bB，bA（否 任意的a A， a B，從而 A B，即 A B B，得 B G，矛盾。） 于元素a* b G，若 a* bA，因 A是子群， a-1A，從而 a-1 * ( a* b) bA，所以矛盾，故 a* bA。同理可 a* bB， 合有 a*b A B G。 上所述，假 不成立，得 A G或 B G。九、若無(wú)向 G是不 通的， 明 G的 G 是 通的（ 10 分）。 明 無(wú)向 G是不 通的，其 k 個(gè) 通分支 G、 G2、 G。任取 點(diǎn) u 、1kv G，若 u 和 v 不在 G的同一個(gè) 通分支中， u ， v 不是 G的 ，因而 u ， v 是 G 的 ；

25、若 u 和 v 在 G的同一個(gè) 通分支中，不妨 其在 通分支Gi （ 1 i k ）中，在不同于 G 的另一 通分支上取一 點(diǎn)w ， u ， w和w ， v都不是 G的 ，i因而 u ， w 和 w ， v 都是 G 的 。 上可知，不管那種情況，u 和 v 都是可達(dá)的。由 u和 v 的任意性可知，G 是連通的。離散數(shù)學(xué)試題（B 卷答案 5）一、（ 10 分）求命題公式解： (P Q)(P Q)PR)（(PR)的主合取范式。(P Q)(PR) ）（(PR)(P Q)）（ (P Q) (PR)）（(P R) (PQ)）(P Q) (PR)(P R)（ QP）（QR）(P QR) (P QR)（P

26、 QR）（P QR）M1 M3M4 M5二、（ 8 分）敘述并證明蘇格拉底三段論解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號(hào)化： F（ x）： x 是一個(gè)人。 G（x）： x 要死的。 A：蘇格拉底。命題符號(hào)化為x（ F（ x）G（ x）， F（ a）G（ a）證明：（ 1）x(F(x)G(x)P（ 2） F(a)G(a)T(1),US（ 3） F(a)P（ 4） G(a)T(2)(3),I三、（ 8 分）已知A、B、 C 是三個(gè)集合，證明證明： xA （ B C）xA xA(B C)=(A B) (A C)（B C）xA （ xBxC）（xA xB）（ xA xC）x（ A

27、 B） xA Cx （ A B）（ A C） A（ B C） =（ A B）（ A C）四、（ 10 分）已知 R和 S 是非空集合 A 上的等價(jià)關(guān)系， 試證： 1）R S 是 A 上的等價(jià)關(guān)系；2）對(duì) a A， a R S=a R a S。解：x A，因?yàn)?R 和 S 是自反關(guān)系， 所以 R、 S，因而 R S，故 R S 是自反的。x、 y A，若 R S，則 R、 S，因?yàn)?R 和 S 是對(duì)稱關(guān)系，所以因 R、 S，因而 R S，故 R S 是對(duì)稱的。x、y、z A，若 R S 且 R S，則 R、 S 且 R、 S，因?yàn)?R 和 S 是傳遞的，所以因 R、 S，因而 R S，故 R S

28、 是傳遞的?？傊?R S 是等價(jià)關(guān)系。2）因?yàn)?x a R S R S R Sx aR x a Sx a R aS所以 aR S=a R aS。五、 (10 分)設(shè) a， ， ，R是A上的二元關(guān)系，且 ， ， ， ，求 r ( R) 、 s( R) 和 t ( R) 。解 r ( R) R I A ， ， ， ， ， ， ，s( R) R R-1 ， ， ， ， ， R2 ， ， ， R3 ， ， ， R4 ， ， ， R2( ) Ri ， 六、 (15 分 ) 設(shè) A、 B、 C、 D 是集合， C B D 且 A C，h()f 是 A 到 B 的雙射， g 是 C 到 D 的雙射，令 h：

29、 A 。證明 h 是雙射。證明： 1）先證 h 是滿射。 B D，則 b B，d D，因?yàn)?f 是 A 到 B 的雙射， g 是 C到 D 的雙射，所以存在a A， c C，使得f(a)=b， f(c)=d，亦即存在 A C，使得h() ，所以 h 是滿射。2）再證 h 是單射。 、 A C，若h() h()，則 ，所以 f(a1) f(a2)，g(c1) g(c2) ，因?yàn)?f 是 A 到 B 的雙射， g 是 C到 D 的雙射，所以 a1 a2，c1 c2，所以 ，所以 h 是單射。綜合 1）和 2），h 是雙射。七、 (12 分 ) 設(shè) 是群， H 是 G 的非空子集，證明 是 的子群的

30、充要條件是若 a， bH，則有 a*b -1H。證明：a,b H 有 b-1 H，所以 a*b -1 H。a H，則 e=a*a -1 Ha-1 =e*a -1 H a,b H 及 b-1 H， a*b=a* （ b-1 ） -1 H H G且 H , * 在 H上滿足結(jié)合律 是 的子群。八、（10 分）設(shè) G=是簡(jiǎn)單的無(wú)向平面圖，證明 G至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。解：設(shè)G 的每個(gè)結(jié)點(diǎn)的度數(shù)都大于等于6，則 2|E|=d(v) 6|V| ，即 |E| 3|V| ，與簡(jiǎn)單無(wú)向平面圖的|E| 3|V|-6矛盾，所以G至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。九 .G=,A=a,b,c,*的運(yùn)算表為：(

31、 寫(xiě)過(guò)程， 7 分 )（ 1） G是否為阿貝爾群（ 2）找出 G的單位元；（ 3）找出 G的冪等元（ 4）求 b 的逆元和 c 的逆元解：（ 1） (a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以 G是阿貝爾群（ 2）因?yàn)?a*a=a a*b=b*a=b a*c=c*a=c所以 G的單位元是a（ 3）因?yàn)?a*a=a 所以 G的冪等元是 a（ 4）因?yàn)?b*c=c*b=a ，所以 b 的逆元是 c 且 c 的逆元是 b十、 (10 分) 求葉的權(quán)分別為2、 4、 6、8、 10、12、 14 的最優(yōu)二叉樹(shù)及其權(quán)。解：最優(yōu)二叉樹(shù)為權(quán)