发布时间 : 星期二 文章离散数学习题五更新完毕开始阅读
（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)引入全称量词
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)
（4）前提：?x(F(x)?G(x)),?x(?G(x)??R(x)),?xR(x)
结论：?xF(x)
（1）证明：1 ?xF(x) 前提引入
2 ?xF(x)??y((F(y)?G(y))?R(y)) 前提引入 3 ?y((F(y)?G(y))?R(y) 1 2假言推理 4 F(c) 1 EI
5 (F(c)?G(c))?R(c) 3 UI 6 F(c)?G(c) 4 附加 7 R(c) 5 6假言推理 8 ?xR(x) 7EG （2）证明：1 ?xF(x) 前提引入
?x(?H(x)),?x?F(x) 2 ?x(F(a)?G(a))?),G(a)I(y)H(a)????x(F(x)?(G(a)?R(x)))
?x(G(a)?H(a)?I(a))前提引入
3 F(c) 1 EI 4 F(c)?(G(a)?R(c)) 2 UI
5 G(a)?R(c) 3 4假言推理 6 R(c) 5化简 7 F(c)?R(c) 3 6合取 8 ?x(F(x)?R(x)) 7EG （3）证明：1 ??xF(x) 前提引入 2 ?x?F(x) 1置换 3 ?F(c) 2UI 4 ?x(F(x)?G(x)) 前提引入 5 F(c)?G(c) 4UI
6F(c) 3 5析取三段论 7 ?xF(x) 6EG
(4)证明：1 ?x(F(x)?G(x)) 前提引入 2 F(y)?G(y) 1 UI 3 ?x(?G(x)??R(X)) 前提引入 4 ?G(y)??R(y) 3 UI 5 ?xR(x) 前提引入 6 R(y) 5UI
7 ?G(y) 4 6析取三段论 8F(y) 27析取三段论 9 ?xF(x) UG
16.找一个解释I，在I下，使得?xF(x)??xG(x)为真，而使得?x(F(x)??G(x))为假，从而说明?xF(x)??xG(x)??x(F(x)??G(x))。
解：取个体域为自然数集合N，F(x):x为奇数，G(x):x 为偶数。显然在以上解释下
?xF(x)??xG(x)为真而?x(F(x)?G(x))为假。
17.给定推理如下：
前提：?x(F(x)??G(x)),?x(H(x)?G(x)) 结论：?x(H(x)??F(x))。 有些人给出的证明如下： 证明：
①?xH(x) 附加前提引入 ②H(y)
③?x(H(x)?G(x)) ④H(y)?G(y) ⑤G(y)
⑥?x(F(x)??G(x)) ⑦F(y)??G(y) ⑧?F(y) ⑨?x?F(x)
解：根据16题可知两公式并不等价。
①UI 前提引入 ③UI ②⑤假言推理 前提引入 ⑥UI ⑤⑦拒取式 ⑧UG
并且说，由附加前提证明法可知，推理正确，请指出以上证明的错误。 18.给出上题（17）推理的正确证明（注意，不能使用附加前提证明法）。
证明：1 ?x(F(x)??G(x)) 前提引入 2 ?x(H(x)?G(x)) 前提引入 3 F(y)??G(y) 1 UI 4 H(y)?G(y) 2UI 5 G(y)??F(y) 3置换 6 H(y)??F(y) 4 5假言三段论 7 ?x(H(x)??F(x)) 6 UG