人工智能经典推理

人工智能经典推理第1页，共98页，2023年，2月20日，星期三3.1图搜索策略图搜索控制策略

一种在图中寻找路径的方法。

图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。第2页，共98页，2023年，2月20日，星期三一般图搜索过程

状态空间搜索的基本思想是：先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了该问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或没有可供扩展的节点为止。搜索术语（用图来描述状态空间）节点：对应于状态描述节点深度：根节点的深度为0,其他节点的深度规定为父节点深度加1,即dn+1=dn+1。第3页，共98页，2023年，2月20日，星期三扩展节点：应用操作符将上一状态（节点ni）变迁到下一状态（节点nj），ni表示被扩展节点，nj

即是由ni

扩展出的子节点。路径：从节点ni到nk的路径是由相邻节点间的弧线构成的折线，通常要求路径是无环的，否则会导致搜索过程进入死循环。搜索图：在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的搜索图。Open表：存放已经生成但未扩展节点Close表：存放已扩展或将要扩展的节点S0表示问题的初始状态G表示搜索过程所得到的搜索图M表示当前扩展节点新生成的且不为自己先辈的子节点集。第4页，共98页，2023年，2月20日，星期三开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1

图搜索过程框图是是否否图搜索过程图树/不修改指针;图/修改指针;修改指针:找最优解第5页，共98页，2023年，2月20日，星期三3.2

盲目搜索特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。3.2.1

宽度优先搜索定义以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。算法第6页，共98页，2023年，2月20日，星期三开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功图3.2宽度优先算法框图是否是否3.2盲目搜索第7页，共98页，2023年，2月20日，星期三例：八数码难题

3×3九宫棋盘，放置数码为1-8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。求解的问题——给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局解答路径——就是一个合法的走步序列用宽度优先搜索方法解决该问题：

为问题状态的表示建立数据结构：3×3的一个矩阵，*矩阵元素Sij∈{0,1,…,8}；其中1≤i,j≤3，*数字0指示空格，*数字1-8指示相应棋牌。第8页，共98页，2023年，2月20日，星期三制定操作算子集：*直观方法——为每个棋牌制定一套可能的走步：左、上、右、下四种移动。这样就需32个操作算子。*简易方法——仅为空格制定这4种走步，因为只有紧靠空格的棋牌才能移动。*空格移动的唯一约束是不能移出棋盘。初始状态S0：23目标状态Sg：123 184 804 765765第9页，共98页，2023年，2月20日，星期三23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654宽度优先搜索91011121314151617从图中得，解的路径是：S0→→→3817第10页，共98页，2023年，2月20日，星期三3.2.2

深度优先搜索定义首先扩展最新产生的(即最深的)节点。算法防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）3.2盲目搜索第11页，共98页，2023年，2月20日，星期三例：八数码难题

231847652318476528314765231847652831476528316475283147652831647528316475123784651238476528364175123412384765目标深度优先搜索…………第12页，共98页，2023年，2月20日，星期三2318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目标设深度界限dm=4例：八数码难题

第13页，共98页，2023年，2月20日，星期三3.2.3

等代价搜索定义

是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。算法若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。3.2盲目搜索第14页，共98页，2023年，2月20日，星期三3.3

启发式搜索特点：重排OPEN表，选择最有希望的节点加以扩展种类：有序搜索(A算法)、A*算法等3.3.1启发式搜索策略和估价函数盲目搜索可能带来组合爆炸启发式信息

用来加速搜索过程的有关问题领域的特征信息。包括：用于决定要扩展的下一个节点的信息；在扩展一个节点时，用于决定要生成哪一个或哪几个后继节点的信息；用于决定某些应该从搜索树中抛弃或修剪的节点的信息；启发式搜索使用启发式信息指导的搜索过程称为启发式搜索.第15页，共98页，2023年，2月20日，星期三

估价函数用来估算节点处于最佳求解路径上的希望程度的函数f(n)=g(n)+h(n)n——搜索图中的某个当前被扩展的节点；f(n)——从初始状态节点s,经由节点n到达目标节点ng，估计的最小路径代价；g(n)——从s到n的实际路径代价；h(n)——从n到ng,估计的最小路径代价。例——八数码难题估价函数：f(n)=d(n)+w(n) 其中：d(n)为n的深度 w(n)为不在位的棋子数

