离散数学期末考试试题(有几套带答案1).doc

离散试卷及答案离散数学试题(A卷及答案）一、证明题（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)(PQR)m0m1m2m7M3M4M5M6三、推理证明题（10分）第 5 页 共 5 页1） CD, (CD) E, E(AB), (AB)(RS)RS证明：(1) (CD)E (2) E(AB) (3) (CD)(AB)(4) (AB)(RS) (5) (CD)(RS) (6) CD (7) RS2) x(P(x)Q(y)R(x)，$xP(x)Q(y)$x(P(x)R(x)证明（1）$xP(x)(2)P(a)(3)x(P(x)Q(y)R(x)(4)P(a)Q(y)R(a)(5)Q(y)R(a)(6)Q(y)(7)R(a)(8)P(a)(9)P(a)R(a)(10)$x(P(x)R(x)(11)Q(y)$x(P(x)R(x) 五、已知A、B、C是三个集合，证明A-(BC)=(A-B)(A-C) （15分）证明 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=x2，R*S=| x,yNy=x2+1，S*R=| x,yNy=（x+1）2，七、若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。R1,2=,，S1,2=1,4。 离散数学试题(B卷及答案）一、证明题（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) (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 五、已知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）六、p=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=F，故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是满射。对任意的xA，若存在y1,y2B，使得f-1且f-1,则有f且f。因为f是函数，则y1=y2。所以，f-1是单射。 因此f-1是双射。 一、 选择题.(每小题2分，总计30) 1. 给定语句如下：（1）15是素数（质数）（2）10能被2整除，3是偶数。（3）你下午有会吗？若无会，请到我这儿来！（4）2x+30.（5）只有4是偶数，3才能被2整除。(6)明年5月1日是晴天。以上6个语句中，是简单命题的为（A）,是复合命题的为（B）,是真命题的为（C）,是假命题的是（D）,真值待定的命题是（E）A: (1)(3)(4)(6) (1)(4)(6) (1)（6） B: (2)(4) (2)(4)(6) (2)(5)C: (1)(2)(5)(6) 无真命题 （5） D: (1)(2) 无假命题 (1)(2)(4)(5)E: (4)(6) （6） 无真值待定的命题2. 将下列语句符号化：（1）4是偶数或是奇数。（A）设p：4是偶数，q：4是奇数（2）只有王荣努力学习，她才能取得好成绩。（B）设p：王荣努力学习，q：王荣取得好成绩（3）每列火车都比某些汽车快。（C）设F(x):x是火车，G(y):y是汽车，H(x,y):x比y快。A: pq pq pq B: pq qp pqC: x $y (F(x) G(y) (H(x,y)x (F(x) $y(G(y)H(x,y)x (F(x) $y(G(y)H(x,y)3. 设S=1,2,3,下图给出了S上的5个关系,则它们只具有以下性质:R1是（A）,R2是(B),R3是(C)。A B C:自反的，对称的，传递的 反自反的，对称的 自反的 反对称的 对称的 自反的，对称的，反对称的，传递的4. 设S=，1，1，2，则有 （1）（A）S （2） (B) S（3） P(S)有（C）个元数。 （4）（D）既是S的元素，又是S的子集A: 1,2 1 B: 1,2 1C: 3 6 7 8 D: 1 二、证明（本大题共2小题，第1小题10分，第2小题10分，总计20分）1、用等值演算算法证明等值式 (pq)(pq)p2、构造下面命题推理的证明如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分，总计30分）1、设，求公式：的真值。2、设集合上的关系 ，求出它的自反闭包，对称闭包和传递闭包。3、设上的整除关系，是否为上的偏序关系？若是，则：1、画出的哈斯图；（10分）2、求它的极小元，最大元，极大元，最大元。（5分）四、用推导法求公式的主析取范式和主合取范式。（本大题10分）答案：一、 选择题1. A: B: C: D: E: 2.A: B: C: 3.A: B: C: 4.A: B: C: D:二、证明题1. 证明 左边（(pq)p）（(pq)q)） （分配律） p（(pq)q)） (吸收律) p（(pq) (qq)） （分配律） p（(pq)1） （排中律） p (pq) （同一律） p （吸收律）2.解：p：今天是星期三。 q：我有一次英语测