《离散数学(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