离散数学课后习题答案 - （左孝凌版）

? P∧Q =?3 ??0，1，2

?(P∨Q)∧(P∨┐Q) ∧(┐P∨Q) c) P∨(┐P→(Q∨(┐Q→R)) ?P∨(P∨(Q∨(Q∨R)) ?P∨Q∨R=?0 ??1，2，3,4,5,6,7

=(┐P∧┐Q∧R) ∨(┐P∧Q∧┐R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R) ∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) d) (P→(Q∧R) )∧(┐P→(┐Q∧┐R)) ? (┐P∨(Q∧R)) ∧(P∨(┐Q∧┐R))

? (P∧┐P) ∨(P∧(Q∧R)) ∨ ((┐Q∧┐R) ∧┐P) ∨((┐Q∧┐R) ∧(Q∧R))

? (P∧Q∧R) ∨(┐P∧┐Q∧┐R) =?0,7 ??1，2，3,4,5,6?

? (P∨Q∨┐R) ∧(P∨┐Q∨R) ∧(P∨┐Q∨┐R) ∧(┐P∨Q∨R) ∧(┐P∨Q∨┐R) ∧(┐P∨┐Q∨R) e) P→(P∧(Q→P) ?┐P∨(P∧(┐Q∨P)

?(┐P∨P)∧(┐P∨┐Q∨P) ?T∨(T∧┐Q) ?T

??0,1,2,3= (┐P∧┐Q) ∨(┐P∧Q) ∨(P∧┐Q) ∨(P∧Q) f) (Q→P) ∧(┐P∧Q) ? (┐Q∨P) ∧┐P∧Q

? (┐Q∨P) ∧┐(P∨┐Q) ?F

??0,1，2，3= (P∨Q) ∧(P∨┐Q) ∧(┐P∨Q) ∧(┐P∨┐Q)

证明：

a)

(A→B) ∧(A→C)

? (┐A∨B) ∧(┐A∨C) A→(B∧C)

?┐A∨(B∧C)

? (┐A∨B) ∧(┐A∨C) b)

(A→B) →(A∧B)

?┐(┐A∨B) ∨(A∧B) ? (A∧┐B) ∨(A∧B) ?A∧(B∨┐B) ?A∧T ?A

(┐A→B) ∧(B→A) ? (A∨B) ∧(┐B∨A) ?A∨(B∧┐B) ?A∨F ?A c)

A∧B∧(┐A∨┐B)

? ((A∧┐A)∨(A∧┐B))∧B ?A∧B∧┐B ?F

┐A∧┐B∧(A∨B)

? ((┐A∧A)∨(┐A∧B))∧┐B ?┐A∧┐B∧B ?F d)

