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

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

(4)前提：?x(F(x)?G(x)),?x(?G(x)??R(x)),?xR(x) 结论：?xF(x)

1?xF(x) 前提引入 证明：(1)○

2?xF(x)??y((F(y)?G(y))?R(y)) 前提引入 ○

3?y((F(y)?G(y))?R(y)) ○1○2假言推理 ○

○

4F(c) ○

5(F(c)?G(c))?R(c) ○

6F(c)?G(c) ○

7R(c) ○

8?xR(x) (2)○

1?xF(x) ○

2?x(F(x)?(G(a)?R(x))) ○

3F(c) ○

4F(c)?(G(a)?R(c)) ○

5G(a)?R(c) ○

6R(c) ○

7F(c)?R(c) ○

8?x(F(x)?R(x)) (3)○

1??xF(x) ○

2?x?F(x) ○

3?F(c) ○

4?x(F(x)?G(x)) ○

5F(c)?G(c) ○

6F(c) ○

7?xF(x) 文章来源：http://www.7zhao.net

○1EI ○3UI ○4附加 ○5○6假言推理 ○7EG 前提引入 前提引入 ○1EI ○2UI ○3○4假言推理 ○5化简 ○3○6合取 ○7EG 前提引入 ○1置换 ○2UI 前提引入 ○4UI ○3○5析取三段论 ○6EG 去找 QQ头像 http://www.7zhao.net

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

2F(y)?G(y) ○1UI ○

3?x(?G(x)??R(x)) 前提引入 ○

4?G(y)??R(y) ○3UI ○

5?xR(x) 前提引入 ○

6R(y) ○5UI ○

7?G(y) ○4○6析取三段论 ○

8F(y) ○2○7析取三段论 ○

9?xF(x) ○8UG ○

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))。有些人证明如下：

1?xH(x) 附加前提引入 ○

2H(y) ○1UI ○

3?x(H(x)?G(x)) 前提引入 ○

4H(y)?G(y) ○3UI ○

5G(y) ○2○5假言推理 ○

6?x(F(x)??G(x)) 前提引入 ○

7F(y)??G(y) ○6UI ○

8?F(y) ○5○7拒取式 ○

9?x?F(x) ○8UG ○

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

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

并且说由附加前提证明法可知，推理正确，请指出以上证明的错误。 答：由第16题可知，本题不能用附加前提证明法。

18.给出上题的正确推理证明。

1?x(F(x)??G(x)) 前提引入 证明：○

2?x(H(x)?G(x)) 前提引入 ○

3F(y)??G(y) ○1UI ○

○

4H(y)?G(y) ○

5G(y)??F(y) ○

6H(y)??F(y) ○

7?x(H(x)??F(x)?? 19在自然推理系统F中，构造下面的推理证明; 前提：?xF(x)??xG(x) 结论：?x(F(x)?G(x)) 证明：1 ?xF(x)??xG(x)

2 F(c)??yG(y)

3 ?x(F(x)?G(x))

20 在自然推理系统F中，构造下面的推理证明; (1)前提：?x(F(x)?G(x)) 结论：?xF(x)??xG(x) 证明：1 ?x(F(x)?G(x)) 2 F(x)?G(x) 3 ?xF(x) 附加前提

4 ?xG(x)

（2）前提：?x(F(x)?G(x))

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

○2UI ○3置换 ○4○5假言三段论 ○

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

结论：??xF(x)??xG(x) 证明：1 ?x(F(x)?G(x)) 2 F(x)?G(x) 3 ??xF(x) 附加前提 4 ?x?F(x)

5 ?F(c) 6 G(c) 7 ?xG(x)

21在自然推理系统F中，构造下面推理的证明：

没有白色的乌鸦，北京鸭都是白色的，因此北京鸭不是乌鸦。 答：设F(x)：x是白色的

G(x)：x是乌鸦 H(x)：x是北京鸭

前提：?x(G(x)??F(x)) ?x(H(x)?F(x ))结论：?x(H(x)??G(x)) 证明：1 ?x(G(x)??F(x)) 2 G(x)??F(x)

3 F(x)??G(x) 4 ?x(H(x)?F(x)) 5 H(x)?F(x) 6 H(x)??G(x) 7 ?x(H(x)??G(x))

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