发布时间 : 星期一 文章离散数学答案（尹宝林版）第二章习题解答更新完毕开始阅读3b8762726ad97f192279168884868762caaebba9
第二章 谓词逻辑
习题与解答
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?是项，则tt?也是项。 证明 ① 若t是x，则tt?是t?，tt?是项。
② 若t是不同于x的变元y，则tt?仍是y，tt?是项。 ③ 若t是常元a，则tt?仍是a，tt?是项。
④若t是f(t1,?,tn)，则tt?是f((t1)tx?,?,(tn)tx?)，由归纳假设知(t1)tx?,?,(tn)tx?都是项，
xxxxxxxx
所以tt?是项。
6. 归纳证明：若t是项，A是公式，则At也是公式。
证明 ① 若A是P(t1,?,tn)，则At是P((t1)tx,?,(tn)tx)，由上题知(t1)tx,?,(tn)tx都是项，所以At是公式。
② 若A是?B，则At是?Bt，由归纳假设知Bt是公式，所以At是公式。
③ 若A是B?C，则At是Btx?Ctx，由归纳假设知Bt和Ct都是公式，所以At是公式。
④ 若A是?xB，则At仍是A，At是公式。
⑤ 若A是?yB，其中y是不同于x的变元，则At是?yBtx，由归纳假设知Bt是公式，所以At是公式。
7. 给定解释I和I中赋值v如下：
xxxxxxxxxxxxxxxxxDI?{1,2}，aI?1，bI?2，fI(1)?2，fI(2)?1
PI(1,1)?PI(1,2)?1，PI(2,1)?PI(2,2)?0，v(x)?1，v(y)?1
计算下列公式在解释I和赋值I中v下的真值。 (1) P(a,f(x))?P(x,f(b))?P(f(y),x) (2) ?x?yP(y,x)
(3) ?x?y(P(x,y)?P(f(x),f(y))) 解 (1) (2)
I(P(a,f(x))?P(x,f(b))?P(f(y),x))(v)
?PI(aI,fI(v(x)))?PI(v(x),fI(bI))?PI(fI(v(y)),v(x)) ?PI(1,fI(1))?PI(1,fI(2))?PI(fI(1),1) ?PI(1,2)?PI(1,1)?PI(2,1)?1?1?0?0
I(?x?yP(y,x))(v)
?I(?yP(y,x))(v[x/1])?I(?yP(y,x))(v[x/2]) ?(I(P(y,x))(v[x/1][y/1])?I(P(y,x))(v[x/1][y/2]))