北京邮电大学 计算机学院 离散数学 1.6- rules of inference.ppt

* * College of Computer Science Technology, BUPT 构造推理的证明(举例) 前提: ?x(F(x)?G(x))，F(a) 结论: G(a) 证明: (1) F(a) 前提引入 (2) ?x(F(x)?G(x)) 前提引入 (3) F(a)?G(a) (2)UI (4) G(a) (1)(3)假言推理 * * College of Computer Science Technology, BUPT 构造推理的证明(举例、续) 前提: ?x(F(x)?G(x))，?xF(x) 结论: ?xG(x) 证明: (1) ?xF(x) 前提引入 (2) F(c) (1) EI (3) ?x(F(x)?G(x)) 前提引入 (4) F(c)?G(c) (3) UI (5) G(c) (2)(4)假言推理 (6) ?xG(x) (5) EG * * College of Computer Science Technology, BUPT 构造推理的证明(举例、续) “先EI，后UI” 证明: (1) ?x(F(x)?G(x)) 前提引入 (2) F(c)?G(c) (2) UI (3) ?xF(x) 前提引入 (4) F(c) (3) EI ? ? ? 说明：这个证明是错的. (3)(4)应当在(1)(2)前，(4)中的c是特定的， (2)中的c是任意的 * * College of Computer Science Technology, BUPT 构造推理的证明(举例、续) 前提: ~?x(F(x)∧H(x)), ?x(G(x)?H(x)), 结论: ?x(G(x)?~F(x)) 证明: (1) ~?x(F(x)∧H(x)) 前提引入 (2) ?x(~F(x)∨~H(x)) (1)置换 (3) ?x(H(x)?~F(x)) (2)置换 (4) H(y)?~F(y) (3) UI (5) ?x(G(x)?H(x)) 前提引入 (6) G(y)?H(y) (5) UI (7) G(y)?~F(y) (4)(6)假言三段论 (8) ?x(G(x)?~F(x)) (7) UG * * College of Computer Science Technology, BUPT Example Every man has two legs. John Smith is a man. Therefore, John Smith has two legs. Define the predicates: M(x): x is a man L(x): x has two legs J: John Smith, a member of the universe * * College of Computer Science Technology, BUPT Example The argument becomes 1.x[M(x) ? L(x)] 2.M( J ) \L( J) The proof is 1.x[M(x) ? L(x)] Hypothesis 1 2.M( J ) ? L(J ) step 1 and UI 3.M( J ) Hypothesis 2 4.L( J) steps 2 and 3 and modus ponens Q. E. D. * * College of Computer Science Technolo