第三章人工智能蔡自兴

人工智能原理第三章归结推理方法,1,第三章归结推理方法,概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理,人工智能原理第三章归结推理方法,2,人工智能原理第三章归结推理方法,3,第三章归结推理方法,概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制,人工智能原理第三章归结推理方法,4,概述,归结原理由J.A.Robinson由1965年提出。是一阶逻辑中至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即：有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。,人工智能原理第三章归结推理方法,5,第三章归结推理方法,概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理,人工智能原理第三章归结推理方法,6,命题逻辑的归结法,命题逻辑基础：定义：合取式：p与q，记做pq析取式：p或q，记做pq蕴含式：如果p则q，记做pq等价式：p当且仅当q，记做pq。,人工智能原理第三章归结推理方法,7,命题逻辑基础,定义：若A无成假赋值，则称A为重言式或永真式；若A无成真赋值，则称A为矛盾式或永假式；若A至少有一个成真赋值，则称A为可满足的；析取范式：仅由有限个简单合取式组成的析取式。合取范式：仅由有限个简单析取式组成的合取式。,人工智能原理第三章归结推理方法,8,命题逻辑基础,基本等值式交换率：pqqp；pqqp结合率：(pq)rp(qr);(pq)rp(qr)分配率：p(qr)(pq)(pr)；p(qr)(pq)(pr),人工智能原理第三章归结推理方法,9,命题逻辑基础,基本等值式摩根率:(pq)pq；(pq)pq吸收率:p(pq)p；p(pq)p同一律:p0p；p1p蕴含等值式:pqpq假言易位式:pqqp,人工智能原理第三章归结推理方法,10,命题举例,命题：能判断真假（不是既真又假）的陈述句。简单陈述句描述事实、事物的状态、关系等性质。例如：11+1=22雪是黑色的。3北京是中国的首都。4到冥王星去渡假。判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第4句的真值现在是假，随着人类科学的发展，有可能变成真，但不管怎样，真值是唯一的。因此，以上4个例子都是命题。而例如：1快点走吧！2到那去？3x+y10等等句子，都不是命题。,人工智能原理第三章归结推理方法,11,命题表示公式（1）,将陈述句转化成命题公式。如：设“下雨”为p，“骑车上班”为q，1“只要不下雨，我骑自行车上班”。p是q的充分条件，因而，可得命题公式：pq2“只有不下雨，我才骑自行车上班”。p是q的必要条件，因而，可得命题公式：qp,人工智能原理第三章归结推理方法,12,命题表示公式（2）,例如：1“如果我进城我就去看你，除非我很累。”设：p，我进城；q，去看你；r，我很累。则有命题公式：r(pq)。2“应届高中生，得过数学或物理竞赛的一等奖，保送上北京大学。”设：p，应届高中生，q，保送上北京大学上学，r，是得过数学一等奖。t，是得过物理一等奖。则有命题公式公式：p(rt)q。,人工智能原理第三章归结推理方法,13,命题逻辑的推理规则,附加：A=（AB)简化：(AB)=A假言推理:(AB)A)=B拒取式：(AB)B)=A析取三段论：(AB)A)=B假言三段论：(AB)(BC)=(AC)等价三段论：(AB)(BC)=(AC)构造性两难：(AB)(CD)（AC)=(BD),人工智能原理第三章归结推理方法,14,利用规则构造证明,例：前提：pq,pr,st,sr,t结论：q证明：st前提引入t前提引入s拒取规则sr前提引入rpr前提引入p拒取规则pq前提引入q析取三段论,人工智能原理第三章归结推理方法,15,命题逻辑的归结法,基本单元：简单命题（陈述句）例：命题：A1、A2、A3和B求证：A1A2A3成立，则B成立，即：A1A2A3B反证法：证明A1A2A3B是矛盾式（永假式）,人工智能原理第三章归结推理方法,16,归谬法证明,例：前提：p（rs)q),p,s结论：q证明：p（rs)q)前提引入p前提引入（rs)q假言推理q否定结论引入（rs)拒取式s前提引入s简化ss合取得到矛盾结果,人工智能原理第三章归结推理方法,17,命题逻辑的归结法,归结原理是在谓词公式的子句集合之上进行归结的，因而首先讨论子句集。建立子句集合取范式：命题、命题和的与，如：P（PQ）（PQ）子句集S：合取范式形式下的子命题（元素）的集合例：命题公式：P（PQ）（PQ）子句集S：S=P,PQ,PQ,人工智能原理第三章归结推理方法,18,命题逻辑的归结法,归结式消除互补对，求新子句得到归结式。如子句：C1,C2，归结式：R(C1,C2)=C1C2注意：C1C2R(C1,C2)，反之不一定成立。,人工智能原理第三章归结推理方法,19,命题逻辑的归结法,归结过程将命题写成合取范式求出子句集对子句集使用归结推理规则归结式作为新子句参加归结归结式为空子句，S是不可满足的（矛盾），原命题成立。（证明完毕）谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。,人工智能原理第三章归结推理方法,20,命题逻辑归结例题（1）,例题，证明公式：(PQ)(QP)证明：（1）根据归结原理，将待证明公式转化成待归结命题公式：(PQ)(QP)（2）分别将公式前项化为合取范式：PQPQ结论求后的后项化为合取范式：(QP)(QP)QP两项合并后化为合取范式：（PQ）QP（3）则子句集为：PQ，Q，P,人工智能原理第三章归结推理方法,21,命题逻辑归结例题（2）,子句集为：PQ，Q，P（4）对子句集中的子句进行归结可得：1.PQ2.Q3.P4.Q，（1，3归结）5.，（2，4归结）由上可得原公式成立。,人工智能原理第三章归结推理方法,22,第三章归结推理方法,概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理,人工智能原理第三章归结推理方法,23,谓词归结原理基础,一阶逻辑基本概念个体词：表示主语的词谓词：刻画个体性质或个体之间关系的词量词：表示数量的词,人工智能原理第三章归结推理方法,24,谓词归结原理基础,小王是个工程师。8是个自然数。我去买花。小丽和小华是朋友。其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。,人工智能原理第三章归结推理方法,25,谓词归结原理基础,一阶逻辑公式及其解释个体常量：a,b,c个体变量：x,y,z谓词符号：P,Q,R量词符号：,人工智能原理第三章归结推理方法,26,谓词归结原理基础,例如：（1）所有的人都是要死的。（2）有的人活到一百岁以上。在个体域D为人类集合时，可符号化为：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(x),其中Q(x)表示x活到一百岁以上。在个体域D是全总个体域时，引入特殊谓词R(x)表示x是人，可符号化为：（1）x（R(x)P(x)）,其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)Q(x)），其中，R(x)表示x是人；Q(x)表示x活到一百岁以上。,人工智能原理第三章归结推理方法,27,谓词归结原理基础,量词否定等值式：(x）M（x）（y）M（y）(x）M（x）（y）M（y）量词分配等值式：(x）(P（x）Q（x）)(x）P（x）(x）Q（x）(x）(P（x）Q（x）)(x）P（x）(x）Q（x）消去量词等值式：设个体域为有穷集合（a1,a2,an）(x）P（x）P（a1）P（a2）P（an）(x）P（x）P（a1）P（a2）P（an）,人工智能原理第三章归结推理方法,28,谓词归结原理基础,量词辖域收缩与扩张等值式：(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(QP（x）)Q(x）P（x）(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(QP（x）)Q(x）P（x）,人工智能原理第三章归结推理方法,29,谓词归结子句形(Skolem标准形),SKOLEM标准形前束范式定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。,人工智能原理第三章归结推理方法,30,谓词归结子句形(Skolem标准形),即：把所有的量词都提到前面去，然后消掉所有量词(Q1x1)(Q2x2)(Qnxn)M(x1,x2,xn)约束变项换名规则：(Qx）M（x）（Qy）M（y）(Qx）M（x,z）（Qy）M（y,z）,人工智能原理第三章归结推理方法,31,谓词归结子句形(Skolem标准形),量词消去原则：消去存在量词“”，即将该量词约束的变量用任意常量（a,b）或任意变量函数(f(x)、g(y)）代替。略去任意量词“”。,人工智能原理第三章归结推理方法,32,谓词归结子句形(Skolem标准形),SKOLEM定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。SKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。,人工智能原理第三章归结推理方法,33,谓词归结子句形(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)(u)(v)(Q(v,b)R(u)第四步，存在量词左移，直至所有的量词移到前面，得：(x)(y)(u)(v)P(a,x,y)(Q(v,b)R(u)由此得到前述范式,人工智能原理第三章归结推理方法,34,谓词归结子句形(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),人工智能原理第三章归结推理方法,35,谓词归结子句形,子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S的求取：GSKOLEM标准形消去存在变量以“，”取代“”，并表示为集合形式。,人工智能原理第三章归结推理方法,36,谓词归结子句形,G是不可满足的S是不可满足的G与S不等价，但在不可满足的意义下是一致的。定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的S是不可满足的。注意：G真不一定S真，而S真必有G真。即：S=G,人工智能原理第三章归结推理方法,37,谓词归结子句形,G=G1G2G3Gn的子句形G的字句集可以分解成几个单独处理。有SG=S1US2US3UUSn则SG与S1US2US3UUSn在不可满足得意义上是一致的。即SG不可满足S1US2US3UUSn不可满足,人工智能原理第三章归结推理方法,38,求取子句集例(1),例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是他的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：P(x,y)表示x是y的父亲Q(x,y)表示x是y的祖父ANS(x)表示问题的解答,人工智能原理第三章归结推理方法,39,求取子句集例(2),对于第一个条件，“如果x是y的父亲，y又是z的父亲，则x是z的祖父”，一阶逻辑表达式如下：A1：(x)(y)(z)(P(x,y)P(y,z)Q(x,z)SA1：P(x,y)P(y,z)Q(x,z)对于第二个条件：“每个人都有父亲”，一阶逻辑表达式：A2：(y)(x)P(x,y)SA2：P(f(y),y)对于结论：某个人是他的祖父B：(x)(y)Q(x,y)否定后得到子句：（(x)(y)Q(x,y)）ANS(x)SB：Q(x,y)ANS(x)则得到的相应的子句集为：SA1，SA2，SB,人工智能原理第三章归结推理方法,40,第三章归结推理方法,概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理,人工智能原理第三章归结推理方法,41,归结原理,归结原理正确性的根本在于，找到矛盾可以肯定不真。方法：和命题逻辑一样。但由于有函数，所以要考虑合一和置换。,人工智能原理第三章归结推理方法,42,置换,置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义：置换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，x1,x2,xn是互不相同的变量，t1,t2,tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。在谓词逻辑的归结过程中，寻找项之间合适的变量置换使表达式一致是一个很重要的过程，这个过程称为合一。,人工智能原理第三章归结推理方法,43,例a/x，c/y，f(b)/z是一个置换g(y)/x，f(x)/y不是一个置换。原因：它在x和y之间出现了循环置换现象。置换的目的是要将某些变量用另外的变量、常量或函数取代，使其不在公式中出现。这里用g(y)置换x,用f(g(y)置换y,既没有消去x,也没有消去y.若改为g(a)/x，f(x)/y就可以了。,人工智能原理第三章归结推理方法,44,置换的合成,设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)最后剩下的元素所构成的集合。合成即是对ti先做置换然后再做置换，置换xi,人工智能原理第三章归结推理方法,45,置换的合成,例：设：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满足定义中的条件i，需要删除；a/x，b/y满足定义中的条件ii，也需要删除。最后得f(b)/x，y/z,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),人工智能原理第三章归结推理方法,46,合一,合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。定义：设有公式集FF1，F2，Fn，若存在一个置换，可使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是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。,人工智能原理第三章归结推理方法,47,例1：设有置换s=z/x,A/y，则：Px,f(y),Bs=Pz,f(A),B。这里x被换成了z，y被换成了A。设有公式的集合Ei(i=1,2,.,m)，如果存在一个置换s，使得这m个公式被施以s以后，变得完全一样了，则称这m个公式是可合一的，置换s是它们的合一者。,人工智能原理第三章归结推理方法,48,例2：设有公式集P(x,f(y),B),P(z,f(B),B)和置换s1=A/x,B/y,A/z，由于：P(x,f(y),B)s=P(A,f(B),B)P(z,f(B),B)s=P(A,f(B),B)所以公式集P(x,f(y),B),P(z,f(B),B)是可合一的，置换s1=A/x,B/y,A/z是它们的合一者。,人工智能原理第三章归结推理方法,49,若存在一个置换s使得表达式集Ei中每个元素经置换后的例有：E1s=E2s=E3s=，则称表达式集Ei是可合一的，这个置换s称作Ei的合一者。在归结法中主要是处理可合一的子句集，例如有子句集:P（x，f（y），B），P（x，f（B），B），若对两个子句作置换sA/x，B/y，则可得P（A，f（B），B），因而该子句集是可合一的。仅仅从合一的角度看，s并不是最简单的合一者，因为还存在另一个s1B/y的合一者，使子句集合一为Px，f（B），B。因此通常还要求找的是最一般或最普通的合一者（mostgeneralunifier）g，记为mgug。,人工智能原理第三章归结推理方法,50,任一合一者s与g之间的关系是：存在一个置换s，使得EisEigs。再比较上例的两个合一者，有A/x，B/yB/yA/x，因此mgugB/y。可见mgug的置换限制最少，所产生的例更一般化，这有利于归结过程的灵活使用。,人工智能原理第三章归结推理方法,51,UNIFY算法,UNIFY算法不仅可以判断两个公式是否可合一，而且在可合一的情况下，给出它们的mgu。该算法为了表述上的方便，假定谓词是以表的形式表示的。如谓词P(x,f(y),B)表示为(Px(fy)B)。UNIFY算法的基本思想是，从左向右按位置扫描两个谓词的每一个对应部分，如果二者一致，则转入下一项。如果不一致，则看是否存在一个置换，使得对应项经过置换后是一致的。如果不存在这样的置换，则两个公式是不可合一的。如果两个谓词的对应部分都是一致的，或者经置换后是一致的，则两个公式是可合一的，这些置换的合成是它们的合一者。如果当两个对应项都是变量时，置换选作用一个变量代替另一个变量，则这样得到的合一者是mgu。,人工智能原理第三章归结推理方法,52,例：公式集如下：P(x,x,z),P(f(y),f(B),y)用表的形式表示为：E1=(Pxxz)E2=(P(fy)(fB)y)从左向右按顺序扫描两个谓词。E1和E2的第一项都是P，是一致的，转入第二项。E1的第二项是x，E2的第二项是(fy)，二者不一致。由于其中一个是变量，可以进行置换。选置换(fy)/x使得二者成为一致的。该置换同时作用于E1的第三项x。这样有：E1=(P(fy)(fy)z)E2=(P(fy)(fB)B),人工智能原理第三章归结推理方法,53,E1=(P(fy)(fy)z)E2=(P(fy)(fB)B)继续看第三项。E1的第三项是(fy)，E2的第三项是(f,B)。由于两个都是表，需要进入表的内部进行比较。在表的内部，第一项均是f，是一致的。第二项一个是变量y，一个是常量B。选置换B/y使二者成为一致的。该置换不仅使得两个公式中的所有y都被替换为了B，而且也作用于前一个置换(fy)/x，使得该置换变成了(fB)/x。这样有：E1=(P(fB)(fB)z)E2=(P(fB)(fB)B),人工智能原理第三章归结推理方法,54,E1=(P(fB)(fB)z)E2=(P(fB)(fB)B)E1的第四项是变量z，E2的第四项是常量B，选置换B/z使得二者成为一致的。有：E1=(P(fB)(fB)B)E2=(P(fB)(fB)B)至此，E1和E2是完全一样的了，说明E1和E2是可合一的。其合一者是这一过程中几个置换的并(fB)/x,B/y,B/z，该合一者也是mgu。,人工智能原理第三章归结推理方法,55,如果这一过程中有某一个对应项是不能置换为一样的，则说明两个公式不可合一。如该例如果是：E1=(PxxA)E2=(P(fy)(fB)y)则是不可合一的。因为经过几步变换后有：E1=(P(fB)(fB)A)E2=(P(fB)(fB)B)此时E1的第四项是常量A，而E2的第四项是常量B，二者不一致，而且都是常量，无法置换。因此两个公式不可合一。,人工智能原理第三章归结推理方法,56,P105例3.16,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,人工智能原理第三章归结推理方法,57,谓词逻辑的归结过程,对于谓词逻辑来说，可以这样判断两个子句是否可进行归结，及其归结式是什么。对于子句C1L1和C2L2，如果L1与L2可合一，且s是其合一者，则(C1C2)s是其归结式。其中L1、L2是单文字。事实上L1、L2中有一个含有否定符，所以对另一个加上否定符后，才能判断它们是否可合一。,人工智能原理第三章归结推理方法,58,设C1和C2为两个不同的子句，子句中的变量已标准化。我们采用文字集的形式来表示子句（即文字之间理解为析取关系），则有C1C1i（i1，2，n），C2C2j（j1，2，m）再设L1k和L2k分别为C1和C2的两个子集。若L1k和L2k的并集存在一个mgus，则两个子句的归结式为CC1iL1ksC2jL2ks可以看出对这两个子句进行归结时，由于有多种方式选取L1k和L2k，因此归结式不是唯一的。,人工智能原理第三章归结推理方法,59,例：C1P（x，f（A）P（x，f（y）Q（y）C2P（z，f（A）Q（z）取L11P（x，f（A），L21P（z，f（A）存在sz/x,使L11和L21合一，所以归结式为P（z，f（y）Q（y）Q（z）取L11P（x，f（y），L21P（z，f（A）则s（z/x，A/y），归结式为Q（A）Q（z）取L11Q（y），L21Q（z）则sy/z，归结式为P（x，f（A）P（x，f（y）P（y，f（A）,人工智能原理第三章归结推理方法,60,这个例子说明，选择不同文字对做归结时可得到不同的归结式，但由于都是用最一般的合一者作置换，因此这些归结式仍是最一般的归结式。就是说，如果对某个文字不是用mgu来合一，那么得到的归结式比最一般的归结式则有较多的限制。实际上我们总是希望用最一般的归结式，以增加归结过程的灵活性。,人工智能原理第三章归结推理方法,61,归结原理,归结的注意事项：谓词的一致性，名称不一致的谓词，如P()与Q()，不可以常量的一致性，含有不同常量的谓词，如P(a,)与P(b,.)，不可以如果是常量与变量，P(a,.)与P(x,)，可以3.变量与函数，P(x,x,.)与P(x,f(x),)，不可以,因为不能进行x/f(x)的置换；但P(x,x,.)与P(x,f(y),)，可以通过对两式分别做f(y)/x置换，而后进行归结。4.不能同时消去两个互补对，PQ与PQ的空，不可以5.先进行内部简化，再进行置换与合并。,人工智能原理第三章归结推理方法,62,例：设C1=P(y)P(f(x)Q(g(x),C2=P(f(g(a)Q(b),求C1和C2的归结式。解：对C1,取最一般合一=f(x)/y得C1的因子C1=P(f(x)Q(g(x)C1与C2归结，2=f(x)/y,g(a)/x得归结式：Q(g(g(a)Q(b),人工智能原理第三章归结推理方法,63,归结原理,归结的过程写出谓词关系公式用反演法写出谓词表达式SKOLEM标准形子句集S对S中可归结的子句做归结归结式仍放入S中，反复归结过程得到空子句得证,人工智能原理第三章归结推理方法,64,例题“快乐学生”问题,假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。,人工智能原理第三章归结推理方法,65,例题“快乐学生”问题,解：先将问题用谓词表示如下：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),人工智能原理第三章归结推理方法,66,例题“快乐学生”问题,由R1及逻辑转换公式: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(10)Pass(zhang,computer)(9)(5)(11)Lucky(zhang)(10)(3)，zhang/u,computer/v(12)(11)(5),人工智能原理第三章归结推理方法,67,归结原理,归结法的实质归结法是仅有一条推理规则的推理方法。归结的过程是一个语义树倒塌的过程。归结法的问题子句中有等号或不等号时，完备性不成立。Herbrand定理的不实用性引出了可实用的归结法。,人工智能原理第三章归结推理方法,68,第三章归结推理方法,概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理,人工智能原理第三章归结推理方法,69,归结过程的控制策略,要解决的问题：归结方法的知识爆炸。控制策略的目的归结点尽量少控制策略的原则给出控制策略，以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。,人工智能原理第三章归结推理方法,70,控制策略的方法(1),删除策略=完备名词解释：归类：设有两个子句C和D，若有置换使得CD成立，则称子句C把子句D归类。由于小的可以代表大的，所以小的吃掉大的了。若对S使用归结推理过程中，当归结式Cj是重言式（永真式）和Cj被S中子句和子句集的归结式Ci(i完备与单元归结策略相似，输入归结策略要求在归结过程中，每一次归结的两个子句中必须有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结，造成恶性循环。可以减少不必要的归结次数。如同单元归结策略，不是所有的可归结谓词公式的最后结论都是可以从原始子句集中得到的。简单的例子，归结结束时，即最后一个归结式为空子句的条件是，参加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式一定不能采用输入归结策略。,人工智能原理第三章归结推理方法,78,第三章归结推理方法,概述命题逻辑的归结法谓词归结子句形归结原理归结过程的策略控制Herbrand定理,人工智能原理第三章归结推理方法,79,Herbrand定理,问题：一阶逻辑公式的永真性（永假性）的判定是否能在有限步内完成？,人工智能原理第三章归结推理方法,80,Herbrand定理,1936年图灵(Turing)和邱吉(Church)互相独立地证明了：,“没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步内判定它是永真（或永假）。对于非永真（或永假）的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。”,人工智能原理第三章归结推理方法,81,Herbrand定理,Herbrand的思想定义：公式G永真：对于G的所有解释，G都为真。思想：寻找一个已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的解释存在，并且算法在有限步内停止。,人工智能原理第三章归结推理方法,82,Herbrand定理,H域H解释语义树结论：Herbrand定理,人工智能原理第三章归结推理方法,83,Herbrand定理（H域）,基本方法：因为量词是任意的，所讨论的个体变量域D是任意的，所以解释的个数是无限、不可数的。简化讨论域。建立一个比较简单、特殊的域，使得只要在这个论域上，该公式是不可满足的。此域称为H域。,人工智能原理第三章归结推理方法,84,人工智能原理第三章归结推理方法,85,H域例题,设子句集S=P(x),Q(y,f(z,b),R(a)，求H域解：H0a,b为子句集中出现的常量H1a,b,f(a,b),f(a,a),f(b,a),f(b,b)H2a,b,f(a,b),f(a,a),f(b,a),f(b,b)，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(b,b),f(a,a),f(f(b,b),f(b,a),f(f(b,b),f(b,b)H=H1H2H3,人工智能原理第三章归结推理方法,86,Herbrand定理（H域）,几个基本概念f（tn）：f为子句集S中的所有函数变量。t1,t2,tn为S的H域的元素。通过它们来讨论永真性。原子集A：谓词套上H域的元素组成的集合。如A=所有形如P(t1,t2,tn)的元素即把H中的东西填到S的谓词里去。S中的谓词是有限的，H是可数的，因此，A也是可数的。,人工智能原理第三章归结推理方法,87,原子集例题,上例题的原子集为：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),)一旦原子集内真值确定好（规定好），则S在H上的真值可确定。成为可数问题。,人工智能原理第三章归结推理方法,88,Herbrand定理,H域H解释语义树结论：Herbrand定理,人工智能原理第三章归结推理方法,89,Herbrand定理（H解释）,解释I：谓词公式G在论域D上任何一组真值的指定称为一个解释。H解释：子句集S在的H域上的解释称为H解释。问题：对于所有的解释，全是假才可判定。因为所有解释代表了所有的情况，如可穷举，问题便可解决。,人工智能原理第三章归结推理方法,90,Herbrand定理（H解释）,基原子、基文字、基子句、基子句集：没有变量出现的原子、文字、子句和子句集，分别称为基原子、基文字、基子句、基子句集。基例：子句集S中某子句C中所有变元符号均以S的H域中的元素代入后，所得的基子句C称为C的一个基例。由定义可知，若一个解释I*使得某个基子句为假，则此解释I*为假。,人工智能原理第三章归结推理方法,91,例:S=P(x)Q(X),R(f(y),求其一个H解释I*.解：S的H域为：a,f(a),f(f(a),S的原子集为：P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),凡对A中各元素真假值的一个具体设定都为S的一个H解释，如：I1*=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),I2*=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),I3*=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),I1*、I2*、I3*中出现的P(a)的取值为T,出现的P(a)表示P(a)的取值为F.显然在H域上，这样的定义I*下，S的真值就确定了。如，S|t1*=T,S|t2*=F,S|t3*=F这是因为子句集S=P(x