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

1、離散數(shù)學(xué)試題(A卷及答案)一、證明題（10分）1)(PQ)(P(QR)(PQ)(PR)T證明: 左端(PQ)(P(QR)(PQ)(PR)(摩根律) (PQ)(PQ)(PR)(PQ)(PR)(分配律) (PQ)(PR)(PQ)(PR) (等冪律)T(代入)2)x(P(x)Q(x)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)(PQ) 的主析取范式和主合取范式（10分）。解：(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (

2、PPQ)(QPQ)(PQ)M1m0m2m3三、推理證明題（10分）1)(P(QS)(RP)QRS證明：（1）R 附加前提（2）RP P（3）P T(1)(2)，I（4）P(QS) P（5）QS T(3)(4)，I（6）Q P（7）S T(5)(6)，I（8）RS CP2) x(P(x)Q(x)，xP(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四、在邊長為1的正方形內(nèi)任意放置九個(gè)點(diǎn)，證明其中必存在三個(gè)點(diǎn)，使得由它們組成的三角形（可能

3、是退化的）面積不超過1/8（5分）。證明：把邊長為1的正方形分成四個(gè)全等的小正方形，則至少有一個(gè)小正方形內(nèi)有三個(gè)點(diǎn)，它們組成的三角形（可能是退化的）面積不超過小正方形的一半，即1/8。五、已知A、B、C是三個(gè)集合，證明A(BC)=(AB)(AC) （10分）。證明：x A（BC） x Ax（BC） x A（xBxC）（ x AxB）（x AxC） x（AB）x AC x（AB）（AC）A（BC）=（AB）（AC）六、A= x1，x2，x3 ，B= y1，y2，R=，求其關(guān)系矩陣及關(guān)系圖（10分）。解：關(guān)系矩陣為七、設(shè)R=，求r(R)、s(R)和t(R)，并作出它們及R的關(guān)系圖（15分）。解：r

4、(R)=，s(R)=，R2=R5=，R3=，R4=，t(R)=，八、=A1，A2，An是集合A的一個(gè)劃分，定義R=|a、bAi，I=1，2，n，則R是A上的等價(jià)關(guān)系（15分）。證明：aA必有i使得aAi，由定義知aRa，故R自反。a，bA，若aRb ，則a，bAi，即b，aAi，所以bRa，故R對稱。a，b，cA，若aRb 且bRc，則a，bAi及b，cAj。因?yàn)閕j時(shí)AiAj=，故i=j，即a，b，cAi，所以aRc，故R傳遞?？傊甊是A上的等價(jià)關(guān)系。九、若f:AB是雙射，則f-1:BA是雙射（15分）。證明:對任意的xA，因?yàn)閒是從A到B的函數(shù)，故存在yB，使f，f-1。所以，f-1是滿射

5、。對任意的xA，若存在y1，y2B，使得f-1且f-1，則有f且f。因?yàn)閒是函數(shù)，則y1=y2。所以，f-1是單射。因此f-1是雙射。離散數(shù)學(xué)試題(B卷及答案）一、證明題（10分）1)(P(QR)(QR)(PR)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(QR)(PQR)的主析取范式和主合取范式（10分）。證明：(P(QR)(PQR)

6、(P(QR)(PQR)（P(QR)）(PQR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m0m1m2m7M3M4M5M6三、推理證明題（10分）CD， (CD) E， E(AB)， (AB)(RS)RS證明：(1) (CD)E P(2) E(AB) P(3) (CD)(AB) T(1)(2)，I(4) (AB)(RS) P(5) (CD)(RS) T(3)(4)， I(6) CD P(7) RS T(5)，I 2) 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

7、)R(x) P(4)P(a)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人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個(gè)會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)（10分）。解：A，B，C分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。則|A|=12，|B|=6，|C|=14，|AC|=6，|

8、BC|=5，|ABC|=2。先求|AB|。6=|（AC）B|=|（AB）（BC）|=|（AB）|+|（BC）|-|ABC|=|（AB）|+5-2，|（AB）|=3。于是|ABC|=12+6+14-6-5-3+2=20。不會打這三種球的人數(shù)25-20=5。五、已知A、B、C是三個(gè)集合，證明A-(BC)=(A-B)(A-C) （10分）。證明：x A-（BC） x Ax（BC） x A（xBxC）（x AxB）（x AxC） x（A-B）x（A-C） x（A-B）（A-C）A-（BC）=（A-B）（A-C）六、已知R、S是N上的關(guān)系，其定義如下：R=| x，yNy=x2，S=| x，yNy=x+1

9、。求R-1、R*S、S*R、R1，2、S1，2（10分）。解：R-1=| x，yNy=x2R*S=| x，yNy=x2+1S*R=| x，yNy=（x+1）2，R1，2=，S1，2=1，4。七、設(shè)R=，求r(R)、s(R)和t(R) （15分）。解：r(R)=，s(R)=，R2= R5=，R3=，R4=，t(R)=，八、證明整數(shù)集I上的模m同余關(guān)系R=|xy(mod m)是等價(jià)關(guān)系。其中，xy(mod m)的含義是x-y可以被m整除（15分）。證明：1）xI，因?yàn)椋▁-x）/m=0，所以xx(mod m)，即xRx。2）x，yI，若xRy，則xy(mod m)，即（x-y）/m=kI，所以（y - x）/m=-kI，所以yx(mod m)，即yRx。3）x，y，zI，若xRy，yRz，則（x-y）/m=uI，（y-z）/m=vI，于是（x-z）/m=（x-y+y-z）/m=u+v I，因此xR