《离散数学(1-4章)自测题(答案).doc》由会员分享，可在线阅读，更多相关《离散数学(1-4章)自测题(答案).doc（8页珍藏版）》请在金锄头文库上搜索。
1、 离散数学题库答案第2，3章(数理逻辑)1.答：（2），（3），（4）2.答：（2），（3），（4），（5），（6）3.答：（1） 是，T （2） 是，F （3） 不是（4） 是，T （5） 不是 （6） 不是4.答：（1） （2） （3） （4）5.答：（1）6.答：2不是偶数且-3不是负数。7.答：（2）8.答：P ，QP9.答：P(x) $yR(y)10.答：x(R(x)Q(x)11、 a、(PQ)R 解：(PQ)R(PQ )R(PR)(QR) （析取范式）(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) m3 m1m7 （主析取范式）
2、m1 m3m7 M0M2M4M5M6 （主合取范式）b、Q(PR) 解：Q(PR)QPRM5（主合取范式） m0 m1 m2m3 m4m6 m7 （主析取范式）c、P(P(QP) 解：P(P(QP)P(P(QP)PP 1 (主合取范式) m0 m1m2 m3 （主析取范式）d、P(P(Q(QR)解：P(P(Q(QR) P(P(Q(QR) PQR M0 (主合取范式) m1 m2m3 m4 m5m6 m7 (主析取范式)12、a、PQ，QR，R，SP=S证明：(1) R 前提(2) QR 前提(3) Q （1），（2）析取三段论(4) PQ 前提(5) P （3），（4）拒取式(6) SP 前提
3、(7) S （5），（6）析取三段论b、P(QR)，R(QS) = P(QS)证明：（1） P 附加前提（2） Q 附加前提（3） P(QR) 前提（4） QR （1），（3）假言推理（5） R （2），（4）假言推理（6） R(QS) 前提（7） QS （5），（6）假言推理（8） S （2），（7）假言推理c、A，AB， AC， B(DC) = D证明：（1） A 前提（2） AB 前提（3） B (1)，(2) 假言推理（4） AC 前提（5） C (1)，(4) 假言推理（6） B(DC) 前提（7） DC (3)，(6) 假言推理（8） D (5)，(7) 拒取式d、PQ，QR，RS
4、 P证明、(1) P 附加前提 （2） PQ 前提 （3） Q （1），（2）假言推理 （4） QR 前提 (5) R （3），（4）析取三段论 (6 ) RS 前提 （7） R （6）化简 （8） RR 矛盾（5），（7）合取 所以该推理正确13.写出x(F(x)G(x)($xF(x) $xG(x)的前束范式。解：原式 x(F(x)G(x)($x)F(x) ($x)G(x) (x)(F(x)G(x) ($x)F(x) ($x)G(x) ($x)(F(x) G(x) G(x) (x) F(x) ($x)(F(x) G(x) (x) F(x) ($x)(F(x) G(x) (y) F(y) ($
5、x) (y) (F(x) G(x) F(y) （集合论部分）1、答：(4)2.答：323.答：（3）4.答：A1=A2=A3=A6， A4=A55. 答：（4）6.答：（1）7.答：（2），（4）8、设，是三个集合，证明：a、A (BC)(AB)(AC) 证明：(AB)(AC)= (AB)（AC）=(AB) （AC）=(ABA)(ABC)= ABC=A（BC）=A（B-C）b、(AB)(AC)=A(BC)证明：(A-B)(A-C)=(AB)(AC) =A (B C)=A（BC）= A-(BC)c、AB=A(B-A)证明： A(B-A)=A(BA)=(AB)(AA)=(AB)E= AB9、P(A
6、)P(B)P(AB) （P(S)表示S的幂集）证明：SP(A)P(B)，有SP(A)或SP(B)，所以SA或SB。从而SAB，故SP(AB)。即P(A)P(B)P(AB) 10、P(A)P(B)=P(AB) （P(S)表示S的幂集）证明：SP(A)P(B)，有SP(A)且SP(B)，所以SA且SB。从而SAB，故SP(AB)。即P(A)P(B)P(AB)。SP(AB)，有SAB，所以SA且SB。从而SP(A)且SP(B)，故SP(A)P(B)。即P(AB)P(A)P(B)。 故P(AB)=P(A)P(B)（二元关系部分）1、答：（1）R=, (2) R=,2.答：RR =1,1，1,3，2,2
7、，2,4R-1 =2,1，1,2，3,2，4,33.答：R=,4.答：R的关系矩阵= R的关系矩阵=5.若R和S都是非空集A上的等价关系，则RS是A上的等价关系。证明：aA，因为R和S都是A上的等价关系，所以xRx且xSx。故xRSx。从而RS是自反的。a,bA，aRSb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。故bRSa。从而RS是对称的。a,b,cA，aRSb且bRSc，即aRb，aSb,bRc且bSc。因为R和S都是A上的等价关系，所以aRc且aSc。故aRSc。从而RS是传递的。故RS是A上的等价关系。6、设RAA，则R自反 IAR。证明：xA，R是自反的，
8、xRx。即R，故IAR。xA，IAR，R。即xRx，故R是自反的。7、设A是集合，RAA，则R是对称的RR1。证明：R ，R是对称的，yRx。即R，故R_1 。从而RR-1。反之R-1,即R 。R是对称的，yRx。即R， R_1R。故R=R-1。x，yA，若R ，即R-1。 R=R-1，R。即yRx，故R是对称的。8、设A=1,2,3,写出下列图示关系的关系矩阵，并讨论它们的性质：解：（1）R=,;MR=;它是反自反的、反对称的、传递的；（2）R=,;MR=;它是反自反的、对称的；（3）R=,;MR=;它既不是自反的、也不是反自反的、也不是对称的、也不是反对称的、也不是传递的。9、R是A=1,2,3,4,5,6上的等价关系，R=I,求R诱导的划分。解：R诱导的划分为1,5,2,4,3,6。10画出下列集合关于整除关系的哈斯图.(1)1, 2, 3, 4, 6, 8, 12, 24.(2)1,2,.,9.并指出它的极小元，最小元，极大元，最大元。32258 124241256(1)325864791(2)在图（1）极小元，最小元是1，极大元，最大元是24；在图（2）中极小元，最小元是1，极大元是5，6，7，8，9，没有最大元。7
