R
4.(1)左式?(?P?Q)?( ?P?R)
?(?P?Q?(R??R))?( ?P?(Q??Q)?R) ?(?P?Q?R)?(?P?Q??R)?(?P??Q?R) 右式??P?(Q?R) ?(?P?Q)?(?P?R) ?(?P?Q?R)?(?P?Q??R)?(?P??Q?R) 故原式成立。 (2)左式（P∧┐Q）∨（P∧Q）， 右式（P∨P）∧(┐Q∨P)P∧（P∨┐Q）PP∧Q），
故原式成立 (3)左式（P∧Q）∧┐（P∧Q）F，主析取范式 右式┐（P∨Q）∧（P∨Q）F， 故原式成立 (4)左式T∨（P∧Q）T，主合取范式 右式┐（P∧Q）∨（P∧Q）T， 故原式成立
习题1.5
（1）①P∧Q 前提 ②P ①，化简 ③P→(Q→R) 前提
④Q→R ②，③，MP ⑤Q ①，化简 ⑥R ④，⑤，MP （2）①R 前提 ②┐（Q∧R） 前提 ③┐Q∨┐R ②，E11
④┐Q ①，③，析取三段论 ⑤┐P∨Q 前提
⑥┐P ④，⑤，析取三段论 （3）①┐S 假设前提 ②S∨P 前提
③P ①，②，析取三段论 ④（P→Q）∧（P→R） 前提
⑤P→Q ④，化简 ⑥P→R ⑤，化简 ⑦Q ③，⑤，MP ⑧R ③，⑥，MP
⑨Q∧R ⑦，⑧，合取引入 ⑩┐（Q∧R） 前提 ?（Q∧R）∧┐（Q∧R） ⑨，⑩，合取引入
P∧┐Q）
∨（（1. ?F ?，E21 故原推理成立
（4）①┐R 假设前提 ②（P→Q）→R 前提
③┐（P→Q） ①，②，拒取式 ④P∧┐Q ③，E14，E10 ⑤Q∧T 前提
⑥P∧┐Q∧Q∧T ④，⑤，合取引入 ⑦F ⑥，E21，E17 故原推理成立
2.（1）①P ②┐P∨Q ③Q ④┐Q∨R ⑤R ⑥R→S ⑦S ⑧P→S （2）①P ②P→Q ③Q ④P∧Q ⑤P→P∧Q （3）①P∧Q ②P ③P∨Q ④P∨Q→R ⑤R ⑥P∧Q→R （4）①P ②Q ③P→（Q→R） ④Q→R ⑤R ⑥Q→（R→S） ⑦R→S ⑧S ⑨P→Q→R 3.（1）①┐（┐P） ②P ③P→┐Q ④┐Q ⑤Q∨┐R ⑥┐R 附加前提 前提
①，②，析取三段论前提
③，④，析取三段论 前提
⑤，⑥，MP CP
附加前提 前提
①，②，MP
①，③，合取引入 CP
附加前提 ①，化简 ②，附加规则 前提
③，④，MP CP
附加前提 附加前提 前提
①，③，MP ②，④，MP 前提
②，⑥，MP ⑤，⑦，MP CP
假设前提 ①，E1 前提
②，③，MP 前提
④，⑤，析取三段论
⑦R∧┐S 前提
⑧┐R∧R∧┐S ⑥，⑦，合取引入 ⑨F ⑧，E21，E17 故原推理成立
（2）①┐（R∨S） 假设前提 ②┐R∧┐S ①，E10 ③┐R ②，化简 ④┐S ②，化简 ⑤P→R 前提 ⑥Q→S 前提
⑦┐P ③，⑤，拒取式 ⑧┐Q ④，⑥，拒取式 ⑨┐P∧┐Q ⑦，⑧，合取引入 ⑩┐（P∨Q） ⑨，E10 ?P∨Q 前提 ?┐（P∨Q）∧（P∨Q） ⑩，?，合取引入 ?F ?，E21 故原推理成立
（3）1.┐(┐S) 假设前提
2.S 1,E1 3.S→┐Q 前提 4.┐Q 2, 3,MP 5.┐R ?Q 前提 6.(┐R→Q) ∧(R→┐Q) 5,E15 7.┐R→Q 6,化简
8.R 4, 7,拒取式 9.┐R 前提
10.R∧┐R 8,9,合取引入 11.F 10,E21 故反推原理正确
(4) 1.┐(P?Q) 假设前提
2.┐（P→Q）∨┐(Q→P) 1,E15,E11 3.┐(P→Q) →┐(R∨S) 前提 4. (Q→P) ∨┐R 前提 5.┐(Q→P) →┐R 4,E14
6.┐(R∨S) ∨┐R 2，3，5构造二难性 7.┐((R∨S) ∧R) 6，E11 8.┐R 7，E13 9.R 前提
10.┐R∧R 8，9合取引入 11.F 10，E21 故反推原理正确
4 （1）先证├ ┐┐A→A
①┐┐A 附加前提
②┐┐A→(┐A→┐┐┐A) P31例1.5.7中用┐A置换
用┐┐┐A置换A
③(┐A→┐┐┐A) ①，②，MP
④(┐A→┐┐┐A) →(┐┐A→A) L3中用┐┐A置换B ⑤┐┐A→A ③，④，MP ⑥A ①，⑤，MP ⑦┐┐A→A 演绎定理
再证├A→┐┐A
①┐┐┐A→┐A 上述结论中用┐A置换A
②(┐┐┐A→┐A) →(A→┐┐A) L3中用┐┐A置换A，用A置
换B
③A→┐┐A ①，②，MP
最后证├((B→A) →(┐A→┐┐B))
① B→A 附加前提 ② ┐┐B→B 上述结论 ③ ┐┐B→A ①，②，HS ④ A→┐┐A 上述结论 ⑤ ┐┐B→┐┐A ③，④，HS
⑥ (┐┐B→┐┐A) →(┐A→┐B) L3中用┐B置换A，用┐A 置换B
⑦ ┐A→┐B ⑤，⑥，MP ⑧ (B→A) →(┐A→┐B) 演绎定理
(2)先证├ ┐(A→B) →A
①┐(A→B) 附加前提 ②┐A→(A→B) P31,例1.5.7 ③(┐A→(A→B)) →(┐(A→B) →┐┐A) （1）
④┐(A→B) →┐┐A ②，③，MP ⑤┐┐A ①，④，MP ⑥┐┐A→┐A 上述结论 ⑦A ⑤，⑥，MP ⑧┐(A→B) →A 演绎定理 再证 ├ ┐(A→B) →(B→A)
①┐(A→B) →A 上述结论 ②A→(B→A) L1
③┐(A→B) →(B→A) ①，②，HS
习题1.6
1. P→Q?┐P∨Q?(P↓P) ∨Q?┐((P↓P) ↓Q) ?((P↓P) ↓Q)↓((P↓P)
↓Q)
(P∨Q) ∧R?┐(┐(P∨Q) ∨┐R) ?┐((P↓Q) ∨(R↓R)) ? (P↓Q) ↓(R↓R)
2. P∧(Q→R) ?P∧(┐Q∨R) ?(P∧┐Q) ∨(P∧ R) ?┐(P↑┐Q) ∨┐(P
↑R) ?┐((P↑(Q↑Q)) ∧(P↑R)) ?(P↑(Q↑Q)) ↑(P↑R) 3.(1)左式?P∧ Q?┐(┐P∨┐Q) ?右式 (2)左式?P∨Q?┐(┐P∧┐Q) ?右式
4．（1）否，见P33，例1.6.1 （2）否，见P33，例1.6.1
（3）是，P→Q ?┐(PQ),P∧Q?┐(┐P∨┐Q) ?┐(P→┐Q) ?
P┐Q, P∨Q?┐P→Q?┐(┐PQ),P?Q?(P→Q) ∧(Q→P) ? ┐(┐(P→Q) ∨┐(Q→P)) ?┐((P→Q) →┐(Q→P)) ? (P→Q) ┐(Q→P) ?┐(PQ) (QP)
{┐，}中去掉┐，无法表示否定，去掉，无法表示二元运算 (4 ) 否。{┐，→}为极小全功能集
(5 ) 否。因为没公式A(P,Q)仅含P,Q, ┐, ?,则A(P,Q)仅在两种解释下为真，
而P∧Q仅在一种解释下为真，故A(P,Q)与A不等价，即P∧Q不能用仅含┐?的公式等价地表示。
（6）是。┐P ?P↑P,
P∧Q ?┐(P↑Q) ?(P↑Q) ↑(P↑Q),
P∨Q ?┐(┐P∧┐Q) ?┐P↑┐Q ?(P↑P) ↑(Q↑Q), P?Q?(P→Q) ∧(Q→P) ?┐((P→Q) ↑(Q→P)) ?
┐((P↑(Q↑Q)) ↑(Q↑(P↑P))) ?
((P↑(Q↑Q)) ↑(Q↑(P↑P))) ?((P↑(Q↑Q)) ↑(Q↑(P↑P)))↑((P↑(Q↑Q))↑(Q↑(P↑P))
(7) 否，由（6）知 (8) 是，类似于（6）
习题2.1
1.(1)R(x):x是实数，M(x,y):x比y大，┐?x(R(x) ∧?y(R(y) →M(x,y)))
(2)R(x):x是实数，M(x,y):x等于y，N(z,x,y):z在x与y之间,?x?y(R(x) ∧R(y) ∧┐M(x,y) →?z(R(z) ∧N(z,x,y) ∧┐M(z,x) ∧┐M(z,y))) (3)E(x):x是偶数，M(x):x是质数。?!x(E(x) ∧M(x)) (4)O(x):x是奇数，E(x):x是偶数。┐?x(E(x) ∧M(x)) (5)N(x):x是自然数，M(X):x+1=0, ┐?x(N(x) ∧M(x))
(6)N(x):x是自然数，M(x,y):x+1=y, ?x(N(x) →?!y(N(y) ∧M(x,y))) (7)M(x):x是火车，N(x):x是汽车，F(x,y):x比y快，?x(M(x) →?y(N(y) ∧F(x,y)))
2. (1)┐?xL(x,0)
(2) ?x?y?z(L(x,y) ∧L(y,z) →L(x,z))
(3) ?x?y(L(x,y)→?z(L(z,0) ∧G(f(x,z),f(y,z)))).其中f(u,v)=uv