离散数学答案(刘玉珍_编著)

习1.1 1、（1）否 （2）否 （3）是，真值为0 （4）否 （5）是，真值为1 2、（1）P：天下雨 Q：我去教室 ┐P → Q （2）P：你去教室 Q：我去图书馆 P → Q （3）P，Q同（2） Q → P （4）P：2是质数 Q：2是偶数 P∧Q 3、（1）0 （2）0 （3）1 4、（1）如果明天是晴天，那么我去教室或图书馆。 （2）如果我去教室，那么明天不是晴天，我也不去图书馆。 （3）明天是晴天，并且我不去教室，当且仅当我去图书馆。 习题1.2 1、（1）是 （2）是 （3）否 （4）是 （5）是 （6）否 2、（1）(P → Q) →R，P → Q，R，P，Q （2）(┐P∨Q) ∨（R∧P），┐P ∨ Q，R∧P，┐P，Q，R，P （3）((P → Q) ∧ (Q → P)) ∨ ┐(P → Q))，(P → Q) ∧(Q → P)，┐(P → Q)，P → Q，(Q → P)，P → Q，P，Q，Q，P，P，Q 3、（1）((P → Q) → (Q → P)) → (P → Q) （2）((P → Q) ∨ ((P → Q) → R))→ ((P → Q) ∧ ((P → Q) → R)) （3）(Q → P∧┐P) → (P∧┐P → Q) 4、(P → Q) ∨ ((P∧Q) ∨ (┐P∧┐Q)) ∧ (┐P∨Q) 习题1.3 1、（1）I(P∨(Q∧R)) = I(P)∨(I(Q)∧I(R)) = 1∨(1∧0) = 1 （2）I((P∧Q∧R)∨(┐(P∨Q)∧┐(R∨S))) = (1∧1∧0)∨(┐(1∨1)∧┐(0∨1)) = 0∨(0∧0) = 0 （3）I((P←→R)∧(┐Q→S)) = (1←→0)∧(┐1→1) = 0∧1 = 0 （4）I((P∨(Q→R∧┐P))←→(Q∨┐S)) = (1∨(1→(0∧┐1)))←→(1∨┐1) = 1←→1 = 1 （5）I(┐(P∧Q)∨┐R∨((Q←→┐P)→R∨┐S)) = ┐(1∧1)∨┐0∨((1←→┐1)→(0∨┐1)) = 0∨1∨1 = 1 2、（1） P Q P→Q Q∧(P→Q) Q∧(P→Q)→P 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 （2） P Q R Q∧R ┐(P∨(Q∧R)) P∨Q P∨R (P∨Q)∧(P∨R) 原式 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 （3） P Q R P∨Q Q∧P P∨Q→Q∧P P∧┐R 原式 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 3、（1）原式 <=> F→Q <=> T 原式为永真式 （2）原式 <=> ┐T∨(┐(┐P∨Q)∨(┐┐Q∨┐P)) <=> (P∧┐Q)∨(Q∨┐P) <=> (P∧┐Q)∨┐(P∧┐Q) <=> T 原式为永真式 （3）原式 <=> ┐(P∧Q) ←→ ┐(P∧Q) <=> T 原式为永真式 （4）原式 <=> P∧(Q∨R) ←→ P∧(Q∨R) <=> T 原式为永真式 （5）原式 <=> ┐(P∨┐Q)∨Q <=> (┐P∧Q)∨Q <=> Q 原式为可满足式 （6）原式 <=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> T 原式为永真式 （7）原式 <=> (┐P∨P∨Q)∧┐P <=> (T∨Q)∧┐P <=> T∧┐P <=> ┐P 原式为可满足式 （8）原式 <=> ┐((P∨Q) ∧(┐Q∨R))∨(┐P∨R) <=> (P∧┐Q)∨(Q∧┐R)∨(┐P∨R) <=> ((P∧┐Q)∨┐P)∨((Q∧┐R)∨R) <=>(( P∨┐P)∧(┐Q∨┐P))∨(( Q∨R)∧(┐R∨R)) <=> (┐Q∧┐P)∨( Q∨R) <=> T 原式为永真式 4、（1）左 <=> ┐P∨┐Q∨P <=> ┐┐P∨(┐P∨┐Q) <=> 右 （2）左 <=> ┐(┐P∨Q) <=> 右 （3）左 <=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> 右 （4）左 <=> ┐(P→Q)∨┐(Q→P) <=> (P∧┐Q)∨(Q∧┐P) <=> 中 <=> ((P∧┐Q)∨Q)∧((P∧┐Q)∨┐P) <=> (P∨Q)∧(┐Q∨Q)∧(P∨┐P)∧(┐Q∨┐P) <=> (P∨Q)∧┐(P∧Q) <=> 右 (5)左 ( P Q) ( R Q) EMBED Equation.3 (P Q) Q 右 5.(1)左 Q EMBED Equation.3 P Q 右 (2)(P (Q R)) ((P Q) (P R)) EMBED Equation.3 ( P EMBED Equation.3 Q R) EMBED Equation.3 ( P Q) ( P R) (P Q EMBED Equation.3 R) (P EMBED Equation.3 Q) EMBED Equation.3 P R (P Q EMBED Equation.3 R) ((P EMBED Equation.3 P) ( Q EMBED Equation.3 P)) R (P Q EMBED Equation.3 R) ( Q EMBED Equation.3 P R) (P Q EMBED Equation.3 R) EMBED Equation.3 (P Q EMBED Equation.3 R) T 故P (Q R) (P Q) (P R) (3).(P Q) (P P Q) EMBED Equation.3 ( P Q) EMBED Equation.3 P (P Q) EMBED Equation.3 ( P Q) ( P P) ( P Q) EMBED Equation.3 ( P Q) ( P Q) T 故P Q P P Q (4).((P Q) Q) P Q EMBED Equation.3 ( ( P Q) Q) P Q (( P Q) EMBED Equation.3 Q) P Q ( P EMBED Equation.3 Q) (Q EMBED Equation.3 Q) P Q EMBED Equation.3 (P Q) (P Q) T 故(P Q) Q P Q (5).((P EMBED Equation.3 P) Q) ((P EMBED Equation.3 P) R) (Q R) EMBED Equation.3 (( T Q) ( T R)) EMBED Equation.3 Q R EMBED Equation.3 (Q R) EMBED Equation.3 Q R EMBED Equation.3 Q EMBED Equation.3 R EMBED Equation.3 Q R EMBED Equation.3 Q T T 故((P EMBED Equation.3 P) Q) ((P EMBED Equation.3 P) R) Q R (6)左 (Q F) (R F) ( Q F) ( R F) EMBED Equation.3 Q EMBED Equation.3 R EMBED Equation.3 R EMBED Equation.3 R Q 右 6.(1)原式 ( P EMBED Equation.3 Q R) (2)原式 EMBED Equation.3 P EMBED Equation.3 Q P EMBED Equation.3 (P Q EMBED Equation.3 P) (3)原式 P (Q EMBED Equation.3 R P) P Q EMBED Equation.3 R EMBED Equation.3 ( P EMBED Equation.3 Q R) 7.(1)原式 EMBED Equation.3 ( P EMBED Equation.3 Q P) (2)原式 ( P Q EMBED Equation.3 R) EMBED Equation.3 P Q EMBED Equation.3 ( ( P Q EMBED Equation.3 R) P EMBED Equation.3 Q) (3)原式 EMBED Equation.3 P EMBED Equation.3 Q (R P) EMBED Equation.3 (P Q EMBED Equation.3 (R P)) 8. (1) (P Q) (( P ( P Q)) R) EMBED Equation.3 P (2)(P Q R) ( P R) (3)(P F) (Q T) 习题1.4 1.(1)原式 EMBED Equation.3 ( P EMBED Equation.3 Q) (( P EMBED Equation.3 Q) (Q P)) EMBED Equation.3 ( P EMBED Equation.3 Q) (Q P) (P Q) Q P Q P,既是析取范式又是合取范式 (2)原式 (( P Q) ( P EMBED Equation.3 Q)) ( ( P Q) EMBED Equation.3 ( P EMBED Equation.3 Q)) (P Q) (P EMBED Equation.3 Q) 析取范式 P (Q EMBED Equation.3 Q)合取范式 (3)原式 EMBED Equation.3 P Q EMBED Equation.3 S ( P Q)析取范式 ( P ( P Q)) Q EMBED Equation.3 S EMBED Equation.3 P Q EMBED Equation.3 S合取范式 (4)原式 P P Q Q R既是析取范式又是合取范式 2.(1)原式 P EMBED Equation.3 Q R为真的解释是：000，001，011，100，101，110，111 故原式的主析取范式为: ( P EMBED Equation.3 Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) ( P Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P EMBED Equation.3 EMBED Equation.3 QR) (P Q EMBED Equation.3 R) (P Q R) (2)原式 (P EMBED Equation.3 Q) R (P EMBED Equation.3 Q (R EMBED Equation.3 R)) ((P EMBED Equation.3 P) R) (P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q) ( P R) (P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P (Q EMBED Equation.3 Q) R) ( P (Q EMBED Equation.3 Q) R) (P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q R) (P EMBED Equation.3 Q R) ( P Q R) ( P EMBED Equation.3 Q R) (P EMBED Equation.3 Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P Q R) ( P Q R) ( P EMBED Equation.3 Q R)为真的解释是101，100，111，011，001 (3)原式 ( P (Q R)) (P ( Q EMBED Equation.3 R)) (( P (Q R)) P) (( P (Q R)) ( Q EMBED Equation.3 R)) ( P P) (Q P R) ( P EMBED Equation.3 Q EMBED Equation.3 R) (Q R EMBED Equation.3 Q EMBED Equation.3 R) (P Q R) ( P EMBED Equation.3 Q EMBED Equation.3 R) 为真的解释是：000,111 (4)原式 P P Q Q R P Q R为真的解释是：001，010，011，100，101，110，111 故原式的主析取范式为： ( P EMBED Equation.3 Q R) ( P Q EMBED Equation.3 R) ( P Q R) (P EMBED Equation.3 Q EMBED Equation.3 R) (P EMBED Equation.3 Q R) (P Q EMBED Equation.3 R) (P Q R) 3.(1)原式 EMBED Equation.3 P Q EMBED Equation.3 P EMBED Equation.3 Q T主合取范式，无为假的解释。 (2)原式 (P Q R) ( P Q R) ( P EMBED Equation.3 Q R) ( P EMBED Equation.3 Q R) 为真的解释为：111，011，001，000，故为假的解释为：010，100，101，110 原式的主合取范式为： (P Q EMBED Equation.3 R) ( P Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) (3)由2.(2)知，原式为真的解释是：101，100，111，011，001，故为假的解释是：000，010，110. 故原式的主合取范式为：(P Q R) (P EMBED Equation.3 Q R) ( P EMBED Equation.3 Q R) (4)由2.(4)知，原式为假的解释是：000，故原式的主合取范式为：P Q R 4.(1)左式 ( P Q) ( P R) ( P Q (R EMBED Equation.3 R)) ( P (Q EMBED Equation.3 Q) R) ( P Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) 右式 EMBED Equation.3 P (Q R) ( P Q) ( P R) ( P Q R) ( P Q EMBED Equation.3 R) ( P EMBED Equation.3 Q R) 故原式成立。 (2)左式（P∧┐Q）∨（P∧Q）， 右式（P∨P）∧(┐Q∨P)P∧（P∨┐Q）P（P∧┐Q）∨（P∧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. （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） ⑨，⑩，合取引入 ⑫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 ⑤，⑥，MP ⑧P→S CP （2）①P 附加前提 ②P→Q 前提 ③Q ①，②，MP ④P∧Q ①，③，合取引入 ⑤P→P∧Q CP （3）①P∧Q 附加前提 ②P ①，化简 ③P∨Q ②，附加规则 ④P∨Q→R 前提 ⑤R ③，④，MP ⑥P∧Q→R CP （4）①P 附加前提 ②Q 附加前提 ③P→（Q→R） 前提 ④Q→R ①，③，MP ⑤R ②，④，MP ⑥Q→（R→S） 前提 ⑦R→S ②，⑥，MP ⑧S ⑤，⑦，MP ⑨P→Q→R CP 3. （1）①┐（┐P） 假设前提 ②P ①，E1 ③P→┐Q 前提 ④┐Q ②，③，MP ⑤Q∨┐R 前提 ⑥┐R ④，⑤，析取三段论 ⑦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)) 1 B→A 附加前提 2 ┐┐B→B 上述结论 3 ┐┐B→A ①，②，HS 4 A→┐┐A 上述结论 5 ┐┐B→┐┐A ③，④，HS 6 (┐┐B→┐┐A) →(┐A→┐B) L3中用┐B置换A，用┐A 置换B 7 ┐A→┐B ⑤，⑥，MP 8 (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 (4) (x(yM(x,y,y) (5) (x(yA(x,y,x) 3. (1) (!x(E(x) ∧M(x)) (2)N(x):x是自然数，F(x,y):x大于y,M(x,y):x-1=y (x(N(x) ∧F(x,0) →(!y(N(y) ∧M(x,y))) (3)M(x):x是平面上的点，N(x):x直线，F(z,x,y):z过x与y， (x(y(M(x) ∧M(y) →(!z(N(z) ∧F(z,y,x))) (4)M(x):x是平面上的点，N(x):x是平面上的直线，F(x,y):x在y上，G(x,y):x过y. H(x,y):x平行y (x(y(N(x) ∧M(y) ∧┐F(y,x) →(!z(N(z) ∧G(z,y) ∧H(z,x))) 4.(1)存在x,对任意y,有x*y=1; (2)对任意x,存在y,使x*y=1. (3)对任意x,存在y，使x*y=0 (4)存在x,对任意y，有x*y=0 (5)对任意x,存在y，使x*y=x (6)存在x,对任意y，有x*y=x (7)对任意x和y，存在y，使x-y=y 习题2.2 1. (1)x是约束变元，也是约束出现；y是自由变元，也是自由出现。 (2)(x(P(x) ∨Q(x))中的x皆为约束出现，也是约束变元，R(x)中的x为自由出现，也是自由变元 (3)x,y是约束出现，也是约束变元；z是自由出现，也是自由变元。 (4)(x(P(x) ∧(xQ(x))中的x圴为约束出现，也是约束变元；(yR(z,y)中的y为约束出现，也是约束变元z和R(x,y)中的x与y为自由出现也是自由变元 2. (1) (的辖域为P(x) →Q(x,y); (的辖域为P(x) (2) (,(的辖域均为R(x,y) ∨P(y) (3) (x,(y的辖域为R(x,y) ∨P(y,z); (x的辖域为Q(x) (4) (,(的辖域均为R(x,y) 3. (1) (zP(z) ∨(y(wR(w,y) ∨Q(x) (2) (u(P(u,y) ∨Q(y)) ∧(vR(∏,v,z) (3) (u(vP(v,u) →(wP(w,y) ∧(zR(x,z) 习题2.3 1. (1)P(1) ∨Q(1)=1.P(2) ∨Q(2)=1.原式在I下为1 (2)由(1)知，原式在I下为1 (3)P(1) ∧Q(1)=0,原式在I下为0 (4)P(1) ∧Q(1)=0,P(2) ∧Q(2)=0.原式在I下为0 (5)P(1) →Q(1)=1,原式在I下为0 (6)P(2) →Q(2)=1,原式在I下为1 (7)P(2)=0, (xP(x)=0;Q(1)=0, (xQ(x)=0,原式在I下为0 (8)P(1)=1, (xP(x)=1;Q(2)=1, (xQ(x)=1,原式在I下为1 2.(1)构造I1：DI1={α}，,,原式在I1下为0 构造I2: DI2={α，β}，,原式在I2下为1，故得证 (2) )构造I1：DI1={α}，,,原式在I1下为0 构造I2: DI2={α} , ,原式在I2下为1，故得证 (3) 构造I1：DI1={α},,原式在I1下为0 构造I2: DI2={α},,原式在I2下为1，故得证 (4) 构造I1：DI1={α,β},,原式在I1下为0 构造I2: DI2={α},,原式在I2下为1，故得证. 3. (1)成立。若(xA(x) →(xB(x)为0，则(xA(x)为1，且(xB(x)为0，即(I，(α∈DI,A（α）为1，且(β∈DI，B(β)为0，则A(β) →B(β)为0，故(x(A(x) →B(x))在I下为0，从而原式成立。 (2)不成立。构造I: DI={α，β}，,,则A(α) →B(α)为0，故(x(A(x) →B(x))为0,而(xA(x), (xB(x)在I下均为0，故(xA(x) →(xB(x)在I下为1，从而((xA(x) →(xB(x)) →(x(A(x) →B(x))在I下为0，故原式不成立。 (3)成立。左式(┐(xA(x) ∨(xB(x) ((x┐A(x) ∨(xB(x) (x(┐A(x) ∨B(x)) (右式 (4)不成立。左式((x(┐A(x) ∨B(x)) (x┐A(x) ∨(xB(x) (┐(xA(x) ∨(xB(x) (右式 4. (1)左式((x(A(x) ∨(yB(y)) (右式 (2)左式((x(A(x) ∧(yB(y)) ((xA(x) ∧(yB(y) (右式 (3)左式((x(A(x) ∧(yB(y)) (右式 (4)左式((x(A(x) →(yB(y)) (右式 (5)左式((x(A(x) →(yB(y)) (右式 5. 由(x(┐P(x) ∧┐Q(x)) (x┐P(x) ∧(x┐Q(x)知┐(x(┐P(x) ∧┐Q(x)) ┐((x┐P(x) ∧(x┐Q(x)) 习题2.4 1.（1）反式(（(xP(x) ∧(x┐Q(x)）∨((xQ(x) ∧(yR(y)) ((x(P(x) ∧┐Q(x) ) ∨((zQ(z) ∧(yR(y)) ((x(z(y((P(x) ∧┐Q(x)) ∨(Q(z) ∧R(y))) (2)反式((yP(y) ∨((x┐Q(x) ∧(xR(x)) ((yP(y) ∨(x(┐Q(x) ∧R(x)) ((y(x(P(y) ∨(┐Q(x) ∧R(x))) (3)反式((x(y┐P(x,y) ∨((xQ(x,y) ∧R(x)) ((u(v┐P(u,v) ∨((uQ(u,y) ∧R(x)) ((u(v(┐P(u,v) ∨(Q(u,y) ∧R(x))) (4)反式((y(x(P(x) ∧┐Q(x,y)) ∨(y┐R(y) ∨(xP(x) ((y((x((P(x) ∧┐Q(x,y)) ∨P(x))) ∨(y┐R(y) ((y(xP(x) ∨(y┐R(y) ((xP(x) ∨(y┐R(y) ((x(y(P(x) ∨┐R(y)) (5)反式((x┐P(x) ∨(xQ(x) ((x(┐P(x) ∨Q(x)) 2. (1) 反式的skolem范式为：(x(y((P(x) ∧┐Q(x)) ∨(Q(f(x)) ∧R(y))) (2) 反式的skolem范式为: (y (x(P(y) ∨(┐Q(x) ∧R(x))) (3) 反式的skolem范式为: (v(┐P(a,v) ∨(Q(a,y) ∧R(x))) (4) 反式的skolem范式为: (y(P(a) ∨┐R(y)) (5) 反式的skolem范式为: ┐P(a) ∨Q(a) 3.不正确。由于(xP(x,y) ∧(xQ(x) (x(P(x,y) ∧Q(x)),故（(xP(x,y) ∧(xQ(x)）→(yR(y) (x(P(x,y) ∧Q(x)) →(zR(z) 习题2.5 1.由P37例2.1.3知，即证明(x(M(x) →D(x)) ∧M(a) D(a) ①(x(M(x) →D(x)) 前提 ②M(a) →D(a) ①,VS ③M(a) 前提 ④D(a) ②,③,MP 2. (1) ①(x(P(x) →Q(x)) 前提 ②P(z) →Q(z) ①,VS ③(y┐Q(y) 前提 ④┐Q(z) ③,VS ⑤┐P(z) ②,④,拒取式 ⑥(x┐P(x) ⑤,UG (2)① ┐(x(P(x) ∨Q(x)) 假设前提 ②(x(┐P(x) ∧┐Q(x)) ①,Q1,E10 ③(xP(x) 前提 ④P(c) ③,ES ⑤┐P(c) ∧┐Q(c) ②,VS ⑥P(c) ∧┐P(c) ∧Q(c) ④,⑤,合取引入 ⑦F ⑥,E21,E17 故反式成立 (3)①(xP(x) 附加前提 ②P(y) ①,VS ③(x(P(x) → Q(x)) 前提 ④P(y) →Q(y) ③,VS ⑤Q(y) ②,④,MP ⑥(xQ(x) ⑤,UG ⑦(xP(x) →(xQ(x) CP (4)①(x(P(x) →R(x)) 前提 ②P(c) →R(c) ①,ES ③(x(┐P(x) →Q(x)) 前提 ④┐P(c) →Q(c) ③,VS ⑤(x┐Q(x) 前提 ⑥┐Q(c) ⑤,VS ⑦P(c) ④,⑥,拒取式，E1 ⑧R(c) ②,⑦,MP ⑨(xR(x) ⑧.EG (5)①(x(P(x) ∧Q(x)) 前提 ②P(c) ∧Q(c) ①,ES ③P(c) 化简 ④(x(P(x) →Q(x) ∧R(x)) 前提 ⑤P(C) →Q(c) ∧R(c) ④,VS ⑥Q(c) ∧R(c) ③,⑤,MP ⑦(x(Q(x) ∧R(x)) ⑥,EG 3.(1)①(xP(x) 附加前提 ②P(c) ①,ES ③┐((xP(x) ∧Q(a)) 前提 ④(x┐P(x) ∨Q(a) ③,Q3,E11 ⑤┐P(c) ∨┐Q(a) ④,VS ⑥┐Q(a) ②,⑤,析取三段论 ⑦(xP(x) →┐Q(a) CP (2)①(x(P(x) ∨Q(x)) 前提 ②P(y) ∨Q(y) ①,VS ③(x┐P(x) 前提 ④┐P(y) ③,VS ⑤Q(y) ②,④,析取三段论 ⑥(xQ(x) ⑤,UG (3)①┐(x(P(x) ∨Q(x)) 前提 ②(x（┐P(x) ∨┐Q(x)） ①,Q4,E11 ③┐P(c) ∨┐Q(c) ②,ES ④(xP(x) 前提 ⑤P(c) ④,VS ⑥┐Q(c) ③,⑤,析取三段论 ⑦(x┐Q(x) ⑥,EG ⑧┐(xQ(x) ⑦,Q4 4.(1)为真。 ①(yP(y) 前提 ②P(c) ①,ES ③(x(P(x) →Q(x)) 前提 ④P(c) →Q(c) ③,VS ⑤Q(c) ②,④,MP ⑥(zQ(z)