离散数学习题五

《离散数学习题五》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题五1.设个体域D={a,b,c}，在D中消去公式的量词。甲乙用了不同的演算过程：甲的演算过程如下：乙的演算过程如下：显然，乙的演算过程简单，试指出乙在演算过程中的关键步骤。解：乙在演算中的关键步骤是，在演算开始就利用量词辖域收缩与扩张等值式，将量词的辖域缩小，因而演算简单。2.设个体域D={a,b,c}，消去下列各式的量词：解：（1）（2）（3）（4）在（1）（2）（4）中均将量词的辖域缩小，所以演算结果都比较简单3.设个体域D={1,2}，请给出两种不同的解释和，使得下面公式在下都是真命题，而在下

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）在I

3、2下为可满足式，设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.请指出下面等值运算的两处错误解：

4、演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定连接词，演算的第二步，在原错的基础上又用错了等值式和不等值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）：

5、x是无理数。都是真命题，于是，由于是真命题，故也是真命题，即有的实数是有理数，也是无理数这个人的结论对吗？为什么？解：存在量词对无分配律9.在求前束范式时有人说已是前束范式，理由是量词已在公式的前面，他说的对吗？为什么？解：在前束范式中，否定联结词不能在量词前面出现11.有人说无法求公式的前束范式，因为公式中的两个量词的指导变元相同。他的理由对吗？为什么？换名规则可以使两个指导变元不相同12.求下列各式的前束范式：(1)(2)(3)(4)(5)解：（1）（2）（3）（4）（5）13.将下列命题符号化，要

6、求符号化的公式权威前束范式：（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中，指出下面各证明序列中的

7、错误：（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)为真（

8、5）这里，c为个体常项，不能对F(c)G(c)引入全称量词15.在自然推理系统F中，构造下面推理的证明：（1）前提：结论：（2）前提：结论：（3）前提：结论：（4）前提：结论：（1）证明：1前提引入2前提引入312假言推理41EI53UI64附加756假言推理87EG（2）证明：1前提引入2前提引入31EI42UI534假言推理65化简736合取87EG（3）证明：1前提引入21置换32UI4前提引入54UI635析取三段论76EG(4)证