人工智能一般搜索原理

搜索技术问题提出：有了知识表示方法之后，就需求有处理问题的方法，也就是搜索技术。所谓搜索，就是寻觅一条从初始问题到问题解的途径本章内容：搜索技术有许多种，本章引见一些早期的、比较简单的搜索原理：1，盲目搜索；2，启发式搜索；3，消解原理；4，通用问题求解技术关键问题： 如何利用知识，尽能够有效地找到问题的解(最正确解)。第三章普通搜索原理12/25/20231普通搜索原理搜索战略可分为三大类不可撤回方式、回朔方式、图搜索方式不可撤回方式：每一次搜索时，利用部分知识根据最优评价，选出下一形状，选定后不能撤回，只能继续回朔方式：在搜索过程中，有时会发现所选的途径不适宜找到目的，这时允许退回去另选一条途径。图搜索方式：假设把问题求解过程用图来表示。节点代表问题的形状，弧代表形状变化的方向，那么搜索就变成对图进展从初始节点开场，到目的节点途径的搜索。第三章普通搜索原理3.1盲目搜索12/25/20232回溯搜索战略例：皇后问题第三章普通搜索原理3.1盲目搜索12/25/20233()皇后问题搜索过程〔一〕第三章普通搜索原理3.1盲目搜索12/25/20234Q()((1,1))皇后问题搜索过程〔二〕第三章普通搜索原理3.1盲目搜索12/25/20235QQ()((1,1))((1,1)(2,3))皇后问题搜索过程〔三〕第三章普通搜索原理3.1盲目搜索12/25/20236Q()((1,1))((1,1)(2,3))皇后问题搜索过程〔四〕第三章普通搜索原理3.1盲目搜索12/25/20237QQ()((1,1))((1,1)(2,3))((1,1)(2,4))皇后问题搜索过程〔五〕第三章普通搜索原理3.1盲目搜索12/25/20238QQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后问题搜索过程〔六〕12/25/20239QQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后问题搜索过程〔七〕12/25/202310Q()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后问题搜索过程〔八〕12/25/202311()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后问题搜索过程〔九〕12/25/202312Q()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))第三章普通搜索原理3.1盲目搜索皇后问题搜索过程〔十〕12/25/202313QQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))第三章普通搜索原理3.1盲目搜索皇后问题搜索过程〔十一〕12/25/202314QQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))第三章普通搜索原理3.1盲目搜索皇后问题搜索过程〔十二〕12/25/202315QQQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))((1,2)(2,4)(3,1)(4,3))第三章普通搜索原理3.1盲目搜索皇后问题搜索过程〔十三〕12/25/202316递归的思想从前有座山……从前有座山……从前有座山……第三章普通搜索原理3.1盲目搜索12/25/202317一个递归的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}第三章普通搜索原理3.1盲目搜索12/25/202318回溯搜索算法阐明 BACKTRACK〔DATA〕

DATA：当前形状。 前往值：从当前形状到目的形状的途径 〔以规那么表的方式表示〕 或FAIL。第三章普通搜索原理3.1盲目搜索12/25/202319回溯搜索算法〔一〕递归过程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);第三章普通搜索原理3.1盲目搜索TERM:找目的DEADEND:形状不合法,无法继续搜索APPRULES:取可运用规那么集12/25/202320回溯搜索算法〔二〕4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);第三章普通搜索原理3.1盲目搜索TAIL:删除头条规那么GEN:调用规那么作用于当前形状CONS:获取解途径规那么表12/25/202321存在问题及处理方法问题：深度问题:假设深度太深死循环问题:假设形状出现反复处理方法：对搜索深度加以限制记录从初始形状到当前形状的途径第三章普通搜索原理3.1盲目搜索12/25/202322添加约束后的回溯搜索算法BACKTRACK1〔DATALIST〕

