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

《离散数学答案(尹宝林版)第二章习题解答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章谓词逻辑习题与解答1.将下列命题符号化：(1)所有的火车都比某些汽车快。(2)任何金属都可以溶解在某种液体中。(3)至少有一种金属可以溶解在所有液体中。(4)每个人都有自己喜欢的职业。(5)有些职业是所有的人都喜欢的。解(1)取论域为所有交通工具的集合。令是火车，是汽车，比y跑得快。“所有的火车都比某些汽车快”可以符号化为。(2)取论域为所有物质的集合。令是金属，是液体，可以溶解在y中。“任何金属都可以溶解在某种液体中”可以符号化为。(3)论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中”可以符号化为。(4)取论域为所有

2、事物的集合。令是人，是职业，喜欢y。“每个人都有自己喜欢的职业”可以符号化为(5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为。2.取论域为正整数集，用函数（加法），（乘法）和谓词，将下列命题符号化：(1)没有既是奇数，又是偶数的正整数。(2)任何两个正整数都有最小公倍数。(3)没有最大的素数。(4)并非所有的素数都不是偶数。解先引进一些谓词如下：能被y整除，可表示为。是奇数，可表示为。是偶数，可表示为。是素数，可表示为。(1)“没有既是奇数，又是偶数的正整数”可表示为，并可进一步符号化为。(2)“任何两个正整数都有

3、最小公倍数”可表示为，并可进一步符号化为(3)“没有最大的素数”可表示为，并可进一步符号化为(4)“并非所有的素数都不是偶数”可表示为，并可进一步符号化为3.取论域为实数集合，用函数，－（减法）和谓词，将下列命题符号化：(1)没有最大的实数。(2)任何两个不同的实数之间必有另一实数。(3)函数在点a处连续。(4)函数恰有一个根。(5)函数是严格单调递增函数。解(1)“没有最大的实数”符号化为。(2)“任何两个不同的实数之间必有另一实数”符号化为。(3)“函数在点a处连续”的定义是：任给，总可以找到，使得只要就有。“函数在点a处连续”符号

4、化为(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的第一次

5、出现的辖域是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、是，由归纳假设知都是项，所以是项。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)

7、解(1)(2)(3)(4)(5)(6)9.写出一个语句A，使得A有模型，并且A的每个模型的论域至少有三个元素。解语句A为。给定解释如下。为自然数集合，当且仅当，，，则是A的模型，A有模型。任取满足语句A的解释I，则，又因为，所以，，是论域中三个不同元素，论域中至少有三个元素。10.写出一个语句A，使得A有模型，并且A的每个模型的论域有无穷多个元素。解语句A为。给定解释如下。为自然数集合，当且仅当则是A的模型，A有模型。任取满足语句A的解释I，取，因为，所以有使得，又因为，故。因为，所以有使得，又因为，故。因为，所以，故。因此，，，是论域

8、中的三个不同元素。这个过程可以不断进行下去，得到因此，论域DI中必然有无穷多个元素。11.判断以下公式是不是永真式、永假式、可满足式，并说明理由。(1)(2)(3)(4)(5)(6)(7)解(1)是永真式。