第4章知识推理课件

第4章 知识推理4.1 推理的基本概念4.2 归结演绎推理归结演绎推理4.3 非归结演绎推理4.4 不确定性推理方法4.1 推理的基本概念推理是以一个或几个命题为根据或理由，从而得出另一个命题的思维过程。推理的根据或理由称为前提，得出的命题称为结论。推理是由称做前提和结论的两部分命题组成的。在智能系统中，推理是由程序实现的，称为推理机。问题求解中的推理就是知识的使用过程，由于知识表示有多种方法，相应地也就有多种推理方法，下面分别从不同角度来探讨这些推理方法。1.经典推理和非经典推理2.演绎推理、归纳推理和缺省推理3.单调推理和非单调推理4.确定性推理和不确定性推理4.2 归结演绎推理4.2.1Herbrand理论4.2.2归结原理4.2.3归结反演定理证明的实质是证明F1F2FnW的永真性。其证明方法可分为二类：一是直接证明F1F2FnW为永真，即演绎法；二是间接证明(F1F2FnW)为永假，即反证法。20世纪60年代，人们把研究的注意力集中在证明永假性，即证明F1F2FnW的永假性，这实际上就是要证明F1,F2,FnW是一个矛盾集。因此证明F1F2FnW永假，只需证明F1F2Fn和W是不可满足的就可以。海伯伦（J.Herbrand）和Robinson在这个方向上先后作了卓越的研究工作。首先，由Herbrand提出的Herbrand域和Herbrand定理，为自动定理证明奠定了理论基础；然后，由Robinson提出的归结原理使自动定理证明成为可能。4.2.1 Herbrand理论证明一个谓词公式的不可满足性是困难的，这是由于个体变量论域的任意性，以及解释的个数的无限性。如果一个具体的谓词公式能够找到一个比较简单的特殊的论域，使得只要在这个论域上该公式是不可满足的，便能保证该公式在任一论域上也是不可满足的，这将对不可满足性的证明是十分有益的。Herbrand首先将合式公式标准化为子句集，然后在此基础上引入Herbrand域（简记为H域），并从理论上给出了证明子句集永假的可行性及方法。1.1.子句和子句集子句和子句集在谓词逻辑中，把不含任何连接词的谓词公式称为文字。把由文字的析取构成的合式公式称为子句，这里文字只能是原子谓词公式或其取反。不包含任何文字的子句我们称为空子句。由子句构成的集合称为子句集。在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系和推理规则转化成相应的子句集。在子句集中各子句之间具有合取关系。鉴于子句集隐含地受到全称量词的约束，而全称量词又可分配到有合取关系的各个子句，所以各子句中的变量实际上都是全称量词的约束变量，且作用域只在子句范围内。为消除子句间不必要的交互作用（即保持子句间的相互独立性），需要作变量换名，使各子句都使用不同的变量。例4-1求下面谓词公式的子句集xyP(x,y)yQ(x,y)R(x,y)解(1)消去蕴含词和等价词xyP(x,y)yQ(x,y)R(x,y)(2)缩小否定词的作用范围，直到其仅作用于原子公式xyP(x,y)yQ(x,y)R(x,y)(3)适当改名，使量词之间不含同名指导变量和约束变量xyP(x,y)zQ(x,z)R(x,z)(4)消去存在量词如果该量词在某些全称量词的辖域内，则用这些全称量词指导变量的一个函数代替该存在量词辖域中相应的约束变量，这样的函数成为Skolem函数；如果该量词不在任何全称量词的辖域内，则用一个常量符号代替该存在量词辖域中相应的约束变量，这样的函数成为Skolem常量。xP(x,f(x)Q(x,g(x)R(x,g(x)(5)消去全称量词P(x,f(x)Q(x,g(x)R(x,g(x)(6)化公式为合取范式P(x,f(x)Q(x,g(x)P(x,f(x)R(x,g(x)(7)适当改名，使子句间无同名变量P(x,f(x)Q(x,g(x)P(y,f(y)R(y,g(y)(8)消去合取词，以子句为元素组成一个集合S S=P(x,f(x)Q(x,g(x),P(y,f(y)R(y,g(y)当一个谓词公式G化简为标准化的子句集S时，有一个重要性质，即S的不可满足（对于任意论域上的任意解释，S中都至少有一个子句真值为假）成为G永假的充分必要条件。注意，这并不意味着G与S间等价。由于在谓词公式G的化简过程中，为消除存在量词而引入了Skolem函数，从而使子句集S实际上只是G的一个特例。然而，可以证明G和S在永假性上是等价的，这成为建立Herbrand定理的重要基础。定理4-1若G是给定的谓词公式，而相应的子句集为S，则G是不可满足的当且仅当S是不可满足的。2.2.HerbrandHerbrand域及域及HerbrandHerbrand定理定理子句集是子句的集合。为了判定子句集的不可满足性，就需要对子句集中的子句进行判定。由谓词公式永假性的定义可知，为判断一个子句的不可满足性，需要对个体域上的一切解释逐个进行判定，只有当子句对任何非空个体域上的任何一个解释都不是不可满足的时，才能判定该子句是不可满足的，这是一件十分麻烦甚至难以实现的困难工作。针对这一情况，Herbrand构造了一个特殊的域，并证明只要对这个特殊域上的一切解释进行判定，就能得知子句集是否不可满足，这个特殊的域称为Herbrand域，简记为H域。定义4-1设S为子句集，则按下述方法构造的域H称为Herbrand伦域：(1)令H0是S中出现的所有个体常量的集合，若S中不包含个体常量，则令就H0=a，其中，a为任意指定的一个个体常量。(2)令Hi+1=HiS中所有n元函数f(x1,xn)|xj(j=1,n)在Hi中的元素，i=1,2,。定义4-2子句集S在H域上的一个解释I*满足下列条件：(1)在解释I*下，常量映射到自身。(2)S中的任一个n元函数是HnT,F的映射。T和F是谓词的真值指派。定理4-2设I是S的论域D上的解释，存在对应于I的H解释I*，使得若有S|I=T，必有S|I*=T。定理4-3子句集S是不可满足的充要条件是S的H域上一切解释都为假。定理4-4子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S。从理论上讲，根据Herbrand定理可以建立计算机程序去实现自动定理证明。但设计这样的程序存在二个主要的困难：(1)子句集的不可满足性是不可判的，即子句集的不可满足性不能确保在有限的计算步范围内判定。(2)即使对于不可满足的子句集，能在有限的计算步范围内加以证明，但依据H域上的每个解释判别不满足的基子句，计算量也往往很大。4.2.2 归结原理归结原理的基本思路是通过归结方法不断扩充待判定的子句集，并设法使其包含进指示矛盾的空子句。空子句是不可满足（即永假）的子句，既然子句集中的子句间隐含着合取关系，空子句的出现实际上判定了子句集的不可满足。(1)归结式定义4-3设L为一个文字，则称L和L为互补文字。定义4-4设有二个子句：C1=LC1，C2=LC2从C1和C2中消去互补文字L和L，并通过析取将C1和C2的剩余部分组成新的子句：C=C1C2则称C为C1和C2的归结式（消解式），C1，C2称为其归结式的亲本子句，L，L称为消解基。(2)归结式性质定理4-5二个子句C1和C2的归结式C是C1和C2的逻辑结论。推论设C1和C2是子句集S中的两个子句，并以C作为它们的归结式，则通过往S中加入C而产生的扩展子句集S与子句集S在不可满足的意义上是等价的，即S的不可满足S的不可满足。1.1.归结方法归结方法(3)空子句当C1=L和C2=L时，归结式为空；通常以字母“NIL”或者符号“”指示为空的归结式，并称C=NIL表示C为空子句。显然C1和C2是一对矛盾子句无论为子句集指派什么解释，C1和C2不可同时满足，所以空子句实际上是不可满足的子句，进而导致子句集不可满足。换言之，空子句就是归结原理判定子句集不可满足的成功标志。2.2.命题逻辑中的归结命题逻辑中的归结例4-7利用归结原理判定子句集S=PQ,PR,Q,R是否可满足。图4-1命题逻辑的归结演绎树3.3.谓词逻辑中的归结谓词逻辑中的归结在谓词逻辑情况下，由于子句中含有变量，不能像命题逻辑那样直接发现和消去互补文字，往往需对潜在的互补文字中的变量作置换与合一处理后，才能用于归结。1)置换与合一(1)置换置换可以简单的理解为是在一个谓词公式中用置换项去置换相应的变量。(1)置换置换可以简单的理解为是在一个谓词公式中用置换项去置换相应的变量。定义4-5置换是形如t1/x1,t2/x2,tn/xn的有限集合，其中x1,x2,xn是互不相同的变量；t1,t2,tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个tj（i,j=1,2,n）中。定义4-6设=t1/x1,t2/x2,tn/xn，=u1/y1,u2/y2,un/yn是两个置换，则与的合成也是一个置换，记作。是从集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn中删去以下两种元素：当ti=xi时，删去ti/xi(i=1,2,n);当yix1,x2,xn时，删去uj/yj(j=1,2,m)最后剩下的元素所构成的集合。(2)合一合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。定义4-7设有公式集F=F1,F2,Fn，若存在一个置换，可使F1=F2=Fn，则称是F的一个合一。同时称F1,F2,.,Fn是可合一的。一般说来，一个公式集的合一不是唯一的。定义4-8设是公式集F的一个合一，如果对F的任意一个合一都存在一个置换，使得=，则称是一个最一般合一（MostGeneralUnifier，简记为MGU）2)谓词逻辑中的归结原理的应用定义4-9设C1和C2是两个没有相同变量的子句，L1和L2分别是C1和C2的文字，如果是L1和L2的最一般合一，则子句(C1-L1)(C2-L2)称作子句C1和C2的一个二元归结式，C1和C2称作归结式的亲本子句，而L1和L2称为被归结的文字。定义4-10若子句C中有两个或两个以上文字存在一个最一般合一，则称C为子句C的因子。如果C为一个单文字，则称它为C的单元因子。定义4-11若C1和C2是无公共变量的子句，则C1和C2的二元归结式；C1的因子和C2的二元归结式；C1和C2的因子的二元归结式；C1的因子和C2的因子的二元归结式。这四种二元归结式都叫子句C1和C2的归结式，仍记作R(C1,C2)。在谓词逻辑的归结演绎推理中只需对原子谓词公式作合一处理，所以实际上只需通过一个匹配过程去检查两个原子谓词公式的可合一性，并同时建立用于实现合一的置换。匹配过程可归纳如下：(1)二个公式必须具有相同的谓词和参数项个数；(2)从左到右逐个检查参数项的可合一性：若一对参数项中有一个变量v（不必关注另一个参数是否为变量），并初次出现，则这对参数项可合一，并以另一参数t为置换项，与该变量一起构成一个置换元素t/v；若该变量出现过，则已建立相应的置换元素，就取其置换项，代替该变量，检查是否与另一参数合一；若不能合一，则合一处理失败。若一对参数项中没有一个是变量（往往都是常量），则它们必须相同，否则合一处理失败。(3)若每对参数项都可合一，则合一处理成功，并构成用于实现合一的置换。4.4.归结原理的完备性归结原理的完备性 定理4-7设子句集S是不可满足的，当且仅当存在一个由S应用归结原理推出空子句的推理过程。4.2.3 归结反演归结原理给出了证明子句集不可满足性的方法。欲证明Q为P1,P2,Pn的逻辑结论，只需证明(P1P2Pn)Q是不可满足的。因此，可用归结原理来进行定理得自动证明。这种应用归结原理证明定理的过程，我们称为归结反演。归结反演的基本思路是：要从作为事实的公式集F证明目标公式W为真，可以先将W取反，加入公式集F，然后将F标准化为子句集S，再通过归结演绎证明S不可满足，并由此得出W为真的结论。因此，一个归结反演系统应由二个部分组成：标准化部件和归结演绎部件。前者将每条事实和取反的目标公式分别标准化为子句集，再合并为子句集S；后者遵从归结演绎方法，控制定理证明的全