离散数学习题五

习题五

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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4