上堂章节内容重点与难点ppt课件.ppt

《上堂章节内容重点与难点ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上堂课的内容、重点与难点公理推理过程假设推理过程只按分离规则代入规则组织公理推理过程了解导出规则，灵活组织假设推理过程公理推理定理公理分离规则、代入规则假设推理系统12.4命题演算的归结推理法机器证明的一个重要方法，仅有一条推理规则(称为归结规则)的机械推理法，便于计算机程序实现。22.4.1归结证明过程证明AB永真证明A∧B永假AB=(A∧B)证明B永真证明B永假B=(B)3一、建立子句集要证明公式AB，将(AB)=A∧B化为合取范式；(2)把合取范式的所有析取式构成一个集合即子句集。A化为

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

3、QQ子句合并成QPQ和PQPP或QQ两个可能的子句均为重言式P和P□空子句，归结结束PQ和QRPR一般归结7三、归结证明依归结规则进行归结，直至归结出空子句(用“□”表示)，则证明原公式为定理，否则不为定理。子句可以多次使用82.4.2归结证明举例证明：(P∨P)=PP归结过程为(1)P(2)P(3)□(1)(2)归结故原式为定理例用归结原理证明PP9例(PQ)((PQ)P)证明：(PQ)((PQ)P)=(PQ)((PQ)P)=(

4、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)归结故原式为定理10例(((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)Q(5)S(6)R(7)R(4)(2)归结(

5、8)□(7)(6)归结11例((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)归结故原式为定理。12例构造下面的归结推理证明：若数a是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是有理数；a

6、是实数且它不能表示成分数。所以a是无理数。解设p：a是实数。q：a是有理数。r：a是无理数。s：a能表示成分数。首先将简单命题符号化：前提：p→(q∨r),s→q,p∧s结论：r13将前提与结论的否定化为子句。归结证明过程：(1)p∨q∨r(2)s∨q(3)p(4)s(5)r(6)p∨r∨s(1)(2)归结(7)r∨s(3)(6)归结(8)r(4)(7)归结(9)□(5)(8)归结14前提：p→(q∨r),s→q,p∧s结论：r14讨论如果将“若数a是实数，则它不是有理数就是无理数”翻译如下：p

7、→((q∧r)∨(q∧r))=p∨((q∧r)∨(q∧r))=p∨((q∨r)∧(q∨r))=(p∨q∨r)∧(p∨q∨r)则有2个子句：p∨q∨rp∨q∨r如果只用到第1个子句，就能够归结出矛盾，当然更好了。15苏格拉底三段论P：凡人要死Q：苏格拉底是人R：苏格拉底要死此三段论表示为:(PQ)R局限性:此三段论是正确的，但却不是重言式。第三章谓词演算基础16谓词演算在命题演算中，把不可剖开或分解为更简单命题的原子命题作为基本单元。对原子命题内部结构进一步剖析，分解为个体谓词173

8、.1谓词与个体个体个体域全总个体域个体变元项3.1.1个体个体是指具有独立意义、独立存在的东西。也称为常个体或实体。用a、b、c…等表示。18个体域、全总个体域(2)个体域：由个体组成的集合。个体域常用I、J、K…等表示。(3)全总个体域：所有个体不管是何种类型的个体综合在一起组成的个体域称为全总个体域。用U表示。19个体变元、项(4)个体变元