如起始节点 283 164 705 则起始节点S0的估价函数值为：f( S0)=0+4=4

第16页，共98页，2023年，2月20日，星期三3.3.2

有序搜索实质

选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。3.3启发式搜索(1)全局择优搜索：选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。(2)局部择优搜索：从刚生成的子节点中选择具有最小f值的节点作为下一个要扩展的节点。第17页，共98页，2023年，2月20日，星期三开始把S放入OPEN表，计算估价函数f(s)OPEN表为空表？选取OPEN表中f值最小的节点i放入CLOSED表i为目标节点吗？扩展i，得后继节点j，计算f(j)，提供返回节点i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针失败成功图3.9有序搜索算法框图是否是否3.3启发式搜索算法第18页，共98页，2023年，2月20日，星期三例子八数码难题（8-puzzleproblem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：3.3启发式搜索第19页，共98页，2023年，2月20日，星期三5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）图3.10八数码难题的有序搜索树123846（4）73.3启发式搜索5第20页，共98页，2023年，2月20日，星期三3.3.3A*算法估价函数的定义：

对节点n定义f*(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。

希望估价函数f定义为：f(n)=g(n)+h(n)

——g是g*的估计，h是h*的估计3.3启发式搜索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)的估计值g(n)通常选择为当前所找到的从初始节点S到节点n的“最佳”路径的代价值，显然有g(n)g*(n)第21页，共98页，2023年，2月20日，星期三在A算法中，如果满足条件：

(1)

g(n)是对g*(n)的估计，且g(n)>0；(2)h(n)是h*(n)的下界，即对任意节点n均有 0≤h(n)≤h*(n)

则A算法称为A*算法A*算法的定义：

定义1在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(n)=g(n)+h(n)进行的，则称该过程为A算法。定义2在A算法中，如果对所有的n存在h(n)≤h*(n),则称h(n)为h*(n)的下界，它表示某种偏于保守的估计。定义3采用h*(n)的下界h(n)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。

第22页，共98页，2023年，2月20日，星期三

A*算法的可纳性

对任一个图，存在从S到目标的路径，如果一个搜索算法总是结束在一条从S到目标的最佳路径上，则称此算法是可采纳的。算法A*保证只要最短路径存在，就一定能找出这条路径，所以算法A*是可纳的。

A*算法应用举例八数码难题估价函数：f(n)=d(n)+w(n) 其中：d(n)为n的深度 w(n)为不在位的棋子数取h(n)=w(n),则有w(n)≤h*(n),h(n)满足A*算法的限制条件。第23页，共98页，2023年，2月20日，星期三1238476528316475初始状态目标状态

在八数码难题中,令估价函数

f(n)=d(n)+p(n)启发函数h(n)=p(n),p(n)为不在位的棋子与其目标位置的距离之和，则有p(n)≤h*(n),满足A*算法的限制条件。第24页，共98页，2023年，2月20日，星期三283164752831476528316475283164752318476528314765283147652318476523184765123847651238476512378465目标12345h=5,g=0,f=5h=6,g=1,f=7h=4,g=1,f=5h=6,g=1,f=7h=5,g=2,f=7h=3,g=2,f=5h=5,g=2,f=7h=2,g=3,f=5h=4,g=3,f=7h=1,g=4,f=5h=0,g=5,f=5第25页，共98页，2023年，2月20日，星期三w(n)——不在位的棋子数，不够贴切，错误选用节点加以扩展。p(n)——更接近于h*(n)的h(n)，其值是节点n与目标状态节点相比较，每个错位棋子在假设不受阻拦的情况下，移动到目标状态相应位置所需走步的总和。p(n)比w(n)更接近于h*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离（移动次数）。说明h值越大,启发功能越强,搜索效率越高.特别地(1)h(n)=h*(n)

搜索仅沿最佳路径进行,效率最高.(2)h(n)=0

无启发信息,盲目搜索,效率低.(3)h(n)>h*(n)

