离散数学试题(A卷及答案)

1、离散数学试题(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的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能

3、是退化的）面积不超过1/8（5分）。证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。五、已知A、B、C是三个集合，证明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=，求其关系矩阵及关系图（10分）。解：关系矩阵为七、设R=，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。解：r

4、(R)=，s(R)=，R2=R5=，R3=，R4=，t(R)=，八、=A1，A2，An是集合A的一个划分，定义R=|a、bAi，I=1，2，n，则R是A上的等价关系（15分）。证明：aA必有i使得aAi，由定义知aRa，故R自反。a，bA，若aRb ，则a，bAi，即b，aAi，所以bRa，故R对称。a，b，cA，若aRb 且bRc，则a，bAi及b，cAj。因为ij时AiAj=，故i=j，即a，b，cAi，所以aRc，故R传递。总之R是A上的等价关系。九、若f:AB是双射，则f-1:BA是双射（15分）。证明:对任意的xA，因为f是从A到B的函数，故存在yB，使f，f-1。所以，f-1是满射

5、。对任意的xA，若存在y1，y2B，使得f-1且f-1，则有f且f。因为f是函数，则y1=y2。所以，f-1是单射。因此f-1是双射。离散数学试题(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名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数（10分）。解：A，B，C分别表示会打排球、网球和篮球的学生集合。则|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。不会打这三种球的人数25-20=5。五、已知A、B、C是三个集合，证明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上的关系，其定义如下：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。七、设R=，求r(R)、s(R)和t(R) （15分）。解：r(R)=，s(R)=，R2= R5=，R3=，R4=，t(R)=，八、证明整数集I上的模m同余关系R=|xy(mod m)是等价关系。其中，xy(mod m)的含义是x-y可以被m整除（15分）。证明：1）xI，因为（x-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