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