第七章_课后习题解答.doc

第七章 谓词逻辑P285：作业：3、5、81、（1）(x)(S(x)G(x)其中S(x)：x是运动员。G(x)：x是大学生。 （2）(x)(S(x)G(x)其中 S(x)：x是运动员。G(x)：x是大学生。（3） ($x)( W(x)A(x)B(x)其中W(x)：x是女同志。A(x)：x是国家选手。B(x)：x是家庭妇女。（4） ($x)( D(x)B(x)C(x)其中D(x)：x是狗。B(x)：x是黑色的。C(x)：x很聪明。2、（1）所有不能被2整除的数都是奇数。（2）存在能被3整除的偶数。（3）存在奇数是素数，但并非所有奇数都是素数。3、（1）令D(x)：x是数。B(x,y)：x与y的和大于x乘y。命题等价于：$x$y(D(x)D(y)B(x,y)（2）令I(x)：x是整数。A(x,y)：x2=y。命题等价于：(x)($y)(I(x)I(y)A(x,y) 4、（1）令 P(x)：x是素数。E(x)：x是偶数。命题等价于：(x)(P(x)E(x)（2）令 I(x)：x是整数。Q(x)：x是有理数。(x)(Q(x)I(x) (x)(Q(x) I(x)5、(1) (x)(P(x)Q(x) (P(1)Q(1) (P(2)Q(2) (P(3)Q(3)(2) (x)($y)R(x,y) (x)(R(x,1) R(x,2) R(x,3) (R(1,1) R(1,2) R(1,3) (R(2,1) R(2,2) R(2,3) (R(3,1) R(3,2) R(3,3)(3) ($y)(x)R(x,y) ($y) (R(1,y) R(2,y) R(3,y) (R(1,1) R(2,1) R(3,1) (R(1,2) R(2,2) R(3,2) (R(1,3) R(2,3) R(3,3)6、(1) 约束变元：x；自由变元：y。(2) 约束变元：x；(3) ($x)(y)(P(x) Q(y) (x)R(x,y)x是约束变元；($x)(y)(P(x) Q(y)中的变元y是约束变元。(x)R(x,y)中的变元y是自由变元。7、(1) (x)(P(x,y) Q(x) R(x,y)对约束变元x换成变元z，可得：(z)(P(z,y) Q(z) R(x,y)(2) ($x)(P(x) Q(x,y) R(x,y)对约束变元x换成变元z，可得：($z)(P(z) Q(z,y) R(x,y)8、(1) ($y)(P(x) R(x,y)将自由元x进行代入可得：($y)(P(z) R(z,y)(2) (y)(P(x) Q(x,y) R(x,y)将自由元x和y分别进行代入可得：(y)(P(z) Q(z,y) R(z,s)P 291: 1、(1) (x)P(x) ($x)Q(x) (x)(P(x) Q(x)证明：(x)P(x) ($x)Q(x) (x) P(x) (x)Q(x)(x)(P(x) Q(x)(2) ($x)(P(x) Q(x) (x) P(x) ($x)Q(x)证明：($x)(P(x) Q(x) ($x)P(x) ($x)Q(x) ($x)P(x) ($x)Q(x) ($x)P(x) ($x)Q(x) (x)P(x) ($x)Q(x)(3) (x) (A(x) B(x) ($x)A(x) ($x)(B(x) A(x)证明：(x) (A(x) B(x) ($x)A(x) (x)A(x) (x)B(x) ($x)A(x) (x)A(x) (x)B(x) ($x)A(x) ($x)A(x) ($x) B(x) ($x)A(x) ($x) (B(x) A(x) ($x)(B(x) A(x)(4) ( ($x)P(x) (x)(P(x) Q(x) (x)P(x) (x)Q(x)证明：( ($x)P(x) (x)(P(x) Q(x) (x)P(x) (x)(P(x) Q(x) (x)P(x) (x)(P(x) Q(x) (x)(P(x)(P(x) Q(x) (x)(P(x)( P(x) Q(x) (x)(P(x)P(x) (P(x)Q(x) (x)(P(x)Q(x) (x)P(x) (x)Q(x)2、（略）3、(1) (x)P(x) ($x)P(x)(x)P(x) (P(a) P(b) P(a) P(b) ($x)P(x)(2) ($x) P(x) (x) P(x)($x) P(x) (P(a) P(b) P(a) P(b) (x) P(x)(3) (x)(A(x) B(x) (x)A(x) (x)B(x)(x)(A(x) B(x) (A(a) B(a) (A(b) B(b) (A(a) A(b) (B(a) B(b) (x)A(x) (x)B(x)(4) ($x)(A(x) B(x) ($x)A(x) ($x)B(x)($x)(A(x) B(x) (A(a) B(a) (A(b) B(b) (A(a) A(b) (B(a) B(b) ($x)A(x) ($x)B(x)4、 (1)是永真式。只需证明当(x)(P(x)Q(x)为真时，(x)P(x)($x)Q(x)必为真。若(x)P(x)为真，显然(x)P(x)($x)Q(x)为真。若 (x)P(x)为真，即($x)P(x)为真，假设P(a)为真，即P(a)为假，而由假设(x)(P(x)Q(x)为真可知：P(a)Q(a)为真，故Q(a)为真，因此($x)Q(x)为真，进而，(x)P(x)($x)Q(x)必为真。所以，当(x)(P(x)Q(x)为真时，(x)P(x)($x)Q(x)必为真。(2)是永真式。(3)不是永真式。5、(1) (x)(P(x) ($y)Q(x,y) (x)(P(x) ($y)Q(z,y) (x)(P(x) ($y)Q(z,y) (x)(P(x) ($y)Q(z,y) (x) ($y) (P(x) Q(z,y)(2) (x)P(x) ($x)Q(x) (x)P(x) ($y)Q(y) (x) ($y) (P(x) Q(y)(3) ($x)( ($y)P(x,y) ($y)Q(z)R(x) ($x)( ($y)P(x,y) ( ($z)Q(z) R(x) ($x)($y)P(x,y) (z)Q(z) R(x) ($x)($y)P(x,y) (z)Q(z) R(w) ($x)($y)(z) (P(x,y) Q(z) R(w)P 294: 作业：1（3、4）、2（3）、31、（1） ($x) (P(x) Q(x) P P(c) Q(c) ES (x) P(x) P P(c) US Q(c) T ($x) Q(x) EG（2） (x) (Q(x) R(x) P (x) (R(x) Q(x) T R(c) Q(c) US (x) (P(x) Q(x) P (x) (Q(x) P(x) T Q(c) P(c) US (x) (R(x) P(x) UG（3） (x) (P(x) Q(x) P (x) (P(x) Q(x) T (x) Q(x) P Q(c) US P(c) Q(c) US P(c) T ($x) P(x) EG（4） ($x) R(x) P R(c) ES (x) (Q(x) R(x) P Q(c) R(c) US Q(c) T (x) (P(x) Q(x) P P(c) Q(c) US P(c) T ($x) P(x) ES2（1） (x) P(x) P(附加前提) P(c) US (x) (P(x) Q(x) P P(c) Q(c) US Q(c) T (x) Q(x) UG（2）显然，($x) Q(x) (x) Q(x) 因此，(x) P(x) ($x) Q(x) (x) Q(x) (x) P(x) (x) Q(x) P(附加前提) Q(c) US (x) (P(x) Q(x) P P(c) Q(c) US P(c) T (x) P(x) UG（3）因为($x) P(x) ($x) P(x) 0 (x) P(x) 0 (x) P(x) 0 因此，可将(x) P(x)作为附加前提。 ($x) R(x) P R(c) ES (x) (Q(x) R(x) P Q(c) R(c) US Q(c) T (x) (Q(x) P(x) P Q(c) P(c) US P(c) T (x) P(x) P(附加前提) P(c) US P(c)P(c)(永假式)3、（1）N(x)：x是自然数；O(x)：x是奇数；E(x)：x是偶数；D(x)：x能被2整除；需证：(x) (N(x) O(x) E(x)，(x) (N(x) E(x) D(x)，($x)(N(x) D(x) ($x)(N(x) O(x)证明： ($x)(N(x) D(x) P N(c) D(c) ES D(c) T (x) (N(x) E(x) D(x) P N(c) E(c) D(c) US N(c) E(c) T N(c) T E(c) T (x) (N(x) O(x) E(x) P N(c) O(c) E(c) US O(c) E(c) T O(c) T ($x)(N(x) O(x) EG（2）M(x)：x是人。S(x): x长期吸烟。 H(x): x身体健康。需证：(x)(M(x) S(x) H(x)，($x) (M(x) H(x) ($x)( M(x) S(x)证明： ($x) (M(x) H(x) P M(c) H(c) ES H(c) T (x)(M(x) S(x) H(x) P M(c) S(c) H(c) US M(c) S(c) T M(c) T S(c) T M(c) S(c) T ($x)( M(x)