第二章 谓词逻辑

习题与解答

1. 将下列命题符号化：

(1) 所有的火车都比某些汽车快。

(2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。

解 (1) 取论域为所有交通工具的集合。令

T(x):x是火车， C(x):x是汽车， F(x,y):x比y跑得快。

“所有的火车都比某些汽车快”可以符号化为?x(T(x)??y(C(y)?F(x,y)))。 (2) 取论域为所有物质的集合。令

M(x):x是金属， L(x):x是液体， D(x,y):x可以溶解在y中。

“任何金属都可以溶解在某种液体中” 可以符号化为?x(M(x)??y(L(y)?D(x,y)))。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为

?x(M(x)??y(L(y)?D(x,y)))。

(4) 取论域为所有事物的集合。令

M(x):x是人， J(x):x是职业， L(x,y):x喜欢y。

“每个人都有自己喜欢的职业” 可以符号化为?x(M(x)??y(J(y)?L(x,y))) (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为

?x(J(x)??y(M(y)?L(y,x)))。

2. 取论域为正整数集，用函数?（加法），?（乘法）和谓词?，?将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。

(4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下：

D(x,y):x能被y整除，D(x,y)可表示为?v(v?y?x)。 J(x):x是奇数，J(x)可表示为??v(v?2?x)。 E(x):x是偶数，E(x)可表示为?v(v?2?x)。

P(x):x是素数，P(x)可表示为?(x?1)??u(?v(v?u?x)?u?1?u?x)。

(1) “没有既是奇数，又是偶数的正整数”可表示为??x(J(x)?E(x))， 并可进一步符号化为??x(??v(v?2?x)??v(v?2?x))。 (2) “任何两个正整数都有最小公倍数”可表示为

?x?y?z(D(z,x)?D(z,y)??u(D(u,x)?D(u,y)?z?u?z?u))，

并可进一步符号化为

?x?y?z(?v(v?x?z)??v(v?y?z)??u(?v(v?x?u)??v(v?y?u)?z?u?z?u))(3) “没有最大的素数”可表示为??x(P(x)??y(P(y)?y?x?y?x))， 并可进一步符号化为

??x(?(x?1)??u(?v(v?u?x)?u?1?u?x)

??y(?(y?1)??u(?v(v?u?y)?u?1?u?y)?y?x?y?x))(4) “并非所有的素数都不是偶数”可表示为??x(P(x)??E(x))，并可进一步符号化为

??x(?(x?1)??u(?v(v?u?x)?u?1?u?x)???v(v?2?x))

3. 取论域为实数集合，用函数?，－（减法）和谓词?，?将下列命题符号化： (1) 没有最大的实数。

(2) 任何两个不同的实数之间必有另一实数。 (3) 函数f(x)在点a处连续。 (4) 函数f(x)恰有一个根。 (5) 函数f(x)是严格单调递增函数。

解 (1) “没有最大的实数”符号化为??x?y(y?x?y?x)。

(2)“ 任何两个不同的实数之间必有另一实数”符号化为?x?y(x?y??z(x?z?z?y))。 (3) “函数f(x)在点a处连续”的定义是：

任给??0，总可以找到??0，使得只要|x?a|??就有|f(x)?f(a)|??。 “函数f(x)在点a处连续”符号化为

??(0?????(0????x(a???x?x?a???f(a)???f(x)?f(x)?f(a)??)))

(4) “函数f(x)恰有一个根”符号化为?x(f(x)?0??y(f(y)?0?y?x))。 (5) “函数f(x)是严格单调递增函数”符号化为?x?y(x?y?f(x)?f(y))。 4. 指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。 (1) ?x(P(y,x)?P(x,a)) (2) ?xP(x)??zQ(x,y)

(3) ?x(P(x)?R(x))??xP(x)?Q(x) (4) ?y(P(f(x,y),x)??xP(z,g(x,y))) (5) ?x(P(x)?Q(x)??xR(x))?R(x)

解 (1) 变元 x 在?x(P(y,x)?P(x,a))中三次出现都是约束出现，?x 的唯一出现的辖域是 P(y, x) ? P(x, a)。

(2) 变元 x 在?xP(x)??zQ(x,y)中的头两次出现是约束出现，第三次出现是自由出现。变元 y 在?xP(x)??zQ(x,y)中的唯一出现是自由出现。变元 z 在

?xP(x)??zQ(x,y)中的唯一出现是约束出现。?x 的唯一出现的辖域是 P(x)，?z 的唯

一出现的辖域是Q(x, y)。

(3) 变元 x 在?x(P(x)?R(x))??xP(x)?Q(x)中的头五次出现是约束出现，第六次出现是自由出现。?x 的第一次出现的辖域是P(x) ? R(x)，第二次出现的辖域是P(x)。 (4) 变元 x 在?y(P(f(x,y),x)??xP(z,g(x,y)))中的头两次出现是自由出现，后两次出现是约束出现。?x 的唯一出现的辖域是 P(z, g(x, y))， ?y 的唯一出现的辖域是 P(f(x, y), x) ? ?xP(z, g(x, y))。

(5) 变元 x 在?x(P(x)?Q(x)??xR(x))?R(x)中的头五次出现是约束出现，第六次出现是自由出现。?x 的唯一出现的辖域是P(x) ? Q(x) ? ?xR(x)，?x 的唯一出现的辖域是R(x)。 5. 归纳证明：若t，t?是项，则ttx?也是项。 证明 ① 若t是x，则ttx?是t?，ttx?是项。

② 若t是不同于x的变元y，则ttx?仍是y，ttx?是项。 ③ 若t是常元a，则ttx?仍是a，ttx?是项。

xxxx④若t是f(t1,?,tn)，则ttx?是f((t1)t?,?,(tn)t?)，由归纳假设知(t1)t?,?,(tn)t?都是项，