DATALIST：从初始到当前的形状表〔逆向〕 前往值：从当前形状到目的形状的途径 〔以规那么表的方式表示〕 或FAIL。第三章普通搜索原理3.1盲目搜索12/25/202323添加约束后的回溯搜索算法(一)1, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL; 3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;第三章普通搜索原理3.1盲目搜索12/25/202324添加约束后的回溯搜索算法(二)6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);9, RULES:=TAIL(RULES);第三章普通搜索原理3.1盲目搜索12/25/202325添加约束后的回溯搜索算法(三)10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);第三章普通搜索原理3.1盲目搜索12/25/202326一些深化的问题失败缘由分析、多步回溯QQ第三章普通搜索原理3.1盲目搜索12/25/202327一些深化问题〔续〕回溯搜索中知识的利用 根本思想： 尽能够选取划去对角线上位置数最少的。QQQQ4334第三章普通搜索原理3.1盲目搜索12/25/202328方式导向搜索这个算法是将递归搜索运用到谓词演算的通用搜索算法要判别一个谓词表达式是某个断言集合的逻辑结论首先谓词表达式作为目的，运用合一来选择能与其后件匹配的蕴涵式并把得到的置换运用于该蕴涵式的前件这个前件成了新的目的—称其为子目的运用递归搜索解这个子目的假设与现实相匹配，那么搜索结实

第三章普通搜索原理3.1盲目搜索12/25/202329方式导向搜索算法描画一Functionpattern_search(current_goal)beginifcurrent_goalisinclosedthenreturnFAILelseputcurrent_goalintoclosedwhileeveryruleandfactsdobegincasecurrent_goal与现实合一returnSUCCESS

第三章普通搜索原理3.1盲目搜索12/25/202330方式导向搜索算法描画二current_goal是合取式beginforevery合取项itemdoret=pattern_search(item)ifret==FAILthenreturnFAILendcurrent_goal与规那么的后件合一begin对前件q运用对应的合一置换ret=pattern_search(q)ifret==FAILthenreturnFAILelseSUCCESSendendreturnFAILend第三章普通搜索原理3.1盲目搜索12/25/202331图搜索战略图搜索战略就是在图中寻觅从起始点到目的点的途径的方法图搜索的普经过程是构造搜索图的过程。令搜索图开场时只需起始点S0，然后逐渐扩展节点，直到将目的点扩展到搜索图里为止。扩展的过程就是搜索的过程扩展节点的方法不同，就意味着搜索的方法不同，也就是搜索的途径不同。

第三章普通搜索原理3.1盲目搜索12/25/202332图搜索战略图示S0Sg第三章普通搜索原理3.1盲目搜索12/25/202333节点扩展扩展一个节点 生成出该节点的一切后继节点，并给出它们之间的代价值。这一过程称为“扩展一个节点〞。第三章普通搜索原理3.1盲目搜索12/25/202334途径途径 设一节点序列为(n0,n1,…,nk)，对于i=1…k，假设节点ni-1具有一个后继节点ni，那么该序列称为从n0到nk的途径。途径的代价值 一条途径的代价值等于衔接这条途径各节点间一切代价值的总和。用C(ni,nj)表示从ni到nj的途径的代价值。第三章普通搜索原理3.1盲目搜索12/25/202335节点深度节点深度： 根节点深度=0 其它节点深度=父节点深度+10123第三章普通搜索原理3.1盲目搜索12/25/202336图搜索的普经过程第三章普通搜索原理3.1盲目搜索胜利是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供前往节点n的指针修正指针方向把S放入OPEN表重排OPEN表是否否OPEN为空？n为目的节点？失败开场12/25/202337图搜索过程阐明我们在搜索过程中用到了OPEN表和CLOSED表两个数据构造OPEN表中的节点都是搜索树的端节点，即至今尚未被选作为扩展的节点CLOSED表中的节点或者是已被扩展而不能生成后继节点的那些端节点，或者是搜索树的非端节点重排OPEN表，实践上就是在选择搜索顺序，也就是扩展的节点的顺序。第三章普通搜索原理3.1盲目搜索12/25/202338节点类型阐明…...mj…...mk…...…...…...ml第三章普通搜索原理3.1盲目搜索扩展的节点OPEN表没有的部分扩展的节点在已在close表中的部分扩展的节点已在OPEN表中的部分选定的扩展节点12/25/202339第三章普通搜索原理3.1盲目搜索图搜索过程的图示〔一〕现要扩展它12/25/202340第三章普通搜索原理3.1盲目搜索图搜索过程的图示〔二〕修正父子关系现要扩展它12/25/202341第三章普通搜索原理3.1盲目搜索图搜索过程的图示〔三〕修正父子关系修正父子关系12/25/202342盲目搜索概述盲目搜索也叫无信息搜索盲目搜索实践上是对解空间的遍历盲目搜索包括有：宽度优先搜索：搜索以接近起始节点的程度依次扩展节点，在对下一层搜索前，必需搜索完本层的一切节点。深度优先搜索：搜索首先扩展最新产生的节点。等代价搜索：搜索沿最小代价节点进展扩展。

