第二章谓词逻辑详解.ppt

* chapter2 * 2.4 谓词逻辑推理 1、推理形式 H1 ∧ H2 ∧ …… ∧ Hm ? C 其中， H1、H2、……Hm 称为推理的前提，C为这一组前提的有效结论。它们一般都是谓词公式。 * chapter2 * 2、推理规则 (1) P规则（前提引入规则）：给定的前提在证明的过程中随时都可以加以引用。 (2)Ｔ规则（结论引用规则）：在证明过程中产生的结论可以作为后续证明的前提加以引用。 (3) CP规则（附加前提引入规则）： 如果证明的形式为H1 ∧ H2 ∧ …… ∧ Hm ? A→B，等价于证明H1∧H2∧……∧Hm∧A ? B。A称为附加前提。 2.4 谓词逻辑推理 * chapter2 * (4) US规则（全称量词消去规则）： ?x A(x) ? A(c) c是指u中任意一个元素 (5) UG规则（全称量词引入规则）： A(c) ? ?x A(x) c是指u中任意一个元素 (6) ES规则（存在量词消去规则）： ?x A(x) ? A(c) c是使A(x)为真的某个元素 (7) EG规则（存在量词引入规则）： A(c) ? ?x A(x) c是指u中某个元素 2.4 谓词逻辑推理 * chapter2 * 【例10】证明三段论方法的正确性: 凡是人都要死。 苏格拉底是人。 苏格拉底要死。 令H(x): x是人。 M(x): x要死。 s: 苏格拉底。 则本题要证明: ?x(H(x)→M(x)), H(s) ? M(s) 证明:① ?x(H(x)→M(x)) P ② H(s)→M(s) US ① ③ H(s) P ④ M(s) T ② ③ 2.4 谓词逻辑推理 * chapter2 * 【例11】证明 ?x (C(x)→W(x)?R(x))??x (C(x)?Q(x)) ? ?x (Q(x)?R(x)) 证明：① ?x (C(x)?Q(x)) P ② C(a)?Q(a) ES① ③ C(a) T② ④ ?x (C(x)→W(x)?R(x)) P ⑤ C(a)→W(a)?R(a) US④ ⑥ W(a)?R(a) T③⑤ ⑦ R(a) T⑥ ⑧ Q (a) T② ⑨ Q(a)?R(a) T⑦ ⑧ ⑩ ?x (Q(x)?R(x)) EG⑨ 2.4 谓词逻辑推理 * chapter2 * 【例12】证明 ?x H(x) ? ?x (H(x)→M(x)) ? ?x M(x) 证明：① ?x H(x) P ② H(a) ES① ③ ?x (H(x)→M(x)) P ④ H(a)→M(a) US③ ⑤ M(a) T②④ ⑥ ?x M(x) EG ⑤ 不能互换 2.4 谓词逻辑推理 * chapter2 * 【例13】例 2.14 判断下列的推理过程是否正确。 证明：① ?x ?y G（x，y） P ② ?y G（z，y） US ① ③ G（z，c） ES ② ④ ?x G（x，c） UG ③ ⑤ ?y ?x G（x，y） EG ④ 2.4 谓词逻辑推理 * chapter2 * 解：此推理过程是错误的。 它的推导错误出现在第③步。?x?y G(x，y)的含义是：对于任意的一个x，存在着与它对应的y，使得G(x，y)成立。但是，对?y G(z，y)利用ES规则消去存在变量后得到G(z，c)的含义却是：对于任意个体z，有同一个体c，使得G(z，c)成立。显然，G(z，c)不是?y G(z，y)的有效结论。 因此，使用ES规则?xP(x)?P(c)消去存在量词的条件是：P(x)中除x外没有其他自由出现的个体变元。 2.4 谓词逻辑推理 人有了知识，就会具备