命題演算的歸結(jié)推理法PPT學(xué)習(xí)教案

1、會計學(xué)1命題演算的歸結(jié)推理法命題演算的歸結(jié)推理法證明證明AB永真永真證明證明A B永假永假AB= (A B)證明證明B永真永真證明證明 B永假永假B= ( B)第1頁/共18頁A化為合取范式化為合取范式、 B化為合取范式化為合取范式第2頁/共18頁如要證明公式如要證明公式 (PQ) P)Q，只要考察只要考察 (PQ) PQ (1) 根據(jù)根據(jù)(1)得合取范式：得合取范式： ( P Q) PQ (2)根據(jù)根據(jù)(2)建立子句集：建立子句集： S = P Q，P， Q第3頁/共18頁稱之為這兩個子句的稱之為這兩個子句的歸結(jié)式歸結(jié)式。第4頁/共18頁第5頁/共18頁子句可以子句可以多次使用多次使用第6頁

2、/共18頁解：考察解：考察 (PQ) P) Q 合取范式為合取范式為 ( P Q) PQ 子句集為子句集為 S = P Q，P， Q歸結(jié)過程為歸結(jié)過程為(1) P Q(2) P(3) Q(4) Q (1)(2)歸結(jié)歸結(jié) (5) (3)(4)歸結(jié)歸結(jié) 故原式為定理故原式為定理2.3.2 歸結(jié)證明舉例歸結(jié)證明舉例第7頁/共18頁證明：考察證明：考察 (P(Q R) (P Q)R) 合取范式為合取范式為 ( PQ R) P QR 建立子句集建立子句集 PQ R，P，Q， R 歸結(jié)過程為：歸結(jié)過程為： (1) PQ R (2) P (3) Q (4) R (5) Q R (1)(2)歸結(jié)歸結(jié) (6)

3、R (5)(3)歸結(jié)歸結(jié) (7) (6)(4)歸結(jié)歸結(jié) 第8頁/共18頁證明：考察證明：考察(PQ) R) ( S P) Q (SR) 合取范式為合取范式為 (P R) ( Q R) ( S P) Q SR 建立子句集建立子句集 P R， Q R， S P，Q，S， R 歸結(jié)過程為歸結(jié)過程為 (1) P R (2) Q R (3) S P (4) Q (5) S (6) R (7) R (4)(2)歸結(jié)歸結(jié) (8) (7)(6)歸結(jié)歸結(jié)第9頁/共18頁證明證明：考察：考察 (PQ) (QR) (PR) 化為合取范式：化為合取范式： 上式上式 = ( P Q) ( Q R) ( P R) = (

4、 P Q) ( Q R) P R 建立子句集建立子句集 P Q, Q R ，P， R , 歸結(jié)過程為歸結(jié)過程為: (1) P Q (2) Q R (3) P (4) R (5) P R (1)(2)歸結(jié)歸結(jié) (6) R (3)(5)歸結(jié)歸結(jié) (7) (4)(6)歸結(jié)歸結(jié) 第10頁/共18頁證明證明： 建立子句集建立子句集 SQ, P Q, R S, R Q, P 歸結(jié)過程為歸結(jié)過程為:(1) SQ(2) P Q(3) R S(4) RQ(5) P(6) PS (1)(2)歸結(jié)歸結(jié) (7) S (5)(6)歸結(jié)歸結(jié) (8) PR (2)(4)歸結(jié)歸結(jié) (9) R (5)(8)歸結(jié)歸結(jié) (10)

5、S (3)(9)歸結(jié)歸結(jié) (11) (7)(10)歸結(jié)歸結(jié) 故原式為定理。故原式為定理。第11頁/共18頁證明：證明： (PQ) (P Q ) P ) = ( P Q) ( P Q) P ) =( P Q) ( ( P Q) P ) =( P Q) ( P Q) P ) 歸結(jié)過程為歸結(jié)過程為(1) P Q(2) P Q(3) P (4) P (1)(2)歸結(jié)歸結(jié) (5) (3)(4)歸結(jié)歸結(jié) 故原式為定理故原式為定理第12頁/共18頁證明：證明： ( (PQ) ( Q R)R ) P = ( P Q) ( Q R)R P 歸結(jié)過程為歸結(jié)過程為(1) P Q(2) Q R(3) R (4) P(5) Q (2)(3)歸結(jié)歸結(jié) (6) P (1)(5)歸結(jié)歸結(jié) (7) (4)(6)歸結(jié)歸結(jié) 故原式為定理故原式為定理第13頁/共18頁證明：證明： ( PP) = P P 歸結(jié)過程為歸結(jié)過程為(1) P(2) P(3) (1)(2)歸結(jié)歸結(jié) 故原式為定理故原式為定理第14頁/共18頁解 設(shè) p：a是實數(shù)。 q：a是有理數(shù)。 r：a是無理數(shù)。 s：a能表示成分?jǐn)?shù)。 首先將簡