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

第三章 基于谓词逻辑的机器推理-3.2 归结演绎推理3.2.1子句集定义1 原子谓词公式及其否定称为文字；文字的析取式称为子句；r个文字组成的子句称为r-文字子句。1-文字子句也称为单元子句。不含任何文字的子句称为空子句，记为或NIL。由子句构成的集合称为子句集。任何一个谓词公式都可以化为子句集，步骤如下：（1）、利用等价式A B A B和 A B (A B)(B A)消去联结词“”和“”。（2）、缩小否定联结词的作用范围，使其仅作用于原子公式。可利用下列等价式：A A；(AB)A B；(A B)A B；xA(x)x A(x)；xA(x)x A(x)（3）、重新命名变元名，使不同量词约束的变元有不同的名字。（4）、消去存在量词。若存在量词不在全称量词的辖域内，则用一个常量符号替换该存在量词辖域中的相应约束变元。这样的常量称为Skolem常量；若该存在量词在一个或多个全称量词的辖域内，则用这些全称量词指导变元的一个函数替换该存在量词约束的变元。这样的函数称为Skolem函数。例如x1 x2 xnyP(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)(AB)(A C)化为子句的合取式，得到的公式称为Skolem标准形。Skolem标准形的一般形式为x1 x2 xnM，其中M是子句的合取式。（7）、消去全称量词。（8）、对变元更名，使子句间无同名变元。（9）、消去合取词，以子句为元素组成的集合称为谓词公式的子句集。例、把谓词公式xyP(x,y)yQ(x,y)R(x,y)化为子句集。定理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，（SU）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的一个最一般合一（Most General Unifier），简称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),u3.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=Sktk/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表即SS1中的子句与S1中的子句两两归结，产生的归结式集合记为S2，再将S2并入CLAUSES；第三轮：将新的CLAUSES表即SS1 S2中的子句与S2中的子句两两归结，。如此下去，直到出现空子句。例1 设有如下的子句集，用穷举算法归结如下：S：（1）PQ （2）PQ （3）P Q （4）P QS1：（5）Q (1),(2)（6）P (1),(3)（7）Q Q (1),(4)（8）P P (1),(4)（9）Q Q (2),(3)（10）P P (2),(3)（11）P (2),(4)（12）Q (3),(4)S2：（13）P Q (1),(7)（14）P Q (1),(8)（15）P Q (1),(9)（16）P Q (1),(10)（17）Q (1),(11)（18）P (1),(12)（19）Q (2),(6)（20）PQ (2),(7)（21）PQ (2),(8)（22）PQ (2),(9)（23）PQ (2),(10)（24）P (2),(12)（25）P (3),(5)（26）P Q (3),(7)（27）P Q (3),(8)（28）P Q (3),(9)（29）P Q (3),(10)（30）Q (3),(11)（31）P (4),(5)（32）Q (4),(6)（33）P Q (4),(7)（34）P Q (4),(8)（35）P Q (4),(9)（36）P Q (4),(10)（37）Q (5),(7)（38）Q (5),(9)（39）(5),(12)3.4.2 几种常用的归结策略1、删除策略定义、设C1，C2是两个子句，若存在替换，使得C1 C2，则称子句C1类含C2。例、P(x)类含P(a)Q(y)；P(x)类含P(a)。删除策略。在归结过程中可随时删除以下子句：（1）、含有纯文字的子句；纯文字是指在子句中无补文字的文字。（2）、含有永真式的子句；（3）、被子句集中别的子句类含的子句。使用删除策略，例1可简化为：（1）PQ （7）P (2),(4)（2）PQ （8）Q (3),(4)（3）P Q （9）(5),(8)（4）P Q（5）Q (1),(2)（6）P (1),(3)删除策略的特点：删除策略的思想是及早删除无用字句，以避免无效归结，缩小搜索空间。删除策略是完备的。一个归结策略是完备的，是指对于不可满足的子句集，使用该策略进行归结，最终必导出空子句。2、支持集策略支持集是指目标公式的否定的子句集。支持集策略指每次归结时，两个亲本子句中至少要有一个是目标公式否定的子句或其后裔。例、见教材P84例4.支持集策略的特点：支持集策略实际是一种目标制导的反向推理。支持集策略是完备的。3、线性归结策略在归结过程中，除第一次归结可都用初始子句集S中的子句外，其它的各次归结至少要有一个亲本子句是前次归结的结果。例、P85例5线性归结策略的特点：完备、高效、与别的策略兼容。4、输入归结策略每次参加归结的亲本子句，必须至少有一个是初始子句集S中的子句。输入策略的特点：输入归结策略实际是一种自底向上的推理，它有相当高的效率。输入归结策略不完备。例如S=PQ,PQ,P Q,P Q不可满足，但用输入归结策略导不出空子句。可与支持集策略、线性归结策略结合。5、单元归结策略（单文字归结策略）每次参加归结的两个亲本子句中，必须至少有一个是单元子句（单文字子句）。单元归结策略的特点：可以尽快逼近空字句；效率高但不完备改进型的单元归结策略：单元优先策略。6、祖先过滤形策略参加归结的两个子句，要么至少有一个是初始子句集中的子句，要么一个是另一个的祖先。例6、P86例6祖先过滤形策略的特点：是输入策略的改进。是完备的3.4.3 归结策略的类型简化性策略。限制性策略。有序性策略。3.5 归结反演程序举例（略）3.6 Horn子句归结与逻辑程序3.6.1 子句的蕴含表示形式正文字：原子公式称为正文字。负文字：原子公式的否定称为负文字。把所有正、负文字分别放在一起，任意子句可写为：Q1 Qn P1 Pm可近一步化为蕴含式：Q1 Q2 Qn P1 P2 Pm如果约定前提文字之间恒为合取关系，结论文字之间恒为析取关系，则上式可简化为：Q1，Q2，Qn P1，P2，Pm写成另一种方式：P1，P2，Pm Q1，Q2，Qn两种特殊情形：当m=0时，变为 Q1，Q2，Qn，相当于（Q1 Q2 Qn）。当n=0时，变为P1，P2，Pm，这相当于P1 P2 Pm。对于子句的蕴含表示形式，归结过程变为：从其中一个子句的“”号左（右）侧与另一个子句的“”号右（左）侧的文字中寻找可合一文字对，然后消去它们，并把其余的左部文字合并，作为消解式的左部；其余的右部文字合并，作为消解式的右部。一般地，设子句C:P1，Pm Q1，Qn和C:P1，P s Q 1，Q t中有Pi与Q j（或 Qi与Pj）可合一，为它们的MGU，则C与C的归结式为P1 ，Pi-1 ，Pi+1 ，Pm ，P 1 ，P s Q1 ，Qn，Q 1 ，Qj-1 ，Qj+1 ，Qt 或P1 ，Pm ，P 1 ，Pj-1 ，P j+1 ，P s Q1，Qi-1，Q i+1 ，Qn ，Q1 ，Qt定义1 至多含有一个正文字的子句称为Horn子句。蕴含型Horn子句共有三种：（1）、P Q1，Q2，Qm 称为条件子句，P称为头部或结论；（2）、P 称为无条件句；（3）、Q1，Q2，Qm 称为目标子句，Qi称为子目标。例1、证明P(a,c)是下面子句集（1），（2），（3），（4）的逻辑结论。证：（1）P(x,z)P1(x，y)，P2(y,z)（2）P1(u,v)P11(u，v)（3）P11(a,b)（4）P2(b,c)（5）P(a,c)归结（从目标子句出发，采用线性归结）（6）P1(a，y)，P2(y,c)(5),(1),a/x,c/z （7）P11(a，y)，P2(y,c)(6),(2),a/u,y/v （8）P2(b，c)(7),(3),b/y (9)(8),(4)第三章 基于谓词逻辑的机器推理-3.7 非归结演绎推理3.7.1 Bledsoe 自然演绎法3.7.2 基于规则的演绎推理3.7.3 王浩算法作业：P85,1.(3),(6);4.(3),(4);7