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

第三章一般搜索原理盲目搜索启发式搜索归结原理1/11/20231盲目搜索图搜索策略深度优先搜索宽度优先搜索等代价搜索1/11/20232一些基本概念节点深度： 根节点深度=0 其它节点深度=父节点深度+101231/11/20233一些基本概念（续1）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。1/11/20234一些基本概念（续1）扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。1/11/20235一般的图搜索算法（GRAPHSEARCH）1,G=G0(G0=s),OPEN=(s);2,CLOSED=();3,LOOP:IFOPEN=()EXIT(FAIL);4,n=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)EXIT(SUCCESS);6,EXPAND(n)→{mi},G=ADD(mi,G);1/11/20236一般的图搜索算法（续）7,标记和修改指针： ADD(mj,OPEN),并标记mj到n的指针； 计算是否要修改mk、ml到n的指针； 计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；1/11/20237深度优先搜索在深度优先搜索中，首先扩展最新产生的(最深的)节点，深度相等的节点可以任意排列。“最晚产生的节点最先扩展”1/11/20238深度优先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G=ADD(mi,G);8,IF目标在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;1/11/20239231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标1/11/202310深度优先搜搜索的性质质一般不能保保证找到最最优解当深度限制制不合理时时，可能找找不到解，，可以将算算法改为可可变深度限限制最坏情况时时，搜索空空间等同于于穷举与回溯法的的差别：图图搜索是一个通用用的与问题题无关的方方法12/31/202211宽度优先搜搜索如果搜索是是以接近起起始节点的的程度依次次扩展节点点的，那么么这种搜索索就叫做宽宽度优先搜搜索。这种种搜索使逐逐层进行的的，在对下下一层的任任意节点进进行搜索之之前，必须须搜索完本本层的所有有节点。““先产生的的节点先扩扩展”12/31/202212宽度优先搜搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→→{mi},G=ADD(mi,G);7,IF目标在在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GOLOOP;12/31/20221323184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标823418765412/31/202214宽度优先搜索索的性质当问题有解时时，一定能找找到解当问题为单位位耗散值，且且问题有解时时，一定能找找到最优解方法与问题无无关，具有通通用性效率较低属于图搜索方方法12/31/202215等代价搜索宽度优先搜索索可被推广用用来解决寻找找从起始节点点到目标节点点具有最小代代价路径问题题，这种推广广了的宽度优优先搜索算法法叫做等代价搜索算算法。12/31/202216等代价搜索算算法算法1,G=G0(G0=s),OPEN=(s),CLOSED=(),g(s)=0;2,LOOP:IFOPEN=()EXIT(FAIL);3,从OPEN表中选选择一个节点点i,使其g(i)为最最小。如果有有几个节点都都合格，那么么就要选择一一个目标节点点作为i(要要是有目标节节点的话)；；否则，就从从中选一个作作为节点I;REMOVE(i,OPEN),ADD(i,CLOSED);4,IFGOAL(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,GOLOOP;12/31/202217启发式图搜索索利用知识来引引导搜索，达达到减少搜索索范围，降低低问题复杂度度的目的。启发信息的强强度强：降低搜索索工作量，但但可能导致找找不到最优优解弱：一般导致致工作量加大大，极限情况况下变为盲盲目搜索，但但可能可以找找到最优解12/31/202218希望：引入启发知知识，在保保证找到最最佳解的情情况下，尽尽可能减少少搜索范围围，提高搜搜索效率。。12/31/202219基本思想定义一个评评价函数f，对当前前的搜索状状态进行评评估，找出出一个最有有希望的节节点来扩展展。12/31/2022201，启发式式搜索算法法A（A算算法）评价函数的的格式：f(n)=g(n)+h(n)f(n)：：评价函数数h(n)：：启发函数数12/31/202221符号的意义义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)的估计值值12/31/202222A算法1,OPEN=(s),f(s)=g(s)+h(s);2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{Mi},计算f(n,mi)=g(n,mi)+h(mi);12/31/202223A算算法法（（续续））ADD(mj,OPEN),标标记记mj到到n的的指指针针；；IFf(n,mk)<f(mk)f(mk)=f(n,mk),标记记mk到n的指指针针；；IFf(n,ml)<f(ml,)f(ml)=f(n,ml),标记记ml到到n的的指指针针,ADD(ml,OPEN);7,OPEN中的的节节点点按按f值从从小小到到大大排排序序；；8,GOLOOP；；12/31/202224一个个A算算法法的的例例子子定义义评评价价函函数数：：f(n)=g(n)+h(n)g(n)为为从从初初始始节节点点到到当当前前节节点点的的耗耗散散值值h(n)为为当当前前节节点点““不不在在位位””的的将将牌牌数数283164751238476512/31/202225h计算举举例h(n)=4283164751234576812/31/2022262831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标123456定义评价价函数：：f(n)=g(n)+h(n)g(n)为从初初始节点点到当前前节点的的耗散值值h(n)为当前前节点““不在位位”的将将牌数12/31/202227最佳图搜搜索算法法A*（（A*算算法）在A算法法中，如如果满足足条件：：h(n)≤h*(n)则A算法法称为A*算法法。12/31/202228A*条件举例例8数码问问题h(n)=““不在在位”的的将牌数数h(n)=将牌“不不在位””的距离离和2