是一般的A算法,效率高,但不能保证找到最佳路径.有时为求解难题取h(n)>h*(n),以提高效率.第26页，共98页，2023年，2月20日，星期三3.4博弈树的启发式搜索参与搜索的不只是一个主体，而包括对抗的多方(对弈)任何一方在选择自己的行为时，都要将对方可能采取的对策考虑在内由此而产生的搜索树称为博弈树(博弈图)博奕:两棋手按一定规则轮流走步,双方都知道对方的走步,当满足一定条件时,走步结束,这时,或一方取胜,或为和局.1.博弈问题第27页，共98页，2023年，2月20日，星期三

我方（指程序方，叫MAX）每走一着棋（半回合），都力图使自己通向取胜的目标。轮到MAX走棋时，由于它掌握着出棋的主动权，只要此时的各种走法中有一个能通向胜局，它就会毫不客气地出这一着。因此由MAX方出棋的结点具有或结点的性质。对手（叫MIN，是一个回合的对棋者）每走一着棋（半回合），都力图干扰MAX的选择，使其偏离取胜的目标。轮到MIN走棋时，由于它掌握着对棋的主动权，因此只要此时的全部着法中有一个能导致败局，它就会毫不客气地出这一着。因此由MIN对棋的结点具有与终点的性质。所以-博弈树一般都是与／或树。博弈树的特点：（1）初始格局是初始节点（2）博弈树中或节点和与节点逐层交替出现（3）所有能使自己一方获胜的终局都是本原问题，而相应使对方获胜的棋局均为不可解节点。第28页，共98页，2023年，2月20日，星期三例分火柴游戏

