1、习题 1.11、 （1）否（2）否（3）是，真值为 0（4）否（5）是，真值为 12、 （1）P：天下雨 Q：我去教室 P Q（2）P：你去教室 Q：我去图书馆 P Q（3）P，Q 同（ 2） Q P（4）P：2 是质数 Q：2 是偶数 PQ3、 （1）0（2）0（3）14、 （1）如果明天是晴天，那么我去教室或图书馆。（2）如果我去教室，那么明天不是晴天，我也不去图书馆。（3）明天是晴天，并且我不去教室，当且仅当我去图书馆。习题 1.21、 （1）是（2）是（3）否（4）是（5）是（6）否2、 （1）(P Q) R，P Q，R ，P ，Q（2）(PQ) （RP） ，P Q，R P，P ，Q，
2、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，Q3、 （1）(P Q) (Q P) (P Q)（2）(P Q) (P Q) R) (P Q) (P Q) R)（3）(Q PP) (P P Q)4、(P Q) (PQ) ( PQ) (PQ)习题 1.31、 （1）I(P(QR) = I(P)(I(Q)I(R) = 1(10) = 1（2）I(P QR)( (P Q)(RS) = (110)(11) (01) = 0(00) = 0（3）I(P R) ( QS) = (10) (11) = 01 = 0（4）
3、I(P (QR P)(QS) = (1(1 (01)(11) = 11 = 1（5）I(P Q)R (QP)RS) = (1 1)0(11) (01) = 011 = 12、 （1）P Q PQ Q(PQ) Q(P Q)P0 0 1 0 10 1 1 1 01 0 0 0 11 1 1 1 1（2）P Q R QR (P(QR) PQ PR (PQ)(PR) 原式0 0 0 0 1 0 0 0 00 0 1 0 1 0 1 0 00 1 0 0 1 1 0 0 00 1 1 1 0 1 1 1 01 0 0 0 0 1 1 1 01 0 1 0 0 1 1 1 01 1 0 0 0 1 1 1
4、 01 1 1 1 0 1 1 1 0（3）P Q R PQ QP PQQ P PR 原式0 0 0 0 0 1 0 00 0 1 0 0 1 0 00 1 0 1 0 0 0 10 1 1 1 0 0 0 11 0 0 1 0 0 1 11 0 1 1 0 0 0 11 1 0 1 1 1 1 11 1 1 1 1 1 0 03、 （1）原式 FQ T 原式为永真式（2）原式 T( PQ)( QP) (P Q)(QP)(PQ)(PQ) T 原式为永真式（3）原式 (PQ) (P Q) T 原式为永真式（4）原式 P(Q R) P(QR) T 原式为永真式（5）原式 (PQ)Q (P Q)Q
5、Q 原式为可满足式（6）原式 (PQ)P PQ P TQ T 原式为永真式（7）原式 (P PQ)P (TQ) P TP P 原式为可满足式（8）原式 (PQ) (Q R)( PR) (P Q)(QR)( P R)(PQ)P)(Q R)R) ( PP)(QP)( QR)(RR)(QP)( QR) T 原式为永真式4、 （1）左 P QP P( PQ) 右（2）左 (P Q) 右（3）左 (PQ)P PQ P TQ 右（4）左 (PQ)(QP) (PQ)(Q P) 中(PQ)Q) (P Q)P)(P Q)(QQ) (P P)(QP) (P Q)(PQ) 右(5)左 ( P Q) ( R Q) (
6、P Q) Q 右5.(1)左 Q P Q 右(2)(P (Q R) (P Q) (P R)( P Q R) ( P Q) ( P R)(P Q R) (P Q) P R(P Q R) (P P) ( Q P) R(P Q R) ( Q P R)(P Q R) (P Q R)T故 P (Q R) (P Q) (P R)(3).(P Q) (P P Q)( P Q) P (P Q)( P Q) ( P P) ( P Q)( P Q) ( P Q)T故 P Q P P Q(4).(P Q) Q) P Q( ( P Q) Q) P Q( P Q) Q) P Q( P Q) (Q Q) P Q(P Q)
7、 (P Q)T故(P Q) Q P Q(5).(P P) Q) (P P) R) (Q R)( T Q) ( T R) Q R(Q R) Q RQ R Q RQ TT故(P P) Q) (P P) R) Q R(6)左 (Q F) (R F) ( Q F) ( R F) Q RRR Q 右6.(1)原式 ( P Q R)(2)原式 P Q P (P Q P)(3)原式 P (Q R P) P Q R ( P Q R)7.(1)原式 ( P Q P)(2)原式 ( P Q R) P Q ( ( P Q R) P Q)(3)原式 P Q (R P) (P Q (R P)8. (1) (P Q) (
8、 P ( P Q) R) P(2)(P Q R) ( P R)(3)(P F) (Q T)习题 1.41.(1)原式 ( P Q) ( P Q) (Q P)( P Q) (Q P)(P Q) Q PQ P,既是析取范式又是合取范式(2)原式 ( P Q) ( P Q) ( ( P Q) ( P Q)(P Q) (P Q) 析取范式P (Q Q)合取范式(3)原式 P Q S ( P Q)析取范式( P ( P Q) Q SP Q S 合取范式(4)原式 P P Q Q R 既是析取范式又是合取范式2.(1)原式 P Q R 为真的解释是：000，001，011，100，101，110，111故
9、原式的主析取范式为:( P Q R) ( P Q R) ( P Q R) (P Q R) (P QR) (P Q R) (P Q R)(2)原式 (P Q) R(P Q (R R) (P P) R)(P Q R) (P Q R) (P Q) ( P R)(P Q R) (P Q R) (P (Q Q) R) ( P (Q Q) R)(P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)(P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)为真的解释是 101，100，111，011，001(3)原式 ( P (Q R) (
10、P ( Q R)( P (Q R) P) ( P (Q R) ( Q R)( P P) (Q P R) ( P Q R) (Q R Q R)(P Q R) ( P Q R)为真的解释是：000,111(4)原式 P P Q Q R P Q R 为真的解释是：001，010，011，100，101，110，111故原式的主析取范式为：( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R)3.(1)原式 P Q P Q T 主合取范式，无为假的解释。(2)原式 (P Q R) ( P Q R) ( P Q R) ( P Q R)为真的解
11、释为：111，011，001，000，故为假的解释为：010，100，101，110原式的主合取范式为：(P Q R) ( P Q R) ( P Q R) ( P Q R)(3)由 2.(2)知，原式为真的解释是：101，100，111，011，001，故为假的解释是：000，010，110.故原式的主合取范式为：(P Q R) (P Q R) ( P Q R)(4)由 2.(4)知，原式为假的解释是：000，故原式的主合取范式为：P Q R4.(1)左式 ( P Q) ( P R)( P Q (R R) ( P (Q Q) R)( P Q R) ( P Q R) ( P Q R)右式 P (
12、Q R) ( P Q) ( P R)( P Q R) ( P Q R) ( P Q R)故原式成立。(2)左式 （PQ）（PQ ） ，右式 （PP ）(Q P) P（PQ ） P （PQ）（PQ） ，故原式成立(3)左式 （PQ）（PQ ） F，主析取范式右式 （PQ）（PQ ） F，故原式成立(4)左式 T（P Q） T，主合取范式右式 （PQ）（PQ ） T，故原式成立习题 1.51.（1）PQ 前提P ，化简P(QR) 前提QR ，MPQ ，化简R ，MP（2）R 前提（QR） 前提QR ，E11Q ，析取三段论PQ 前提P ，析取三段论（3）S 假设前提 SP 前提P ，析取三段论（P
13、Q）（PR） 前提PQ ，化简PR ，化简Q ，MPR ，MPQR ，合取引入（QR） 前提（QR）（QR ） ，合取引入F ，E21故原推理成立（4）R 假设前提（PQ）R 前提（PQ） ，拒取式PQ ，E14，E10QT 前提PQQT ，合取引入F ，E21，E17故原推理成立2.（1）P 附加前提PQ 前提Q ，析取三段论QR 前提R ，析取三段论RS 前提S ，MPPS CP（2）P 附加前提PQ 前提Q ，MPPQ ，合取引入PPQ CP（3）PQ 附加前提P ，化简PQ ，附加规则PQ R 前提 R ，MPPQ R CP（4）P 附加前提Q 附加前提P（QR ） 前提QR ，MPR
14、 ，MPQ（RS ） 前提RS ，MPS ，MPPQ R CP3.（1）（P） 假设前提P ，E1PQ 前提Q ，MPQR 前提R ，析取三段论RS 前提RRS ，合取引入F ，E21，E17故原推理成立（2）（RS） 假设前提RS ，E10R ，化简S ，化简PR 前提QS 前提P ，拒取式 Q ，拒取式PQ ，合取引入（PQ） ，E10PQ 前提（PQ）（PQ ） ，合取引入F ，E21故原推理成立（3）1.(S) 假设前提2.S 1,E13.SQ 前提4.Q 2, 3,MP5.R Q 前提6.(RQ) (R Q) 5,E157.RQ 6,化简8.R 4, 7,拒取式9.R 前提10.RR
15、 8,9,合取引入11.F 10,E21故反推原理正确(4) 1.(P Q) 假设前提2.（PQ） (QP) 1,E15,E113.(PQ) (RS) 前提4. (Q P) R 前提5.(Q P) R 4,E146.(RS) R 2，3，5 构造二难性7.(RS) R) 6，E118.R 7，E139.R 前提10.RR 8，9 合取引入11.F 10，E21故反推原理正确4 （1）先证 AAA 附加前提A(AA) P31 例 1.5.7 中用A 置换用A 置换 A(AA) ，MP(AA) ( A A) L3 中用A 置换 BAA ，MPA ，MPAA 演绎定理再证AA AA 上述结论中用 A
16、 置换 A(AA) (A A) L3 中用 A 置换 A，用 A 置换 BAA ， MP最后证(BA) (AB) BA 附加前提 BB 上述结论 BA ，HS AA 上述结论 BA ，HS (BA) ( AB) L3 中用B 置换 A，用A 置换 B AB ，MP (BA) (AB) 演绎定理(2)先证 (AB) A(AB) 附加前提A(AB) P31,例 1.5.7(A(A B) (AB) A) （1）(AB) A ，MPA ，MPAA 上述结论A ，MP(AB) A 演绎定理再证 (AB) (B A)(AB) A 上述结论A(BA) L1(AB) (B A) ，HS习题 1.61. PQ
17、PQ(P P) Q(PP) Q) (PP) Q)(P P) Q)(PQ) R (PQ) R) (P Q) (RR) (PQ) (RR)2. P(QR) P(Q R) (PQ) (P R) (PQ) (PR) (P(Q Q) (PR) (P(QQ) (PR)3.(1)左式 P Q(PQ) 右式(2)左式 PQ(PQ) 右式4 （1）否，见 P33，例 1.6.1（2）否，见 P33，例 1.6.1（3）是，PQ (P Q),PQ(P Q) (PQ) P Q, PQPQ(P Q),P Q(PQ) (QP) (PQ) (Q P) (P Q) (QP) (PQ) (Q P) (P Q) (Q P)，
18、中去掉，无法表示否定，去掉 ，无法表示二元运算(4 ) 否。，为极小全功能集 (5 ) 否。因为没公式 A(P,Q)仅含 P,Q, , ,则 A(P,Q)仅在两种解释下为真，而 PQ 仅在一种解释下为真，故 A(P,Q)与 A 不等价，即 PQ 不能用仅含 的公式等价地表示。（6）是。P P P,PQ (P Q) (PQ) (PQ),PQ (PQ) PQ (PP) (QQ),P Q(PQ) (QP) (P Q) (Q P) (P(Q Q) (Q(PP) (P(Q Q) (Q(PP) (P(Q Q) (Q (PP)(P(QQ)(Q(PP)(7) 否，由（6）知(8)是，类似于（6）习题 2.11
19、.(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(
20、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)
21、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,
22、存在 y，使 x*y=x(6)存在 x,对任意 y，有 x*y=x(7)对任意 x 和 y，存在 y，使 x-y=y习题 2.21. (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)
