离散数学习题五_离散数学第五版习题

离散数学习题五由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学第五版习题”。

习题五

1.设个体域D={a,b,c}，在D中消去公式x(F(x)yG(y))的量词。甲乙用了不同的演算过程：

甲的演算过程如下： x(F(x)yG(y))x(F(x)(G(a)G(b)G(c)))(F(a)(G(a)G(b)G(c)))

(F(b)(G(a)G(b)G(c)))(F(c)(G(a)G(b)G(c)))(F(a)F(b)F(c))(G(a)G(b)G(c))乙的演算过程如下：

x(F(x)yG(y))xF(x)yG(y)(F(a)F(b)F(c))(G(a)G(b)G(c))

显然，乙的演算过程简单，试指出乙在演算过程中的关键步骤。

解：乙在演算中的关键步骤是，在演算开始就利用量词辖域收缩与扩张等值式，将量词的辖域缩小，因而演算简单。

2.设个体域D={a,b,c}，消去下列各式的量词：

(1)xy(F(x)G(y))(2)xy(F(x)G(y))(3)xF(x)yG(y)(4)（xF(x,y)yG(y))

解：

（1）(F(a)F(b)F(c))(G(a)G(b)G(c))（2）(F(a)F(b)F(c))(G(a)G(b)G(c))（3）(F(a)F(b)F(c))(G(a)G(b)G(c))（4）(F(a,y)F(b,y)F(c,y))(G(a)G(b)G(c))在（1）（2）（4）中均将量词的辖域缩小，所以演算结果都比较简单

3.设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。（1）x(F(x)G(x))（2）x(F(x)G(x))解：

解释I1为：个体为实数集合R，F(x)：x为自然数，G(x)：x为整数。在I1下，（1）为自然数都是整数，（2）为存在整数为自然数。他们都是真命题

解释I2为：个体域仍为实数集R，F(x)：x是无理数，G(x)：x能表示成分数，在I2下，（1）为无理数都能表示成分数，（2）为存在能表示成分数的无理数，他们都是假命题

4.给定公式AxF(x)xF(x)

（1）在解释I1中，个体域D1={a}，证明公式A在I1下的真值为1.（2）在解释I2中，个体域D2={a1,a2,,an}，n2,A在I2下的真值还一定是1吗？为什么？ 解：

（1）在I1下，xF(x)xF(x)F(a)F(a)F(a)F(a)1（2）在I2下

xF(x)xF(x)(F(a1)F(a2)F(an))(F(a1)F(a2)F(an))

为可满足式，设F(x)：x为奇数，aii,i1,2,n,n2，此时，蕴涵式前件为真，后件为假，故蕴含式为假，若令F(x)；x为整数，则蕴含式前后件均为真，所以（2）中公式在I2下为可满足式

5.给定解释I如下：（a）个体域D={3,4}；（b）f(x)为f(3)4,f(4)3;

（c）F(x,y)为F(3,3)F(4,4)0,F(3,4)F(4,3)1.试求下列公式在I下的真值。

(1)xyF(x,y)(2)xyF(x,y)(3)xyF(x,y)F(f(x),f(y)))

解：

（1）

xyF(x,y)x(F(x,3)F(x,4))(F(3,3)F(3,4))(F(4,3)F(4,4))111（2）