设一堆火柴有7根，由MAX（我方）和MIN（对手）两人轮流来分它们，要求每次都要把某一堆火柴分成不相等的两部分，最后不能分下去的人为负，对方为胜。如果MIN先走，可以有三种选择：（6，1）、（5，2）、（4，3）在每一种选择下，MAX又可以有两种走法，整个博弈过程的状态空间如图所示。结点中的数字表示各堆火柴的根数分布，名字表示轮到他继续向下走棋。第29页，共98页，2023年，2月20日，星期三(5,1,1,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(3,2,2,MIN)(4,2,1,MIN)(7,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(2,1,1,1,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)第30页，共98页，2023年，2月20日，星期三2.极大极小过程

极大极小搜索策略是考虑双方对弈若干步之后,从可能的走步中选一步相对好棋的走法来走,即在有限的搜索深度范围内进行求解。定义一个静态估计函数f,以便对棋局的势态(节点)作出优劣估值。一般规定有利于MAX的势态,f(p)取正值,有利于MIN的势态,f(p)取负值,势均力敌的势态,f(p)取0值,若f(o)=+∞,则表示MAX赢,若f(o)=-∞,则表示MIN赢。在轮到MAX走时,选择f(p)大的节点走;而轮到MIN走时,应考虑对方会选f(p)最小的节点走.因此,在博奕图搜索时,可采用一步走f(p)值极大的节点(MAX走),一步走f(p)值极小的节点(MIN走),这样交替前进的方法.这种搜索过程称为极大极小过程.第31页，共98页，2023年，2月20日，星期三例:一字棋 棋局中,我方(MAX)棋子用表示,对方(MIN)棋子用°表示.开始由我方先走,估价函数:

我方获胜e(p)=- 对方获胜

e(+p)-e(-p)其他情况

空格视为时我方三连子数-空格视为°时对方三连子数°e(p)=6-4=2为了计算非叶节点的值，必须从叶节点向上倒推，叫倒推值。MAX的倒推值是其后继节点估值的最大值。MIN的倒推值是其后继节点估值的最小值。

第32页，共98页，2023年，2月20日，星期三°°°°°°°°°°°°1-1-211010-1-10-10-2

12第33页，共98页，2023年，2月20日，星期三°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°11213121010201112231221100第34页，共98页，2023年，2月20日，星期三°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°111212-101001122111-------ABCD第35页，共98页，2023年，2月20日，星期三3.

-剪枝

极大极小过程是把搜索树的生成和格局估值这两个过程分开来进行,即先生成全部搜索树,然后再进行端节点静态估值和倒推值计算,这显然会导致低效率。如果把生成和倒推估值结合起来进行,再根据一定条件判定,有可能尽早修剪掉一些无用的分枝,即α-β剪枝过程的思想。α-β剪枝方法：（1）MAX节点的值为当前子节点的最大倒推值；MAX节点的值在搜索过程中永不减少（2）MIN节点的值为当前子节点的最小倒推值；MIN节点的值在搜索过程中永不增加第36页，共98页，2023年，2月20日，星期三

（3）α-β剪枝规则：①任何MAX节点n的值大于或等于它的任一先辈节点MIN的值,则可终止该MAX节点以下的搜索,并可将其最终倒推值设为它的值.这种剪枝称为β剪枝②任何MIN节点n的值小于或等于它的任一先辈节点MAX的值,则可终止该MIN节点以下的搜索,并可将其最终倒推值设为它的值。这种剪枝称为α剪枝。

α剪枝：α（先辈节点）≥β（后继节点）β剪枝：α（后继节点）≥β（先辈节点）第37页，共98页，2023年，2月20日，星期三05-333-302-23523α≥0β≤0α≥00-303α≥330β≤52α≥2β≤-5-5-522ααββα剪枝：α（先辈节点）≥β（后继节点）β剪枝：α（后继节点）≥β（先辈节点）β≤-3α剪枝β剪枝2α剪枝第38页，共98页，2023年，2月20日，星期三481*5P80**α≥4β≤4α≥4414α≥554β≤00α≥0β≤-6-6-6004ααβββ≤1α剪枝β剪枝S0KLM6FNGQ5HD*ABRISJEα剪枝α剪枝C第39页，共98页，2023年，2月20日，星期三3.5消解原理回顾：

原子公式（atomicformulas）

文字—一个原子公式及其否定。P(x),

P(x)

子句—由文字的析取组成的合适公式。P(x)Q(x)

空子句---不包含任何子句的文字。用NIL表示

子句集---由子句或空子句所构成的集合.

消解—对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。3.5.1

子句集的求取步骤：共9步。第40页，共98页，2023年，2月20日，星期三例子:将下列谓词演算公式化为一个子句集(x)｛P(x)｛(y)［P(y)P(f(x,y))］∧～(y)［Q(x,y)P(y)］｝｝开始：消去蕴涵符号只应用∨和～符号，以～A∨B替换AB。(1)(x)｛～P(x)∨{(y)［~P(y)∨P(f(x,y))］∧～(y)［~Q(x,y)∨P(y)］}}3.5消解原理第41页，共98页，2023年，2月20日，星期三(2)减少否定符号的辖域每个否定符号～最多只用到一个谓词符号上，并反复应用狄·摩根定律。(3)对变量标准化对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。3.5消解原理(2)(x)｛～P(x)∨｛(y)［～P(y)∨P(f(x,y))］∧(y)［Q(x,y)∧～P(y)］｝｝(3)(x)｛～P(x)∨｛(y)［～P(y)∨P(f(x,y))］∧(w)［Q(x,w)∧～P(w)］｝｝第42页，共98页，2023年，2月20日，星期三(4)消去存在量词以Skolem函数代替存在量词内的约束变量，然后消去存在量词化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形={前缀}{母式}

全称量词串无量词公式(4)(x)｛～P(x)∨{(y)[~P(y)∨P(f(x,y))］∧［Q(x,g(x)）∧～P(g(x))］｝｝式中，w=g(x)为一Skolem函数。(5)(x)(y)｛～P(x)∨｛［～P(y)∨P(f(x,y))］∧［Q(x,g(x))∧～P(g(x))］｝｝3.5消解原理第43页，共98页，2023年，2月20日，星期三把母式化为合取范式任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(7)消去全称量词所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。3.5消解原理(6)(x)(y)｛［～P(x)∨～P(y)∨P(f(x,y))］∧［～P(x)∨Q(x,g(x))］∧［～P(x)∨～P(g(x))］｝(7)｛［～P(x)∨～P(y)∨P(f(x,y))］∧［～P(x)∨Q(x,g(x))］∧［～P(x)∨～P(g(x))］｝第44页，共98页，2023年，2月20日，星期三(8)消去连词符号∧用{A,B}代替(A∧B)，消去符号∧。最后得到一个有限集，其中每个公式是文字的析取。(9)更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。3.5消解原理(8)

～P(x)∨～P(y)∨P(f(x,y))

～P(x)∨Q(x,g(x))

～P(x)∨～P(g(x))(9)

～P(x1)∨～P(y)∨P［f(x1,y)］～P(x2)∨Q［x2,g(x2)］～P(x3)∨～P［g(x3)］第45页，共98页，2023年，2月20日，星期三3.5.2

消解推理规则消解式的定义

令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1∨α和～L2∨β,如果L1和L2具有最一般合一σ，那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式。

消解式求法取各子句的析取，然后消去互补对。3.5消解原理第46页，共98页，2023年，2月20日，星期三几种从父辈子句求消解式的例子假言推理AAB则B合并P∨QPQ则Q重言式P∨Q～

P∨

～

Q空子句～PP链式PQQR则PR第47页，共98页，2023年，2月20日，星期三3.5.3含有变量的消解式

要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈子句的置换，使父辈子句含有互补文字。

含有变量的子句之消解式例子P[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)/z}3.5消解原理第48页，共98页，2023年，2月20日，星期三3.5.4

消解反演求解过程消解反演

给出{S}，L否定L，得～L；把～L添加到S中去；把新产生的集合｛～L，S｝化成子句集；应用消解原理，力图推导出一个表示矛盾的空子句例1—储蓄问题前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱3.5消解原理第49页，共98页，2023年，2月20日，星期三(1）规定原子公式：

S(x,y)表示“x储蓄y”

M(x)表示“x是钱”

I(x)表示“x是利息”

E(x，y)表示“x获得y”(2）用谓词公式表示前提和结论：前提：(x)[(y)(S(x,y))∧M(y)][(y)(I(y)∧E(x,y))]结论：～(x)I(x)(x)(y)(M(y)→～S(x,y))(3)

化为子句形证明：3.5消解原理第50页，共98页，2023年，2月20日，星期三把前提化为子句形：1)

～S(x,y)∨～M(y)∨I(f(x))2)

～S(x,y)∨～M(y)∨E(x,f(x))把结论化为子句形：3)

～I(z)4)S(a,b)5)M(b)(4)

