离散数学 第2章习题答案

1、第2章 谓词逻辑第2章习题答案1. 解 (1)设F(x)表示“x犯错误”，N(x)表示“x为人”，则此语句符号化为：$x(N(x)F(x)。(2)设F(x)表示“x是推理”，M(x)表示“x是计算机”， H(x，y)表示“x能由y完成”，则此语句符号化为：x(F(x)$ y M(y)H(x，y)。(3)设C(x)表示“x是计算机系的学生”，D(x)表示“x学习离散数学”，则此语句符号化为：x(C(x) D(x)。(4)因原语句与“一切自然数x，都有一个自然数y，使得y是x的后继数；并且对任意自然数x，当y和z都是x的后继时，则有yz”的意思相同，所以原语句可符号化为：x(N(x)$ y(N(y

2、)M(x，y)xyz(N(x)N(y)N(z)(M(x，y)M(x，z)( yz)其中N(x)表示x是自然数，M(x，y)表示y是x的后继数。(5)设S(x，y，z)表示“xyz”，则此语句符号化为：xy$z S(x，y，z)。(6)设Z(x)表示“x是整数”，S(x，y)表示“xy0”，T(x，y)表示“xy”，则此语句符号化为：xy(Z(x)Z(y)(S(x，y) T(x，0)T(y，0)。(7)设E(x)表示“x是偶数”，P(x)表示“x是素数”，S(x，y)表示“xy”，则此语句符号化为：x(E(x)P(x)y(E(y)P(y) S(x，y)。(8)设E(x)表示“x是偶数”，O(x)

3、表示“x是奇数”，N(x)表示“x是自然数”，则此语句符号化为：$x(E(x)O(x)N(x)。(9)设R(x)表示“x是实数”，Q(x)表示“x是有理数”，Z(x)表示“x是整数”，则此语句符号化为：$x(R(x)Q(x)Z(x)。(10)设R(x)表示“x是实数”，Q(x，y)表示“y大于x”，则此语句符号化为：x(R(x)$y(R(y)Q(x，y)。2. 解 (1)符号化为：y(E(1，y)x P(x，y，x)。(2)符号化为：xy(P(x，y，0)(E(x，0)E(0，y)。(3)符号化为：xy(P(x，y，0)(E(x，0)E(0，y)。(4)符号化为：xy(E(x，y)G(y，x)

4、(E(x，y)G(x，y) E(x，y)。3. 解 (1)存在x，x是偶数，且x整除6。(2)对任意x，如果x是奇数，则对任意y，若y是素数，则x不整除y。(3)对任意x，如果x不是偶数，则2不整除x。(4)对任意x，如果x是偶数，则对任意y，若x整除y，则y是偶数。4.解 (1)在公式x(P(x)$xQ(x)(x(P(x)Q(x)中，第一次出现的x的辖域为P(x)$xQ(x)，$x的辖域为Q(x)，而第二次出现的x的辖域为P(x)Q(x)。公式中只出现了变元x，所有x都是约束变元。(2)在公式x(P(x，y)$yQ(y)(xR(x)Q(x)中，第一次出现的x的辖域为P(x，y)$yQ(y)，

5、而第二次出现的x的辖域为R(x)，$y的辖域为Q(y)。P(x，y)中的y是自由变元，x是约束变元。Q(y)中的y是约束变元。R(x)中的x是约束变元，而Q(x)中的x是自由变元。(3)在公式x(P(x，y)Q(z)$y(R(x，y) zQ(z)，x的辖域为P(x，y)Q(z)，$y的辖域为R(x，y)zQ(z)，z的辖域为Q(z)。公式中第一次出现的x是约束变元，第二次出现的x是自由变元，第一次出现的y和z都是自由变元，而第二次出现的y和z都是约束变元。5.解 x(P(x，y)$yQ(y)M(x，y)(xR(x)Q(x)u(P(u，y)$yQ(y)M(u，y)(xR(x)Q(x)u(P(u，

6、y)$vQ(v)M(u，y)(xR(x)Q(x)u(P(u，y)$vQ(v)M(u，y)(wR(w)Q(x)6.解 $y(P(x，y)(zQ(x，y)R(x，y，z)x$zS(x，y，z)$y(P(u，y)(zQ(u，y)R(u，y，z)x$zS(x，y，z)$y(P(u，y)(zQ(u，y)R(u，y，z)x$zS(x，v，z)$y(P(u，y)(zQ(u，y)R(u，y，z)x$wS(x，v，w)7. 解 (1)xF(f(a，x)，a)x(f(a，x)a)x(axa)x(0x0)x(0x)F(2)xy(F(f(x，y)，x)xy(f(x，y)x)xy(xyx)xy(0y)xy(y0)F(3

7、)xyz(F(x，y)F(f(x，z)，f(y，z)xyz(xy)(f(x，z)f(y，z)xyz(xy)(xzyz)xyz(xy)(xy)T(4)x$yF(x，f(f(x，y)，y)x$y(xf(f(x，y)，y)x$y(x(f(x，y)y)x$y(x(xyy)x$y(xx2y)T8. 解 (1)设论域为1，2。若P(1)P(2)T，则$xP(x)xP(x)( P(1)P(2)( P(1)P(2)(TT)(TT)FTT若P(1)P(2)F，则$xP(x)xP(x)( P(1)P(2)( P(1)P(2)(FF)(FF)TFF 所以，$xP(x)xP(x)为可满足式。(2)xA(x)$x(A(

8、x)$x(A(x)$x(A(x)T，所以xA(x)$x(A(x)为永真式。(3)设论域为1，2。若P(1)P(2)Q(1)Q(2)F，则$x(P(x)Q(x)($xP(x)Q(x)(P(1)Q(1)(P(2)Q(2)( P(1)P(2)Q(x)(FF)(FF)(FF)Q(x)T若P(1)Q(1)Q(2)T，P(2)F，则$x(P(x)Q(x)($xP(x)Q(x)(P(1)Q(1)(P(2)Q(2)( P(1)P(2)Q(x)(TT)(FT)(TF)Q(x)T(TF)F所以，$x(P(x)Q(x)($xP(x)Q(x)为可满足式。(4)设论域为实数集R。若F(x，y)表示“xy”，则$xy(F

9、(x，y)F(y，x)$xy(xy)( yx)T。若F(x，y)表示“xy”，则$xy(F(x，y)F(y，x)$xy(xy)( yx)F。所以，$xy(F(x，y)F(y，x) 为可满足式。9.解 xP(x)$xQ(x)(P(a)P(b)P(c)(Q(a)Q(b)Q(c)。10. 解 (1)x(F(x)G(x)(F(2)G(2)(F(3)G(3)(F(6)G(6)(TF)(TF)(FT)F(2)x(R(x)F(x)G(5)(R(2)F(2)(R(3)F(3)(R(6)F(6)G(5)(TT)(TT)(TF)F(TTF)F F(3)$x(F(x)G(x)(F(2)G(2)(F(3)G(3)(F

10、(6)G(6)(TF)(TF)(FT)T11. 证明 (1)x(A(x)B)为假$a使(A(a)B)为假$a使A(a)为假且B为假xA(x)为假且B为假xA(x)B为假，故x(A(x)B)xA(x)B。(2)x(A(x)B)为假$a使(A(a)B)为假$a使A(a)为假或B为假xA(x)为假或B为假xA(x)B为假，故x(A(x)B)xA(x)B。(4)x(BA(x)x(BA(x)Bx A(x)BxA(x)(5)$x(A(x)B)为真$a使(A(a)B)为真$a使A(a)为真或B为真$xA(x)为真或B为真$xA(x)B为真，故$x(A(x)B)$xA(x)B。(6)$x(A(x)B)为真$a

11、使(A(a)B)为真$a使A(a)为真且B为真$xA(x)为真且B为真$xA(x)B为真，故$x(A(x)B)$xA(x)B。(7)$x(A(x)B)$x(A(x)B)$xA(x)BxA(x)B xA(x)B(8)$x(BA(x)$x(BA(x)B$x A(x)B$xA(x)12. 证明 (1)x(A(x)B(x)x(A(x)B(x)$x(A(x)B(x)$x(A(x)B(x)(2)xy(P(x)Q(y)xy(P(x)Q(y)x(P(x)yQ(y)xP(x)yQ(y)$xP(x)yQ(y)($xP(x)yQ(y)(3)$xP(x)$xQ(x)($xP(x)$xQ(x)$x(P(x)Q(x)x(

12、P(x)Q(x)x(P(x)Q(x)13. 解 因为yA(0，y)y(0yy)T，所以$xyA(x，y)为真。14. 解 (1)设论域为1，2。若P(1)P(2)T，Q(1)Q(2)F，R(1，1)R(1，2)R(2，1)R(2，2)F，则x(P(x)$y(Q(y)R(x，y)x(P(x)(Q(1)R(x，1)(Q(2)R(x，2)(P(1)(Q(1)R(1，1)(Q(2)R(1，2)(P(2)(Q(1)R(2，1)(Q(2)R(2，2)(T(FF)(FF)(T(FF)(FF)(TF)(TF)F若P(1)P(2)T，Q(1)Q(2)T，R(1，1)R(1，2)R(2，1)R(2，2)T，则x(

13、P(x)$y(Q(y)R(x，y)x(P(x)(Q(1)R(x，1)(Q(2)R(x，2)(P(1)(Q(1)R(1，1)(Q(2)R(1，2)(P(2)(Q(1)R(2，1)(Q(2)R(2，2)(T(TT)(TT)(T(TT)(TT)(TT)(TT)T(2) 设论域为1，2。若P(1，1)P(1，2)P(2，1)P(2，2)T，则xy(P(x，y)P(y，x)x(P(x，1)P(1，x)(P(x，2)P(2，x)(P(1，1)P(1，1)(P(1，2)P(2，1)(P(2，1)P(1，2)(P(2，2)P(2，2)(TF)(TF)(TF)(TF)F若P(1，1)P(1，2)P(2，1)P(

14、2，2)F，则xy(P(x，y)P(y，x)x(P(x，1)P(1，x)(P(x，2)P(2，x)(P(1，1)P(1，1)(P(1，2)P(2，1)(P(2，1)P(1，2)(P(2，2)P(2，2)(FT)(FT)(FT)(FT)T(3)设论域为a，b，若P(a)F，P(b)T，则$xP(x)为真，所以$xP(x)P(a)为假；若P(a)T，P(b)F，则$xP(x)为真，所以$xP(x)P(a)为真。(4)设论域为1，2若P(x，y)：xy，则xy(P(x，y)P(y，x)x(P(x，1)P(1，x)(P(x，2)P(2，x)(P(1，1)P(1，1)(P(1，2)P(2，1)(P(2，

15、1)P(1，2)(P(2，2)P(2，2)(FF)(FT)(TF)(FF)TTFTF若P(x，y)：xy，则xy(P(x，y)P(y，x)x(P(x，1)P(1，x)(P(x，2)P(2，x)(P(1，1)P(1，1)(P(1，2)P(2，1)(P(2，1)P(1，2)(P(2，2)P(2，2)(FF)(TT)(TT)(FF)TTTTT15. 证明 (2)若$x(A(x)B(x)为真，则存在个体a使A(a)B(a)为真，于是A(a)和B(a)皆为真，$xA(x)和$xB(x)为真，从而$xA(x)$xB(x)真，所以，$x(A(x)B(x)$xA(x)$xB(x)。(4)$x(A(x)B(x)

16、$x(A(x)B(x)$xA(x)$x B(x)xA(x)$x B(x)xA(x)$xB(x)所以，$x(A(x)B(x)xA(x)$xB(x)。16.证明 (2)设I为任意解释。如果$xA(x，x)在I下为真，则存在一个个体a使得A(a，a)为真，于是$yA(a，y)为真，从而$x$yA(x，y)为真。因此$xA(x，x)$x$yA(x，y)。(3)设I为任意解释。如果$yxA(x，y)为假，则存在一个个体a使得xA(x，a)为假，于是A(x，a)为假，从而yA(x，y)为假，因此xyA(x，y)为假。故xyA(x，y)$yxA(x，y)。(4)设I为任意解释。如果$xyA(x，y)在I下为

17、真，则存在一个个体a使得yA(a，y)为真，于是A(a，y)为真，从而$xA(x，y)为真，于是y$xA(x，y)为真。因此$xyA(x，y)y$xA(x，y)。(5)设I为任意解释。如果$y$xA(x，y)为假，则存在个体a和b使得A(a，b)为假，于是$yA(a，y)为假，从而x$yA(x，y)为假。故xyA(x，y)$yxA(x，y)。17. 解 (1)x(P(x)($yQ(y)$yR(x，y)x(P(x)($zQ(z)$yR(x，y) x(P(x)$y($zQ(z)R(x，y)x(P(x)$yz(Q(z)R(x，y)x$y$z(P(x)(Q(z)R(x，y) (2)x(F(x)G(x)

18、($xF(x)$xG(x)x(F(x)G(x)($uF(u)$vG(v) x(F(x)G(x)u(F(u)$vG(v)x(F(x)G(x)u$v(F(u)G(v)xu$v(F(x)G(x)(F(u)G(v) (3)xy($zP(x，z)P(y，z)$uQ(x，y，u)xy($zP(x，z)P(y，z)$uQ(x，y，u)xyz(P(x，z)P(y，z)$uQ(x，y，u)xyz$u(P(x，z)P(y，z)Q(x，y，u)18. 解 (1)($xA(x)$xB(x)$x(A(x)B(x)($xA(x)$xB(x)$x(A(x)B(x)($xA(x)$xB(x)$x(A(x)B(x)($xA(x

19、)$xB(x)$xA(x)$xB(x)($xA(x)$xA(x)$xB(x)($xB(x)$xA(x)$xB(x)$x(A(x)A(x)$xB(x)T 所以，($xA(x)$xB(x)$x(A(x)B(x)为永真式。(2)设论域为1，2，令A(1)T；A(2)F；B(1)F；B(2)T。则xA(x)为假，xB(x)也为假，从而xA(x)xB(x)为真；而由于A(1)B(1)为假，所以x(A(x)B(x)也为假，因此公式(xA(x)xB(x)x(A(x)B(x)为假。该公式不是永真式。(3)因为($xA(x)xB(x)($xA(x)xB(x)(xA(x)xB(x)x(A(x)B(x)x(A(x)

20、B(x)所以，($xA(x)xB(x)x(A(x)B(x)为永真式。(4)设论域为1，2，令A(1)T；A(2)T；B(1)F；B(2)T。则xA(x)$xB(x)(A(1)A(2)(B(1)B(2)TTT，而x(A(x)B(x) (A(1)B(1)(A(2)B(2)(TF)(TT) FTF，所以(xA(x)$xB(x)x(A(x)B(x)不是为永真式。19. 证明 1)(1)$xF(x) P(2)F(a) T(1)，ES(3)$x(R(x)T(x) P(4)R(b)T(b) T(3)，ES(5)(R(b)T(b) T(4)，E(6)(R(b)T(b) T(5)，E(7)$y(R(y)T(y)

21、 T(6)，EG(8)y(R(y)T(y) T(7)，E(9)z(F(x)x$yQ(x，y)y(R(x)T(y) P(10)z(F(x)x$yQ(x，y)y(R(x)T(y) T(9)，E(11)z(F(x)x$yQ(x，y) T(8)(10)，I(12)z(F(x)x$yQ(x，y) T(11)，E(13)F(a)x$yQ(x，y) T(12)，US(14)F(a)x$yQ(x，y) T(13)，E(15)x$yQ(x，y) T(2)(14)，I(16)$xyQ(x，y) T(15)，E(17)yQ(c，y) T(16)，ES(18)y$xQ(x，y) T(17)，EG2)(1)xP(x)

22、P(2)P(a) T(1)，US(3)x(P(x)(Q(y)R(x) P(4)P(a)(Q(y)R(a) T(3)，US(5)Q(y)R(a) T(2)(4)，I(6)Q(y) T(5)，I(7)R(a) T(5)，I(8)P(a)R(a) T(2)(7)，I(9)$x(P(x)R(x) T(8)，EG(10)Q(y)$x(P(x)R(x) T(5)(9)，I3)(1)$x(A(x)yB(y) P (2)A(a)yB(y) T(1)，ES(3)x(B(x)$yC(y) P(4)x(B(x)C() T(3)，ES(5)B()C() T(4)，US(6)A(a)B() T(2)，US(7)A(a)

23、C() T(5)(6)，I(8)xA(x)C() T(7)，UG(9)xA(x)$yC(y) T(8)，EG4)(1)x(y(B(x，y)A(y)C(x) P (2)x(B(x，)A()C(x) T(1)，US (3)x(C(x)(B(x，)A() T(2)，E (4)x(C(x)(B(x，)A() T(3)，E (5)x(C(x)(B(x，)A() T(4)，E (6)x(C(x)$y(A(y)B(x，y) T(5)，EG5)(1)x(A(x)B(x)C(x) P(2)A(a)B(a)C(a) T(1)，US(3)x(C(x)D(x) P(4)C(a)D(a) T(3)，US(5)B(a)C

24、(a)B(a)D(a) T(4)，I(6)A(a)B(a)D(a) T(2)(5)，I(7)A(a)B(a)D(a) T(6)，E(8)D(a)(A(a)B(a) T(7)，E(9)D(a)(A(a)B(a) T(8)，E(10)x(D(x)(A(x)B(x) T(9)，UG20. 解 (1)设论域为1，2，令A(1)A(2)B(1)B(2)F。则：x(A(x)xB(x)x(A(x)( B(1)B(2) (A(1)( B(1)B(2)(A(2)( B(1)B(2)(F(FF)(F(FF)T但$xA(x)$xB(x)( A(1)A(2)(B(1)B(2)(FF)(FF)F所以，x(A(x)xB(

25、x)$xA(x)$xB(x)不正确。(2)设论域为1，2，令P(1)P(2)T；Q(1)Q(2)T；R(1)R(2)F。则：x$y(P(x)Q(y)x(P(x)Q(1)(P(x)Q(2) (P(1)Q(1)(P(1)Q(2)(P(2)Q(1)(P(2)Q(2)(TT)(TT)(TT)(TT)Ty$z(R(y)Q(z)y(R(y)Q(1)(R(y)Q(2) (R(1)Q(1)(R(1)Q(2)(R(2)Q(1)(R(2)Q(2) (FT)(FT)(FT)(FT) T但$xz(P(x)R(z)$x(P(x)R(1)(P(x)R(2)(P(1)R(1)(P(1)R(2)(P(2)R(1)(P(2)R

26、(2)(TF)(TF)(TF)(TF)F所以，x$y(P(x)Q(y)，y$z(R(y)Q(z)$xz(P(x)R(z)不正确。21. 解 1)论域：所有人的集合。()：喜欢步行；()：喜欢坐汽车；()：喜欢骑自行车；则推理化形式为：()()，()()，()()下面给出证明：(1)() P(2)() T(1)，ES(3)()() P(4)()() T(3)，US(5)() T(2)(4)，I(6)()() P(7)()() T(6)，US(8)() T(5)(7)，I(9)() T(8)，EG2)令()：是牛；()：有角；()：是动物；则推理化形式为：()()，()()()()下面给出证明：(1)()() P(2)()() T(1)，ES(3)()() P(4)()() T(3)，US(5)() T(2)，I(6)() T(4)(5)，I(7)() T(2)，I(8)()() T(6)(7)，I(9)()() T(8)，EG3) 论域：所有人的集合。()：是勤奋的；()：是身体健康的；()：是科学家；()：是事业获得成功的人；()：是事业半途而废的人；则推理化形式为：()()，()()()，()()()