离散数学答案(尹宝林版)第二章习题解答.docVIP

第二章 谓词逻辑 习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 是火车， 是汽车， 比y跑得快。 “所有的火车都比某些汽车快”可以符号化为。 (2) 取论域为所有物质的集合。令 是金属， 是液体， 可以溶解在y中。 “任何金属都可以溶解在某种液体中” 可以符号化为。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为。 (4) 取论域为所有事物的集合。令 是人， 是职业， 喜欢y。 “每个人都有自己喜欢的职业” 可以符号化为 (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为。 2. 取论域为正整数集，用函数（加法），（乘法）和谓词，将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： 能被y整除，可表示为。 是奇数，可表示为。 是偶数，可表示为。 是素数，可表示为。 (1) “没有既是奇数，又是偶数的正整数”可表示为， 并可进一步符号化为。 (2) “任何两个正整数都有最小公倍数”可表示为 ， 并可进一步符号化为 (3) “没有最大的素数”可表示为， 并可进一步符号化为 (4) “并非所有的素数都不是偶数”可表示为，并可进一步符号化为 3. 取论域为实数集合，用函数，－（减法）和谓词，将下列命题符号化： (1) 没有最大的实数。 (2) 任何两个不同的实数之间必有另一实数。 (3) 函数在点a处连续。 (4) 函数恰有一个根。 (5) 函数是严格单调递增函数。 解 (1) “没有最大的实数”符号化为。 (2) “任何两个不同的实数之间必有另一实数”符号化为。 (3) “函数在点a处连续”的定义是： 任给，总可以找到，使得只要就有。 “函数在点a处连续”符号化为 (4) “函数恰有一个根”符号化为。 (5) “函数是严格单调递增函数”符号化为。 4. 指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。 (1) (2) (3) (4) (5) 解 (1) 变元 x 在中三次出现都是约束出现，?x 的唯一出现的辖域是 P(y, x) ? P(x, a)。 (2) 变元 x 在中的头两次出现是约束出现，第三次出现是自由出现。变元 y 在中的唯一出现是自由出现。变元 z 在中的唯一出现是约束出现。?x 的唯一出现的辖域是 P(x)，?z 的唯一出现的辖域是Q(x, y)。 (3) 变元 x 在中的头五次出现是约束出现，第六次出现是自由出现。?x 的第一次出现的辖域是P(x) ? R(x)，第二次出现的辖域是P(x)。 (4) 变元 x 在中的头两次出现是自由出现，后两次出现是约束出现。?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)，?x 的唯一出现的辖域是R(x)。 5. 归纳证明：若t，是项，则也是项。 证明 ① 若t是x，则是，是项。 ② 若t是不同于x的变元y，则仍是y，是项。 ③ 若t是常元a，则仍是a，是项。 ④若t是，则是，由归纳假设知都是项，所以是项。 6. 归纳证明：若t是项，A是公式，则也是公式。 证明 ① 若A是，则是，由上题知都是项，所以是公式。 ② 若A是，则是，由归纳假设知是公式，所以是公式。 ③ 若A是，则是，由归纳假设知和都是公式，所以是公式。 ④ 若A是，则仍是A，是公式。 ⑤ 若A是，其中y是不同于x的变元，则是，由归纳假设知是公式，所以是公式。 7. 给定解释I和I中赋值v如下： ，，，， ，，， 计算下列公式在解释I和赋值I中v下的真值。 (1) (2) (3) 解 (1) (2) (3) 7. 给定解释I如下： ， ， 判断I是不是以下语句的模型。 (1) (2) (3) (4) (5) (6) 解 (1) (2) (3) (4) (5) (6) 9. 写出一个语句A，使得A有模型，并且A的每个模型的论域至少有三个元素。 解 语句A为。给定解释如下。 为自然数集合， 当且仅当， ，， 则是A的模型，A有模型。 任取满