831

647512345768将牌1：1将牌2：1将牌6：1将牌8：212/31/202229A*算算法的的性质质定理1：对有限限图，，如果果从初初始节节点s到目目标节节点t有路路径存存在，，则算算法A一定定成功功结束束。12/31/202230A*算算法的的性质质（续续1））引理2.1：：对无限限图，，若有有从初初始节节点s到目目标节节点t的路路径，，则A*不不结束束时，，在OPEN表表中即即使最最小的的一个个f值值也将将增到到任意意大，，或有有f(n)>f*(s)。12/31/202231A*算算法的的性质质（续续2））引理2.2：A*结束前前，OPEN表中必必存在在f(n)≤≤f*(s)。。12/31/202232A*算算法的的性质质（续续3））定理2：对无限限图，，若从从初始始节点点s到到目标标节点点t有有路径径存在在，则则A*一定定成功功结束束。12/31/202233A*算法的的性质（续续4）推论2.1：OPEN表表上任一具具有f(n)<f*(s)的的节点n，，最终都将将被A*选选作扩展的的节点。12/31/202234A*算法的的性质（续续5）定理3(可采纳性性定理)：：若存在从初初始节点s到目标节节点t有路路径，则A*必能找找到最佳解解结束。12/31/202235A*算法的的性质（续续6）推论3.1：A*选作扩扩展的任一一节点n，，有f(n)≤f*(s)。。12/31/202236A*算算法法的的性性质质（（续续7））定理理4：：设设对对同同一一个个问问题题定定义义了了两两个个A*算算法法A1和和A2，，若若A2比比A1有有较较多多的的启启发发信信息息，，即即对对所所有有非非目目标标节节点点有有h2(n)>h1(n)，，则则在在具具有有一一条条从从s到到t的的路路径径的的隐隐含含图图上上，，搜搜索索结结束束时时，，由由A2所所扩扩展展的的每每一一个个节节点点，，也也必必定定由由A1所所扩扩展展，，即即A1扩扩展展的的节节点点数数至至少少和和A2一一样样多多。。简写写：：如如果果h2(n)>h1(n),则则A1扩扩展展的的节节点点数数≥A2扩展展的的节节点点数数12/31/202237A*算算法法的的改改进进问题题的的提提出出：：因A算算法法第第6步步对对ml类类节节点点可可能能要要重重新新放放回回到到OPEN表表中中，，因因此此可可能能会会导导致致多多次次重重复复扩扩展展同同一一个个节节点点，，导导致致搜搜索索效效率率下下降降。。12/31/202238s(10)A(1)B(5)C(8)G目标631118一个个例例子子：：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)12/31/202239出现现多多次次扩扩展展节节点点的的原原因因在前前面面的的扩扩展展中中，，并并没没有有找找到到从从初初始始节节点点到到当当前前节节点点的的最最短短路路径径，，如如节节点点A。。12/31/202240解决决的的途途径径对h加加以以限限制制能否否对对h增增加加适适当当的的限限制制，，使使得得第第一一次次扩扩展展一一个个节节点点时时，，就就找找到到了了从从s到到该该节节点点的的最最短短路路径径。。对算算法法加加以以改改进进能否否对对算算法法加加以以改改进进，，避避免免或或减减少少节节点点的的多多次次扩扩展展。。12/31/202241改进的条件可采纳性不变变不多扩展节点点不增加算法的的复杂性12/31/202242对h加以限制制定义：一个启启发函数h，，如果对所有有节点ni和和nj，其中中nj是ni的子节点，，满足h(ni)-h(nj)≤c(ni,nj)h(t)=0则称h是单调调的。h(ni)ninjh(nj)c(ni,nj)12/31/202243h单调的性质质定理5：若h(n)是是单调的，则则A*扩展了了节点n之后后，就已经找找到了到达节节点n的最佳佳路径。即：当A*选选n扩展时，，有g(n)=g*(n)。12/31/202244h单调调的性性质（（续））定理6：若h(n)是单单调的的，则则由A*所所扩展展的节节点序序列其其f值值是非非递减减的。。12/31/202245h单调调的例例子8数码码问题题：h为““不在在位””的将将牌数数1h(ni)-h(nj)=0(nj为ni的后继继节点点)-1h(t)=0c(ni,nj)=1满足单单调的的条件件。12/31/202246对算法法加以以改进进一些结结论：：OPEN表表上任任一具具有f(n)<f*(s)的的节点点定会会被扩扩展。。A*选选作扩扩展的的任一一节点点，定定有f(n)≤≤f*(s)。。12/31/202247改进的的出发发点OPEN=(……………………)f*(s)f值小于于f*(s)的节点点f值大于于等于于f*(s)的节点点fm：：到目前前为止止已扩扩展节节点的的最大大f值，用fm代替替f*(s)12/31/202248修正过过程A1,OPEN=(s),f(s)=g(s)+h(s),fm=0;2,LOOP:IFOPEN=()EXIT(FAIL);3,NEST={ni|f(ni)<fm}IFNEST≠≠()n=NEST中g最小的的节点点ELSEn=FIRST(OPEN),fm=f(n);4,……,8:同过程程A。12/31/202249s(10)A(1)B(5)C(8)G目标631118前面的的例子子：OPEN表表CLOSED表表fms(0+10)s(0+10)10A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)12/31/202250例子子：：传教教士士与与野野人人问问题题设有有3个个传传教教士士和和3个个野野人人来来到到河河边边，，打打算算乘乘一一只只船船从从右右岸岸渡渡到到左左岸岸去去。。该该船船的的负负载载能能力力为为两两人人。。在在任任何何时时候候，，如如果果野野人人人人数数超超过过传传教教士士人人数数，，那那么么野野人人就就会会把把传传教教士士吃吃掉掉。。他他们们怎怎样样才才能能用用这这条条船船安安全全地地把把所所有有人人都都渡渡河河过过去去？？12/31/202251问题题表表示示：需需要要考考虑虑两两岸岸的的修修道道士士人人数数和和野野人人人人数数，，船船的的位位置置。。用用三三元元式式表表示示状状态态：：S=(m,c,b)其其中中，，m表表示示左左岸岸修修道道士士人人数数，，c表表示示左左岸岸野野人人人人数数，，b表表示示左左岸岸船船的的数数目目。。解：确确定定估估价价函函数数。。f(n)=g(n)＋＋h(n)=d(n)＋＋m＋＋c－－2b其其中中，，d(n)为为节节点点深深度度。。h(n)＜＜h*(n)，，满满足足A*算算法法的的限限制制条条件件。。12/31/202252(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4,f=4f(n)=d(n)+m+c-2bhh=5,f=6h=4,f=5h=4,f=5(3,2,1)h=3,f=5(2,1,0)(3,0,0)h=3,f=6h=3,f=6(2,2,1)(3,1,1)h=2,f=6h=2,f=6h=2,f=7h=2,f=7传教士和野人问题的A*搜索图(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0)(1,1,0)12/31/2022534.5AO*算算法法搜索索与或或图图的A*算算法法节点点评评价价方方法法A*算算法法中中，，对对节节点点n的的评评价价，，实实际际上上是是对对““初始始节节点点--节节点点n--目目标标节节点点”这这一一条条路路径径的的评评价价AO*算算法法中中，，由由于于与与节节点点的的存存在在，，解解对对应应的的不不是是一一条条路路径径，，而而是是一一个个子子图图，，因因此此对对节节点点的的评评价价，，实实际际是是对对局部部解解图图的评评价价12/31/202254A(6)BCD(3)(4)(5)f(A)=min{(B)+(C)+2,(D)+1}GHEF(4)(4)(5)(7)(10)(9)(6)(11)与或图节节点扩展展与评价价12/31/202255算法的两两个阶段段第一阶段段：自上上而下的的图生成成过程对于每一一个已经经扩展过过的节点点，都都对应一一个指针针，指向向该节点点后继节节点中，，代价值值小的那那条边。。图生成成过程，，就是从从初始节节点出发发，按照照该指针针向下搜搜索，一一直到找找到一个个未扩展展的节点点为止。。然后扩扩展该节节点。第二阶段段：自下下而上的的代价值值计算过过程设n为最最新被扩扩展的节节点，计计算节点点n对应应的最小小代价值值，并标标记一个个指针指指向对应应最小代代价的边边。对于于n的父父节点，，进行同同样的计计算。重重复这一一过程，，直到初初始节点点s为止止。这时时，从s出发，，选择那那些指针针所指向向的边得得到的局局部图，，为当前前代价值值最小的的局部图图。12/31/202256具体步骤骤Step1建建立一个个仅由初初始节点点s构成成的搜索索图G，，计算h(s)Step2在在以下两两过程间间循环，，直到s标记为为可解或或不可解解，或其其代价值值大于阈阈值：2.1选选择节节点进行行扩展2.2根根据扩扩展情况况修改节节点的可可解性与与代价值值12/31/202257Step2.1选择择节点进进行扩展展：1根据据指针找找出待扩扩展的局局部解图图G′。。2选择择G′中中的一个个非终节节点n作作为当前前节点。。3扩展展节点n，如不不能扩展展，则标标记为不不可解，，否则生生成子节节点集，，如子节节点为非非终节点点，计算算其代价价值，若若为终节节点，标标注其可可解。将将所有子子节点添添加到G中。4建立立含n的的单一节节点集合合S，，S:＝＝{n}12/31/202258Step2.2修修改节点点的可解解性与代代价值重复以下下步骤，，直到S为空：：1从S中挑选选一个子子孙节点点都不在在S中的的节点m2计算算始于m的每条条连接线线的代价价，取其其中最小小值为m对应的的代价，，并在对对应于最最小代价价的连接接线上加加指针。。3如果果连接于于最小代代价连接接线上的的所有节节点都可可解，则则标注m可解。。4如果果m的可可解性或或代价值值发生改改变，则则把m的的所有祖祖先节点点添加到到S中。。12/31/202259AO*算法举举例目标目标初始节点n0n1n2n3n4n5n6n7n8h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0连接线的代价价=后继节点个数数12/31/202260n0n1n2n3n4n5n6n7n8n0(3)n1(2)n4(1)n5(1)红色代价：4蓝色代价：312/31/202261n0n1n2n3n4n5n6n7n8n4(1)n5(1)红色代价：4蓝色代价：6n1(2->5)n2(4)n3(4)n0(3)n0(3->4)12/31/202262n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1->2)12/31/202263n0n1n2n3n4n5n6n7n8红色代价：5蓝色代价：6n0(4)n4(1)n5(1->2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4->5)12/31/202264n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)12/31/202265目标目标初始节点n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)12/31/202266目标标目标标初始始节节点点n0n1n2n3n4n5n6n7n8初始始节节点点可可解解n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)12/31/202267归结结原原理理概述述命题题逻逻辑辑的的归归结结法法子句句形形Herbrand定定理理归结结原原理理归结结过过程程的的策策略略控控制制12/31/202268归结原原理概述命题逻逻辑的的归结结法子句形形Herbrand定定理归结原原理归结过过程的的策略略控制制12/31/202269概述归结原原理由J.A.Robinson由1965年年提出出。与演绎绎法完完全不不同，，新的的逻辑辑演算算算法法。一阶逻逻辑中中，至至今为为止的的最有有效的的半可可判定定的算算法。。即，，一阶阶逻辑辑中任任意恒恒真公公式，，使用用归结结原理理，总总可以以在有有限步步内给给以判判定。。语义网网络、、框架架表示示、产产生式式规则则等等等都是是以推推理方方法为为前提提的。。即，，有了了规则则已知知条件件，顺顺藤摸摸瓜找找到结结果。。而而归结结方法法是自自动推推理、、自动动推导导证明明用的的。（（“数数学定定理机机器证证明””）本课程程只讨讨论一一阶谓谓词逻逻辑描描述下下的归归结推推理方方法，，不涉涉及高高阶谓谓词逻逻辑问问题。12/31/202270归结原原理概述命题逻逻辑的的归结结法子句形形Herbrand定定理归结原原理归结过过程的的策略略控制制12/31/202271归结原原理概述命题逻逻辑的的归结结法子句形形Herbrand定定理归结原原理归结过过程的的策略略控制制12/31/202272命题逻辑辑的归结结法基本单元元：简单单命题（（陈述句句）例：命题：A1、A2、A3和B求证：A1ΛA2ΛA3成立，则则B成立立，即：A1ΛA2ΛA3→B反证法：：证明A1ΛA2ΛA3Λ～B是是矛盾盾式（永假式式）12/31/202273命题逻辑辑的归结结法建立子句句集合取范式式：命题题、命题题和的与与，如如：PΛ（P∨Q）Λ（（～P∨Q））子句集S：合取范范式形式式下的子子命题（（元素））的集合合例：命题题公式：：PΛ（P∨Q）Λ（（～P∨Q））子句集S：S={P,P∨∨Q,～～P∨∨Q}12/31/202274命题逻辑辑的归结结法归结式消除互补补对，求求新子句句→得到归结结式。如子句：：C1=C1′∨L,C2=C2′∨归结式：：R(C1,C2)=C1′∨C2′注意：C1ΛC2→R(C1,C2)，反之之不一定成立。假言推理理:由合适公公式W1和W1→W2产生合适适公式W2,如何用用归结法法证明?12/31/202275命题逻辑辑的归结结法归结过程程对结论作作否定,并加入入前提中中将命题写写成合取取范式求出子句句集对子句集集使用归归结推理理规则归结式作作为新子子句参加加归结归结式为为空子句句□，S是不不可满足足的（矛矛盾），，原命题题成立。。（证明完完毕）谓词的归归结：除除了有量量词和函函数以外外，其余余和命题题归结过过程一样样。12/31/202276命题逻辑辑的归结结法例证明先将化为合取取范式建立子句句集S=对S做归归结PNIL12/31/202277归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制12/31/202278归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制12/31/202279子句形引用Herbrand定理，，以说明明归结原原理的意意义及一一个原理理形成的的根基与与背景SKOLEM标标准形前束范式式：把所有有的量词词都提到到前面去去，然后后消掉所所有量词词。定义：说公式式A是一一个前束束范式，，如果A中的一一切量词词都位于于该公式式的最左左边（不不含否定定词），，且这些些量词的的辖域都都延伸到到公式的的末端。。即(Q1x1)…(Qnxn)M(x1,…,xn),其中Qixi为存在量量词或全全称量词词,M(x1,…,xn)为合取范范式(由由一些子子句的合合取组成成)。12/31/202280子句形(Skolem标准准形)量词消去原则则：消去存在量词词“”，略去全程程量词“”。注意：左边有全称量量词的存在量量词，消去时时该变量改写写成为全称量量词的函数(Skloem函数)；；如没有，改改写成为常量量。例子：见《人人工智能及其其应用》P7512/31/202281子句形(Skolem标准准形)定理：谓词逻辑的任任意公式都可可以化为与之之等价的前束束范式，但其其前束范式不不唯一。SKOLEM标准形定义义：消去量词后的的谓词公式。。注意：谓词公式G的SKOLEM标准形形同G并不等值。12/31/202282子句形(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)12/31/202283子句形子句与子句集集文字：不含任任何连接词的的谓词公式。。子句：一些文文字的析取（（谓词的和））。子句集S的求取：G→SKOLEM标准形形→消去存在在变量→以“，”取代“Λ”，并表示为为集合形式。。12/31/202284子句形形G是不不可满满足的的<=>S是不不可满满足的的G与S不等价价，但但在不不可满满足的的意义义下是是一致致的。。定理：：若G是是给定定的公公式，，而S是相相应的的子句句集，，则G是不不可满满足的的<=>S是不不可满满足的的。注意：G真不不一定定S真真，而而S真真必有有G真真。即：S=>G12/31/202285子句形形G=G1ΛG2ΛG3Λ……ΛGn的子句句形G的子句句集可可以分分解成成几个个单独独处理理。有SG=S1US2US3U……USn则SG与S1US2US3U……USn在不可可满足足的意意义上上是一一致的的。即SG不可满满足<=>S1US2US3U……USn不可满满足12/31/202286归结原原理概述命题逻逻辑的的归结结法子句形形Herbrand定定理归结原原理归结过过程的的策略略控制制12/31/202287归结原原理概述命题逻逻辑的的归结结法子句形形Herbrand定定理归结原原理归结过过程的的策略略控制制12/31/202288Herbrand定理理问题题：：一阶阶逻逻辑辑公公式式的的永永真真性性（（永永假假性性））的的判判定定是是否否能能在在有有限限步步内内完完成成？12/31/202289Herbrand定理理1936年年图图灵灵(Turing)和和邱邱吉吉(Church)互互相相独独立立地地证证明明了了：：“没没有有一一般般的的方方法法使使得得在在有有限限步步内内判判定定一一阶阶逻逻辑辑的的公公式式是是否否是是永永真真（（或或永永假假））。。但但是是如如果果公公式式本本身身是是永永真真（（或或永永假假））的的，，那那么么就就能能在在有有限限步步内内判判定定它它是是永永真真（（或或永永假假））。。对对于于非非永永真真（（或或永永假假））的的公公式式就就不不一一定定能能在在有有限限步步内内得得到到结结论论。。判判定定的的过过程程将将可可能能是是不不停停止止的的。。””12/31/202290Herbrand定理理Herbrand的的思思想想定义义：：公式式G永永真真：：对对于于G的的所所有有解解释释，，G都都为为真真。。思想想：：寻找找一一个个已已给给的的公公式式是是真真的的解解释释。。然然而而，，如如果果所所给给定定的的公公式式的的确确是是永永假假的的，，就就没没有有这这样样的的解解释释存存在在，，并并且且算算法法在在有有限限步步内内停停止止。。12/31/202291Herbrand定理H域H解释语义树结论：Herbrand定理理12/31/202292Herbrand定理H域H解释语义树结论：Herbrand定理理12/31/202293Herbrand定理理（H域））基本方法法：因为量词是任任意的，，所讨论论的个体体变量域域D是任任意的，，所以解解释的个个数是无无限、不不可数的的。简化讨论论域。建建立一个个比较简简单、特特殊的域域，使得得只要在在这个论论域上，，该公式式是不可可满足的的。此域称为为H域：：H0为G中所所出现的的常量的的集合，，若G中中没有常常量，就就任取常常量，，H0={a}。规定为为H域※例题请参参考教科科书P2712/31/202294H域举例例例1S={P(a),～P(x)∨P(f(x))}依定义有有H0={a}H1={a}U{f(a)}={a,f(a)}H2={a,f(a)}U{f(a),f(f(a))}={a,f(a),f(f(a))}…H∞={a,f(a),f(f(a))，……}12/31/202295Herbrand定定理（H域域）几个基基本概概念f（t1,t2,……tn）：f为为子句句集S中的的所有有函数数变量量。t1,t2,……tn为S的的H域域的元元素。。通过过它们们来讨讨论永永真性性。原子集集A：：谓词词套上上H域域的元元素组组成的的集合合。如如A={所有有形如如P(t1,t2,……tn)的元素素}即把H中的的东西西填到到S的的谓词词里去去。S中的的谓词词是有有限的的，H是可可数的的，因因此，，A也也是可可数的的。一旦原原子集集内真真值确确定好好（规规定好好），，则S在H上的的真值值可确确定。。成为为可数数问题题。12/31/202296原子集集举例例例1S={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))),…}12/31/202297Herbrand定定理（H域域）没有变变量出出现的的原子子、文文字、、子句句和子子句集集，分别称称作基基原子子、基基文字字、基基子句句和基基子句句集。。它们在在讨论论子句句集S的不不可满满足性性时占占有重重要置置。12/31/202298Herbrand定理H域H解释语义树结论：Herbrand定理理12/31/202299Herbrand定理H域H解释语义树结论：Herbrand定理理12/31/2022100Herbrand定定理（H解释））解释I*：取一个值值得到一个个结论I映射S中到所有常常量符号到到它们本身身。(即原原子集)令f是n元函数，I是f下的一个指指派，即H中的元素素到f的一个映射射（函数值值）。简单单地说(P29)，，A中的各各元素真假假组合都是是H的解释释。（或真真或假只取取一个）问题：对于所有的的解释，全全是假才可可判定。因因为所有解解释代表了了所有的情情况，如可可穷举，问问题便可解解决。12/31/2022101H解释-举举例例1S={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解释释：I1*={P(a),P(f(a)),P(f(f(a))),…}S|I1*=TI2*={～P(a),P(f(a)),P(f(f(a))),…} S|I2*=FI3*={P(a),～P(f(a)),P(f(f(a))),…} S|I3*=F我们关心的的是：对论论域上的任任一解释I，若有S|I=T,如何何求得一个个相应的H解释I*,使得S|I*=T成立。。12/31/2022102Herbrand定定理理（H解解释释））如下下三三个个定定理理保保证证了了归归结结法法的的正正确确性性：：定理理1：设I是S的论论域域D上上的的解解释释，，存存在在对对应应于于I的H解解释释I*，使使得得若若有有S|I=T，必必有有S|I*=T。定理理2：子句句集集S是不不可可满满足足的的，，当当且且仅仅当当所所有有的的S的H解解释释下下为为假假。。定理理3：子句句集集S是不不可可满满足足的的，，当当且且仅仅当当对对每每一一个个解解释释I下，，至至少少有有S的某某个个子子句句的的某某个个基例例为假假。。12/31/2022103Herbrand定定理理（H解解释释））基例例S中某某子子句句中中所所有有变变元元符符号号均均以以S的H域域中中的的元元素素代代入入时时，，所所得得的的基基子子句句C’’称为为C的一一个个基基例例。。若一一个个子子句句为为假假，，则则此此解解释释为为假假。。一般般来来说说，，D是是无无穷穷不不可可列列的的，，因因此此，，子子句句集集S也是是无无穷穷不不可可列列的的。。但但S确定定后后H是是无无穷穷可可列列的的。。不不过过在在H上上证证明明S的不不可可满满足足性性仍仍然然是是不不可可能能的的。。解决决问问题题的的方方法法：：语义义树树12/31/2022104Herbrand定理理H域域H解解释释语义义树树结论论：：Herbrand定定理理12/31/2022105Herbrand定理H域H解释语义树结论：Herbrand定理12/31/2022106Herbrand定理（语义树）构成方法原子集中所有有元素逐层添添加的一棵二二叉树。将元元素的是与非非分别标记在在两侧的分枝枝上（可不完完全画完）。。(P34)特点一般情况H是是可数集，S的语义树是无无限树。12/31/2022107Herbrand定理（语义树）意义SHA语义义树可以理解语义义树为H域的的图形解释。。目的：把每个个解释都摊开开。语义树中中包含原子集集的全部元素素，因此，语义树是完全全的。每一个直到叶叶子节点的分分支对应S的一个解释。。可以通过对对语义树每一一个分支来计计算S的真值。如果果每个基例都都为假，则可可认为是不可可满足的。12/31/2022108语义树-举例例例1设设子句集S的的原子集A={P,Q,R}语义树：N0N11N12N21N22N23N24N31N32N33N34N35N36N37N38P～QQR～R～PI(N)表示从从根节节点到到节点点N分分枝上上所标标记的的所有有文字字的并并集。。如I(N34)={P,～Q,～R}12/31/2022109Herbrand定定理（语义义树））几个概概念失败结结点：当（由由上））延伸伸到点点N时，I(N)已表明明了S的某子子句的的某基基例假假。但但N以前尚尚不能能判断断这事事实。。就称称N为失败败结点点。完全语语义树树：如果对对语义义树的的所有有叶结结点N来说说，I(N)包含了了S的的原子子集A={A1,A2,…}中的的所有有元素素Ai或～Ai，I=1…n。。封闭语语义树树：如果S的完全全语义义树的的每个个分枝枝上都都有一一个失失败结结点，，就称称它是是一棵棵封闭闭语义义树。。12/31/2022110封闭语语义树树-举举例例子子句句集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)),…}语义树树：N0N11N12N21N22N23N24N31N32N33N34N35N36N37N38P(a)Q(a)P(f(a))N41N42N43N44N45N46N47N48N49N410N411N413N415N412N414N416这是一一个无无限树树，然然而它它是否否是一一个封封闭树树？Q(f(a))ΧΧΧΧΧΧΧΧΧΧI(N41)={P(a),Q(a),P(f(a)),Q(f(a))},它它使S的子子句～Q(f(y))的的基例～Q(f(a))为假，而N41的父辈辈不能能使子子句的的基例例为假假12/31/2022111封闭语语义树树-举举例例子子句句集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)),…}封闭语语义树树：N0N11N12N21N22N23N24N31N32N36N37N38P(a)Q(a)P(f(a))N41N42N49N410N413N414Q(f(a))ΧΧΧΧΧΧΧΧΧΧ12/31/2022112Herbrand定理H域H解释语义树结论：Herbrand定理理12/31/2022113Herbrand定理H域H解释语义树结论：Herbrand定理理12/31/2022114Herbrand定理理（结论））Herbrand定理理：子句集S是不可满满足的，，当且仅仅当对应应于S的完全语语义数是是棵有限限封闭树树。子句集S是不可满满足的，，当且仅仅当存在在不可满满足的S的有限基基例集。。12/31/2022115Herbrand定理理（结论））定理的意意义Herbrand定理理已将证证明问题题转化成成了命题题逻辑问问题。由此定理理保证，，可以放放心的用用机器来来实现自自动推理理了。（（归结原原理）注意Herbrand定理理给出了了一阶逻逻辑的半半可判定定算法，，即仅当当被证明明定理是是成立时时，使用用该算法法可以在在有限步步得证。。而当被被证定理理并不成成立时，，使用该该算法得得不出任任何结论论。但是12/31/2022116例S={P(x,g(x),y,h(x,y),z,k(x,y,z)),～P(u,v,e(v),w,f(v,w)),x)}有H0={a},S0´={P(a,g(a),a,h(a,a),a,k(a,a,a)),～P(a,a,e(a),a,f(a,a)),a)}H1={a,g(a),h(a,a),k(a,a,a),e(a),f(a,a)}共6个元元素S1´：63+64=1512个元素H2：元素个数数有63数量级（（由于变变量最多多的函数数是k(x,y,z),三个个变量量都可可能取值值于H1的六个元元素）S2´：元素个数数有(63)4数量级建立S3´，S4´，直到S5´才是不可可满足。。然而S5´元素个数数已达（1064）4=10256Herbrand定理理（结论））仍存在的的问题：基例集序序列元素素的数目目随子句句基的元元素数目目成指数数地增加加。因此，Herbrand定理理是30年代提提出的，，始终没没有显著著的成绩绩。直至1965年年Robinson提提出了归结原理理。12/31/2022117归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制12/31/2022118归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制12/31/2022119归结原理归结原理正正确性的根根本在于，，找到矛盾盾可以肯定定不真。方法：和命题逻辑辑一样。但由于有函函数，所以以要考虑合一和置换。(定义与例例题参考教教科书P41)12/31/2022120归结原理置换和合一一的注意事事项：谓词的一致致性，P()与Q()，不可以以常量的一致致性，P(a,……)与P(b,…….)，不可以以常量与变量量，P(a,…….)与P(x,……)，可以变量与函数数，P(a,x,…….)与P(x,f(x),…)，不可以；；但P(a,x,……)与P(x,f(y),…)，可以是不能同时时消去两个个互补对，，P∨Q与～P∨～Q的空，不可可以先进行内部部简化（置置换、合并并）12/31/2022121归结原理归结的过程程(P48)写出谓词关关系公式→→用反演法写写出谓词表表达试→→SKOLEM标准形形→子句集S→对S中可归结的的子句做归归结→归结式仍放放入S中，反复归归结过程→→得到空子句句▯得证12/31/2022122归结原理归结法的实实质：归结法是仅仅有一条推推理规则的的推理方法法。归结的过程程是一个语语义树倒塌塌的过程。。(P51)归结法的问问题子句中有等等号或不等等号时，完完备性不成成立。※Herbrand定定理的不实实用性引出出了可实用用的归结法法。12/31/2022123归结原理概述命题逻辑的的归结法子句形Herbrand定定理归结原理归结过程的的策略控制制12/31/2022124归结原理概述命题逻辑的的归结法子句形Herbrand定定理归结原理归结过程的的策略控制制12/31/2022125归结过程的的控制策略略要解决的问问题：归结方法的的知识爆炸炸。控制策略的的目的归结点尽量量少控制策略的的原则给出控制策策略，以使使仅对选择择合适的子子句间方可可做归结。。避免多余余的、不必必要的归结结式出现。。或者说，，少做些归归结仍能导导出空子句句。12/31/2022126归结过程的控控制策略盲目归结例S={P∨Q,～P∨Q,P∨～Q,～P∨～Q}是不可满足足。证明从S0=S开始，依依次构造Si={C1,C2的归结式|C1∈S0∪S1∪…∪Si-1,C2∈Si-1},i=1,2,…,直至至得到空子句句。具体过程程如下：S0(1)P∨Q(2)～P∨Q(3)P∨～Q(4)～P∨～QS1(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)12/31/2022127归结过程的控控制策略(盲盲目归结)S2(13)P(1)(7)(14)P∨∨Q(1)(8)(15)P∨∨Q(1)(9)(16)P∨∨Q(1)(10)(17)Q(1)(11)(18)P(1)(12)(19)Q(2)(6)(20)～P∨Q(3)(4)(21)～P∨Q(2)(8)(22)～P∨Q(2)(9)(23)～P∨Q(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(