内容发布更新时间 : 2024/12/25 23:02:36星期一 下面是文章的全部内容请认真阅读。
.
习题五
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))
解:
演算的第一步,应用量词辖域收缩与扩算值式时丢掉了否定连接词?,演算的第二步,在
.