消解反演求NIL图3.12储蓄问题反演树子句（1）子句（3）f(x)/z～M(b)NIL子句（5）子句（7）子句（4）{a/x,b/y}～S(x,y)∨～M(y)子句（6）3.5消解原理第51页，共98页，2023年，2月20日，星期三例2：“快乐学生”问题

假设：任何通过计算机考试并获奖的人都是快乐的。任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。解：将问题用谓词表示如下：“任何通过计算机考试并获奖的人都是快乐的”

(x)(Pass(x,computer)Win(x,prize))Happy(x))“任何肯学习或幸运的人都可以通过所有考试”(x)(

y)(Study(x)Lucky(x)Pass(x,y))“张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)“任何幸运的人都能获奖”(x)(Lucky(x)Win(x,prize))

结论“张是快乐的”的否定Happy(zhang)第52页，共98页，2023年，2月20日，星期三将谓词转化为子句集：

P1:

Pass(x,computer)

Win(x,prize)Happy(x)P2:

Study(y)

Pass(y,z)P3:

Lucky(u)

Pass(u,v)P4:Study(zhang)P5:Lucky(zhang)P6:

Lucky(w)Win(w,prize)

Q:Happy(zhang)所以：S’={P1,

P2,

P3,

P4,

P5,

P6},S’’=

{P1,

P2,

P3,

P4,

P5,

P6,

Q}对S’’进行归结操作，直至推出NIL。归结反演过程如下：第53页，共98页，2023年，2月20日，星期三P6

Pass(x,computer)

Win(x,prize)Happy(x)

Lucky(w)Win(w,prize)

Pass(w,computer)

Happy(w)

Lucky(w)置换{w/x}

P1Happy(zhang)

Q

Pass(zhang,computer)

Lucky(zhang)置换{zhang/w}Lucky(zhang)

P5

Pass(zhang,computer)

Lucky(u)

Pass(u,v)

P3

Lucky(zhang)置换{zhang/u,computer/v}Lucky(zhang)

P5NIL

归结出NIL，证明结论为真。第54页，共98页，2023年，2月20日，星期三从反演树求取问题的答案步骤1.把问题的已知条件用谓词公式表达出来，并转换成子句集S’；2.把问题的目标的否定用谓词公式表达出来，并转换成子句集Q；3.对Q中的每个子句，构造其重言式（包含互补文字对的子句），代替相应的目标否定子句，加入到S’中，得到S’’；4.对S’’应用消解原理求出消解树，该消解树的根子句为所求答案。实质把一棵根部有NIL的反演树变换为根部带有回答语句的一棵证明树。第55页，共98页，2023年，2月20日，星期三例3：已知：李和张是同班同学，如果x和y是同班同学，则x的教室也是y的教室，现在张在302教室上课，问：李现在在哪里上课？解：定义谓词：C(x,y)x和y是同班同学