第三章普通搜索原理3.1盲目搜索12/25/202343宽度优先搜索胜利是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供前往节点n的指针把S放入OPEN表是否否OPEN为空？能否有任何后继节点为目的节点？失败开场第三章普通搜索原理3.1盲目搜索12/25/202344目的231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765125673123847658234187654第三章普通搜索原理3.1盲目搜索八数码难题的宽度优先搜索树按上下左右序走步12/25/202345宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位代价值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法第三章普通搜索原理3.1盲目搜索12/25/202346第三章普通搜索原理3.1盲目搜索深度优先搜索胜利是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的前端，提供前往节点n的指针把S放入OPEN表是否否OPEN为空？节点n的深度能否等于深度界限？失败开场能否有任何后继节点为目的节点？是否S能否为目的节点？否胜利12/25/202347231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765123456789abcd12384765目的。。。。。。。。。。第三章普通搜索原理3.1盲目搜索八数码难题的深度优先搜索树12/25/202348深度优先搜索的性质普通不能保证找到最优解当深度限制不合理时，能够找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举是一个通用的与问题无关的方法第三章普通搜索原理3.1盲目搜索12/25/202349第三章普通搜索原理3.1盲目搜索等代价搜索胜利是把具有最小g(i)值的节点i从OPEN表移至CLOSED表计算其后继节点j的g(j)值。把其后继节点放入OPEN表把S放入OPEN表否否OPEN为空？失败开场i能否为目的节点？是S能否为目的节点？否胜利是令g(s)=012/25/202350什么是启发式搜索盲目搜索的效率低，耗费过多的计算时间和空间，容易产生组合爆炸。利用知识来引导搜索，到达减少搜索范围，降低问题复杂度的目的。对搜索产生协助的信息称为启发信息第三章普通搜索原理3.2启发式搜索12/25/202351启发式信息对搜索方法的影响启发信息的多少用启发信息强度来表示不同的启发信息对搜索方法带来不同的影响：强：降低搜索任务量，但能够导致找不到最优解弱：普通导致任务量加大，极限情况下变为盲目搜索，但能够可以找到最优解第三章普通搜索原理3.2启发式搜索12/25/202352启发式搜索类型启发信息按用途可分为3类：用于决议要扩展的下一个节点〔这个节点称为最有希望的节点〕，以免像在宽度优先或深度优先搜索中那样盲目地扩展在扩展一个节点的过程中，用于决议要生成哪些其后继节点，以免盲目地生成一切节点。用于决议哪些节点应从搜索树中丢弃或修剪。用来估算节点希望程度的方法为估价函数第三章普通搜索原理3.2启发式搜索12/25/202353对启发式搜索的认识有些启发信息可以大大减少搜索任务量，但不能保证可以得到最小代价途径我们往往希望获得途径代价和求该途径所需的搜索代价的综合为最小由于计算综合代价很困难，因此，比较两种方法的优劣，依赖运用的阅历运用估价函数实践是对OPEN表进展排序，再按顺序扩展节点，进展搜索第三章普通搜索原理3.2启发式搜索12/25/202354有序搜索假设按估价函数的增序对OPEN表进展排序，这种搜索方法叫做有序搜索或最正确优先搜索有序搜索的有效性取决于估价函数的选择，否那么有能够失去一个最好的解甚至全部的解假设没有适宜的选择，可思索两个方面的内容：一个是时间和空间的折中保证有一个解第三章普通搜索原理3.2启发式搜索12/25/202355有序搜索框图第三章普通搜索原理3.2启发式搜索胜利是选取f值最小的节点i，从OPEN表移至CLOSED表扩展i，计算后继节点j的f(j)，对OPEN表重排序，调整亲子关系把S放入OPEN表，计算f(s)是否否OPEN为空？i是目的节点？失败开场12/25/202356估价函数：f(n)=d(n)+w(n)其中，d(n):节点的深度w(n):节点放错棋子数目第三章普通搜索原理3.2启发式搜索八数码难题的有序搜索树28316475231847652831476523184765283147651238476528314765283164752831647528371465832147651237846523184765546466775675512384765目的5估价函数值12/25/202357A算法A算法是一种有序搜索的启发式搜索算法。它采用估算节点n的两个代价：从起始点s到n的最小代价途径的代价从n到某个目的节点的最小代价途径的代价估价函数的方式： f(n)=g(n)+h(n)其中：g(n)：是对g*(n)的估价值h(n)：是对h*(n)的估价值,称为启发函数第三章普通搜索原理3.2启发式搜索12/25/202358A算法估价函数的阐明g*(n)：从s到n的最正确途径的代价h*(n)：从n到某个目的节点的最正确途径的代价f*(n)=g*(n)+h*(n)：从s经过n到某个目的节点的最正确途径的代价g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值阐明，估价函数f(n)是对从起始点s经过n到某个目的节点的最正确途径的代价的估计值第三章普通搜索原理3.2启发式搜索12/25/202359A算法流程1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi}, 计算f(n,mi):=g(n,mi)+h(mi);

