命题演算的推理理论.ppt

1、第二章 命题演算的推理理论,2.1 命题演算的公理系统 2.2 命题演算的假设推理系统 2.3 命题演算的归结推理法 2.3.1 归结证明过程 2.3.2 归结证明举例,2.3 命题演算的归结推理法,归结推理法 是机器证明的一个重要方法， 仅有一条推理规则(称为归结规则)的机械推理法， 从而便于计算机程序实现。,2.3.1 归结证明过程,要证明公式(如AB，其中A和B为子公式)为定理，实际上是证明AB为矛盾式。 归结法就是从公式AB出发对子句进行归结。,一、建立子句集,要证明公式AB，将 A B 化为合取范式； (2) 把合取范式的所有析取式构成一个集合即子句集。,A化为合取范式、 B化为合取

2、范式,例 建立子句集,如要证明公式 (PQ)P)Q， 只要考察 (PQ)PQ (1) 根据(1)得合取范式： (PQ)PQ (2) 根据(2)建立子句集： S =PQ，P，Q,二、对子句集S的归结,设有两个子句 P1 P2 Pn 和 P1 Q2 Qm， 注意到这两个子句，其中一个含有命题变元的肯定形式，另一个含有该变元的否定，由这两个子句就可推出一个新子句： P2 Pn Q2 Qm 称之为这两个子句的归结式。,若干重要的归结规则,父辈子句 归结式 说明 P和PQ Q 假设推理 PQ和PQ Q 子句合并成Q PQ和PQ PP或QQ 两个可能的子句 均为重言式 P和P 空子句， 归结结束 PQ和Q

3、R PR 三段论,三、归结证明,依归结规则进行归结，直至归结出空子句(用“”表示)， 则证明原公式为定理，否则不为定理。,子句可以 多次使用,第二章 命题演算的推理理论,2.1 命题演算的公理系统 2.2 命题演算的假设推理系统 2.3 命题演算的归结推理法 2.3.1 归结证明过程 2.3.2 归结证明举例,例 证明 (PQ)P)Q,解：考察 (PQ)P)Q 合取范式为 (PQ)PQ 子句集为 S =PQ，P，Q,归结过程为 PQ P Q (4) Q (1)(2)归结 (5) (3)(4)归结 故原式为定理,例1 (P(Q R)(PQ)R),证明：考察 (P(Q R) (PQ)R) 合取范式

4、为 (PQ R)PQR 建立子句集 PQ R，P，Q，R 归结过程为： (1) PQ R (2) P (3) Q (4) R (5) Q R (1)(2)归结 (6) R (5)(3)归结 (7) (6)(4)归结,例2(p22) (PQ) R)(SP)Q (SR),证明：考察(PQ) R)(SP)Q (SR) 合取范式为 (PR)(QR)(SP)QSR 建立子句集 PR，QR，SP，Q，S，R 归结过程为 (1) PR (2) QR (3) SP (4) Q (5) S (6) R (7) R (4)(2)归结 (8) (7)(6)归结,例 (PQ) (QR) (PR),证明：考察 (PQ)

5、 (QR) (PR) 化为合取范式： 上式 = ( P Q) ( QR) ( P R) = ( P Q) (Q R) P R 建立子句集 P Q, Q R ，P，R , 归结过程为: (1) P Q (2) Q R (3) P (4) R (5) P R (1)(2)归结 (6) R (3)(5)归结 (7) (4)(6)归结,例 (SQ)(PQ)(RS)(RQ)P,证明： (SQ)(PQ)(RS)(RQ) P =(SQ)(PQ)(RS)(RQ)P 建立子句集 SQ, P Q, RS, RQ, P 归结过程为:,(1) SQ (2) P Q (3) RS (4) RQ (5) P,(6) PS

6、 (1)(2)归结 (7) S (5)(6)归结 (8) PR (2)(4)归结 (9) R (5)(8)归结 (10) S (3)(9)归结 (11) (7)(10)归结 故原式为定理。,例 (p23) (PQ)(PQ)P),证明： (PQ)(P Q ) P ) = (P Q) (P Q) P ) =(P Q) (P Q) P ) =(P Q) (P Q) P ),归结过程为 (1) P Q (2) P Q (3) P,(4) P (1)(2)归结 (5) (3)(4)归结 故原式为定理,例 (p23) (PQ)(Q R)RP,证明： (PQ)(Q R)R ) P = (P Q) (Q R)R P,归结过程为 (1) P Q (2) Q R (3) R (4) P,(5) Q (2)(3)归结 (6) P (1)(5)归结 (7) (4)(6)归结 故原式为定理,例 用归结原理证明 PP,证明： (PP) = P P,归结过程为 (