At(x,u)x在u教室上课已知前提谓词公式表示如下：

C(zhang,li)(x)(

y)(u)(C(x,y)At(x,u)At(y,u))At(zhang,302)目标的否定用谓词公式表示如下：(v)At(li,v)将谓词转化为子句集：

P1:C(zhang,li)P2:C(x,y)

At(x,u)

At(y,u)P3:

At(zhang,302)第56页，共98页，2023年，2月20日，星期三把目标的否定化为子句，用重言式Q:At(li,z)

At(li,z)代替所以：S’={P1,

P2,

P3,

},S’’=

{P1,

P2,

P3,

Q}对S’’进行归结操作，归结反演过程如下：

P3

C(x,y)

At(x,u)

At(y,u)At(li,z)

At(li,z)

QAt(li,z)

C(x,li)At(x,z)C(zhang,li)

P1At(li,z)

At(zhang,z)置换{li/y,z/u}At(zhang,302)

P2At(li,302)置换{zhang/x}置换{302/z}答案：李在302教室。第57页，共98页，2023年，2月20日，星期三正向演绎系统的基本思想逻辑蕴涵式与子句的区别：上面二个表达式在逻辑上是等价的，但所表达的概念有区别：：强调推理性(即：前件为真时后件为真)

：只是表示了A、B、C中有一个为真，则公式为真可见：将蕴涵式写成与其等价的子句形式会损失一些逻辑信息。直接利用蕴涵式所做的证明系统就是基于规则的演绎系统。3.6规则演绎系统第58页，共98页，2023年，2月20日，星期三

定义

基于规则的问题求解系统运用If→Then规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。IFATHENBIFBTHENCIFCTHEND已知A

第59页，共98页，2023年，2月20日，星期三3.6.1规则正向演绎系统定义正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。

3.6规则演绎系统第60页，共98页，2023年，2月20日，星期三正向规则演绎的求解过程事实表达式的与或形变换

在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。方法：将规则前件的事实表达式从规则中分离出来，单独变换成与或形式的表达式，但是不必化简成子句。第61页，共98页，2023年，2月20日，星期三例如：一个事实表达式：消去存在量词，由常量代替变元x，得到一个与或表达式：利用等价变换，得到：对第一个合取项进行变量换名(w/y)，目的是保证每个合取项的变量名都不相同得到公式：上式不是子句，但是一个与或表达式，可以直接用于正向推理系统。第62页，共98页，2023年，2月20日，星期三2.用与或图表示一个与或表达式：与或图中的节点代表子表达式当表达式为析取式(E1∨E2∨

…∨Ek)时，则每个子表达式表示为原表达式的一个后继节点，且用一个K连接符连接每个Ei

，表示为与关系。当表达式为合取式(E1∧E2∧

…∧Ek)时，则每个子表达式单独作为原表达式的一个子节点，用1连接符连接，表示为或关系。第63页，共98页，2023年，2月20日，星期三上例的事实表达式用与或图表示如下：可以看出，每个端节点都是一个文字，所以与或图相当于把一个表达式按照与或关系拆分成文字表示。第64页，共98页，2023年，2月20日，星期三讨论：利用与或图求解图：方法与可分解系统中的解图求法相同。不同的是与或图中的节点之间的合取、析取关系是相反的。因此，求解图是按照K连接方式求解，而不是按照真值求解。上图中的三个解图分别构成三个子句：

Q(w,A),~R(y)∨~S(A,y),~P(y)∨~S(A,y)基于规则正向推理系统中的与或图是一种知识表达方式；可分解系统中的与或图是一种图搜索方式，二者是不同的。第65页，共98页，2023年，2月20日，星期三3.与或图的F规则变换

这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：

LW 式中：L是单文字；W为与或形的唯一公式。3.6规则演绎系统如果规则为(L1∨L2)→W形式，即前提是析取形式，则将其分解成二条规则