A∨(A→(A∧B) ?A∨┐A∨(A∧B) ?T

┐A∨┐B∨(A∧B) ?┐(A∧B) ∨(A∧B) ?T

(6)解：A?R↑(Q∧┐(R↓P)),则A*? R↓(Q∨┐(R↑P))A?R↑(Q∧┐(R↓P)) ?┐(R∧(Q∧(R∨P))) ?┐R∨┐Q∨┐(R∨P) ?┐(R∧Q) ∨┐(R∨P)

(5)

A*?R↓(Q∨┐(R↑P)) ?┐(R∨(Q∨(R∧P)) ?┐R∧┐Q∧┐(R∧P) ?┐(R∨Q) ∧┐(R∧P)

(7) 解：设A：A去出差。B：B去出差。C：C去出差。D：D去出差。 若A去则C和D中要去一个。 A→(CVD) B和C不能都去。 ┐(B∧C) 因为 (P∧┐Q∧┐R∧S)与(┐P∧Q∧R∧┐S)不合题意，所以原式可化为 ((P∧┐Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S) ∨(┐E∧S))

? (P∧┐Q∧R∧┐S∧E∧┐S) ∨(P∧┐Q∧R∧┐S∧┐E∧S) ∨(┐P∧Q∧┐R∧S∧E∧┐S)∨(┐P∧Q∧┐R∧S∧┐E∧S) ? (P∧┐Q∧R∧┐S∧E) ∨(┐P∧Q∧┐R∧S∧┐E) 因R与E矛盾，故┐P∧Q∧┐R∧S∧┐E为真，

即A不是第一，B是第二，C不是第二，D为第四，A不是第二。 于是得： A是第三 B是第二 C是第一 D是第四。 C去则D要留下。 C→┐D

按题意应有：A→(CVD)，┐(B∧C)，C→┐D必须同时成立。 因为CVD ? (C∧┐D) ∨(D∧┐C) 故(A→(CVD))∧┐(B∧C) ∧(C→┐D)

? (┐A∨(C∧┐D) ∨(D∧┐C)) ∧┐(B∧C) ∧(┐C∨┐D) ? (┐A∨(C∧┐D) ∨(D∧┐C)) ∧(┐B∨┐C) ∧(┐C∨┐D)

? (┐A∨(C∧┐D) ∨(D∧┐C)) ∧((┐B∧┐C) ∨(┐B∧┐D) ∨(┐C∧┐D) ∨┐C)

? (┐A∧┐B∧┐C) ∨(┐A∧┐B∧┐D) ∨(┐A∧┐C∧┐D) ∨(┐A∧┐C) ∨(┐B∧┐C∧D) ∨(┐C∧D∧┐B∧┐D) ∨(┐C∧D∧┐C∧┐D) ∨(┐C∧D∧┐C) ∨(┐D∧C∧┐B∧┐C) ∨(┐D∧C∧┐B∧┐D) ∨(┐D∧C∧┐C∧┐D) ∨(┐D∧C∧┐C)

在上述的析取范式中，有些（画线的）不符合题意，舍弃，得 (┐A∧┐C) ∨(┐B∧┐C∧D) ∨（┐C∧D）∨(┐D∧C∧┐B) 故分派的方法为：B∧D ,或 D∧A,或 C∧A。

(8) 解：设P：A是第一。Q：B是第二。R：C是第二。S：D是第四。E：A是第二。 由题意得 (PVQ) ∧(RVS) ∧(EVS)

? ((P∧┐Q) ∨(┐P∧Q)) ∧((R∧┐S) ∨(┐R∧S)) ∧((E∧┐S)

∨(┐E∧S))

? ((P∧┐Q∧R∧┐S) ∨(P∧┐Q∧┐R∧S) ∨(┐P∧Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S)∨(┐E∧S))

习题1-8 (1)证明：

a)┐(P∧┐Q)，┐Q∨R，┐R?┐P (1) ┐R P (2) ┐Q∨R P

(3) ┐Q (1)(2)T,I (4) ┐(P∧┐Q) P (5) ┐P∨Q (4)T,E (6) ┐P (3)(5)T,I

b)J→(M∨N)，(H∨G)→J，H∨G?M∨N (1) (H∨G) →J P (2) (H∨G) P

(3) J (1)(2)T,I (4) J→(M∨N) P (5) M∨N (3)(4)T,I c)B∧C，(B?C)→(H∨G)?G∨H (1) B∧C P (2) B (1)T,I (3) C (1)T,I (4) B∨┐C (2)T,I (5) C∨┐B (3)T,I (6) C→B (4)T,E (7) B→C (5)T,E (8) B?C (6)(7)T,E

(9) (B?C) →(H∨G) P (10) H∨G (8)(9)T,I

d)P→Q，(┐Q∨R)∧┐R，┐(┐P∧S)?┐S (1) (┐Q∨R) ∧┐R (2) ┐Q∨R (1)T,I (3) ┐R (1)T,I (4) ┐Q (2)(3)T,I (5) P→Q P

(6) ┐P (4)(5)T,I (7) ┐(┐P∧┐S) P (8) P∨┐S (7)T,E (9) ┐S (6)(8)T,I 证明：

a)┐A∨B，C→┐B?A→┐C

(1) ┐(A→┐C) P (2) A (1)T,I (3) C (1)T,I (4) ┐A∨B P

(5) B (2)(4)T,I (6) C→┐B P

(7) ┐B (3)(6)T,I (8) B∧┐B 矛盾。(5),(7)

