人工智能一般搜索算法原理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工智能讲义,*,第三章 一般搜索原理,盲目搜索,启发式搜索,归结原理,10/23/2026,1,人工智能讲义,盲目搜索,图搜索策略,深度优先搜索,宽度优先搜索,等代价搜索,10/23/2026,2,人工智能讲义,一些基本概念,节点深度：,根节点深度=0,其它节点深度=父节点深度+1,0,1,2,3,10/23/2026,3,人工智能讲义,一些基本概念（续1）,路径,设一节点序列为(n,0,n,1,n,k,)，对于i=1,k，若节点n,i-1,具有一个后继节点n,i,，则该序列称为从n,0,到n,k,的路径。,路径的耗散值,一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(n,i,n,j,),表示从,n,i,到n,j,的路径的耗散值。,10/23/2026,4,人工智能讲义,一些基本概念（续1）,扩展一个节点,生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。,10/23/2026,5,人工智能讲义,一般的图搜索算法（GRAPHSEARCH）,1,G=G0(G0=s),OPEN=(s);,2,CLOSED=();,3,LOOP:IF OPEN=()EXIT(FAIL);,4,n=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);,5,IF GOAL(n)EXIT(SUCCESS);,6,EXPAND(n)mi,G=ADD(mi,G);,10/23/2026,6,人工智能讲义,一般的图搜索算法（续）,7,标记和修改指针：,ADD(mj,OPEN),并标记,mj,到,n,的指针；,计算是否要修改,mk、ml,到,n,的指针；,计算是否要修改,ml,到其后继节点的指针；,8,对OPEN中的节点按,某种原则,重新排序；,9,GO LOOP；,10/23/2026,7,人工智能讲义,深度优先搜索,在深度优先搜索中，首先扩展最新产生的(最深的)节点，深度 相等的节点可以任意排列。“最晚产生的节点最先扩展”,10/23/2026,8,人工智能讲义,深度优先搜索的性质,一般不能保证找到最优解,当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制,最坏情况时，搜索空间等同于穷举,与回溯法的差别：图搜索,是一个通用的与问题无关的方法,10/23/2026,11,人工智能讲义,宽度优先搜索,如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索使逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完本层的所有节点。“先产生的节点先扩展”,10/23/2026,12,人工智能讲义,宽度优先搜索算法,1,G=G0(G0=s),OPEN=(s),CLOSED=();,2,LOOP:IF OPEN=()EXIT(FAIL);,3,n=FIRST(OPEN);,4,IF GOAL(n)EXIT(SUCCESS);,5,REMOVE(n,OPEN),ADD(n,CLOSED);,6,EXPAND(n)mi,G=ADD(mi,G);,7,IF 目标在mi中 THEN EXIT(SUCCESS);,8,ADD(OPEN,mj),并标记mj,到,n,的指针,;,9,GO LOOP;,10/23/2026,13,人工智能讲义,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,1,2,5,6,7,3,1 2 3,8 4,7 6 5,目标,8,2 3 4,1 8,7 6 5,4,10/23/2026,14,人工智能讲义,宽度优先搜索的性质,当问题有解时，一定能找到解,当问题为单位耗散值，且问题有解时，一定能找到最优解,方法与问题无关，具有通用性,效率较低,属于图搜索方法,10/23/2026,15,人工智能讲义,等代价搜索,宽度优先搜索可被推广用来解决寻找从起始节点到目标节点具有最小代价路径问题，这种推广了的宽度优先搜索算法叫做,等代价搜索算法,。,10/23/2026,16,人工智能讲义,等代价搜索算法,算法,1,G=G0(G0=s),OPEN=(s),CLOSED=(),g(s)=0;,2,LOOP:IF OPEN=()EXIT(FAIL);,3,从OPEN表中选择一个节点i,使其g(i)为最小。如果有几个节点都合格，那么就要选择一个目标节点作为i(要是有目标节点的话)；否则，就从中选一个作为节点I;REMOVE(i,OPEN),ADD(i,CLOSED);,4,IF GOAL(i)EXIT(SUCCESS);,5,EXPAND(i)j,G=ADD(j,G);,6,对每个后继节点j,计算g(j)=g(i)+c(i,j)且,ADD(OPEN,j),并标记j,到,i,的指针,;,7,GO LOOP;,10/23/2026,17,人工智能讲义,启发式图搜索,利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。,启发信息的强度,强：降低搜索工作量，但可能导致找不到最 优解,弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解,10/23/2026,18,人工智能讲义,希望：,引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。,10/23/2026,19,人工智能讲义,基本思想,定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。,10/23/2026,20,人工智能讲义,1，启发式搜索算法A（A算法）,评价函数的格式：,f(n)=g(n)+h(n),f(n)：评价函数,h(n)：启发函数,10/23/2026,21,人工智能讲义,符号的意义,g*(n)：从s到n的最短路径的耗散值,h*(n)：从n到g的最短路径的耗散值,f*(n)=g*(n)+h*(n)：,从,s,经过,n,到,g,的最短路径的耗散值,g(n)、h(n)、f(n),分别是,g*(n)、h*(n)、f*(n)的估计值,10/23/2026,22,人工智能讲义,A算法,1,OPEN=(s),f(s)=g(s)+h(s);,2,LOOP:IF OPEN=()EXIT(FAIL);,3,n=FIRST(OPEN);,4,IF GOAL(n)EXIT(SUCCESS);,5,REMOVE(n,OPEN),ADD(n,CLOSED);,6,EXPAND(n),Mi,计算,f(n,mi)=g(n,mi)+h(mi);,10/23/2026,23,人工智能讲义,A算法（续）,ADD(mj,OPEN),标记mj到n的指针；,IF f(n,mk)f(mk)f(mk)=f(n,mk),标记,mk,到,n,的指针；,IF f(n,ml)f*(s)。,10/23/2026,31,人工智能讲义,A*算法的性质（续2）,引理2.2：,A*,结束前，,OPEN,表中必存在,f(n)f*(s)。,10/23/2026,32,人工智能讲义,A*算法的性质（续3）,定理2：,对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。,10/23/2026,33,人工智能讲义,A*算法的性质（续4）,推论2.1：,OPEN表上任一具有f(n)h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。,简写：如果h2(n),h1(n),则A1扩展的节点数,A2,扩展的节点数,10/23/2026,37,人工智能讲义,A*算法的改进,问题的提出：,因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。,10/23/2026,38,人工智能讲义,s(10),A(1),B(5),C(8),G 目标,6,3,1,1,1,8,一个例子：,OPEN表,CLOSED表,s(10),s(10),A(7)B(8)C(9),A(7)s(10),B(8)C(9)G(14),A(5)C(9)G(14),C(9)G(12),B(7)G(12),A(4)G(12),G(11),A(7)B(8)s(10),A(5)B(8)s(10),C(9)A(5)B(8)s(10),A(5)B(7)C(9)s(10),A(4)B(7)C(9)s(10),10/23/2026,39,人工智能讲义,出现多次扩展节点的原因,在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。,10/23/2026,40,人工智能讲义,解决的途径,对h加以限制,能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。,对算法加以改进,能否对算法加以改进，避免或减少节点的多次扩展。,10/23/2026,41,人工智能讲义,改进的条件,可采纳性不变,不多扩展节点,不增加算法的复杂性,10/23/2026,42,人工智能讲义,对h加以限制,定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足,h(ni)-h(nj)c(ni,nj),h(t)=0,则称h是单调的。,h(ni),ni,nj,h(nj),c(ni,nj),10/23/2026,43,人工智能讲义,h单调的性质,定理5：,若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。,即：当A*选n扩展时，有g(n)=g*(n)。,10/23/2026,44,人工智能讲义,h单调的性质（续）,定理6：,若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。,10/23/2026,45,人工智能讲义,h单调的例子,8数码问题：,h为“不在位”的将牌数,1,h(ni)-h(nj)=0(nj,为,ni,的后继节点,),-1,h(t)=0,c(ni,nj)=1,满足单调的条件。,10/23/2026,46,人工智能讲义,对算法加以改进,一些结论：,OPEN表上任一具有f(n)f*(s)的节点定会被扩展。,A*选作扩展的任一节点，定有f(n)f*(s)。,10/23/2026,47,人工智能讲义,改进的出发点,OPEN=(),f*(s),f,值小于,f*(s),的节点,f,值大于等于,f*(s),的节点,fm：,到目前为止已扩展节点的最大,f,值，,用fm代替f*(s),10/23/2026,48,人工智能讲义,修正过程A,1,OPEN=(s),f(s)=g(s)+h(s),fm=0;,2,LOOP:IF OPEN=()EXIT(FAIL);,3,NEST=ni|f(ni)5),n2(4),n3(4),n0(3),n0(3-4),10/23/2026,62,人工智能讲义,n0,n1,n2,n3,n4,n5,n6,n7,n8,n4(1),n1(5),n2(4),n3(4),n6(2),n7(0),n8(0),n0(4),n5(1),n5(1-2),10/23/2026,63,人工智能讲义,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色代价,：5,蓝色,代价,：6,n0(4),n4(1),n5(1-2),n1(5),n2(4),n3(4),n6(2),n7(0),n8(0),n0(4-5),10/23/2026,64,人工智能讲义,n0,n1,n2,n3,n4,n5,n6,n7,n8,n0(5),n4(1),n5(2),n1(5),n2(4),n3(4),n6(2),n7(0),n8(0),10/23/2026,65,人工智能讲义,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,n0(5),n4(1),n5(2),n1(5),n2(4),n3(4),n6(2),n7(0),n8(0),10/23/2026,66,人工智能讲义,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,初始节点可解,n0(5),n4(1),n5(2),n1(5),n2(4),n3(4),n6(2),n7(0),n8(0),10/23/2026,67,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,68,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,69,人工智能讲义,概述,归结原理,由J.A.Robinson由1965年提出。,与演绎法完全不同，新的逻辑演算算法。,一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。,语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）,本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题,。,10/23/2026,70,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,71,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,72,人工智能讲义,命题逻辑的归结法,基本单元：简单命题（陈述句）,例：,命题：A,1,、A,2,、A,3,和 B,求证：A,1,A,2,A,3,成立，则B成立，,即：A,1,A,2,A,3,B,反证法：证明A,1,A,2,A,3,B 是矛盾式,（永假式）,10/23/2026,73,人工智能讲义,命题逻辑的归结法,建立子句集,合取范式：命题、命题和的与，如：,P（PQ）（PQ）,子句集,S,：,合取范式形式下的子命题（元素）的集合,例：命题公式：,P,（,PQ,）,（,PQ,）,子句集,S,：,S=P,PQ,PQ,10/23/2026,74,人工智能讲义,命题逻辑的归结法,归结式,消除互补对，求新子句,得到归结式,。,如子句：,C,1,=C,1,L,C,2,=C,2,归结式：,R(C,1,C,2,)=C,1,C,2,注意：,C,1,C,2,R(C,1,C,2,),，反之,不一定,成立。,假言推理:,由合适公式,W,1,和W,1,W,2,产生合适公式W,2,如何用归结法证明?,10/23/2026,75,人工智能讲义,命题逻辑的归结法,归结过程,对结论作否定,并加入前提中,将命题写成合取范式,求出子句集,对子句集使用归结推理规则,归结式作为新子句参加归结,归结式为空子句,，S是不可满足的（矛盾），原命题成立。,（证明完毕）,谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。,10/23/2026,76,人工智能讲义,命题逻辑的归结法,例,证明,先将,化为合取范式,建立子句集 S=,对S做归结,P,NIL,10/23/2026,77,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,78,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,79,人工智能讲义,子句形,引用Herbrand定理，以说明归结原理的意义及一个原理形成的根基与背景,SKOLEM标准形,前束范式,：把所有的量词都提到前面去，然后消掉所有量词。,定义,：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。即(Q,1,x,1,),(Q,n,x,n,)M(x,1,x,n,),其中,Q,i,x,i,为存在量词或全称量词,M(x,1,x,n,),为合取范式(由一些子句的合取组成)。,10/23/2026,80,人工智能讲义,子句形,(Skolem 标准形),量词消去原则：,消去存在量词“,”，略去全程量词“,”。,注意：,左边有全称量词的存在量词，消去时该变量改写成为全称量词的函数(Skloem函数)；如没有，改写成为常量。,例子：见人工智能及其应用P75,10/23/2026,81,人工智能讲义,子句形,(Skolem 标准形),定理,：,谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。,SKOLEM标准形定义：,消去量词后的谓词公式。,注意,：谓词公式G的SKOLEM标准形同G,并不等值,。,10/23/2026,82,人工智能讲义,子句形,(Skolem 标准形),例,:,G=(,x,)(,y,)(,z,)(,u,)P(x,y,z,u),Skolem 标准形为：,(,y,)(,z,)P(a,y,z,f(y,z),其中，,x=a(常量)，u=f(y.z),10/23/2026,83,人工智能讲义,子句形,子句与子句集,文字：不含任何连接词的谓词公式。,子句：一些文字的析取（谓词的和）。,子句集,S,的求取：,G,SKOLEM标准形,消去存在变量,以“,，”,取代“,”，并表示为集合形式。,10/23/2026,84,人工智能讲义,子句形,G是不可满足的,S是不可满足的,G,与,S,不等价，但在不可满足的意义下是一致的。,定理：,若G是给定的公式，而S是相应的子句集，则G是不可满足的,S是不可满足的。,注意,：,G真不一定S真，而S真必有G真。,即：S,=,G,10/23/2026,85,人工智能讲义,子句形,G=G,1,G,2,G,3,G,n,的子句形,G,的子句集可以分解成几个单独处理。,有,S,G,=S,1,U S,2,U S,3,U U S,n,则,S,G,与,S,1,U S,2,U S,3,U U S,n,在不可满足的意义上是一致的。,即,S,G,不可满足,S,1,U S,2,U S,3,U U S,n,不可满足,10/23/2026,86,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,87,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,88,人工智能讲义,Herbrand,定理,问题：,一阶逻辑公式的永真性（永假性）的判定是否能在有限步内完成,？,10/23/2026,89,人工智能讲义,Herbrand,定理,1936年图灵(Turing)和邱吉(Church)互相独立地证明了：,“没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步内判定它是永真（或永假）。对于非永真（或永假）的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。”,10/23/2026,90,人工智能讲义,Herbrand,定理,Herbrand的思想,定义：,公式G永真：对于G的所有解释，G都为真。,思想：,寻找一个已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的解释存在，并且算法在有限步内停止。,10/23/2026,91,人工智能讲义,Herbrand,定理,H域,H解释,语义树,结论：Herbrand定理,10/23/2026,92,人工智能讲义,Herbrand,定理,H域,H解释,语义树,结论：Herbrand定理,10/23/2026,93,人工智能讲义,Herbrand定理,（H域）,基本方法：,因为,量词是任意的，所讨论的个体变量域D是任意的，所以解释的个数是无限、不可数的,。,简化讨论域。建立一个比较简单、特殊的域，使得只要在这个论域上，该公式是不可满足的。,此域称为H域：H,0,为G中所出现的常量的集合，若G中没有常量，就任取常量 ，H,0,=a。,规定 为H域,例题请参考教科书,P,27,10/23/2026,94,人工智能讲义,H域举例,例1 S=P(a),P(x),P(f(x),依定义有,H,0,=a,H,1,=a,Uf(a)=a,f(a),H,2,=a,f(a)Uf(a),f(f(a)=a,f(a),f(f(a),H,=a,f(a),f(f(a)，,10/23/2026,95,人工智能讲义,Herbrand定理,（H域）,几个基本概念,f（t,1,t,2,t,n,）,：f为子句集S中的所有函数变量。,t,1,t,2,t,n,为S的H域的元素。通过它们来讨论永真性。,原子集A：谓词套上H域的元素组成的集合。如,A=所有形如,P(t,1,t,2,t,n,),的元素,即把H中的东西填到S的谓词里去。S中的谓词是有限的，H是可数的，因此，A也是可数的。,一旦原子集内真值确定好（规定好），则S在H上的真值可确定。成为可数问题。,10/23/2026,96,人工智能讲义,原子集举例,例1 S=P(a),P(x),P(f(x),H,=a,f(a),f(f(a)，,S的原子集为,A=P(a),P(f(a),P(f(f(a),10/23/2026,97,人工智能讲义,Herbrand定理,（H域）,没有变量出现的原子、文字、子句和子句集，,分别称作基原子、基文字、基子句和基子句集。,它们在讨论子句集S的不可满足性时占有重要置。,10/23/2026,98,人工智能讲义,Herbrand,定理,H域,H解释,语义树,结论：Herbrand定理,10/23/2026,99,人工智能讲义,Herbrand,定理,H域,H解释,语义树,结论：Herbrand定理,10/23/2026,100,人工智能讲义,Herbrand定理,（H解释）,解,释,I,*,：取一个值得到一个结论,I,映射,S,中到所有常量符号到它们本身。(即原子集),令,f,是,n,元函数，,I,是,f,下的一个指派，即H中的元素到,f,的一个映射（函数值）。简单地说(P29)，A中的各元素真假组合都是H的解释。（或真或假只取一个）,问题：,对于所有的解释，全是假才可判定。因为所有解释代表了所有的情况，如可穷举，问题便可解决。,10/23/2026,101,人工智能讲义,H解释-举例,例1 S=P(a),P(x),P(f(x),S的H域,H,=a,f(a),f(f(a)，,S的原子集为,A=P(a),P(f(a),P(f(f(a),S的H解释：,I,1,*=,P(a),P(f(a),P(f(f(a),S|,I,1,*=,T,I,2,*=,P(a),P(f(a),P(f(f(a),S|,I,2,*=,F,I,3,*=,P(a),P(f(a),P(f(f(a),S|,I,3,*=,F,我们关心的是：对论域上的任一解释,I，若有 S|,I,=T,如何求得一个相应的H解释I,*,使得S|,I*,=T成立。,10/23/2026,102,人工智能讲义,Herbrand定理,（H解释）,如下三个定理保证了归结法的正确性：,定理1,：,设,I,是,S,的论域D上的解释，存在对应于,I,的H解释,I,*,，使得若有,S|,I,=T,，必有,S|,I*,=T,。,定理2,：,子句集,S,是不可满足的，当且仅当所有的,S,的H解释下为假。,定理3,：,子句集,S,是不可满足的，当且仅当对每一个解释,I,下，至少有,S,的某个子句的某个,基例,为假。,10/23/2026,103,人工智能讲义,Herbrand定理,（H解释）,基例,S,中某子句中所有变元符号均以,S,的H域中的元素代入时，所得的基子句,C,称为,C,的一个基例。,若一个子句为假，则此解释为假。,一般来说，D是无穷不可列的，因此，子句集,S,也是无穷不可列的。但,S,确定后H是无穷可列的。不过在H上证明,S,的不可满足性仍然是不可能的。,解决问题的方法：,语义树,10/23/2026,104,人工智能讲义,Herbrand,定理,H域,H解释,语义树,结论：Herbrand定理,10/23/2026,105,人工智能讲义,Herbrand,定理,H域,H解释,语义树,结论：Herbrand定理,10/23/2026,106,人工智能讲义,Herbrand定理,（语义树）,构成方法,原子集中所有元素逐层添加的一棵二叉树。将元素的是与非分别标记在两侧的分枝上（可不完全画完）。(P34),特点,一般情况H是可数集，,S,的语义树是无限树。,10/23/2026,107,人工智能讲义,Herbrand定理,（语义树）,意义,S,H A 语义树,可以理解语义树为H域的图形解释。,目的：把每个解释都摊开。语义树中包含原子集的全部元素，因此，,语义树是完全的。,每一个直到叶子节点的分支对应,S,的一个解释。可以通过对语义树每一个分支来计算,S,的真值。如果每个基例都为假，则可认为是不可满足的。,10/23/2026,108,人工智能讲义,语义树-举例,例1 设子句集S的原子集 A=P,Q,R,语义树：,N,0,N,11,N,12,N,21,N,22,N,23,N,24,N,31,N,32,N,33,N,34,N,35,N,36,N,37,N,38,P,Q,Q,R,R,P,I(N),表示从根节点到节点N分枝上所标记的所有文字的并集。如 I(N,34,)=P,Q,R,10/23/2026,109,人工智能讲义,Herbrand定理,（语义树）,几个概念,失败结点,：,当（由上）延伸到点,N,时，,I(N),已表明了,S,的某子句的某基例假。但,N,以前尚不能判断这事实。就称,N,为失败结点。,完全语义树,：,如果对语义树的所有叶结点N来说，,I(N),包含了S的原子集,A=A1,A2,中的所有元素A,i,或,A,i,，I=1,n。,封闭语义树,：,如果,S,的完全语义树的每个分枝上都有一个失败结点，就称它是一棵封闭语义树。,10/23/2026,110,人工智能讲义,封闭语义树-举例,例 子句集S=,P(x)Q(x),P(f(y),Q(f(y),H=a,f(a),f(f(a),A=P(a),Q(a),P(f(a),Q(f(a),语义树：,N,0,N,11,N,12,N,21,N,22,N,23,N,24,N,31,N,32,N,33,N,34,N,35,N,36,N,37,N,38,P(a),Q(a),P(f(a),N,41,N,42,N,43,N,44,N,45,N,46,N,47,N,48,N,49,N,410,N,411,N,413,N,415,N,412,N,414,N,416,这是一个无限树，然而它是否是一个封闭树？,Q(f(a),I(N,41,)=P(a),Q(a),P(f(a),Q(f(a),它使S的子句,Q(f(y)的,基例,Q(f(a),为假,，,而,N,41,的父辈不能使子句的基例为假,10/23/2026,111,人工智能讲义,封闭语义树-举例,例 子句集S=,P(x)Q(x),P(f(y),Q(f(y),H=a,f(a),f(f(a),A=P(a),Q(a),P(f(a),Q(f(a),封闭语义树：,N,0,N,11,N,12,N,21,N,22,N,23,N,24,N,31,N,32,N,36,N,37,N,38,P(a),Q(a),P(f(a),N,41,N,42,N,49,N,410,N,413,N,414,Q(f(a),10/23/2026,112,人工智能讲义,Herbrand,定理,H域,H解释,语义树,结论：Herbrand定理,10/23/2026,113,人工智能讲义,Herbrand,定理,H域,H解释,语义树,结论：Herbrand定理,10/23/2026,114,人工智能讲义,Herbrand定理,（结论）,Herbrand定理：,子句集,S,是不可满足的，当且仅当对应于,S,的完全语义数是棵有限封闭树,。,子句集,S,是不可满足的，当且仅当存在不可满足的,S,的有限基例集。,10/23/2026,115,人工智能讲义,Herbrand定理,（结论）,定理的意义,Herbrand定理已将证明问题转化成了命题逻辑问题。,由此定理保证，可以放心的用机器来实现自动推理了。（归结原理）,注意,Herbrand定理给出了一阶逻辑的半可判定算法，即仅当被证明定理是成立时，使用该算法可以在有限步得证。而当被证定理并不成立时，使用该算法得不出任何结论。,但是,10/23/2026,116,人工智能讲义,例,S=,P(x,g(x),y,h(x,y),z,k(x,y,z),P(u,v,e(v),w,f(v,w),x),有,H,0,=a,S,0,=P(a,g(a),a,h(a,a),a,k(a,a,a),P(a,a,e(a),a,f(a,a),a),H,1,=a,g(a),h(a,a),k(a,a,a),e(a),f(a,a),共6个元素,S,1,：,6,3,+6,4,=1512,个元素,H,2,：,元素个数有,6,3,数量级（由于变量最多的函数是k(x,y,z),三个变 量都可能取值于H,1,的六个元素）,S,2,：,元素个数有,(,6,3,),4,数量级,建立,S,3,，,S,4,，,直到S,5,才是不可满足。然而,S,5,元素个数已达,（10,64,）,4,=10,256,Herbrand定理,（结论）,仍存在的,问题,：,基例集序列元素的数目随子句基的元素数目成指数地增加。,因此，,Herbrand,定理是,30,年代提出的，始终没有显著的成绩。,直至,1965,年,Robinson,提出了,归结原理,。,10/23/2026,117,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,118,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,119,人工智能讲义,归结原理,归结原理正确性的根本在于，找到矛盾可以肯定不真。,方法：,和命题逻辑一样。,但由于有函数，所以要考虑,合一,和,置换,。,(定义与例题参考教科书P41),10/23/2026,120,人工智能讲义,归结原理,置换和合一的注意事项：,谓词的一致性,，,P(),与,Q(),，,不可以,常量的一致,性，,P(a,),与,P(b,.),，,不可以,常量与变量，,P(a,.),与,P(x,),，,可以,变量与函数，,P(a,x,.),与,P(x,f(x),),，,不可以；但,P(a,x,),与,P(x,f(y),),，,可以,是不能同时消去两个互补对，,PQ,与,P,Q,的空，不可以,先进行内部简化（置换、合并）,10/23/2026,121,人工智能讲义,归结原理,归结的过程(P48),写出谓词关系公式,用反演法写出谓词表达试,SKOLEM标准形,子句集,S,对,S,中可归结的子句做归结,归结式仍放入,S,中，反复归结过程,得到空子句,得证,10/23/2026,122,人工智能讲义,归结原理,归结法的实质：,归结法是仅有一条推理规则的推理方法。,归结的过程是一个语义树倒塌的过程。(P51),归结法的问题,子句中有等号或不等号时，完备性不成立。,Herbrand定理的不实用性引出了可实用的归结法。,10/23/2026,123,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,124,人工智能讲义,归结原理,概述,命题逻辑的归结法,子句形,Herbrand定理,归结原理,归结过程的策略控制,10/23/2026,125,人工智能讲义,归结过程的控制策略,要解决的问题：,归结方法的知识爆炸。,控制策略的目的,归结点尽量少,控制策略的原则,给出控制策略，以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。,10/23/2026,126,人工智能讲义,归结过程的控制策略,盲目归结,例 S=P,Q,P,Q,P,Q,P,Q,是不可满足。,证明从S,0,=S开始，依次构造,S,i,=C,1,C,2,的归结式|C,1,S,0,S,1,Si-1,C,2,S,i-1,i=1,2,直至得到空子句。具体过程如下：,S,0,(1),P,Q (2),P,Q,(3)P,Q (4),P,Q,S,1,(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),10/23/2026,127,人工智能讲义,归结过程的控制策略(盲目归结),S,2,(13)P,(1)(7),(14)PQ,(1)(8),(15)PQ,(1)(9),(16)PQ,(1)(10),(17)Q,(1)(11),(18)P,(1)(12),(19),Q,(2)(6),(20),PQ,(3)(4),(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),产生过多不必要的归结式。一类是重言式（7）-（10）由它们又产生了（13）-（16），（20）-（23），(26)-(29),(33)-(39)。另一类是重复的，如P,Q,P,Q.,10/23/2026,128,人工智能讲义,归结过程的控制策略,删除策略,设有两个子句C和D，若有置换使得 C,D,成立，便说子句C把子句D归类。,例 C=P(X)D=P(a),Q(a),取=a/x,便有C=P(a),P(a),Q(a),。,删除策略：若对s使用归结推理过程中，当归结式C,j,是重言式或C,j,被S中子句或归结式C,i,(iQR,解释I=,P,Q,R,10/23/2026,131,人工智能讲义,归结过程的控制策略,线性归结策略,首先从子句集S中选取一个称为顶子句的子句C,0,开始做归结，其次是归结过程中所得到的归结式C,i,立即同另一个子句B,i,进行归结得归结式C,i+1,。而B,i,属于S或是已出现的归结式C,j,(j完备,采用支撑集完备,语义归结完备,线性归结 完备,单元归结=完备,输入归结=完备,10/23/2026,135,人工智能讲义,谓词逻辑的归结方法,对于子句C1,L1,和,C2L2，如果L1与L2可合一，且s是其合一者，则(C1C2),s,是其归结式。,例：,P(x),Q(y),P(f(z),R(z),=Q(y)R(z),10/23/2026,136,人工智能讲义,归结举例,设公理集：,(,x)(R(x)L(x),(x)(D(x)L(x),(x)(D(x)I(x),求证：(x)(I(x)R(x),化子句集：,(,x)(R(x)L(x),=,(,x)(R(x)L(x),=R(x)L(x)(1),10/23/2026,137,人工智能讲义,(x)(D(x)L(x),=(x)(D(x)L(x),=D(x)L(x)(2),(x)(D(x)I(x),=D(A)I