发布时间 : 星期五 文章离散数学习题五更新完毕开始阅读
习题五
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跑得快