b)A→(B→C)，(C∧D)→E，┐F→(D∧┐E)?A→(B→F) (1) ┐(A→(B→F)) P (2) A (1)T,I (3) ┐(B→F) (1)T,I (4) B (3)T,I (5) ┐F (3)T, (6) A→(B→C) P

(7) B→C (2)(6)T,I (8) C (4)(7)T,I (9) ┐F→(D∧┐E) P

(10) D∧┐E (5)(9)T,I (11) D (10)T,I (12) C∧D (8)(11)T,I (13) (C∧D) →E P

(14) E (12)(13)T,I (15) ┐E (10)T,I

(16) E∧┐E 矛盾。(14),(15) c)A∨B→C∧D，D∨E→F?A→F

(1) ┐(A→F) P (2) A (1)T,I (3) ┐F (1)T,I (4) A∨B (2)T,I (5) (A∨B) →C∧D P

(6) C∧D (4)(5)T,I (7) C (6)T,I (8) D (6)T,I (9) D∨E (8)T,I (10) D∨E→F P

(11) F (9)(10)T,I (12) F∧┐F 矛盾。(3),(11)

d)A→(B∧C)，┐B∨D，(E→┐F)→┐D，B→(A∧┐E)?B→E (1) ┐(B→E) P (2) B (1)T,I (3) ┐E (1)T,I (4) ┐B∨D P

(5) D (2)(4)T,I (6) (E→┐F) →┐D P

(7) ┐(E→┐F) (5)(6)T,I (8) E (7)T,I (9) E∧┐E 矛盾

e)(A→B)∧(C→D)，(B→E)∧(D→F)，┐(E∧F)，A→C?┐A (1) (A→B) ∧(C→D) P (2) A→B (1)T,I (3) (B→E) ∧(D→F) P

(2) (4) B→E (3)T,I (5) A→E (2)(4)T,I (6) ┐(E∧F) P (7) ┐E∨┐F (6)T,E (8) E→┐F (7)T,E (9) A→┐F (5)(8)T,I (10) C→D (1)T,I (11) D→F (3)T,I

(12) C→F (10)(10)T,I (13) A→C P

(14) A→F (13)(12)T,I (15) ┐F→┐A (14)T,E (16) A→┐A (9)(15)T,I (17) ┐A∨┐A (16)T,E (18) ┐A (17) T,E (3) 证明：

a)┐A∨B，C→┐B?A→┐C

(1) A P (2) ┐A∨B P

(3) B (1)(2)T,I (4) C→┐B P

(5) ┐C (3)(4)T,I (6) A→┐C CP

b)A→(B→C)，(C∧D)→E，┐F→(D∧┐E)?A→(B→F)

(1) A P (2) A→(B→C) P

(3) B→C (1)(2)T,I (4) B P

(5) C (3)(4)T,I (6) (C∧D) →E P (7) C→(D→E) (6)T,E (8) D→E (5)(7)T,I (9) ┐D∨E (8)T,E (10) ┐(D∧┐E) (9)T,E (11) ┐F→(D∧┐E) P

(12) F (10)(11)T,I (13) B→F CP (14) A→(B→F) CP c)A∨B→C∧D，D∨E→F?A→F

(1) A P (2) A∨B (1)T,I (3) A∨B→C∨D P

(4) C∧D (2)(3)T,I (5) D (4)T,I (6) D∨E (5)T,I (7) D∨E→F P

(8) F (6)(7)T,I (9) A→F CP

d)A→(B∧C)，┐B∨D，(E→┐F)→┐D，B→(A∧┐E)(1) B P(附加前提) (2) ┐B∨D P

(3) D (1)(2)T,I (4) (E→┐F)→┐D P

(5) ┐(E→┐F) (3)(4)T,I (6) E (5)T,I (7) B→E CP (4)证明：

a) R→┐Q，R∨S，S→┐Q，P→Q?┐P (1) R→┐Q P (2) R∨S P (3) S→┐Q P

(4) ┐Q (1)(2)(3)T,I (5) P→Q P

(6) ┐P (4)(5)T,I b) S→┐Q，S∨R，┐R，┐P?Q?P 证法一：

?B→E