离散数学 杨圣洪等著第二章习题三解答.pdf

《离散数学 杨圣洪等著第二章习题三解答.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章习题三一、证明如下推理式1、∃xF(x)→∀y((F(y)∨G(y))→R(y))，∃xF(x)⇒∃xR(x)(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)存在量词指定(5)F(c)∨G(c)(4)及析取的定义(6)(F(c)∨G(c))→R(c)(3)全称量词指定(7)R(c)(5)(6)假言推理(8)∃xR(x)(7)存在推广2、∀x(F(x)→(G(a)∧R(x)))，∃xF(x)⇒∃x(F(x)∧R(x))(1)∃xF(x)前提条件(2)

2、F(c)(1)存在量词指定(3)∀x(F(x)→G(a)∧R(x)))前提条件(4)F(c)→G(a)∧R(c))(3)全称指定，尤其x=c应成立(5)G(a)∧R(c)(2)(4)假言推理或分离原则(6)R(c)(5)与合取的定义(7)F(c)∧R(c)(2)(6)与合取的定义(8)∃x(F(x)∧R(x)(7)存在推广3、∀x(F(x)∨G(x))，¬∃xG(x)⇒∃xF(x)(1)¬∃xG(x)前提条件(2)∀x¬G(x)(1)的等值(3)¬G(x0)(2)全称指定，x0为任意变元(4)∀x(F(x)∨G(x))前提条件(5)(F(x0)∨G(x0))(4)全称指定为x0(6)

3、¬G(x0)→F(x0)(5)等值变换(7)F(x0)(3)(6)分离原则或假言推理(8)∃xF(x)(7)存在推广4、∀x(F(x)∨G(x))，∀x(¬R(x)∨¬G(x))，∀xR(x)⇒∃xF(x)(1)∀x(F(x)∨G(x))前提条件(2)(F(x0)∨G(x0))(1)全称指定，x0为任意变元(3)∀x(¬R(x)∨¬G(x))前提条件(4)(¬R(x0)∨¬G(x0))(3)全称指定，变元x指定为(2)中确定的变元x0，即是同一个x0(5)∀xR(x)前提条件(6)R(x0)(5)全称指定，与(2)中的x0为同一个(7)R(x0)→¬G(x0)(4)的等值变换(8)¬

4、G(x0)(6)(7)分离原则或假言推理(9)¬G(x0)→F(x0)(2)的等值变换(10)F(x0)(8)(9)分离原则或假言推理(11)∃xF(x)(10)存在推广。其实也可推出∀xF(x)，因为其中的x0是任意的5、∀x(F(x)→¬G(x))，∀x(H(x)→G(x))⇒∀x(H(x)→¬F(x))(1)∀x(F(x)→¬G(x))前提条件(2)F(x0)→¬G(x0)(1)全称指定x为x0(3)∀x(H(x)→G(x))前提条件(4)H(x0)→G(x0)(3)全称指定，尤其将x指定(2)中的x0(5)G(x0)→¬F(x0)(2)等值演算(6)H(x0)→¬F(x0)(

5、4)(5)的传递律(7)∀x(H(x)→¬F(x))(6)的全称扩充，因为其中的x0是任意的6、∃xF(x)→∀xG(x)⇒∀x(F(x)→G(x))(1)∃xF(x)→∀xG(x)前提条件(2)¬∃xF(x)∨∀xG(x)(1)等值演算(3)∀x¬F(x)∨∀xG(x)(2)等值演算(4)∀x(¬F(x)∨G(x))(3)推理定律(5)∀x(F(x)→G(x))(4)等值演算7、∀x(F(x)→G(x))⇒∀xF(x)→∀xG(x)(1)∀xF(x)附加条件(2)F(x0)(1)全称指定，x0为任意值(3)∀x(F(x)→G(x))前提条件(4)(F(x0)→G(x0))(3)全称

6、指定，尤其指定为(2)中的x0(5)G(x0)(2)(4)假言推理或分离原则(6)∀xG(x)(5)全称推广，x0为任意变元8、∀x(F(x)∨G(x))⇒¬∀xF(x)→∃xG(x)(1)¬∀xF(x)附加前提条件(2)∃x¬F(x)(1)等值演算(3)¬F(c)(2)存在指定，当x=c时成立(4)∀x(F(x)∨G(x))前提条件(5)F(c)∨G(c)(4)全称指定，当x=c时肯定成立。(6)¬F(c)→G(c)(5)等值演算(7)G(c)(3)(6)假言推理即分离原则(8)∃xG(x)(7)存在推广二、应用题在自然推理系统中，构造下面的推理，要求先将如下语句用谓词公式表示出来

7、，再证明结论的正确性。1、没有白色的乌鸦，北京鸭是白色的，因此北京鸭不是乌鸦。解：W(x)表示x是白色，A(x)表示x是乌鸦，B(x)表示x是北京鸭前提：¬∃x(W(x)∧A(x))，∀x(B(x)→W(x))结论：∀x(B(x)→¬A(x))证明：(1)¬∃x(W(x)∧A(x))前提条件(2)∀x¬(W(x)∧A(x))(1)等值演算(3)¬(W(x0)∧A(x0))(2)全称指定(4)¬W(x0)∨¬A(x0)(3)等值演算(5)W(x0)→¬A(x