x(F(x,3)F(x,4))(F(3,3)F(3,4))(F(4,3)F(4,4)0（3）

x((F(x,3)F(f(x),f(3)))(F(x,4)F(f(x),f(4))))(((F(3,3)F(f(3),f(3)))(F(3,4)F(f(3),f(4))))(((F(4,3)F(f(4),f(3)))(F(4,4)F(f(4),f(4))))1

6.甲使用量词辖域收缩与扩张等值式进行如下演算

x(F(x)G(x,y))xF(x)G(x,y)

乙说甲错了，乙说的对吗？为什么？

解：乙说的对，甲错了，全称量词的指导变元x，辖域为(F(x)G(x,y))，其中F(x)与G(x,y)都是x的约束变元，因而不能讲量词的辖域变小

7.请指出下面等值运算的两处错误

xy(F(x)(G(y)H(x,y))xy(F(x)(G(y)H(x,y))xy((F(x)G(y))H(x,y))

解：

演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定连接词，演算的第二步，在原错的基础上又用错了等值式

(F(x)G(y)H(x,y))和(F(x)G(y)H(x,y))不等值

8.在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式（1）没有小于负数的正数

（2）相等的两个角未必都是对顶角 解：

（1）x(F(x)G(x))x(G(x)F(x))

其中F(x)：x小于负数，G(x)：x是正数

（2）xy(F(x)F(y)H(x,y)L(x,y)xy(F(x)F(y)H(x,y)L(x,y))其中F(x)：x是角，H(x,y)：x=y，L(x,y)：x和y是对顶角

9.设个体域D为实数集合，命题“有的实数既是有理数又是无理数”，这显然是个假命题。可是某人却说这是真命题，其理由如下

设F(x)：x是有理数，G(x）：x是无理数。xF(x),xG(x)都是真命题，于是，xF(x)xG(x)x(F(x)G(x))由于xF(x)xG(x)是真命题，故x(F(x)G(x))也是真命题，即有的实数是有理数，也是无理数这个人的结论对吗？为什么？ 解：存在量词对无分配律

10.在求前束范式时有人说x(F(x)G(x,y))已是前束范式，理由是量词已在公式的前面，他说的对吗？为什么？

解：在前束范式中，否定联结词不能在量词前面出现 11.有人说无法求公式

x(F(x)G(x))xG(x,y)的前束范式，因为公式中的两个量词的指导变元相同。他的理由对吗？为什么？ 换名规则可以使两个指导变元不相同 12.求下列各式的前束范式：(1)xF(x)yG(x,y)(2)x(F(x,y)yG(x,y,z))(3)xF(x,y)xG(x,y)

(4)x1(F(x1)G(x1,x2))(x2H(x2)x3L(x2,x3))(5)x1F(x1,x2)(F(x1)x2G(x1,x2))解：

（1）xy(F(x)G(z,y))（2）xt(F(x,t)G(x,t,z))

（3）x1x2x3x4((F(x1,y)G(x2,y))(G(x3,y)F(x4,y)))（4）y1y2y3((F(y1)G(y1,x2))(H(y2)L(x2,y3)))（5）y1y2(F(y1,x2)(F(x1)G(x1,y2)))

13.将下列命题符号化，要求符号化的公式权威前束范式：（1）有点火车比有的汽车跑的快（2）有的火车比所有的汽车跑的快

（3）说有的火车比所有汽车跑得快是不对的（4）说有的飞机比有的汽车慢也是不对的 解：

（1）xy(F(x)G(y)H(x,y))其中F(x)：x是汽车 G(y):y是 火车 H(x,y)：x比y跑得快（2）xy(F(x)(G(y)H(x,y)))其中F(x)：x是火车 G(y):y是 汽车 H(x,y)：x比y跑得快

（3)xy(F(x)G(y)H(x,y))其中F(x)：x是火车 G(y):y是 汽车H(x,y)：x比y跑得快

（4）xy(F(x)G(y)H(x,y))其中F(x)：x是飞机 G(y):y是 汽车 H(x,y)：x比y跑得慢

14.在自然推理系统F中，指出下面各证明序列中的错误：（1）①F(x)xG(x)前提引入

②F(c)G(c)①EI规则（2）①xF(x)yG(y)前提引入

②F(a)F(b)①EI规则（3）①F(y)G(y)前提引入

②x(F(x)G(x))①EG规则（4）①F(a)F(b)前提引入

②x(F(x)G(x))①EG规则（5）①F(c)G(c)前提引入

②x(F(x)G(x))①UG规则

解：（1）对F(x)xG(x)不能使用EI规则，它不是前束范式，首先化成前束范式F(x)xG(x)x(F(y)G(x))，因为量词辖域(F(y)G(x)中，除了x还有自由出现的y所以不能用EI规则

（2）对xF(x)yG(y)也应该先化成前束范式才能消去量词，其前束范式为xy(F(x)G(y))，要消去量词，既要用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）前提：xF(x)y((F(y)G(y))R(y)),xF(x)

结论：xR(x)

（2）前提：x(F(x)(G(a)R(x))),xF(x)

结论：x(F(x)R(x))（3）前提：x(F(x)G(x)),xG(x)

结论：xF(x)

（4）前提：x(F(x)G(x)),x(G(x)R(x)),xR(x)

结论：xF(x)

（1）证明：1 xF(x)

前提引入xF(x)y((F(y)G(y))R(y))

前提引入y((F(y)G(y))R(y)2假言推理F(c)EI(F(c)G(c))R(c)UIF(c)G(c)附加R(c)6假言推理xR(x)

7EG

（2）证明：1 xF(x)

前提引入

x(H(x)),xF(x)x(F(a)G(a))),G(a)I(y)H(a)x(F(x)(G(a)R(x)))

x(G(a)H(a)I(a))前提引入F(c)EIF(c)(G(a)R(c))UIG(a)R(c)4假言推理R(c)

5化简 F(c)R(c)6合取x(F(x)R(x))

7EG

（3）证明：1 xF(x)

前提引入xF(x)

1置换F(c)

2UIx(F(x)G(x))

前提引入F(c)G(c)

4UI

6F(c)5析取三段论xF(x)

6EG(4)证明：1 x(F(x)G(x))

前提引入F(y)G(y)UIx(G(x)R(X))

前提引入G(y)R(y)UIxR(x)

前提引入R(y)

5UIG(y)6析取三段论

8F(y)

27析取三段论xF(x)

UG 16.找一个解释I，在I下，使得xF(x)xG(x)为真，而使得x(F(x)G(x))为假，从而说明xF(x)xG(x)x(F(x)G(x))。解：取个体域为自然数集合N，F(x):x为奇数，G(x):x 为偶数。显然在以上解释下xF(x)xG(x)为真而x(F(x)G(x))为假。

17.给定推理如下：

前提：x(F(x)G(x)),x(H(x)G(x))

结论：x(H(x)F(x))。

有些人给出的证明如下：

证明：

①xH(x)附加前提引入

②H(y)

③x(H(x)G(x))

④H(y)G(y)

⑤G(y)

⑥x(F(x)G(x))

⑦F(y)G(y)

⑧F(y)

⑨xF(x)

解：根据16题可知两公式并不等价。

①UI 前提引入 ③UI ②⑤假言推理 前提引入 ⑥UI ⑤⑦拒取式 ⑧UG 并且说，由附加前提证明法可知，推理正确，请指出以上证明的错误。18.给出上题（17）推理的正确证明（注意，不能使用附加前提证明法）。

证明：1 x(F(x)G(x))

前提引入x(H(x)G(x))

前提引入F(y)G(y)UIH(y)G(y)

2UIG(y)F(y)

3置换H(y)F(y)5假言三段论x(H(x)F(x))UG

19.在自然推理系统F中，构造下列推理的证明：

前提：xF(x)xG(x)

结论：x(F(x)G(x))

证明：1xF(x)xG(x)

前提引入yF(y)xG(x)

换名规则yx(F(x)G(x))化简x(F(x)G(x))EI

20.在自然推理系统F中，构造下列推理的证明（可以使用附加前提证明法）：（1）前提：x(F(x)G(x))

结论：xF(x)xG(x)（2）前提：x(F(x)G(x))

结论：xF(x)xG(x)

证明：（1）.1xF(x)

附加前提引入F(y)UIx(F(x)G(x))

前提引入F(y)G(y)

3UIG(y)3假言推理xG(x)

（2）1 xF(x)

附加前提引入xF(x)

置换原则F(c)

2EIx(F(x)G(x))

前提引入F(c)G(c)

UIG(c)5析取三段论xG(x)

EG 21.在自然推理系统中，构造下面推理的证明：

没有白色的乌鸦，北京鸭都是白色的。因此，北京鸭都不是乌鸦。

设F(x):x是乌鸦，G(x)：x是北京鸭，H(x):x是白色的。前提 x(F(x)H(x)),x(G(x)H(x))结论 x(G(x)F(x))

证明：1 x(F(x)H(x))

前提引入 2 x(F(x)H(x))

置换原则 3 x(F(x)H(x))

置换原则 4 x(H(x)F(x))H(y)F(y)

4UI 6 x(G(x)H(x))

前提引入 7 G(y)H(y)

5UI 8 G(y)F(y)7假言三段论 9 x(G(x)F(x))

8UG 22.在自然推理系统F中，构造下面推理的证明：

(1)偶数都能被2整除。6是偶数。所以6能被2整除。

(2)凡大学生都是勤奋的。王晓山不勤奋，所以王晓山不是大学生。

（1）设F(x):x为偶数，G(x)：x能被2整除 前提 x(F(x)G(x)),F(6)结论 G(6)证明：1 x(F(x)G(x))

前提引入F(6)G(6)

1UIF(6)

前提引入G(6)3假言推理

(2)设F(x):x是大学生，G(x)：x是勤奋的，a 王晓山 前提 x(F(x)G(x)),G(a)，结论 F(a)

证明：1 x(F(x)G(x))

前提引入F(a)G(a)

1UIG(a)

前提引入F(a)3 据取式

23.在自然推理系统F中，证明下面推理：

（1）每个有理数都是实数。有的有理数是整数。因此，有的实数是整数9（2）有理数，无理数都是实数。虚数不是实数。因此，虚数既不是有理数也不是无理数。

（1）设F(x):x是有理数，G(x)：x实数，H(x):x是整数

前提 x(F(x)G(x))，x(F(x)H(x))

结论 x(G(x)H(x))

(2)设F(x):x是有理数，G(x)：x是无理数，H(x):x是实数，I(x):x是虚数 前提 x((F(x)G(x))H(x)),x(I(x)H(x))结论 x(I(x)(F(x)G(x)))

证明：1 x(I(x)H(x))

前提引入I(y)H(y)UIx((F(x)G(x))H(x)),前提引入(F(y)G(y))H(y)UIH(y)(F(y)G(y))

置换I(y)(F(y)G(y))5假言三段论x(I(x)(F(x)G(x))

UG 24.在自然推理系统F中，构造下面推理的证明：

每个喜欢不行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人类集合）

设F(x):x喜欢步行，G(x)：x喜欢骑自行车，H(x):x喜欢乘汽车 前提 x(F(x)G(x)，x(G(x)H(x)),xH(x)结论 xF(x)

证明：1 xH(x)

前提引入H(c)UIx(G(x)H(x))

前提引入G(c)H(c)UIG(c)4析取三段论x(F(x)G(x))

前提引入F(c)G(c)UIF(c)

57拒取式xF(x)

8UG 25.在自然推理系统F中，构造下列推理的证明（个体域为人类集合）：

每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的，所以王大海在他的事业中将获得成功。

设F(x):x是科学工作者，G(x)：x是刻苦钻研的，H(x):x是聪明的，I(x):x在事业中获得成功

前提 x(F(x)G(x))，x(G(x)H(x)I(x))，a:王大海，F(a),H(a)结论 I(a)证明：1 F(a)

前提引入x(F(x)G(x))

前提引入F(a)G(a)

2UIG(a)3假言推论H(a)

前提引入x(G(x)H(x)I(x))

前提引入G(a)H(a)I(a)

6UIG(a)H(a)5合取I(a)8假言推论