离散数学习题解答(耿素云屈婉玲)北京大学出版社

去找 QQ头像 http://www.7zhao.net

a) 在解释I1中,个体域D1={a},证明公式A在I1下的真值为1。

b) 在解释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

在I2下,?xF(x)??xF(x)?(F(a1)?F(a2)....?F(an))?(F(a1)?F(a2).....?F(an))为可满足式,但不是永真式。设F(x):x为奇数,此时蕴含式前件为真,后件为假,故蕴含式真值为0。若将F(x)改为令F(x),x为整数,则蕴含式的前件后件均为真,则真值为1。问题的关键是n?2,n项的析取为真,只需要其中的一项为真,而不能保证所有的项为真。

5. 给定解释I如下: (a) 个体域D={3,4}; (b)

f(x)为f(3)?4,f(x)?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?y(F(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?yF(x,y)??x(F(x,3)?F(x,4))?(F(3,3)?F(3,4))?(F(4,3)?F(4,4))?0?0?0(3).

?x?y(F(x,y)?F(f(x),f(y)))??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)))?(0?0)?(1?1)?(1?1)?(0?0)?1?1?1?1?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都是约束变元,因而不能将量词的辖域缩小。

文章来源:http://www.7zhao.net

去找 QQ头像 http://www.7zhao.net

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)),(1)

其中F(x):x小于负数,G(x):x是正数。

(2).

??x(F(x)?G(x)??x(F(x)??G(x)),

其中F(x):两个角相等,G(x):两个角是对顶角

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)

文章来源:http://www.7zhao.net

去找 QQ头像 http://www.7zhao.net

(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,y)?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)F(x):x是汽车,G(y):y是火车,H(x,y):x比y跑得快

?x?y(F(x)?G(y)?H(x, y)) ))?x?y(F(x)?(G(y)?H(x,y(2) )F(x):x是火车,G(y):y是汽车,H(x,y):x比y跑得快

(3) F(x):x是火车,G(y):y是汽车,H(x,y):x比y跑得快

?x?y(F(x)?G(y)??H(x, y))?x?y(F(x)?G(y)??H(x,、y) )(4) F(x):x是飞机,G(y):y是汽车,H(x,y):x比y慢

14. 在自然推理系统F中,指出下面各证明序列中的错误:

1F(x)??xG(x) 前提引入 (1)○

2F(c)?G(c) ○1EI规则 ○

1?xF(x)??yG(y) 前提引入 (2)○

2F(a)?F(b) ○1EI规则 ○

1F(y)?G(y) 前提引入 (3)○

文章来源:http://www.7zhao.net

去找 QQ头像 http://www.7zhao.net

2?x(F(x)?G(x)) ○1EG规则 ○

1F(a)?G(b) 前提引入 (4)○

2?x(F(x)?G(x)) ○1EG规则 ○

1F(c)?G(c) 前提引入 (5)○

2?x(F(x)?G(x)) ○1UG规则 ○

答:(1)对F(x)??xG(x)不能使用EI规则。它不是前束范式,化为前束范式得

F(x)??xG(x)??x(F(y)?G(x)),因为量词辖域(F(y)?G(x))中,除了

x外还有自由出现的y,所以不能使用EI规则。 (2)对

F(c)?G(c)也应先化成前束范式才能消去量词,其前束范式为

?x?y(F(x)?G(y)),要消去量词,既要使用UI规则又要使用EI规则。

(3)在自然推理系统F中,EG

A(c)规则为

??xA(x),其中c为特定的个体常项,这里

A(y)?F(y)?G(y)不满足要求。

(4)这里使F(a)为真的a不一定使G(a)为真,同样地使G(b)为真的b不一定使F(b)为真,如F(x):x为奇数,G(x):x为偶数,显然F(3)?G(4)为真,但不存在使F(x)?G(x)为真的个体。

(5)这里c为个体常项,不能对?x(H(x)??F(x)

15.在自然推理系统F中,构造下面推理的证明:

(1)前提:?xF(x)??y((F(y)?G(y))?R(y)),?xF(x) 结论:?xR(x)

(2)前提:?x(F(x)?(G(a)?R(x))),?xF(x) 结论:?x(F(x)?R(x))

(3)前提:?x(F(x)?G(x)),??xG(x) 结论:?xF(x)

??引入全称量词。

文章来源:http://www.7zhao.net

联系客服:779662525#qq.com(#替换为@)