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

第二章谓词逻辑练习和解决方案1.象征以下命题：所有的火车都比一些汽车快。(2)任何金属都可以溶解在某种液体中。(3)至少一种金属可以溶解在所有液体中。(4)每个人都有自己喜欢的职业。有些职业是所有人都喜欢的。解决方案(1)将宇宙视为所有交通工具的集合。制造这是一列火车，一辆汽车，它跑得比你快。“所有的火车都比一些汽车快”可以象征为。(2)把宇宙看作所有物质的集合。制造它是金属，它是液体，它能溶解在y中。“任何金属都可以溶解在液体中”可以表示为。(3)话语和谓语的领域与(2)相同。“至少一种金属可以溶解在所有的液体中”可以表示为。(4)把话语的宇宙看作是所有事物的集合。制造这是一个人，一个职业，喜欢你。“每个人都有自己喜欢的职业”可以象征为(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是一个项目，它也是一个项目。证明(1)如果t是x，那么是，是。(2)如果t是一个不同于x的变量y，它仍然是y并且是一个项。(3)如果t是常数元a，它仍然是a，是的。(4)如果t是，那么它是，由归纳假设可知是一个项，所以它是一个项。6.归纳证明：如果T是一个项目，A是一个公式，那么它也是一个公式。证明(1)如果A是，那么是的，上面的问题都是项目，所以它是一个公式。(2)如果a是，那么它就是，被归纳假设称为公式，所以它是一个公式。(3)如果A是，那么是的，归纳假设已知的和是一个公式，所以它是一个公式。(4)如果A是，它仍然是A并且是一个公式。(5)如果A是，其中Y是一个不同于X的变量，那么它是，通过归纳假设被称为公式，所以它是一个公式。7.给出的解释I和I中的赋值v如下：，在解释一和作业一中，计算下列公式的真值。(1)(2)(3)解决方案(1)(2)(3)7.我给出的解释如下：，判断我是否是以下陈述的模型。(1)(2)(3)(4)(5)(6)解决方案(1)(2)(3)(4)(5)(6)9.写一个陈述A，这样A就有了一个模型，并且A的每个模型在它的宇宙中至少有三个元素。解决方案语句a是。给出的解释如下。是一组自然数，当且仅当，它是一个模型，一个有模型。任何解释我都满足陈述A，然后，再次因为，因此，宇宙中有三种不同的元素，并且宇宙中至少有三种元素。10.写一个陈述A，这样A就有一个模型，A的每个模型在它的宇宙中都有无限多的元素。解决方案语句a是。给出的解释如下。是一组自然数，当且仅当它是一个模型，一个有模型。让我们以满足陈述a的解释I为例，因为，因此，有原因，因为，因此。因为，所以，有原因，因为，所以。因为，所以，所以。所以，是宇宙中三种不同的元素。这一过程可以连续进行，并得出结论，宇宙DI中一定有无限多的元素。11.判断下列公式是否永久正确、永久错误和可满足，并解释原因。(1)(2)(3)(4)(5)(6)(7)解答(1)是一个永恒的真理。如果我做出解释，那么或者。(1)如果，则有使，(2)如果是，是有原因的。因此。(2)非永久性真实满足。我给出的解释如下。，然后。给出的解释如下。，然后。(3)非永久性真实满足。我给出的解释如下。，然后。给出的解释如下。，然后。(4)非永久性真实满足。我给出的解释如下。,然后。给出的解释如下。，然后。(5)非永久性真实满足。我给出的解释如下。，然后。给出的解释如下。，然后。(6)这是永恒的真理。如果我使被解释，那么就有使，因此，和，(7)这是永恒的真理。如果我做解释，那么和。存在使，并且因为，因此。因此。12.设A和B是任意公式，证明下面的公式是永久真公式。(1)，其中术语t可代替a中的x。(2)(3)(4)(5)(6)，其中x不是a的自由参数解决方案(1)采用解释I和I中的赋值v，如果是这样，那么。这表明这是永恒的真理。(2)取解释I和I中的任何值v，iff如果并且只有当有这样一个东西如果并且只有当有这样一个东西iff这表明这是永恒的真理。(3)取解释I和I中的任何值V，iff如果并且只有当有这样一个东西如果并且只有当有这样一个东西iff这表明这是永恒的真理。(4)以解释I和I中的赋值v为例，如果是，那么就有这样的，和。这表明这是永恒的真理。(5)拿任何解释我和我中的赋值v来说，如果是这样，那么就有一个原因，这表明它是永恒的真理。(6)以解释I和I中的赋值v为例，如果是这样的话，对于每一个，因为x不是a的自由参数，因此，这表明这是永恒的真理。13.假设它是一级方程式的结束，是的，在那里。证据：(1) A是一个永恒的真理，当且仅当它是一个永恒的真理；(2) A是一个令人满意的公式，当且仅当它是一个令人满意的公式。证明(1)(首先，证明如果A是一个永久真形式，那么它就是一个永久真形式。让A成为永恒的真理。任何解释我和我分配v，任何，因为也分配在我，所以，它总是真实的。如果A是永恒的真理，那它就是永恒的真理，那它就是永恒的真理。()因为它是永恒的真理，所以如果它是永恒的真理，那么a就是永恒的真理。(2)()因为它是一个永久的真表达式，如果我和我被解释为赋值V来满足A，那么我和V就满足了。()如果我和我被解释为满意，那么我和我就满意了。14.判断下面的等价公式是否正确，并解释原因。(1)(2)(3)(4)(5)(6)溶液(1)不含水。把我的解释如下。，然后。(2)不正确。把我的解释如下。，然后。(3)不成立。取I和I中的v值。，然后。(4)设立。我和我赋予v的任何解释，因为x不是一个自由的参数，所以对于每一个。如果并且仅当对于每一个，iff(5)不成立。把我的解释如下。，然后。(6)不正确。把我的解释如下。，然后。15.设A和B是任意公式，并证明下面的等价公式。(1)，其中y不出现在a中(2)(3)，其中x不是b的自由参数，y不是a的自由参数。(4)，其中x不是b的自由参数，y不是a的自由参数。(5)，其中x不是b的自由参数，y不是a的自由参数。(6)证明(1)(2)(3)(4)(5)(6)取解释I和I中的任何值v，如果且仅当有理由如果且仅当有理由如果且仅当有理由如果且仅当有理由iff16.判断下列逻辑推理关系是否成立，并解释原因。(1)(2)(3)(4)(5)(6)溶液(1)不含水。把我的解释如下。，然后。这表明。(2)不正确。把我的解释如下。，然后。这表明。(3)不成立。把我的解释如下。，然后。这表明。(4)如果我做了解释，那么就有一个make，而且，这表明。(5)不成立。把我的解释如下。，这表明。(6)不正确。把我的解释如下。，然后但是。所以。17.让A和B是任意公式来证明下面的结论。(1)(2)(3)，其中x可代替a中的y。(4)证明(1)如果我和我被解释为赋予V作，那么就有作，和。这表明。(2)如果I和I中的赋值V被解释为，对于每个，这表明。(3)如果我和我指定V为使，那么就有一个使，因为，因此。这表明。(4)如果I和I中的赋值V被解释为，对于每个、和，因此和。所以。18.让参数X既不是公式B中的自由参数，也不是公式集中任何公式中的自由参数。a是一个公式。如果是，那么。证明了如果解释I和I中的赋值v是满足的，那么就有原因。因为x不是公式集中任何公式的自由参数，所以我和也满足，我和也满足。因为，因为，因为x不是b中的自由参数，所以。这表明。19.如果集合是一个公式集合，而A是一个公式，那么当且仅当它不满足时。证明集合是可满足的，解释如果赋值V在I和I中是满足的，