习题五

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)引入全称量词