L1→W，L2→W如果规则为(L1∧L2)→W形式，即前提是合取形式，不予讨论。第66页，共98页，2023年，2月20日，星期三例：初始数据库的与或表达式为：

[(P∨Q)∧R]∨[S∧(T∨U)]

规则：S→(X∧Y)∨Z推理过程：①用与或图表示初始条件表达式②寻找与规则前提匹配的文字③用匹配弧连接上述两个文字④将规则结论的与或图连接到前提上，扩充与或图⑤正向系统的推理树根节点在下部上面例题的推理树见下页。第67页，共98页，2023年，2月20日，星期三从上图的事实表达式部分可以得到四个子句：(1)(P∨Q)∨S(2)(P∨Q)∨(T∨U)(3)(R∨S)(4)R∨(T∨U)[(P∨Q)∧R]∨[S∧(T∨U)]X∧YXYZSSTUT∨US∧(T∨U)(P∨Q)∧RP∨QRPQ规则：S→(X∧Y)∨Z第68页，共98页，2023年，2月20日，星期三从上图的规则结论部分可以得到二个子句：(1)X∨Z(2)Y∨Z用这二个子句代替前提中的S，得到四个新子句(1)(P∨Q)∨(X∨Z)(2)(P∨Q)∨(Y∨Z)(3)R∨(X∨Z)(4)R∨(Y∨Z)下面说明这四个子句就是用事实表达式和规则构成的子句集进行归结所得到的全部归结式。X∧YXYZS第69页，共98页，2023年，2月20日，星期三首先将事实表达式和规则写成子句形式：事实表达式[(P∨Q)∧R]∨[S∧(T∨U)](P∨Q∨S)∧(P∨Q∨T∨U)∧(R∨S)∧(R∨T∨U)规则S→(X∧Y)∨Z~S∨(X∧Y)∨Z(~S∨X∨Z)∧(~S∨Y∨Z)得到子句集：{P∨Q∨S,P∨Q∨T∨U,R∨S,R∨T∨U,~S∨X∨Z,~S∨Y∨Z}①②③④⑤⑥由上面的子句集求出归结式：①与⑤式：P∨Q∨X∨Z①与⑥式：P∨Q∨Y∨Z③与⑤式：R∨X∨Z③与⑥式：R∨Y∨Z由此可见，用归结方法与用与或树方法得到的归结式是相同的。第70页，共98页，2023年，2月20日，星期三例：事实表达式A∨B

规则R1：A→(C∧D)R2：B→(E∧G)

目标C∨G推理树：由此解图得到子句集：{C∨E,C∨G,D∨E,D∨G}其中：C∨G是目标A∨BCGCDEGABABR1R2第71页，共98页，2023年，2月20日，星期三3.6.2规则逆向演绎系统定义

逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。

求解过程目标表达式的与或形式与或图的B规则变换作为终止条件的事实节点的一致解图3.6规则演绎系统第72页，共98页，2023年，2月20日，星期三1目标表达式的与或表示逆向推理系统从目标开始，与正向系统相反，规则的使用是反向的。目标表达式的与或形式：(1)利用skolem函数对目标公式进行标准化（同以前讲的标准化过程相同）(2)各析取项之间变元要各不相同（变量换名）(3)子表达式之间为析取关系时，使用1连接符连接子表达式之间为合取关系时，使用K连接符连接(4)与或图的根节点在上面例：目标公式：第73页，共98页，2023年，2月20日，星期三标准化，得到：变量换名，得到：第74页，共98页，2023年，2月20日，星期三2逆向推理系统关于规则的限制：B规则的形式：W→L其中：W：任何与或公式L：单文字结论①规则中的变元全部是全称量词约束②如果规则为W→(L1∧L2)形式，则分解为两条规则：

W→L1