第三章普通搜索原理3.2启发式搜索12/25/202360A算法流程〔续〕 ADD(mj,OPEN),标志mj到n的指针； IFf(n,mk)<f(mk)THENf(mk):=f(n,mk), 标志mk到n的指针； IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml), 标志ml到n的指针, ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序；8,GOLOOP；第三章普通搜索原理3.2启发式搜索12/25/202361最正确图搜索算法A*〔A*算法〕在A算法中，假设对于恣意点n满足条件： h(n)≤h*(n) 那么A算法称为A*算法。第三章普通搜索原理3.2启发式搜索12/25/202362A*算法估价函数举例在问题求解过程中，不能够明确知道h*(n)，可根据阅历估计下界范围条件例如，8数码问题如取h(n)=“不在位〞的牌数，可估计出至少要挪动h(n)步，才干到达目的，因此，有h(n)≤h*(n)如取h(n)=每个牌与目的位置的间隔和，同样可估计出至少要挪动h(n)步，才干到达目的，因此，有h(n)≤h*(n)第三章普通搜索原理3.2启发式搜索283164751238476512/25/202363博弈中的启发式搜索博弈空间的极小极大搜索:假定对手具有一样的关于形状空间的知识,且用该知识以一致方式竞赛.博弈中的对手分别称为MIN和MAX一种余一棋变体：博弈双方要交替地将一堆牌分成数量不同的两堆牌,最先无法分堆的棋手为失败第三章普通搜索原理3.2启发式搜索12/25/202364穷举式的极小极大搜索博弈过程可以用一个树来表示标志叶节点假设MIN获胜标0,MAX获胜标1,标志MIN节点为其子节点值中的最大值标志MAX节点为其子节点值中的最小值这样向上传播,直至根节点第三章普通搜索原理3.2启发式搜索12/25/202365第三章普通搜索原理3.2启发式搜索一种余一棋变体树4-34-2-15-1-175-22-2-1-1-13-2-1-16-14-1-1-12-2-2-13-1-1-1-12-1-1-1-1-13-2-200110111111003-3-10MINMAXMINMAXMINMAX12/25/202366固定层深的极小极大搜索这种战略称为n-层预判用于形状空间不能够全部展开的情形，比如国际象棋的形状数大约是10120n的值由可用的时间和空间资源而定由于叶节点不是博弈的最终形状,不能用胜利或失败来标志需用某个启发评价函数的值来标志这个向上传播的值不表示能否可以胜利,只表示经过n步可到达的最正确形状,也能够是完全误导性的大多数博弈都为设计启发提供了无限的想象空间第三章普通搜索原理3.2启发式搜索12/25/202367第三章普通搜索原理3.2启发式搜索一种九宫游戏的启发函数启发值为对MAX来说存在的一切能够胜利道路,减去对MIN来说存在的一切能够胜利道路XOXOXOX有6条,O有5条能够的胜利道路E(n)=6-5=1X有4条,O有6条能够的胜利道路E(n)=4-6=-2X有5条,O有4条能够的胜利道路E(n)=5-4=112/25/202368第三章普通搜索原理3.2启发式搜索α-β搜索单纯的极小极大搜索需求对搜索空间进展两遍分析,效率低α-β搜索对极小极大搜索进展改良根本思想：不搜索预判深度的整个空间，对能判别不起作用的分支那么去掉，不搜索以深度优先方式到达预判层，在不断剪枝的过程中，向上传播评价值α值是与MAX节点关联的不减小值β值是与MIN节点关联的不增大值12/25/202369第三章普通搜索原理3.2启发式搜索α-β搜索举例MINMAXMINMAX235907421563907263023≥2≤3≥5≥2≤0≤2××≥3×12/25/202370双向搜索搜索可以是从初始形状开场向目的形状的正向搜索；搜索也可以是从目的形状开场向初始形状的逆向搜索再能够是同时从初始形状向目的形状的正向搜索和从目的形状向初始形状的逆向搜索，直至这两条途径在中途某处小结接为止，这种搜索战略称为双向搜索第三章普通搜索原理3.2启发式搜索12/25/202371消解原理概述消解原理又称为归结原理是一种重要的推理规那么它来源于定理证明：F1∧F2∧…∧Fn→W用反证法证：F=F1∧F2∧…∧Fn∧～W为永假等价于证明：F对应的子句集S为不可满足的归结原理的根本思绪是：寻觅将S扩展后的子句集S1，它可满足性与S一样，且容易判别可满足性，从而知道S的可满足性，那么定理得证第三章普通搜索原理3.3消解原理12/25/202372消解过程原子公式和原子公式的否认称为文字文字的析取构成的公式称为子句假设S中存在空子句，S为不可满足的将F化为对应的子句集S将S扩展为可满足性一样的子句集S1，这个扩展的过程就是归结的过程 判别S1能否存在空子句第三章普通搜索原理3.3消解原理12/25/202373消解过程举例E2∨E1〔前提〕 ～E2∨E3〔前提〕〔消解式〕E1∨E3〔结论〕第三章普通搜索原理3.3消解原理12/25/202374建立子句集消去蕴涵符号：～P∨Q取代P→Q减少否认符号的管辖域对变量规范化消去存在量词化为前束形化为合取范式：如：PΛ(P∨Q〕Λ(～P∨Q〕消去全称量词获得子句集改换变量名第三章普通搜索原理3.3消解原理12/25/202375化子句集例例：(z)(x)(y){[(P(x)Q(x))R(y)]U(z)}1,消蕴涵符 实际根据：ab=>~ab (z)(x)(y){[~(P(x)Q(x))R(y)]U(z)}2,挪动否认符 实际根据：~(ab)=>~a~b ~(ab)=>~a~b ~(x)P(x)=>(x)~P(x) ~(x)P(x)=>(x)~P(x) (z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}第三章普通搜索原理3.3消解原理12/25/202376化子句集例〔续1〕3,变量规范化 即：对于不同的约束，对应于不同的变量 (x)A(x)(x)B(x)=>(x)A(x)(y)B(y)4,量词左移 (x)A(x)(y)B(y)=>(x)(y){A(x)B(y)}5,消存在量词(skolem化〕 原那么：对于一个受存在量词约束的变量，假设他不受全程量词约束，那么该变量用一个常量替代，假设他受全程量词约束，那么该变量用一个函数替代。 (z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}=>(x){[(~P(x)~Q(x))R(f(x))]U(a)}第三章普通搜索原理3.3消解原理12/25/202377化子句集例〔续2〕6,化为合取范式 即(ab)(cd)(ef)的方式(x){[(~P(x)~Q(x))R(f(x))]U(a)}=>(x){(~P(x)~Q(x))R(f(x))U(a)}=>(x){[~P(x)R(f(x))U(a)][~Q(x))R(f(x))U(a)]}7,隐去全程量词 {[~P(x)R(f(x))U(a)][~Q(x))R(f(x))U(a)]}第三章普通搜索原理3.3消解原理12/25/202378化子句集例〔续3〕8,表示为子句集{~P(x)R(f(x))U(a),~Q(x))R(f(x))U(a)}9,变量规范化〔变量换名〕{~P(x1)R(f(x1))U(a),~Q(x2))R(f(x2))U(a)}第三章普通搜索原理3.3消解原理12/25/202379消解推理规那么L1、L2为任一原子公式，他们具有一样的谓词符号，但普通变量名不同知两子句L1∨α和～L2∨β假设L1、L2具有最普通合一者σ那么可得新子句(α∨β)σ这个新子句叫做消解式第三章普通搜索原理3.3消解原理12/25/202380命题逻辑的消解推理举例第三章普通搜索原理3.3消解原理假言推理：P～P∨Q(P→Q〕消解式：Q合并：P∨Q～P∨Q消解式：Q∨Q=Q重言式：P∨Q～P∨～Q消解式：P∨～P或Q∨～Q空子句：P～P消解式：NIL三段论：～P∨Q(P→Q〕～Q∨R(Q→R〕消解式：～P∨R(P→Q〕12/25/202381谓词逻辑的消解推理举例第三章普通搜索原理3.3消解原理B(x)～B(x)∨C(x〕消解式：C(x)P(x)∨Q(x〕～Q[f(y)]消解式：P[f(y)]置换：f(y)/xP[x,f(y)]∨Q(x)∨R[f(a),y]～P[f(f(a)),z]∨R(z,w〕消解式：Q[f(f(a))]∨R[f(a),y]∨R[f(y),w]置换：f(f(a))/x,f(y)/z12/25/202382消解反演求解过程消解反演是利用消解原理进展命题证明。给定公式集S和目的公式L证明公式L的步骤如下：否认L，得～L把～L添加到S中去把新产生的集合{～L,S}化成子句集运用消解原理力图推导出一个表示矛盾的空子句第三章普通搜索原理3.3消解原理12/25/202383命题逻辑消解反演的例子设公理集： P, (PQ)R, (ST)Q, T求证：R子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R〔目的求反〕化子句集： (PQ)R=>~(PQ)R=>~P~QR (ST)Q=>~(ST)Q=>(~S~T)Q=>(~SQ)(~TQ)=>{~SQ,~TQ}第三章普通搜索原理3.3消解原理12/25/202384命题逻辑消解反演的例子〔续〕子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R〔目的求反〕归结： (7)~P~Q(2,6) (8)~Q (1,7)(9)~T(4,8)(10)nil(5,9)第三章普通搜索原理3.3消解原理12/25/202385谓词逻辑消解反演的例子例：知：IfFidogoeswhereverJohngoesandifJohnisatschool,whereisFido?(x)[AT(John,x)AT(Fido,x)] AT(John,School)求证：(x)AT(Fido,x)子句集：~AT(John,y)AT(Fido,y)AT(John,