人工智能,第三章2说课材料.ppt

《人工智能,第三章2说课材料.ppt》由会员分享，可在线阅读，更多相关《人工智能,第三章2说课材料.ppt（81页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、谓词谓词(wi c)归结子句形归结子句形(Skolem 标准形标准形)为了能够像命题逻辑那样进行归结，首先必须解决谓词逻辑中的量词问题。前束范式：如果A中的一切量词都位于该公式的最左边（不含否定词），且这些(zhxi)量词的辖域都延伸到公式的末端。人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑与谓词逻辑与归结原理归结原理第一页，共81页。谓词归结谓词归结(guji)子句形子句形(Skolem 标准形标准形)Skolem标准形前束范式中消去所有的量词。Skolem函数 如果某个存在量词是在其他任意量词的辖域内，就存在某种依赖关系(gun x)，可以用一个函

2、数描述这种依赖关系(gun x)，叫做Skolem函数。人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第二页，共81页。谓词谓词(wi c)归结子句形归结子句形(Skolem 标准形标准形)量词消去原则：存 在 量 词。将 该 量 词 约 束 的 变 量(binling)用任意常量（a，b等）或任意变量(binling)的函数（f(x)，g(y)等）代替。左边有任意量词的存在量词，消去时该变量(binling)改写成为任意量词的函数；如没有，改写成为常量。任意量词。简单地省略掉该量词。人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑

