人工智能原理教案02章归结推理方法22命题逻辑的归结.pdf

《人工智能原理教案02章归结推理方法22命题逻辑的归结.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2.2命题逻辑的归结2.2.1命题逻辑基础逻辑可分为经典逻辑和非经典逻辑，其中经典逻辑包括命题逻辑和谓词逻辑。归结原理是一种主要基于谓词（逻辑）知识表示的推理方法，而命题逻辑是谓词逻辑的基础。因此，在讨论谓词逻辑之前，先讨论命题逻辑的归结，便于内容上的理解。本节中，将主要介绍命题逻辑的归结方法，以及有关的一些基础知识和重要概念，如数理逻辑基本公式变形、前束范式、子句集等。描述事实、事物的状态、关系等性质的文字串，取值为真或假（表示是否成立）的句子称作命题。命题：非真即假的简单陈述句在命题逻辑里，单元命题是基本的单元或作为不可再分的原子

2、。下面所列出的是一些基本的数理逻辑公理公式和一些有用的基本定义，如合取范式、子句集，这些公式和定义在归结法的推理过程中是必不可少的，也是归结法的基础，应该熟练掌握。－数理逻辑的基本定义下面所列的是一些数理逻辑中重要的定义，在后面的分析中要用到：·合取式：p与q，记做p∧q·析取式：p或q，记做p∨q·蕴含式：如果p则q，记做p→q·等价式：p当且仅当q，记做pq·若A无成假赋值，则称A为重言式或永真式；·若A无成真赋值，则称A为矛盾式或永假式；·若A至少有一个成真赋值，则称A为可满足的；·析取范式：仅由有限个简单合取式组成的析取式·合

3、取范式：仅由有限个简单析取式组成的合取式－数理逻辑的基本等值式下面这些基本的等式在归结原理实施之前的公式转化过程中是非常重要的。只有将逻辑公式正确转换成为归结原理要求的范式，才能够保证归结的正常进行。·交换律：p∨qq∨p；p∧qq∧p·结合律：(p∨q)∨rp∨(q∨r);(p∧q)∧rp∧(q∧r)·分配律：p∨(q∧r)(p∨q)∧(p∨r)；p∧(q∨r)(p∧q)∨(p∧r)·双重否定律：p～～p·等幂律：pp∨p；pp∧p·摩根律:～(p∨q)～p∧～q；～(p∧q)～p∨～q·吸收律:p∨(p∧q)p；p∧(p∨q)p·

4、同一律:p∨0p；p∧1p·零律：p∨11p∧00·排中律：p∨～p1·矛盾律：p∧～p0·蕴含等值式：p→q～p∨q·等价等值式：pq(p→q)∧(q→p)·假言易位式:p→q～p→～q·等价否定等值式：pq～p～q·归谬论：(p→q)∧(p→～q)～p－合取范式范式：范式是公式的标准形式，公式往往需要变换为同它等价的范式，以便对它们作一般性的处理。合取范式：单元子句、单元子句的或（∨）的与（∧）。如：P∧（P∨Q）∧（～P∨Q）例：求取P∧(Q→R)→S的合取范式解：P∧(Q→R)→S=～（P∧(～Q∨R)）∨S=～P∨～(～Q∨

5、R)∨S=～P∨(～～Q∧～R)∨S=～P∨(Q∧～R)∨S=～P∨S∨(Q∧～R)=(～P∨S∨Q)∧(～P∨S∨～R)注意：首先一定要将原有的命题公式整理、转换成为各个"或"语句的"与"，不然后续推导没有意义。转换是基于数理逻辑的基本等值公式进行的，"或"转换到"与"中。思路与代数学的提取公因式方法相似。－子句集命题公式的子句集S是合取范式形式下的子命题（元素）的集合。子句集是合取范式中各个合取分量的集合，生成子句集的过程可以简单地理解为将命题公式的合取范式中的与符号"∧"，置换为逗号"，"。上例转换的合取范式：(～P∨S∨Q)∧

6、(～P∨S∨～R)其子句集为S={～P∨S∨Q,～P∨S∨～R}又如，有命题公式：P∧（P∨Q）∧（～P∨Q）其子句集S：S={P,P∨Q,～P∨Q}2.2.2命题逻辑的归结归结法推理的核心是求两个子句的归结式，因此需要先讨论归结式的定义和性质。归结式的定义设C和C2是子句集中的任意两个子句，如果C中的文字11L与C中的文字L互补，那么可从C和C中分别消去L122121和L，并将C和C中余下的部分按析取关系构成一个新子212句C，则称这一个过程为归结，称C为C和C的归结式，121212称C和C为C的亲本子句。1212例如：有子句：C＝

7、P∨C'，11C＝～P∨C'22存在互补对P和～P，则可得归结式：C=C'∨C'1212注意：CΛC→C，反之不一定成立。1212下面证明归结式是原两子句的逻辑推论，或者说任一使C、C为真的解释I下必有归结式C也为真。1212证明：设I是使C，C为真的任一解释，若I下的P为真，从12而～P为假，必有I下C'为真，故C为真。若不然，在I212下P为假，从而I下C'为真，故I下C为真。于是C∧C11212为真。于是C∧C→R(C,C)成立。1212反之不一定成立，因为存在一个使C'∨C'为真的解释I，12不妨设C'为真，C'为假。若P为真

8、，则～P∨C'就为假了。122因此反之不一定成立。由此可得归结式的性质。归结式的性质：归结式C是亲本子句C和C的逻121212辑结论。命题逻辑的归结法证明过程命题逻辑的归结过程也就是推理过程。推理是根据一定的准则由称为前