离散数学课后习题合集(7)

第四章 谓演算的推理理论

4.1 用永真的公理系统证明下列定理

（1）?x(??P(x))?(???xP(x)) 证明

先证?x(??P(x))?(???xP(x))

（1）?x(??P(x))?(??P(x)) 公理20 （2）（1） ?x(??P(x))?(???xP(x)) 全2规则再证(???xP(x))??x(??P(x))

（3）?xP(x)?P(x) 公理20 （4）(?xP(x)?P(x))?((???xP(x))?(??P(x))) 定理 （5）（4）（3） (???xP(x))?(??P(x)) 分（6）(???xP(x))??x(??P(x)) 全规则（5） （7）(?x(??P(x))?(???xP(x)))?(((???xP(x))??x(??P(x))) ?(?x(??P(x))?(???xP(x))) ) 公理7 （8）((???xP(x))??x(??P(x)))?(?x(??P(x))?(???xP(x))) 分（7）（2） （9）（8）（6） ?x(??P(x))?(???xP(x)) 分（2）?x(P(x)??)?(?xP(x)??) 证明

先证?x(P(x)??)?(?xP(x)??)

（1）?x(P(x)??)?(P(x)??)) 公理20 （2）?x(P(x)??)?(?xP(x)??)) 存1规则（1） 再证(?xP(x)??)??x(P(x)??)

31

（3）P(x)??xP(x) 公理21 （4）(P(x)??xP(x))?(?x(P(x)??)?(P(x)??)) 公理3 （5）?x(P(x)??)?(P(x)??) 分（4）（3） （6）?x(P(x)??)??x(P(x)??) 全（5） （7）(?x(P(x)??)?(?xP(x)??))?((?x(P(x)??)??x(P(x)??)) ?(?x(P(x)??)?(?xP(x)??)) ) 公理7 （8）(?x(P(x)??)??x(P(x)??))?(?x(P(x)??)?(?xP(x)??)) 分（7）（（2） （9）（8）（6） ?x(P(x)??)?(?xP(x)??) 分4.2 已知公理

(A)?(P?(Q?P)) (B)?(P?P)

及分离规则和全称规则，全称规则为：

?(?1?(?2??(x)))├?(?1?(?2??x?(x))) 试证明：全0规则??(x)├??x?(x)。

证明 （1）??(x)

（2）?(?(x)?((???)??(x))) 公理(A) （3）?((???)??(x)) 分（2）（1） （4）?(((???)??(x))?((???)?((???)??(x)))) 公理(A) （5）?((???)?((???)??(x))) 分（4）（3）

?((???)?((???)??x?(x))) 全（6）（5）

（7）?(???) 公理(B)

?((???)??x?(x)) 分（8）（6）（7）

32

（9）??x?(x) 分（8）（7） 4.3 指出下列推理过程的错误所在

（1）①?x?y(x?y) 假设

②?y(z?y) 全称量词消去 ③z?b 额外假设引入 ④?z(z?b) 全0规则 ⑤b?b 全称量词消去 ⑥?x(x?x) 全0规则 解

第④步有错，因为额外假设中的自由变元不能实施全0称规则。 （2）?xP(x)??xP(x)的证明过程如下：

①?xP(x) 假设 ②P(e) 额外假设 ③?xP(x) 全0规则

解

第③步有错，因为额外假设中的自由变元不能实施全0称规则。

（3）①?x(P(x)?Q(x)) 假设

②?xP(x) 假设 ③P(c)?Q(c) 全称量词消去 ④P(c) 额外假设引入 ⑤Q(c) 分③④ ⑥?xQ(x) 存在量词引入 解

第④步P(c)中的c为使用过的变元，额外假设要求引入的变元为未使用过的变元。 4.4 用假设推理证明下列公式

（1）?x(P(x)?Q(x))?((?xQ(x)??xR(x))?(?xP(x)??xR(x)))

证明

33

（1）?x(P(x)?Q(x)) 假设 （2）?xQ(x)??xR(x) 假设 （3）?xP(x) 假设 （4）（1） P(x)?Q(x) 全称量词消去规则（5）（3） P(x) 全称量词消去规则（6）（4）（5） Q(x) 分（7）（6） ?xQ(x) 全0规则（8）?xR(x) 分（2）（7） 由假设推理的定义过程知

?x(P(x)?Q(x))，?xQ(x)??xR(x)，?xP(x)├?xR(x) 由推理定理知

?x(P(x)?Q(x))?((?xQ(x)??xR(x))?(?xP(x)??xR(x))) （2）?xP(x)??x((P(x)?Q(x))?R(x))，?xP(x)├?x?y(R(x)?R(y))

证明

?xP(x)??x((P(x)?Q(x))?R(x)) 假设 （1）

（2）?xP(x) 假设

?x((P(x)?Q(x))?R(x)) 分（3）（1）（2）

（4）P(a) 额外假设 （5）P(a)?(P(a)?Q(a)) 公理11 （6）P(a)?Q(a) 分（5）（4） （7）(P(a)?Q(a))?R(a) 全称量词消去（3） （8）R(a) 分（7）（6） （9）P(b) 额外假设 （10）P(b)?(P(b)?Q(b)) 公理11

34

（11）P(b)?Q(b) 分（10）（9） （12）（3） (P(b)?Q(b))?R(b) 全称量词消去（13）R(b) …… 此处隐藏：956字，全部文档内容请下载后查看。喜欢就下载吧 ……