【人工智能课件】基于谓词逻辑的机器推理

《【人工智能课件】基于谓词逻辑的机器推理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章基于谓词逻辑的机器推理----3.2归结演绎推理3.2.1子句集定义1原子谓词公式及其否定称为文字；文字的析取式称为子句；r个文字组成的子句称为r-文字子句。1-文字子句也称为单元子句。不含任何文字的子句称为空子句，记为或NIL。由子句构成的集合称为子句集。任何一个谓词公式都可以化为子句集，步骤如下：（1）、利用等价式ABAB和AB(AB)(BA)消去联结词“”和“”。（2）、缩小否定联结词的作用范围，使其仅作用于原子公式。可利用下列等价式：AA；(AB)AB；(AB)AB；xA(x)x

2、A(x)；xA(x)xA(x)（3）、重新命名变元名，使不同量词约束的变元有不同的名字。（4）、消去存在量词。若存在量词不在全称量词的辖域内，则用一个常量符号替换该存在量词辖域中的相应约束变元。这样的常量称为Skolem常量；若该存在量词在一个或多个全称量词的辖域内，则用这些全称量词指导变元的一个函数替换该存在量词约束的变元。这样的函数称为Skolem函数。例如x1x2•••xnyP(x1,x2,…,xn,y)中y可用Skolem函数f(x1,x2,…,xn)替换为x1x2•••xnP(x1,x2,…,xn,f(x1,x

3、2,…,xn))。（5）、把全称量词全部移到公式的左边。（6）、把全称量词后面的公式利用等价关系A(BC)(AB)(AC)化为子句的合取式，得到的公式称为Skolem标准形。Skolem标准形的一般形式为x1x2•••xnM，其中M是子句的合取式。（7）、消去全称量词。（8）、对变元更名，使子句间无同名变元。（9）、消去合取词，以子句为元素组成的集合称为谓词公式的子句集。例、把谓词公式x{yP(x,y)y[Q(x,y)R(x,y)]}化为子句集。定理1谓词公式G不可满足当且仅当其子句集S不可满足。子句集S是不可满足的

4、是指其全部子句的合取式是不可满足的。3.2.2命题逻辑中的归结原理要证明在前提P下结论Q成立，即是证明PQ永真，这只须证明PQ不可满足。根据定理1，只须证明PQ的子句集不可满足。由于子句之间是合取关系，只要有一个子句不可满足，则整个子句集不可满足。由于空子句是不可满足的，所以如果子句集中包含空子句，则该子句集是不可满足的。若子句集中不包含空子句，则可通过Robinson提出的归结原理对子句集进行归结，归结过程保证子句集的不可满足性不变。一旦归结出空子句，则证明结束。因此，归结原理把定理的证明化为子句集中归结出空子句的过程。定义４、设L是一个

5、文字，则称L与L为互补文字。定义５、设C1、C2是命题逻辑中的两个子句，C1中有文字L1，C２中有文字L２，且L1与L２互补，从C1，C２中分别删除L1，L２，再将剩余部分析取起来，构成的新子句C1２称为C1与C2的归结式（消解式），C1，C2称为C1２的亲本子句。定理２、归结式C1２是其亲本子句C1与C2的逻辑结论。推论、设C1，C2是子句集S的两个子句，C1２是它们的归结式，则（１）若用C1２代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性。即S1不可满足S不可满足（２）若把C1２加入到S中，得到新子句集S２

6、，则S２与S在不可满足意义上是等价的。即S2不可满足S不可满足例、用归结原理证明R是P，（PQ）R，（SU）R，U的逻辑结果。3.2.3替换与合一定义６、一个替换(Substitution)是形如{t1/x1,t2/x2,…,tn/xn}的有限集合，其中t1,t2,…,tn是项，x1,x2,…,xn是互不相同的个体变元。ti/xi表示用ti代换xi。ti与xi不同，xi也不能出现在tj中(j=1,2,…,n)。例、｛a/x,g(y)/y,f(g(b))/z}是一个替换，{g(y)/x,f(x)/y}不是一个替换。定义７、设＝{t1/x1,

7、t2/x2,…,tn/xn}是一个替换，E是一个表达式（项、原子公式、文字、子句），把E中出现的所有个体变元xi都用ti替换，得到的结果记为E，称为E在下的替换实例。例、若E=P(x,y,g(z)),＝{a/x,f(b)/y,c/z}，则E=P(a,f(b),g(c))。定义８、设＝{t1/x1,t2/x2,…,tn/xn}，＝{u1/y1,u2/y2,…,um/ym}是两个替换，则将集合{t1/x1,t2/x2,…,tn/xn，u1/y1,u2/y2,…,um/ym}中符合下列条件的两种情形删除：１）、ti/xi，当ti＝xi

8、。２）、ui/yi，当yi{x1,x2,…,xn}。得到的集合仍是一个替换，称为与的复合，记为º。