离散习题答案1-4 下载本文

13. 对下列各公式,试仅用↑或↓表示。 (1)┐P (2)P∧Q (3)P∨Q (4)P→Q 解:

(1)┐P?┐(P∧P)? P↑P (2)P∧Q?(P↑Q)↑(P↑Q)

(3)P∨Q?┐(┐P∧┐Q) ?(┐P↑┐Q) ?(P↑P)↑(Q↑Q) (4)P→Q?┐P∨Q? (P↑P)∨Q ?((P↑P)↑(P↑P))↑(Q↑Q)

14. 将下列公式化成与之等值且仅含{┐,→}中联结词的公式。 (1)(P→┐Q)∧R

(Q∧R)∨P (2)P ←→

解:

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

?┐(R→P)∨┐(R→Q)?(R→P)→┐(R→Q) (Q∧R)∨P?(P→((Q∧R)∨P))∧(((Q∧R)∨P)→P)?(┐P∨((Q∧R)∨P))∧(┐((Q(2)P ←→∧R)∨P)∨P)? T∧(((┐Q∨┐R)∧┐P)∨P)?((┐Q∨┐R)∨P)? P∨(┐Q∨┐R)?P∨

(Q→┐R)? ┐P→(Q→┐R)

**

15. 如果A(P,Q,R)由R↑(Q∧┐(R↓P))给出,求它的对偶A(P,Q,R),并求出与A及A等价且仅包含联接词“∧”,“∨”及“┐”的公式。 解: *

A(P,Q,R):R↓ (Q∨┐(R↑P))

R↑(Q∧┐(R↓P))?┐(R∧(Q∧(R∨P)))?┐R∨┐Q∨(┐R∧┐P) R↓ (Q∨┐(R↑P))?┐R∧┐Q∧(┐R∨┐P) 16. 把P↑Q表示为只含有“↓”的等价公式。 解:P↑Q?┐(P∧Q)?┐((P↓P)↓(Q↓Q))? ((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q)) 17. 证明:

(1)┐(P↑Q)?┐P↓┐Q (2)┐(P↓Q)?┐P↑┐Q 证明:

(1)┐(P↑Q)?┐(┐(P∧Q)) ?(P∧Q)?┐(┐P∨┐Q)?┐P↓┐Q (2)┐(P↓Q)?┐(┐(P∨Q)) ?(P∨Q)?┐(┐P∧┐Q)?┐P↑┐Q 18. 求公式P∧(P→Q)的析取范式和合取范式。 解:P∧(P→Q) ? P∧(┐P∨Q) 合取范式

? (P∧┐P)∨(P∧Q) 析取范式

19. 求下列公式的主析取范式和主合取范式。 (1)(┐P→Q)→(┐Q∨P) (2)(P→ (P∨Q))∨R

(3)(P→ Q∧R)∧(┐P→ (┐Q∧┐R)) 解:

(1)真值表法

P 1 Q 1 ┐P→Q 1 ┐Q∨P 1 (┐P→Q)→(┐Q∨P) 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 1

主析取范式为:(P∧Q)∨(P∧┐Q)∨(┐P∧┐Q) 主合取范式为:P∨┐Q 公式化归法

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

?(┐P∨┐Q∨P)∧(┐Q∨┐Q∨P) ?P∨┐Q 主合取范式 ?(P∧Q)∨(P∧┐Q)∨(┐P∧┐Q) 主析取范式 (2)真值表法(P→ (P∨Q))∨R

P Q R P∨Q P→ (P∨Q) (P→ (P∨Q))∨R 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 1 原式为永真式,其主析取范式为所有小项的析取,即:

m000∨m001∨m010∨m011∨m100∨m101∨m110∨m111

不能表示为主合取范式。 公式化归法

