人工智能,第三章281

《人工智能》第三章谓词逻辑与归结原理谓词归结子句形(Skolem标准形)为了能够像命题逻辑那样进行归结，首先必须解决谓词逻辑中的量词问题。前束范式：如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。《人工智能》第三章谓词逻辑与归结原理谓词归结子句形(Skolem标准形)Skolem标准形前束范式中消去所有的量词。Skolem函数如果某个存在量词是在其他任意量词的辖域内，就存在某种依赖关系，可以用一个函数描述这种依赖关系，叫做Skolem函数。《人工智能》第三章谓词逻辑与归结原理谓词归结子句形(Skolem标准形)量词消去原则：•存在量词。将该量词约束的变量用任意常量（a，b等）或任意变量的函数（f(x)，g(y)等）代替。•左边有任意量词的存在量词，消去时该变量改写成为任意量词的函数；如没有，改写成为常量。•任意量词。简单地省略掉该量词。《人工智能》第三章谓词逻辑与归结原理谓词归结子句形(Skolem标准形)例:将下式化为Skolem标准形：～((x)(y)P(a,x,y)→(x)(～(y)Q(y,b)→R(x)))解：–第一步，消去→，得：～((～(x)(y)P(a,x,y))∨(x)(～～(y)Q(y,b)∨R(x)))–第二步，～深入到量词内部，得：(x)(y)P(a,x,y)∧～(x)((y)Q(y,b)∨R(x))＝(x)(y)P(a,x,y)∧(x)((y)～Q(y,b)∧～R(x))–第三步，任意量词左移，得：(x)(y)P(a,x,y)∧(y)(～Q(y,b)∧～R(x))《人工智能》第三章谓词逻辑与归结原理谓词归结子句形(Skolem标准形)第四步，变量易名，存在量词左移，直至所有的量词移到前面，得：(x)(y)P(a,x,y)∧(y)(～Q(y,b)∧～R(x))＝(x)(y)P(a,x,y)∧(z)(～Q(z,b)∧～R(x))＝(x)(y)(z)(P(a,x,y)∧～Q(z,b)∧～R(x))由此得到前述范式《人工智能》第三章谓词逻辑与归结原理谓词归结子句形(Skolem标准形)–第五步，消去存在量词，略去任意量词消去(y)，因为它左边只有(x)，所以使用x的函数f(x)代替，这样得到：(x)(z)(P(a,x,f(x))∧～Q(z,b)∧～R(x))–消去(z)，同理使用g(x)代替，这样得到：(x)(P(a,x,f(x))∧～Q(g(x),b)∧～R(x))–略去任意量词，原式的Skolem标准形为：P(a,x,f(x))∧～Q(g(x),b)∧～R(x)《人工智能》第三章谓词逻辑与归结原理谓词归结子句形(Skolem标准形)•Skolem定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。注意：谓词公式G的Skolem标准形同G并不等值。《人工智能》第三章谓词逻辑与归结原理谓词归结子句形•子句与子句集–文字：不含任何连接词的谓词公式。–子句：一些文字的析取（谓词的和）。–空子句：不含任何文字的子句。记作NIL或□–子句集：所有子句的集合。–对于任何一个谓词公式G，都可以通过Skolem标准形，建立起一个子句集与之对应。《人工智能》第三章谓词逻辑与归结原理谓词归结子句形•子句集S的求取：–将谓词公式G转换成前束范式；–生成Skolem标准形；–将各个子句提出，以“，”取代“Λ”，并表示为集合形式。《人工智能》第三章谓词逻辑与归结原理谓词归结子句形•定理3.1谓词公式G是不可满足的，当且仅当其子句集S是不可满足的。–G与S不等价，但在不可满足的意义下是一致的。注意：G真不一定S真，而S真必有G真。即：S=G《人工智能》第三章谓词逻辑与归结原理谓词归结子句形•定理3.1的推广–对于形如G=G1ΛG2ΛG3Λ…ΛGn的谓词公式–G的子句集可以分解成几个部分单独处理。–有SG=S1US2US3U…USn则SG与S1US2US3U…USn在不可满足的意义上是一致的。即SG不可满足=S1US2US3U…USn不可满足。可以对一个复杂的谓词公式分而治之。《人工智能》第三章谓词逻辑与归结原理求取子句集例(1)例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是他的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：•P(x,y)表示y是x的父亲•Q(x,y)表示y是x的祖父•ANS(x)表示问题的解答《人工智能》第三章谓词逻辑与归结原理求取子句集例(2)对于第一个条件，“如果y是x的父亲，z又是y的父亲，则z是x的祖父”，一阶逻辑表达式如下：A1：(x)(y)(z)(P(x,y)∧P(y,z)→Q(x,z))SA1：～P(x,y)∨～P(y,z)∨Q(x,z)对于第二个条件：“每个人都有父亲”，一阶逻辑表达式：A2：(x)(y)P(x,y)SA2：P(x,f(x))对于结论：某个人是他的祖父B：(x)(y)Q(x,y)否定后得到子句：～((x)(y)Q(x,y))∨ANS(y)S～B：～Q(x,y)∨ANS(y)则得到的相应的子句集为：{SA1，SA2，S～B}《人工智能》第三章谓词逻辑与归结原理置换与合一•一阶谓词逻辑得归结比命题逻辑的归结要复杂的多，其中一个原因就是谓词逻辑公式中含有个体变量与函数。•如P(x)∨Q(y)与~P(a)∨R(z)•所以要考虑置换与合一。即对变量作适当的替换。《人工智能》第三章谓词逻辑与归结原理置换•置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。•定义：置换是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，x1,x2,…,xn是互不相同的变量，t1,t2,…,tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。例如：{a/x，c/y，f(b)/z}是一个置换。{g(y)/x，f(x)/y}不是一个置换。《人工智能》第三章谓词逻辑与归结原理置换的合成•设＝{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);–当yi{x1,x2,…,xn}时，删去uj/yj(j=1,2,…,m)最后剩下的元素所构成的集合。合成即是对ti先做置换然后再做置换《人工智能》第三章谓词逻辑与归结原理置换的合成•例：设：＝{f(y)/x,z/y}，＝{a/x,b/y,y/z}，求与的合成。解：先求出集合{f(b/y)/x,(y/z)/y,a/x,b/y,y/z}＝{f(b)/x,y/y,a/x,b/y,y/z}其中，f(b)/x中的f(b)是置换作用于f(y)的结果；y/y中的y是置换作用于z的结果。在该集合中，y/y满足定义中的条件i，需要删除；a/x，b/y满足定义中的条件ii，也需要删除。最后得·＝{f(b)/x，y/z}《人工智能》第三章谓词逻辑与归结原理合一•合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。•定义：设有公式集F＝{F1，F2，…，Fn}，若存在一个置换，可使F1＝F2＝…=Fn，则称是F的一个合一。同时称F1，F2，...，Fn是可合一的。•例：设有公式集F＝{P(x,y,f(y)),P(a,g(x),z)}，则＝{a/x,g(a)/y,f(g(a))/z}是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。《人工智能》第三章谓词逻辑与归结原理最一般合一（mgu）•设σ是谓词公式集F的一个合一，如果对F的任意一个合一都存在一个置换λ，使得θ=σ.λ，则称σ是一个最一般合一。•最一般合一求取方法–令W={F1,F2}–令k=0,W0=W,σ0=ε–如果Wk已合一，停止，σk=mgu,否则找Dk–若Dk中存在元素vk和tk，其中，vk不出现在tk中，转下一步，否则，不可合一。–令σk+1=σk.{tk/vk},Wk+1=Wk{tk/vk}=Wσk+1–K=k+1转第3步。《人工智能》第三章谓词逻辑与归结原理最一般合一（mgu）例：W={P(a,x,f(g(y))),P(z,f(a),f(u))},其中，F1＝P(a,x,f(g(y)))，F2＝P(z,f(a),f(u))求F1和F2的mgu解：由mgu算法(1)W={P(a,x,f(g(y))),P(z,f(a),f(u))}(2)W0=W,σ0=ε(3)W0未合一，从左到右找差异集，有D0={a,z}(4)取V0=z,t0＝a《人工智能》第三章谓词逻辑与归结原理最一般合一（mgu）(5)令σ1=σ0.{t0/v0}={a/z}W1=W0σ1={P(a,x,f(g(y))),P(a,f(a),f(u))}(3)’W1未合一，找差异集，有D1={x,f(a)}(4)’取v1=x,t1＝f(a)(5)’令σ2=σ1.{t1/v1}={a/z,f(a)/x}W2=W1σ2={P(a,f(a),f(g(y))),P(a,f(a),f(u))}(3)’’W2未合一，找差异集，有D2={g(y),u}(4)’’取v2=u,t2＝g(y)《人工智能》第三章谓词逻辑与归结原理最一般合一（mgu）(5)’’令σ3=σ2.{t2/v2}={a/z,f(a)/x,g(y)/u}W3=W2σ3={P(a,f(a),f(g(y))),P(a,f(a),f(g(y)))}(3)’’’W3已合一σ3={a/z,f(a)/x,g(y)/u}便是F1和F2的mgu。算法的第(4)步，当不存在vk或不存在tk或出现差异集为{x,f(x)},都会导致不可合一。此时，算法返回失败。《人工智能》第三章谓词逻辑与归结原理最一般合一（mgu）谓词逻辑的归结方法和命题逻辑基本相同，但在进行归结之前，应采用最一般合一方法对待归结的一对子句进行置换。然后再判断是否可以进行归结。《人工智能》第三章谓词逻辑与归结原理归结原理•归结时的注意事项：1.谓词的一致性，P()与Q()，不可以2.常量的一致性，P(a,…)与P(b,….)，不可以。3.变量与函数，P(a,x,….)与P(x,f(x),…)，不可以；4.不能同时消去两个互补对，P∨Q与～P∨～Q得空，不可以5.先进行内部简化再进行置换与合并。《人工智能》第三章谓词逻辑与归结原理归结原理•归结的过程写出谓词关系公式→用反演法写出谓词表达式→SKOLEM标准形→求子句集S→对S中可归结的子句做归结→归结式仍放入S中，反复归结过程→得到空子句命题得证。《人工智能》第三章谓词逻辑与归结原理例题“快乐学生”问题例：假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。•解：先将问题用谓词表示如下：•R1:任何通过计算机考试并获奖的人都是快乐的(x)((Pass(x,computer)∧Win(x,prize))→Happy(x))•R2:“任何肯学习或幸运的人都可以通过所有考试”(x)(y)(Study(x)∨Lucky(x)→Pass(x,y))《人工智能》第三章谓词逻辑与归结原理例题“快乐学生”问题•R3:“张不肯学习但他是幸运的”～Study(zhang)∧Lucky(zhang)•R4:“任何幸运的人都能获奖”(x)(Luck(x)→Win(x,prize))•结论：“张是快乐的”的否定～Happy(zhang)《人工智能》第三章谓词逻辑与归结原理•由R1及逻辑转换公式:P∧W→H=～（P∧W）∨H，得(1)～Pass(x,computer