命题演算的推理理论.ppt

《命题演算的推理理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、R)证明：考察(P(QR))((PQ)R)合取范式为(PQR)PQR建立子句集{PQR，P，Q，R}归结过程为：(1)PQR(2)P(3)Q(4)R(5)QR(1)(2)归结(6)R(5)(3)归结(7)□(6)(4)归结例2(p22)((PQ)R)(SP)Q(SR)证明：考察((PQ)R)(SP)Q(SR)合取范式为(PR)(QR)(SP)QSR建立子句集{PR，QR，SP，Q，S，R}归结过程为(1)PR(2)QR(3)SP(4

5、)Q(5)S(6)R(7)R(4)(2)归结(8)□(7)(6)归结例((PQ)(QR))(PR)证明：考察((PQ)(QR))(PR)化为合取范式：上式=(PQ)(QR)(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)归结例(SQ)(PQ)(RS)(RQ)P证明：(SQ)(PQ)(RS)(RQ)P=(

6、SQ)(PQ)(RS)(RQ)P建立子句集{SQ,PQ,RS,RQ,P}归结过程为:(1)SQ(2)PQ(3)RS(4)RQ(5)P(6)PS(1)(2)归结(7)S(5)(6)归结(8)PR(2)(4)归结(9)R(5)(8)归结(10)S(3)(9)归结(11)□(7)(10)归结故原式为定理。例(p23)(PQ)((PQ)P)证明：(PQ)((PQ)P)=(PQ)((PQ)P)=(PQ)((PQ)P)=

7、(PQ)(PQ)P)归结过程为(1)PQ(2)PQ(3)P(4)P(1)(2)归结(5)□(3)(4)归结故原式为定理例(p23)(PQ)(QR)RP证明：((PQ)(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)归结故原式为定理例用归结原理证明PP证明：(P∨P)=PP归结过程为(1)P(2)P(3)□(1)(2)归结故原式

8、为定理第二章命题演算的推理理论2.1命