3、与归结原理逻辑与归结原理第三页，共81页。谓词归结子句谓词归结子句(z j)形形(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)第二步，深入到量词(lingc)内部，得：(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)第三步，任意量词(lingc)左移，得：(x)(y)P(a,x,y)(y)(Q(y,b)R(x)人工智能第三章人工智能第三章 谓词谓词(wi c)(wi

4、 c)逻辑与归结原理逻辑与归结原理第四页，共81页。谓词归结谓词归结(guji)子句形子句形(Skolem 标准形标准形)第四步，变量易名，存在量词左移，直至所有的量词移到前面(qin mian)，得：(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)由此得到前述范式人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第五页，共81页。谓词归结谓词归结(guji)子句形子句形(Skolem 标准形标准形)第五步，消去存在量词，略去任意量词消

5、去(y)，因为它左边只有(zhyu)(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)人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第六页，共81页。谓词归结谓词归结(guji)子句形子句形(Skolem 标准形标准形)Skolem定理：谓词逻辑的任意公式(gngsh)都可以化为与之等价的前束范式，但其前束范式不唯一

6、。注意：谓词公式(gngsh)G的Skolem标准形同G并不等值。人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第七页，共81页。谓词归结谓词归结(guji)子句形子句形子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。空子(kngzi)句：不含任何文字的子句。记作NIL或子句集：所有子句的集合。对于任何一个谓词公式G，都可以通过Skolem标准形，建立起一个子句集与之对应。人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑与谓词逻辑与归结原理归结原理第八页，共81页。谓词谓词(wi c

7、)归结子句形归结子句形子句集S的求取：将谓词公式(gngsh)G转换成前束范式；生成Skolem标准形；将各个子句提出，以“，”取代“”，并表示为集合形式。人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第九页，共81页。谓词归结谓词归结(guji)子句形子句形 定理3.1 谓词公式G是不可满足(mnz)的，当且仅当其子句集 S是不可满足(mnz)的。G与S不等价，但在不可满足(mnz)的意义下是一致的。注意：G真不一定S真，而S真必有G真。即：S=G人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第十页，共8

8、1页。谓词谓词(wi c)归结子句形归结子句形定理3.1的推广对于形如G=G1 G2 G3 Gn 的谓词公式(gngsh)G的子句集可以分解成几个部分单独处理。有 SG=S1 U S2 U S3 U U Sn则SG 与 S1 U S2 U S3 U U Sn在不可满足的意义上是一致的。即SG 不可满足 S1 U S2 U S3 U U Sn不可满足。可以对一个复杂的谓词公式(gngsh)分而治之。人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第十一页，共81页。求取求取(qi q)子句集例子句集例(1)例：对所有的x,y,z来说，如果y是x的父亲，z

9、又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是他的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词(wic)：P(x,y)表示y是x的父亲Q(x,y)表示y是x的祖父ANS(x)表示问题的解答人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑与归结原理谓词逻辑与归结原理第十二页，共81页。求取求取(qi q)子句集例子句集例(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)

10、Q(x,z)对于第二个条件：“每个人都有父亲”，一阶逻辑表达式：A2：(x)(y)P(x,y)SA2：P(x,f(x)对于结论(jiln)：某个人是他的祖父B：(x)(y)Q(x,y)否定后得到子句：(x)(y)Q(x,y)ANS(y)SB：Q(x,y)ANS(y)则得到的相应的子句集为：SA1，SA2，SB人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第十三页，共81页。置换置换(zhhun)与合一与合一一阶谓词逻辑得归结比命题逻辑的归结要复杂的多，其中一个原因就是谓词逻辑公式中含有个体变量与函数。如P(x)Q(y)与P(a)R(z)所以要考虑置换

11、与合一(hy)。即对变量作适当的替换。人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第十四页，共81页。置换置换(zhhun)置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量(binling)。定义：置换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，x1,x2,xn是互不相同的变量(binling)，t1,t2,tn是 不 同 于 xi的 项（常 量、变 量(binling)、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。例如：a/x，c/y，f(b)/z是一个置换。g(

12、y)/x，f(x)/y不是一个置换。人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第十五页，共81页。置换置换(zhhun)的合成的合成设t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,un/yn，是两个置换(zhhun)。则与的合成也是一个置换(zhhun)，记作。它是从集合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)最后剩下的元素所构成的集合。合成即是对ti先做置换(zhhun)然后

13、再做置换(zhhun)人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑谓词逻辑与归结原理与归结原理第十六页，共81页。置换置换(zhhun)的合成的合成例：设：f(y)/x,z/y，a/x,b/y,y/z，求与的合成。解：先求出集合f(b/y)/x,(y/z)/y,a/x,b/y,y/zf(b)/x,y/y,a/x,b/y,y/z其中，f(b)/x中的f(b)是置换作用于f(y)的结果；y/y中的y是置换作用于z的结果。在该集合中，y/y满足定义中的条件(tiojin)i，需要删除；a/x，b/y满足定义中的条件(tiojin)ii，也需要删除。最后得f(

14、b)/x，y/z人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第十七页，共81页。合一合一(h y)合一可以简单地理解为“寻找相对变量的置换(zhhun)，使两个谓词公式一致”。定义：设有公式集FF1，F2，Fn，若存在一个置换(zhhun)，可使F1F2=Fn，则称是F的一个合一。同时称F1，F2，.，Fn是可合一的。例：设有公式集FP(x,y,f(y),P(a,g(x),z)，则a/x,g(a)/y,f(g(a)/z是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第

15、三章 谓词逻辑与归结原理谓词逻辑与归结原理第十八页，共81页。最一般最一般(ybn)合一（合一（mgu）设是谓词公式集F的一个合一，如果对F的任意(rny)一个合一都存在一个置换，使得=.，则称是一个最一般合一。最一般合一求取方法令W=F1,F2令k=0,W0=W,0=如果Wk已合一，停止，k=mgu,否则找Dk若Dk中存在元素vk和tk，其中，vk不出现在tk中，转下一步，否则，不可合一。令k+1=k.tk/vk,Wk+1=Wktk/vk=Wk+1K=k+1转第3步。人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第十九页，共81页。最一般最一般(y

16、bn)合一（合一（mgu）例：W=P(a,x,f(g(y),P(z,f(a),f(u),其中(qzhng)，F1P(a,x,f(g(y)，F2P(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,t0a人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第二十页，共81页。最一般最一般(ybn)合一（合一（mgu）(5)令1=0.t0/v0=a/zW1=W01=P(a,x,f(g(y),P(a,f(a

17、),f(u)(3)W1 未 合 一(h y)，找 差 异 集，有D1=x,f(a)(4)取v1=x,t1f(a)(5)令2=1.t1/v1=a/z,f(a)/xW2=W12=P(a,f(a),f(g(y),P(a,f(a),f(u)(3)W2 未合一(h y)，找差异集，有D2=g(y),u(4)取v2=u,t2g(y)人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第二十一页，共81页。最一般最一般(ybn)合一（合一（mgu）(5)令3=2.t2/v2=a/z,f(a)/x,g(y)/uW3=W23=P(a,f(a),f(g(y),P(a,f(a)

18、,f(g(y)(3)W3已合一3=a/z,f(a)/x,g(y)/u便是F1和F2的mgu。算法(sunf)的第(4)步，当不存在vk或不存在tk或出现差异集为x,f(x),都会导致不可合一。此时，算法(sunf)返回失败。人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第二十二页，共81页。最一般最一般(ybn)合一（合一（mgu）谓词逻辑的归结方法和命题逻辑基本相同，但在进行归结之前，应采用最一般合一方法对待归结的一对子句(zj)进行置换。然后再判断是否可以进行归结。人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)

19、原理原理第二十三页，共81页。归结归结(guji)原理原理归结时的注意事项：谓词的一致性，P()与Q()，不可以常量的一致性，P(a,)与P(b,.)，不可以。变量与函数，P(a,x,.)与P(x,f(x),)，不可以；不能同时消去两个互补对，PQ与PQ得空，不可以先进行(jnxng)内部简化再进行(jnxng)置换与合并。人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第二十四页，共81页。归结归结(guji)原理原理归结的过程写出谓词关系公式用反演法写出谓词表达式SKOLEM标准形求子句集S对S中可归结的子句做归结归结式仍放入S中，反复(fnf)归

20、结过程得到空子句命题得证。人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第二十五页，共81页。例题例题“快乐快乐(kuil)学生学生”问问题题例：假设任何通过(tnggu)计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过(tnggu)所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。解：先将问题用谓词表示如下：R1:任何通过(tnggu)计算机考试并获奖的人都是快乐的(x)(Pass(x,computer)Win(x,prize)Happy(x)R2:“任何肯学习或幸运的人都可以通过(tnggu)所有考试”(x

21、)(y)(Study(x)Lucky(x)Pass(x,y)人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑与归结谓词逻辑与归结原理原理第二十六页，共81页。例题例题“快乐快乐(kuil)学生学生”问问题题R3:“张不肯学习但他是幸运(xngyn)的”Study(zhang)Lucky(zhang)R4:“任何幸运(xngyn)的人都能获奖”(x)(Luck(x)Win(x,prize)结论：“张是快乐的”的否定Happy(zhang)人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑与归结谓词逻辑与归结原理原理第二十七

22、页，共81页。由R1及逻辑转换公式(gngsh):PWH=（PW）H，得(1)Pass(x,computer)Win(x,prize)Happy(x)由R2：(2)Study(y)Pass(y,z)(3)Lucky(u)Pass(u,v)由R3：(4)Study(zhang)(5)Lucky(zhang)由R4：(6)Lucky(w)Win(w，prize)由结论：(7)Happy(zhang)（结论的否定）(8)Pass(w,computer)Happy(w)Luck(w)(1)(6)，w/x(9)Pass(zhang,computer)Lucky(zhang)(8)(7)，zhang/w(

23、10)Pass(zhang,computer)(9)(5)(11)Lucky(zhang)(10)(3)，zhang/u,computer/v(12)(11)(5)人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第二十八页，共81页。第三章谓词逻辑与归结第三章谓词逻辑与归结(guji)原理原理概述命题逻辑谓词(wic)逻辑的归结法归结过程的控制策略Herbrand定理人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第二十九页，共81页。第三章谓词逻辑与归结第三章谓词逻辑与归结(guji)原理原理概述命题逻辑(l

24、uj)谓词逻辑(luj)的归结法归结过程的控制策略Herbrand定理人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第三十页，共81页。归结归结(guji)过程的控制策略过程的控制策略要解决的问题：归结方法的知识爆炸。控制策略的目的归结点尽量少控制策略的原则给出控制策略，以使仅对选择合适(hsh)的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第三十一页，共81页。控制策略的方法控制策略的方法(fngf)(1)删除策略归类：

25、设有两个子句C和D，若有置换使得(sh de)C D成立，则称子句C把子句D归类。若对S使用归结推理过程中，当归结式Cj是重言式和Cj被S中子句和子句集的归结式Ci(ij)所归类时，便将Cj删除。这样的推理过程便称作使用了删除策略的归结过程。人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第三十二页，共81页。控制策略的方法控制策略的方法(fngf)(1)删除(shnch)策略如P(x)P(x),P(x)Q(x)P(x)P(x)归类P(y)Q(z)=y/x纯文字删除(shnch)。如果某文字L在子句集中不存在可与之互补的文字L，则称该文字为纯文字。如S

26、=PQR,QR,Q,R尽管使用删除(shnch)策略的归结，少做了归结但不影响产生空子句，就是说删除(shnch)策略的归结推理是完备的。人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第三十三页，共81页。控制策略的方法控制策略的方法(fngf)(2)支撑集策略(cl)支撑集：设有不可满足子句集S的子集T，如果S-T是可满足的，则T是支撑集。采用支撑集策略(cl)时，从开始到得到空子句的整个归结过程中，只选取不同时属于S-T的子句，在其间进行归结。就是说，至少有一个子句来自于支撑集T或由T导出的归结式。人工智能人工智能(rn n zh nn)(rn

27、n zh nn)第三章第三章 谓词逻辑与谓词逻辑与归结原理归结原理第三十四页，共81页。控制策略的方法控制策略的方法(fngf)(2)支撑集策略例如：A1A2A3B中的B可以作为支撑集使用。要求每一次参加归结的亲本子句(z j)中，至少应该有一个是由目标公式的否定（B）所得到的子句(z j)或者它们的后裔。支撑集策略的归结是完备的。同样，所有可归结的谓词公式都可以用采用支撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句(z j)的非，即SB。人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第三十五页，共81页

28、。ST可满足支撑集示意图人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第三十六页，共81页。控制策略的方法控制策略的方法(fngf)(2)支撑集策略例如：S(1)I(X)R(X)目标公式的否定得到(d do)的子句(2)I(a)(3)R(Y)VL(Y)(4)L(a)S1：(5)R(a)(1)与(2)归结(6)I(x)VL(x)(1)与(3)归结(7)L(a)(2)与(6)归结(8)NIL (4)与(7)归结人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第三十七页，共81页。控制策略的方法控制策略的方法(fn

29、gf)(3)语义归结策略语义归结策略是将子句S按照一定的语义分成两部分，约定每部分内的子句间不允许作归结。同时还引入了文字次序，约定归结时其中(qzhng)的一个子句的被归结文字只能是该子句中“最大”的文字。语义归结策略的归结是完备的。人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑与归结谓词逻辑与归结原理原理第三十八页，共81页。控制策略的方法控制策略的方法(fngf)(4)线性归结 线性归结策略首先从子句集中选取一个称作顶子句的子句C0开始(kish)作归结。归结过程中所得到的归结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现

30、的归结式Cj(ji)。即，如下图所示归结得到的新子句立即参加归结。线性归结是完备的。人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第三十九页，共81页。C0C1C2C3C4C5空线性归结策略示意图人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第四十页，共81页。控制策略的方法控制策略的方法(fngf)(5)单元归结策略单元归结策略要求在归结过程中，每次归结都有一个子句是单元子句（只含一个文字的子句）或单元因子。显而易见，此种方法可以简单(jindn)地削去另一个非单子句中的一个因子，使其长度减少，构成简单(

31、jindn)化，归结效率较高。初始子句集中没有单元子句时，单元归结策略无效。所以说“反之不成立”，即此问题不能采用单元归结策略。人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑谓词逻辑与归结原理与归结原理第四十一页，共81页。控制策略的方法控制策略的方法(fngf)(6)输入归结策略与单元归结策略相似，输入归结策略要求在归结过程中，每一次归结的两个子句中必须(bx)有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结，造成恶性循环。可以减少不必要的归结次数。如同单元归结策略，不是所有的可归结谓词公式的最后结论都是可以从原始子句集中的得到的。人工

32、智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第四十二页，共81页。第三章谓词第三章谓词(wi c)逻辑与归结逻辑与归结原理原理概述(ish)命题逻辑谓词逻辑的归结法归结过程的控制策略Herbrand定理人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑谓词逻辑与归结原理与归结原理第四十三页，共81页。第三章谓词逻辑与归结第三章谓词逻辑与归结(guji)原理原理概述命题逻辑谓词(wic)逻辑的归结法归结过程的控制策略Herbrand定理人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归

33、结原理第四十四页，共81页。HerbrandHerbrand定理定理(dngl)(dngl)问题：一阶逻辑(lu j)公式的永真性（永假性）的判定是否能在有限步内完成？人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第四十五页，共81页。HerbrandHerbrand定理定理(dngl)(dngl)1936年图灵(Turing)和邱吉(Church)互相(h xing)独立地证明了：“没有一般(ybn)的方法使得在有限步内判定一阶逻辑的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步内判定它是永真（或永假）。对于非永真（

34、或永假）的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。”人工智能第三章人工智能第三章 谓词逻辑与归结原理谓词逻辑与归结原理第四十六页，共81页。HerbrandHerbrand定理定理(dngl)(dngl)Herbrand的思想定义：公式G永真：对于G的所有解释，G都为真。思想：寻找(xnzho)一个已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的解释存在，并且算法在有限步内停止。人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第四十七页，共81页。HerbrandHerbrand定理定理(dngl)(dngl

35、)H域H解释(jish)语义树结论：Herbrand定理人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第四十八页，共81页。HerbrandHerbrand定理定理(dngl)(dngl)H域H解释(jish)语义树结论：Herbrand定理人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑与谓词逻辑与归结原理归结原理第四十九页，共81页。Herbrand定理定理(dngl)（H域）域）基本方法：因为量词是任意的，所讨论的个体变量域D是任意的，所以解释的个数是无限、不可数的。简化讨论域。建立一个比较简单、特殊的域，

36、使得(shde)只要在这个论域上，该公式是不可满足的。此域称为H域。人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第五十页，共81页。D域H域H域与D域关系示意图人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第五十一页，共81页。H H域例题域例题(lt)(lt)设子句集S=P(x),Q(y,f(z,b),R(a)，求H域解：H0 a,b为子句集中出现(chxin)的常量H1 a,b,f(a,b),f(a,a),f(b,a),f(b,b)H2 a,b,f(a,b),f(a,a),f(b,a),f(b,b)，

37、f(a,f(a,b),f(a,f(a,a),f(a,f(b,a),f(a,f(b,b),f(b,f(a,b),f(b,f(a,a),f(b,f(b,a),f(b,f(b,b),f(f(a,b),f(a,b),f(f(a,b),f(a,a),f(f(a,b),f(b,a),f(f(a,b),f(b,b),f(f(a,a),f(a,b),f(f(a,a),f(a,a),f(f(a,a),f(b,a),f(f(a,a),f(b,b),f(f(b,a),f(a,b),f(f(b,a),f(a,a),f(f(b,a),f(b,a),f(f(b,a),f(b,b),f(f(b,b),f(a,b),f(f(

38、b,b),f(a,a),f(f(b,b),f(b,a),f(f(b,b),f(b,b)H=H1H2H3人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第五十二页，共81页。Herbrand定理定理(dngl)（H域）域）几个基本概念f（tn）：f为子句集S中的所有函数变量(binling)。t1,t2,tn为S的H域的元素。通过它们来讨论永真性。原子集A：谓词套上H域的元素组成的集合。如A=所有形如P(t1,t2,tn)的元素即把H中的东西填到S的谓词里去。S中的谓词是有限的，H是可数的，因此，A也是可数的。人工智能人工智能(rn n zh nn)(r

39、n n zh nn)第三章第三章 谓词逻辑谓词逻辑与归结原理与归结原理第五十三页，共81页。原子原子(yunz)(yunz)集例题集例题上例题的原子集为：A=P(a),Q(a,a),R(a),P(b),Q(b,a),Q(b,b),Q(a,b),R(b),P(f(a,b),Q(f(a,b),f(a,b),R(f(a,b),P(f(a,a),P(f(b,a),P(f(b,b),)一旦原子集内真值确定好（规定(gudng)好），则S在H上的真值可确定。成为可数问题。人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第五十四页，共81页。HerbrandHerb

40、rand定理定理(dngl)(dngl)H域H解释(jish)语义树结论：Herbrand定理人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑与归结谓词逻辑与归结原理原理第五十五页，共81页。HerbrandHerbrand定理定理(dngl)(dngl)H域H解释语义树结论(jiln)：Herbrand定理人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑谓词逻辑与归结原理与归结原理第五十六页，共81页。Herbrand定理定理(dngl)（H解解释）释）解释I：谓词公式G在论域D上任何一组真值的指定称为一个(y)解释

41、。H解释：子句集S在的H域上的解释称为H解释。问题：对于所有的解释，全是假才可判定。因为所有解释代表了所有的情况，如可穷举，问题便可解决。人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第五十七页，共81页。Herbrand定理定理(dngl)（H解解释）释）如下三个定理保证了归结法的正确性：定理1：设I是S的论域D上的解释，存在对应于I的H解释I*，使得若有S|I=T，必有S|I*=T。定理2：子句集S是不可满足的，当且仅当所有(suyu)的S的H解释下为假。定理3：子句集S是不可满足的，当且仅当对每一个解释I下，至少有S的某个子句的某个基例为假。人

42、工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第五十八页，共81页。Herbrand定理定理(dngl)（H解解释）释）基例S中某子句中所有变元符号均以S的H域中的元素代入时，所得的基子句C称为C的一个(y)基例。若一个(y)子句为假，则此解释为假。一般来说，D是无穷不可列的，因此，子句集S也是无穷不可列的。但S确定后H是无穷可列的。不过在H上证明S的不可满足性仍然是不可能的。解决问题的方法：语义树人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第五十九页，共81页。HerbrandHerbrand定理定理(d

43、ngl)(dngl)H域H解释(jish)语义树结论：Herbrand定理人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑与谓词逻辑与归结原理归结原理第六十页，共81页。HerbrandHerbrand定理定理(dngl)(dngl)H域H解释(jish)语义树结论：Herbrand定理人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第六十一页，共81页。Herbrand定理定理(dngl)（语义（语义树）树）构成方法原子集中所有元素(yun s)逐层添加的一棵二叉树。将元素(yun s)的是与非分别标记在两侧的分

44、枝上（可不完全画完）。特点一般情况H是无限可数集，S的语义树是无限树。人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第六十二页，共81页。N0P(a)N12Q(a)P(f(a)N24N31N38无限语义树N11P(a)Q(a)Q(a)Q(a)P(f(a)N21SP(x)Q(x)，P(f(y)，Q(f(y)人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第六十三页，共81页。Herbrand定理定理(dngl)（语义（语义树）树）意义SHA语义树可以理解语义树为H域的图形解释。目的：把每个解释都摊开。语义树中包

45、含原子集的全部元素。因此，语义树是完全的。每一个直到叶子节点(jidin)的分支对应S的一个解释。可以通过对语义树每一个分支来计算S的真值。如果每个基例都为假，则可认为是不可满足的。人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第六十四页，共81页。Herbrand定理定理(dngl)（语义（语义树）树）几个概念失败结点：当（由上）延伸到点N时，I(N)已表明了S的某子句的某基例为假。但N以前(yqin)尚不能判断这个事实。就称N为失败结点。封闭语义树：如果S的完全语义树的每个分枝上都有一个失败结点，就称它是一棵封闭语义树。人工智能第三章人工智能第三

46、章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第六十五页，共81页。N0P(a)N1,2Q(a)P(f(a)N2,4N3,1N3,8N1,1N4,2N4,1N2,1N3,2N2,2N3,6N4,9N4,10N4,13N4,14封闭语义树Q(f(a)SP(x)Q(x)，P(f(y)，Q(f(y)人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第六十六页，共81页。HerbrandHerbrand定理定理(dngl)(dngl)H域H解释(jish)语义树结论：Herbrand定理人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)

47、(lu j)与归结原理与归结原理第六十七页，共81页。HerbrandHerbrand定理定理(dngl)(dngl)H域H解释(jish)语义树结论：Herbrand定理人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原理第六十八页，共81页。Herbrand定理定理(dngl)（结论）（结论）Herbrand定理：子句集S是不可满足的，当且仅当对应于S的完全语义数是棵有限(yuxin)封闭树。子句集S是不可满足的，当且仅当存在不可满足的S的有限(yuxin)基例集。人工智能第三章人工智能第三章 谓词逻辑谓词逻辑(lu j)(lu j)与归结原理与归结原

48、理第六十九页，共81页。Herbrand定理定理(dngl)（结论）（结论）定理(dngl)的意义Herbrand定理(dngl)已将证明问题转化成了命题逻辑问题。由此定理(dngl)保证，可以放心的用机器来实现自动推理了。（归结原理）注意Herbrand定理(dngl)给出了一阶逻辑的半可判定算法，即仅当被证明定理(dngl)是成立时，使用该算法可以在有限步得证。而当被证定理(dngl)并不成立时，使用该算法得不出任何结论。但是人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第七十页，共81页。Herbrand定理定理(dngl)（结论）（结论）仍存

49、在的问题：基例集序列元素的数目随子句集的元素数目成指数地增加。因此，Herbrand定理是30年代提出的，始终没有显著的成绩。直至1965年Robinson提出了归结(guji)原理。人工智能人工智能(rn n zh nn)(rn n zh nn)第三章第三章 谓词逻辑与归结谓词逻辑与归结原理原理第七十一页，共81页。归结归结(guji)原理与原理与Herbrand定理定理归结过程(guchng)是语义树的倒塌过程(guchng)最后归结出空，就是剩一个根节点，就说明语义树是有限封闭的，证明结束。人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第七十二

50、页，共81页。人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第七十三页，共81页。人工智能第三章人工智能第三章 谓词逻辑与归结谓词逻辑与归结(guji)(guji)原理原理第七十四页，共81页。习题：设已知：(1)能阅读者是识字的；(2)海豚不识字；(3)有些海豚是很聪明的。试证明：有些聪明者并不能阅读。证 首先(shuxin)，定义如下谓词：R(x)：x能阅读。L(x)：x识字。I(x)：x是聪明的。D(x)：x是海豚。人工智能第三章人工智能第三章 谓词谓词(wi c)(wi c)逻辑与归结原理逻辑与归结原理第七十五页，共81页。然后把上述各语句翻