离散数学习题五

习题五1.设个体域D=a,b,c，在D中消去公式的量词。甲乙用了不同的演算过程：甲的演算过程如下：乙的演算过程如下：显然，乙的演算过程简单，试指出乙在演算过程中的关键步骤。解：乙在演算中的关键步骤是，在演算开始就利用量词辖域收缩与扩张等值式，将量词的辖域缩小，因而演算简单。2. 设个体域D=a,b,c，消去下列各式的量词：解：（1）（2）（3）（4）在（1）（2）（4）中均将量词的辖域缩小，所以演算结果都比较简单3. 设个体域D=1,2，请给出两种不同的解释和，使得下面公式在下都是真命题，而在下都是假命题。（1）（2）解：解释I1为：个体为实数集合R，F(x)：x为自然数，G(x)：x为整数。在I1下，（1）为自然数都是整数，（2）为存在整数为自然数。他们都是真命题解释I2为：个体域仍为实数集R，F(x)：x是无理数，G(x)：x能表示成分数，在I2下，（1）为无理数都能表示成分数，（2）为存在能表示成分数的无理数，他们都是假命题4. 给定公式（1）在解释中，个体域=a，证明公式A在下的真值为1.（2）在解释中，个体域=，,A在下的真值还一定是1吗？为什么？解：（1） 在I1下，（2） 在I2下为可满足式，设F(x)：x为奇数，此时，蕴涵式前件为真，后件为假，故蕴含式为假，若令F(x)；x为整数，则蕴含式前后件均为真，所以（2）中公式在I2下为可满足式5. 给定解释如下：（a）个体域D=3,4；（b）为（c）为试求下列公式在下的真值。解：（1）（2）（3）6. 甲使用量词辖域收缩与扩张等值式进行如下演算乙说甲错了，乙说的对吗？为什么？解：乙说的对，甲错了，全称量词的指导变元x，辖域为，其中F(x)与G(x,y)都是x的约束变元，因而不能讲量词的辖域变小7. 请指出下面等值运算的两处错误解：演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定连接词，演算的第二步，在原错的基础上又用错了等值式和不等值8. 在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式（1） 没有小于负数的正数（2） 相等的两个角未必都是对顶角解：（1） 其中F(x)：x小于负数，G(x)：x是正数（2） 其中F(x)：x是角，H(x,y)：x=y，L(x,y)：x和y是对顶角9. 设个体域D为实数集合，命题“有的实数既是有理数又是无理数”，这显然是个假命题。可是某人却说这是真命题，其理由如下 设F(x)：x是有理数，G(x）：x是无理数。都是真命题，于是，由于是真命题，故也是真命题，即有的实数是有理数，也是无理数这个人的结论对吗？为什么？解：存在量词对无分配律10. 在求前束范式时有人说已是前束范式，理由是量词已在公式的前面，他说的对吗？为什么？解：在前束范式中，否定联结词不能在量词前面出现11. 有人说无法求公式的前束范式，因为公式中的两个量词的指导变元相同。他的理由对吗？为什么？换名规则可以使两个指导变元不相同12. 求下列各式的前束范式：(1)(2)(3)(4)(5)解：（1）（2）（3）（4）（5）13. 将下列命题符号化，要求符号化的公式权威前束范式：（1） 有点火车比有的汽车跑的快（2） 有的火车比所有的汽车跑的快（3） 说有的火车比所有汽车跑得快是不对的（4） 说有的飞机比有的汽车慢也是不对的解：（1） 其中F(x)：x是汽车 G(y):y是 火车 H(x,y)：x比y跑得快（2） 其中F(x)：x是火车 G(y):y是 汽车 H(x,y)：x比y跑得快（3) 其中F(x)：x是火车 G(y):y是 汽车H(x,y)：x比y跑得快（4） 其中F(x)：x是飞机 G(y):y是 汽车 H(x,y)：x比y跑得慢14. 在自然推理系统F中，指出下面各证明序列中的错误：（1） 前提引入 EI规则（2） 前提引入 EI规则（3） 前提引入 EG规则（4） 前提引入 EG规则（5） 前提引入 UG规则解：（1）对不能使用EI规则，它不是前束范式，首先化成前束范式，因为量词辖域中，除了x还有自由出现的y所以不能用EI规则（2）对也应该先化成前束范式才能消去量词，其前束范式为，要消去量词，既要用UI规则，又要用EI规则（3）这里A(y)=F(y)G(y)满足要求（4）这里，使F(a)为真的a不一定使G(a)为真，同样的，使G(b)为真的b不一定使F(b)为真（5）这里，c为个体常项，不能对F(c)G(c)引入全称量词15. 在自然推理系统F中，构造下面推理的证明：（1） 前提： 结论：（2） 前提： 结论：（3） 前提： 结论：（4） 前提： 结论：（1）证明：1 前提引入 2 前提引入 3 1 2假言推理 4 1 EI 5 3 UI 6 4 附加 7 5 6假言推理 8 7EG （2）证明：1 前提引入 2 前提引入 3 1 EI 4 2 UI 5 3 4假言推理 6 5化简 7 3 6合取 8 7EG （3）证明：1 前提引入 2 1置换 3 2UI 4 前提引入 5 4UI 6 3 5析取三段论 7 6EG(4)证明：1 前提引入 2 1 UI 3 前提引入 4 3 UI 5 前提引入 6 5UI 7 4 6析取三段论 8 27析取三段论 9 UG16.找一个解释I，在I下，使得为真，而使得为假，从而说明。解：取个体域为自然数集合N，F(x):x为奇数，G(x):x 为偶数。显然在以上解释下为真而为假。17.给定推理如下： 前提： 结论：。 有些人给出的证明如下： 证明： 附加前提引入 UI 前提引入 UI 假言推理 前提引入 UI 拒取式 UG并且说，由附加前提证明法可知，推理正确，请指出以上证明的错误。解：根据16题可知两公式并不等价。18.给出上题（17）推理的正确证明（注意，不能使用附加前提证明法）。证明：1 前提引入 2 前提引入 3 1 UI 4 2UI 5 3置换 6 4 5假言三段论 7 6 UG19.在自然推理系统F中，构造下列推理的证明： 前提： 结论：证明：1 前提引入2 换名规则 3 化简 4 3 EI20.在自然推理系统F中，构造下列推理的证明（可以使用附加前提证明法）：（1）前提：结论：（2）前提： 结论：证明：（1）. 1 附加前提引入 2 1 UI 3 前提引入 4 3UI 5 2 3假言推理 6 （2）1 附加前提引入 2 置换原则 3 2EI 4 前提引入 5 UI 6 3 5析取三段论 7 EG21.在自然推理系统中，构造下面推理的证明：没有白色的乌鸦，北京鸭都是白色的。因此，北京鸭都不是乌鸦。设F(x):x是乌鸦，G(x)：x是北京鸭，H(x):x是白色的。前提 结论 证明：1 前提引入2 置换原则3 置换原则4 5 4UI6 前提引入7 5UI8 5 7假言三段论9 8UG22.在自然推理系统F中，构造下面推理的证明：(1) 偶数都能被2整除。6是偶数。所以6能被2整除。(2) 凡大学生都是勤奋的。王晓山不勤奋，所以王晓山不是大学生。（1）设F(x):x为偶数，G(x)：x能被2整除前提 结论 G(6)证明：1 前提引入 2 1UI 3 前提引入 4 2 3假言推理(2) 设F(x):x是大学生，G(x)：x是勤奋的，a 王晓山前提 ，结论 证明：1 前提引入 2 1UI 3 前提引入 4 2 3 据取式23.在自然推理系统F中，证明下面推理：（1） 每个有理数都是实数。有的有理数是整数。因此，有的实数是整数9（2） 有理数，无理数都是实数。虚数不是实数。因此，虚数既不是有理数也不是无理数。（1）设F(x):x是有理数，G(x)：x实数，H(x):x是整数 前提 ， 结论 (2) 设F(x):x是有理数，G(x)：x是无理数，H(x):x是实数，I(x):x是虚数前提 结论 证明：1 前提引入 2 1 UI 3 前提引入 4 3 UI 5 置换 6 2 5假言三段论 7 UG24.在自然推理系统F中，构造下面推理的证明： 每个喜欢不行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人类集合）设F(x):x喜欢步行，G(x)：x喜欢骑自行车，H(x):x喜欢乘汽车前提 ，结论 证明：1 前提引入 2 1 UI 3 前提引入 4 3 UI 5 2 4析取三段论 6 前提引入 7 6 UI 8 57拒取式 9 8UG25.在自然推理系统F中，构造下列推理的证明（个体域为人类集合）： 每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的，所以王大海在他的事业中将获得成功。设F(x):x是科学工作者，G(x)：x是刻苦钻研的，H(x):x是聪明的，I(x):x在事业中获得成功前提 ，a:王大海，F(a),H(a)结论 I(a)证明：1 前提引入 2 前提引入 3 2UI 4 1 3假言推论 5 前提引入 6 前提引入 7 6UI 8 4 5合取 9 7 8假言推论