发布时间 : 星期六 文章离散数学习题解答（耿素云屈婉玲）北京大学出版社更新完毕开始阅读
去找 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