《离散数学期末考试试题及答案》由会员分享，可在线阅读，更多相关《离散数学期末考试试题及答案（30页珍藏版）》请在金锄头文库上搜索。
1、离散数学试题(B卷答案1）一、证明题（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)(P(QR)(PQR)（P(QR)）(PQR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(
2、PQR)m0m1m2m7M3M4M5M6三、推理证明题（10分）1） 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)R(x) P(4)P(a)Q(y)R(a) T(3)，US(5)Q(y)R(a) T(2)(4)，I
3、(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，|BC|=5，|ABC|=2。先求|AB|。6=|（AC）B|=|（AB）（BC）|=|（AB）|+
4、|（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。求R-1、R*S、S*R、R1，2、S1，2（10分）。解：R-1=| x，yNy=x2R*S=
5、| 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，则（
6、x-y）/m=uI，（y-z）/m=vI，于是（x-z）/m=（x-y+y-z）/m=u+v I，因此xRz。九、若f:AB和g:BC是双射，则（gf）-1=f-1g-1（10分）。证明：因为f、g是双射，所以gf：AC是双射，所以gf有逆函数（gf）-1：CA。同理可推f-1g-1：CA是双射。因为f-1g-1存在z（g-1f-1）存在z（fg）gf（gf）-1，所以（gf）-1=f-1g-1。离散数学试题(B卷答案2）一、证明题（10分）1)(PQ)(P(QR)(PQ)(PR)T证明: 左端(PQ)(P(QR)(PQ)(PR)(摩根律) (PQ)(PQ)(PR)(PQ)(PR)(分配律)
7、(PQ)(PR)(PQ)(PR) (等幂律) 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)二、求命题公式(PQ)(PQ) 的主析取范式和主合取范式（10分）解：(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PPQ)(QPQ)(PQ)M1m0m2m3三、推理证明题（10分）1)(P(QS)(RP)QRS证明：(1)R(2)RP(3)P(4)P(QS)(5)QS(6)Q(7)S(8)RS2) $x(A(x)yB(y)，x
8、(B(x)$yC(y)xA(x)$yC(y)。证明：(1)$x(A(x)yB(y) P (2)A(a)yB(y) T(1)，ES(3)x(B(x)$yC(y) P(4)x(B(x)C() T(3)，ES(5)B()C() T(4)，US(6)A(a)B() T(2)，US(7)A(a)C() T(5)(6)，I(8)xA(x)C() T(7)，UG(9)xA(x)$yC(y) T(8)，EG四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15分）。解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进
9、入考场，个体域：考生的集合，则命题可符号化为：P$xA(x)，xA(x)QQP。(1)P$xA(x) P(2)PxA(x) T(1)，E(3)xA(x)P T(2)，E (4)xA(x)Q P(5)(xA(x)Q)(QxA(x) T(4)，E(6)QxA(x) T(5)，I(7)QP T(6)(3)，I五、已知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(R)=,s(R)=,R2=R5=,R3=,R4=,t(R)=,5,
