第四章 谓词演算的推理理论.ppt

例 已知知识 （1） （2） 结论： 用假设推理证明之。 定理 (P?R)?((Q??R)?(P??Q)) 证明: P?R 假设 Q??R 假设 (3) (P?R)?((R??Q)?(P??Q)) 公理3 (4) (R??Q)?(P??Q) (1)(3)分离 (5) (Q??R)?(R??Q) 公理14 (6) R??Q (2)(5)分离 (7) P??Q (4)(6)分离 例 所有羊都吃草,所有死羊都不吃草. 所以,所有死羊都不是羊. 解: 推理如下: (1) ?x(羊(x) →吃草(x)) (2) ?x(死羊(x) →?吃草(x)) (3) 羊(x) →吃草(x) (4) 死羊(x) →?吃草(x) (5) (羊(x) →吃草(x)) →(?吃草(x)→?羊(x)) 定理 (6) ?吃草(x)→?羊(x) (7) (死羊(x) →?吃草(x)) 传递公理 →((?吃草(x)→?羊(x)) →(死羊(x) →?羊(x))) (8) (?吃草(x)→?羊(x)) →(死羊(x) →?羊(x)) (9) 死羊(x) →?羊(x) (10) ?x(死羊(x) →?羊(x)) 如果△A1，…，△An，△A├△B， 则 △A1，…，△An ├△（A?B） 在徐洁磐《离散数学导论》2011年4月第4版p210提到的条件是：不对各Ai中的自由变元施行全称规则、存在规则 如果在假设中或在推理过程中出现?xP(x)，我们可引入额外假设P(e)(其中e为尚未使用过的变元)，若能推导出不含e的公式Q，则说证明了该公式。 * 闭式:无自由变元 F（x，c）表示对常元c与任意变元x成立, 错误在于: c可能与x有关的. 公理21是说 △(P(x)??x P(x))， 即?x(P(x)??x P(x))， 故当x=c时，P(c)??xP(x) 为真。 进而，由 P(c)为真, 分离可以得到 ?xP(x)为真. 注意定义中的假设?1，?2，?3，…，?k只能理解为其本身，而不能代入。 差别在哪里? 该证明过程为假设推理证明过程！ 问题: △P(x)=△?xP(x) ? 此等式应该成立. 全0规则相当于永真公式： △P(x) ?△?xP(x) = ?xP(x) ? ?xP(x) （对于仅一个自由变元来说） 注意： △(P(x) ??xP(x)) = ?x(P(x) ??xP(x)) 非永真 （对于仅一个自由变元来说） 该证明过程为假设推理证明过程！ 该证明过程为假设推理证明过程！ 两次运用调头公理2即可以。 例 试利用全1规则求证 全2规则 △(?1?(?2??(x))) ├ △(?1?(?2??x?(x))) 证明： (1) △(?1?(?2??(x))) (2) △(?1??x(?2??(x))) 对于(1)全1规则 (3) △((?1??x(?2??(x))) ?((?x(?2??(x)) ? (?2??x?(x))) ? (?1?(?2??x?(x))))) 公理3 (4) △((?x(?2??(x)) ? (?2??x?(x))) ? (?1?(?2??x?(x)))) 分离(2)(3) (5) △(?x(?2??(x))) ? (?2??x?(x))) 全1规则的一种理解,见 练习4.1(1), 其证明应用了全2规则。欠妥！ (6) △(?1?(?2??x?(x)))