.
习题五
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,L,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))
解：
演算的第一步，应用量词辖域收缩与扩算值式时丢掉了否定连接词?，演算的第二步，在
.