离散数学 第2章习题答案 .pdfVIP

第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)yM(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的后继时，则有y＝z”的意思相同，所以原语句可符号化为：

x(N(x)y(N(y)∧M(x，y)))∧xyz(N(x)∧N(y)∧N(z)(M(x，y)∧M(x，z)(y＝z)))

其中N(x)表示x是自然数，M(x，y)表示y是x的后继数。

(5)设S(x，y，z)表示“x＋y＝z”，则此语句符号化为：xyzS(x，y，z)。

(6)设Z(x)表示“x是整数”，S(x，y)表示“xy＝0”，T(x，y)表示“x＝y”，则此语句符号化为：

xy(Z(x)∧Z(y)(S(x，y)T(x，0)∨T(y，0)))。

(7)设E(x)表示“x是偶数”，P(x)表示“x是素数”，S(x，y)表示“x＝y”，则此语句符号化为：

x(E(x)∧P(x)y(E(y)∧P(y)S(x，y)))。

(8)设E(x)表示“x是偶数”，O(x)表示“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)xP(x，y，x))。

(2)符号化为：xy(P(x，y，0)(E(x，0)∧E(0，y)))。

(3)符号化为：xy(P(x，y，0)(E(x，0)∧E(0，y)))。

(4)符号化为：xy(((E(x，y)∨G(y，x))∧((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)，

而第二次出现的x的辖域为R(x)，y的辖域为Q(y)。P(x，y)中的y是自由变元，x是约束变元。Q(y)

1

第2章谓词逻辑

中的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的辖域为