和W→L2推理过程：(1)用与或图表示目标表达式(2)寻找与规则结论匹配的文字(3)用匹配弧连接上述的二个匹配文字(4)将规则的结论与前提连接，扩充与或图，直至出现事实表达式的文字(5)反向推理树的根节点在上面第75页，共98页，2023年，2月20日，星期三反向推理例题：P83事实表达式：F1：D(FIDO)F2：~B(FIDO)F3：W(FIDO)F4：M(MR)规则：R1：（W(x1)∧D(x1))→F(x1)R2：(F(x2)∧~B(x2))→~A(y2,x2)R3：M(x3)→C(x3)目标公式：()()（C(x)∧D(y)∧~A(x,y)）第76页，共98页，2023年，2月20日，星期三得到一个解图：M(MR)∧D(FIDO)∧W(FIDO)∧D(FIDO)∧~B(FIDO)判断是否是一致解图：C(x)~A(x,y)D(y)~A(y2,x2)M(x3)F(x2)~B(x2){x3/x}{y2/x,x2/y}{FIDO/y}逆向推理树C(x)∧D(y)∧~A(x,y)C(x3)D(FIDO)M(MR){MR/x3}F(x1)~B(FIDO){FIDO/x2}{x1/x2}D(x1)W(x1)W(FIDO)D(FIDO){FIDO/x1}{FIDO/x1}第77页，共98页，2023年，2月20日，星期三(1)由反向推理树得到所有置换：{{x3/x},{MR/x3},{{FIDO/y},{y2/x,x2/y},{x1/x2},{FIDO/x2},

{FIDO/x1},{FIDO/x1}}(2)求出：

U1=(x,x3,y,x,y,x2,x2,x1,x1)U2=(x3,MR,FIDO,y2,x2,x1,FIDO,FIDO,FIDO)(3)求出合一复合：

U=(MR/x,FIDO/y)(4)利用合一复合对目标公式作置换，得到置换例：

C(MR)∧D(FIDO)∧~A(MR,FIDO)该置换例就是推理结果

第78页，共98页，2023年，2月20日，星期三

正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。3.6.3规则双向演绎系统3.6规则演绎系统第79页，共98页，2023年，2月20日，星期三3.7产生式系统定义：用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统。第80页，共98页，2023年，2月20日，星期三3.7.1产生式系统的组成图3.22产生式系统的主要组成控制策略总数据库规则库3.7产生式系统第81页，共98页，2023年，2月20日，星期三规则库用于存放与求解问题有关的某个领域知识的规则集。在建立规则库时，应注意如下问题：

（1）规则库知识的完整性、一致性、准确性、灵活性。（2）对知识进行合理的组织与管理：目的是使得推理避免访问与所求解的问题无关的知识，以提高问题求解效率。第82页，共98页，2023年，2月20日，星期三总数据库总数据库又称为事实库、上下文、黑板等。它是一个用于存放问题求解过程中各种当前信息的数据结构，例如：问题的初始状态、原始证据、推理中得到的中间结论、最终结论等。 当规则库中某条产生式的前提可与总数据库中的某些已知事实匹配时，该产生式就被激活，并把其结论放入总数据库中，作为后面推理的已知事实。显然，总数据库的内容是在不断变化的，是动态的。总数据库中的已知事实通常用字符串、向量、集合、矩阵、表等数据结构表示。第83页，共98页，2023年，2月20日，星期三控制策略控制策略又称推理机构，由一组程序组成，负责整个产生式系统的运行，实现对问题的求解。主要包括推理策略和搜索策略两部分。

推理策略：主要解决推理方向、冲突消解等问题。搜索策略：主要解决搜索线路、推理效果、推理效率等问题。控制策略的主要工作：（1）按一定的策略从规则库中选择与总数据库中的已知事实相匹配的规则。（2）当发生冲突（即匹配成功的规则不止一条）时，调用相应的冲突解决策略予以消解。（3）在执行某条规则时，若该规则的右部是一个或多个结论，则把这些结论加到总数据库中；若规则的右部是一个或多个操作，则执行这些操作。第84页，共98页，2023年，2月20日，星期三（4）对于不确定性知识，在执行每一条规则时，还要按一定的算法计算结论的不确定性。（5）对要执行的规则，如果该规则的后件满足问题的结束条件，则停止推理。（6）在问题的求解过程中，记住应用过的规则序列，以便最终能够给出问题的解路径。第85页，共98页，2023年，2月20日，星期三选择规则到执行操作的步骤

1匹配把当前数据库与规则的条件部分相匹配。

2冲突当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。

3操作操作就是执行规则的操作部分。3.7产生式系统第86页，共98页，2023年，2月20日，星期三选取规则的原则称为控制策略（冲突消解）不可撤回方式：属盲目性搜索,