(P→ (P∨Q))∨R?(┐P∨(P∨Q))∨R?T∨R? T (3)真值表法(P→ Q∧R)∧((┐P→ (┐Q∧┐R))

P Q R Q∧R P→ Q∧R ┐Q∧┐R ┐P→ (┐Q∧┐R) 原公式 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 主析取范式为:(P∧Q∧R)∨(┐P∧┐Q∧┐R)?m111∨m000?m7∨m0 主合取范式为:M1∧M2∧M3∧M4∧M5∧M6? M001∧M010∧M011∧M100∧M101∧M110?(P∨Q∨┐R)∧(P∨┐Q∨R)∧(P∨┐Q∨┐R)∧(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R) 20. 求下列公式的主析取范式和主合取范式,并指出该公式的类型。

┐Q) (1)(┐P∨┐Q)→(P←→

(2)Q∧(P∨┐Q)

(3)P∨(┐P→(Q∨(┐Q→R)))

(4)(P→(Q∧R))∧(┐P→(┐Q∧┐R)) (5)P→(P∧(Q→ P)) (6)(Q→P)∧(┐P∧Q) 解:

(1)

┐Q P Q ┐P∨┐Q P←→1 1 0 0 1 0 1 1 0 1 1 1 0 0 1 0 主析取范式为:(P∧Q)∨(P∧┐Q)∨(┐P∧Q) 主合取范式为:P∨Q 公式为可满足式。 (2)

P 1 1 0 0 Q 1 0 1 0 P∨┐Q 1 1 0 1 ┐Q) (┐P∨┐Q)→(P←→1 1 1 0 Q∧(P∨┐Q) 1 0 0 0 主析取范式为:P∧Q

主合取范式为:(┐P∨Q)∧(P∨┐Q)∧(P∨Q) 公式为可满足式。

(3)P∨(┐P→(Q∨(┐Q→R)))? P∨(P∨(Q∨(Q∨R))) ? P∨Q∨R 主合取范式

? M000?M0 ? m1∨m2∨m3∨m4∨m5∨m6∨m7 主析取范式 公式为可满足式。

(4)(P→(Q∧R))∧(┐P→(┐Q∧┐R))?(┐P∨(Q∧R))∧(P∨(┐Q∧┐R))?(┐P∨Q)∧(┐P∨R)∧(P∨┐Q)∧(P∨┐R)?(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨┐R)∧(P∨┐Q∨R)∧(P∨┐Q∨┐R)∧(P∨Q∨┐R) ? M100∧M101∧M111∧M010∧M011∧M001?M4∧M5∧M7∧M2∧M3∧M1 主合取范式 ? m0∨m6? m000∨m110 主析取范式 公式为可满足式。

(5)P→(P∧(Q→ P))?┐P∨(P∧(┐Q∨P))?(┐P∨P)∧(┐P∨(┐Q∨P))?T 主析取范式为:m0∨m1∨m2∨m3 公式为永真式。

(6)(Q→P)∧(┐P∧Q)?(┐Q∨P)∧(┐P∧Q)?(┐Q∧┐P∧Q)∨(P∧┐P∧Q) ?F 主合取范式为:M0∧M1∧M2∧M3 公式为永假式。

21. 用将合式公式化为范式的方法证明下列各题中两式是等价的。 (1)(P→Q)∧(P→R) ,P→(Q∧R)

(2)(P→Q)→(P∧Q),(┐P→Q)∧(Q→P) (3)P∧Q∧(┐P∨┐Q),┐P∧┐Q∧(P∨Q) (4)P∨(P→(P∧Q)),┐P∨┐Q∨(P∧Q) 证明:

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

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

(2)(P→Q)→(P∧Q) ?┐(┐P∨Q)∨(P∧Q)?(P∧┐Q)∨(P∧Q)?P∧(┐Q∨Q)?P

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

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

┐P∧┐Q∧(P∨Q) ?(┐P∧┐Q∧P)∨(┐P∧┐Q∧Q) ? F (4)P∨(P→(P∧Q)) ? P∨(┐P∨(P∧Q)) ? T∨(P∧Q) ? T

┐P∨┐Q∨(P∧Q) ?(┐P∨┐Q∨P)∧(┐P∨┐Q∨Q) ? T 22. 用推理规则证明以下各式。

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

(2)A→(B∨C),(D∨E)→A,D∨E ? B∨C

C)→(D∨E)?D∨E (3)B∧C,(B ←→(4)P→Q,(┐Q∨R)∧┐R,┐(┐P∧S)?┐S

证明:

(1)┐(P∧┐Q),┐Q∨R,┐R ?┐P 证明:

(1) ┐R P (2) ┐Q∨R P (3) ┐Q T(1)(2) I (4) ┐(P∧┐Q) P (5) ┐P∨Q T(4) E (6) ┐P T(3)(5) I (2)A→(B∨C),(D∨E)→A,D∨E ? B∨C 证明:

(1) D∨E P (2) (D∨E)→A P (3) A T(1)(2) I (4) A→(B∨C) P (5) B∨C T(3)(4) I

C)→(D∨E)?D∨E (3)B∧C,(B ←→

证明:

(1) B∧C P

C (2) B ← T(1) I → C)→(D∨E) (3) (B ← P →(4) D∨E T(2)(3) I

(4)P→Q,(┐Q∨R)∧┐R,┐(┐P∧S)?┐S 证明:

(1) (┐Q∨R)∧┐R P (2) ┐Q∨R T(1) I (3) ┐R T(1) I (4) ┐Q T(2)(3) I (5) ┐(┐P∧S) P (6) S→ P T(5) E (7) P→Q P (8) S→Q T(6) (7) I (9) ┐Q→┐S T(8) E (10) ┐S T(4) (8) I 23. 仅用规则P和T,推证以下公式。

(1)┐A∨B,C→┐B? A→┐C

(2)A→(B→C),(C∧D)→E,┐F→(D∧┐E) ? A→(B→F) (3)A∨B→C∧D,D∨E→F,? A→F

(4)A→(B∧C),┐B∨D,(E→┐F) →┐D,B→(A∧┐E)?B→E (5)(A→B)∧(C→D),(B→E)∧(D→F),┐(E∧F),A→C ? ┐A 证明:

(1)┐A∨B,C→┐B? A→┐C 证明:

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

(2)A→(B→C),(C∧D)→E,┐F→(D∧┐E) ? A→(B→F) 证明:

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

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

(4)A→(B∧C),┐B∨D,(E→┐F) →┐D,B→(A∧┐E)?B→E 证明:

(1) ┐B∨D P (2) B→D T(1)E (3) (E→┐F) →┐D P (4) D→┐(E→┐F) T(3) E (5) D→(E∧F) T(4) E (6) B→(E∧F) T(2)(5) I (7) B→E T(6) I