人工智能3-4章

第三章基于谓词逻辑的机器推理----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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,x2,…,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)]}化为子句集。xy{P(x,y)[Q(x,y)R(x,y)]}SKOLEM标准形xy(PQR)子句集合为{PQR}定理1谓词公式G不可满足当且仅当其子句集S不可满足。子句集S是不可满足的是指其全部子句的合取式是不可满足的。命题逻辑中的归结原理3.2.2命题逻辑中的归结原理要证明在前提P下结论Q成立，即是证明PQ永真，这只须证明PQ不可满足。根据定理1，只须证明PQ的子句集不可满足。由于子句之间是合取关系，只要有一个子句不可满足，则整个子句集不可满足。由于空子句是不可满足的，所以如果子句集中包含空子句，则该子句集是不可满足的。若子句集中不包含空子句，则可通过Robinson提出的归结原理对子句集进行归结，归结过程保证子句集的不可满足性不变。一旦归结出空子句，则证明结束。因此，归结原理把定理的证明化为子句集中归结出空子句的过程。定义４、设L是一个文字，则称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２，则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,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。２）、ui/yi，当yi{x1,x2,…,xn}。得到的集合仍是一个替换，称为与的复合，记为º。例、见教材p67例3.13。定义９、设S={F1,F2,…,Fn}是一个原子谓词公式集，若存在一个替换，使得F1＝F2＝…＝Fn，则称为S的一个合一（Unifier），并称S为可合一的。一个公式集的合一一般不唯一。定义１０、设是公式集S的一个合一，如果对S的任何一个合一，都存在一个替换，使得＝º，则称为S的一个最一般合一（MostGeneralUnifier），简称MGU。定义１１、设S是一个非空的具有相同谓词名的原子公式集，从S中各公式的左边第一个项开始，同时向右比较，每一组不都相同的项的差异部分组成的集合称为S的差异集。例、公式集S={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的差异集为{a,z},{x,h(z,u)},{g(y),u}3.2.3替换与合一设S为一非空有限具有相同谓词名的原子谓词公式集，求S的MGU的算法：（1）、令k=0,Sk=S,k=（表示空替换）。（2）、若Sk只含有一个谓词公式，则算法停止，k就是要求的最一般合一。（3）、求Sk的差异集Dk。（4）、若Dk中存在元素xk和tk，其中xk是变元，tk是项且xk不在tk中出现，则置Sk+1=Sk{tk/xk}，k+1=kº{tk/xk}，k=k+1，然后转步（2）。（5）、算法停止，S的最一般合一不存在。定理3（合一定理）、如果S是一个非空有限可合一的公式集，则合一算法总是在步（2）停止，且最后的k即是S的最一般合一。3.2.4谓词逻辑中的归结原理定义12、设C1，C2是两个没有相同变元的子句，L1，L2分别是C1，C2中的两个文字，如果L1与L2有最一般合一，则子句C12=(C1-{L1})(C2-{L2})，称作C1和C2的二元归结式（二元消解式）。C1和C2称为C12的亲本子句，L1，L2称为消解文字。若在参加归结的子句内部含有可合一文字，则在进行归结之前，应对这些文字进行合一。定义13、如果子句C中，两个或两个以上的文字有一个最一般合一，则称C为C的因子。定义14、子句C1，C2的归结式，是下列二元归结式之一：1）、C1和C2的二元归结式；2）、C1和C2的因子的二元归结式；3）、C1的因子和C2的二元归结式；4）、C1的因子和C2的因子的二元归结式。定理4、谓词逻辑中的归结式是它的亲本子句的逻辑结果。类似于命题逻辑中的两个推论仍成立。归结反演：应用归结原理证明定理的过程称为归结反演。若F为已知前提的公式集，Q为结论，用归结反演证明Q为真的步骤是：（1）、否定Q，得到Q；（2）、把Q并入到公式集F中，得到{F,Q}；（3）、把公式集{F,Q}化为子句集S；（4）、应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，直到出现空子句，就证明了Q为真。例、自然数都是大于零的数；所有整数不是偶数就是奇数；偶数除以2是整数。求证：所有自然数不是奇数就是其一半为整数的数。证明：前提：F1：x(N(x)GZ(x)I(x))F2：x(I(x)E(x)O(x))F3：x(E(x)I(h(x)))结论：G：x(N(x)O(x)I(h(x)))F1、F2、F3及G化为子句集：（1）N(x)GZ(x)（2）N(y)I(y)（3）I(z)E(z)O(z)（4）E(u)I(h(u))（5）N(c)（6）O(c)（7）I(h(c))归结：（8）I(c)((2),(5),c/y)（9）I(c)E(c)((3),(6),c/z)（10）E(c)((8),(9))（11）I(h(c))((4),(10),c/u)（12）((7),(11))定理5（归结原理的完备性）、如果子句集S是不可满足的，则必存在一个由S推出空子句的归结序列。其它例见教材p78,例15，16。课堂练习：p94，题6。归结演绎树：N(y)I(y)N(c)I(z)E(z)O(z)O(c)I(c)I(c)E(c)E(c)E(u)I(h(u))I(h(c))I(h(c))3.3应用归结原理求取问题答案应用归结原理求取问题答案的步骤：（1）、把已知前提用谓词公式表示出来，并化为子句集S。（2）、把待求解问题也用谓词公式表示出来，然后把它的否定与谓词ANS构成析取式。ANS的变元应与问题的变元完全一致。（3）、把此析取式化为子句集，并把该子句集并入S中得到子句集S'。（4）、对S'应用归结原理进行归结。（5）、若得到归结式ANS，则答案就在ANS中。例、设A、B、C三人中有人从不说真话，也有人从不说假话，某人向这三人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。求谁是老实人，谁是说谎者？解、设T(x)表示x说真话。如果A说的是真话，则有：T(A)T(B)T(C)如果A说的是假话，则有：T(A)T(B)T(C)。同理，对B和C有：T(B)T(A)T(C)T(B)T(A)T(C)T(C)T(A)T(B)T(C)T(A)T(B)化为子句集S：（1）、T(A)T(B)（2）、T(A)T(C)（3）、T(A)T(B)T(C)（４）、T(B)T(C)（５）、T(A)T(B)T(C)（６）、T(C)T(A)（７）、T(C)T(B)先求谁是老实人，把T(x)ANS(x)并入S（８）、T(x)ANS(x)（９）、T(A)ANS(C)((8),(6),C/x)（１０）、T(B)ANS(C)((7),(8),C/x)（１１）、T(B)ANS(C)((9),(1))（１２）、ANS(C)((10),(11))因此C是老实人。无论如何归结，推不出ANS(A),ANS(B)。下证A是说谎者，即T(A)，其否定为（８）’T(A)即T(A)（９）’T(B)((8)’,(1))（１０）’T(C)（（９）’，（７））（１１）’T(C)（（８）’，（２））（１２）’NIL（（１０）’，（１１）’）3.４归结策略3.4.1问题的提出归结反演的一般过程。步１将子句集S置入CLAUSES表；步２若空子句NIL在CLAUSES中，则归结成功，结束。步３若CLAUSES表中存在可归结的子句对，则归结之，并将归结式并入CLAUSES表，转步２；步３归结失败，退出。穷举算法（广度优先策略）第一轮：将原子句集S中的子句两两归结，产生的归结式集合记为S1，再将S1并入CLAUSES表；第二轮：将新的CLAUSES表即SS1中的子句与S1中的子句两两归结，产生的归结式集合记为S2，再将S2并入CLAUSES；第三轮：将新的CLAUSES表即SS1S2中的子句与S2中的子句两两归结，…。如此下去，直到出现空子句。例1设有如下的子句集，用穷举算法归结如下：S：（1）PQ（2）PQ（3）PQ（4）PQ