人工智能经典推理讲稿.ppt

人工智能经典推理第一页，讲稿共九十八页哦3.1 3.1 图搜索策略图搜索策略 图搜索控制策略图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。第二页，讲稿共九十八页哦一般图搜索过程一般图搜索过程 状态空间搜索的状态空间搜索的基本思想基本思想是：先把问题的初始状态作为当前是：先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到标状态是否出现在这些子节点中。若出现，则搜索成功，找到了该问题的解；若没出现，则再按照了该问题的解；若没出现，则再按照某种搜索策略某种搜索策略从已生成从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或没有可供扩展的节点为止。直到目标状态出现在子节点中或没有可供扩展的节点为止。搜索术语（搜索术语（用图来描述状态空间）用图来描述状态空间）节点：对应于状态描述节点：对应于状态描述节点深度：根节点的深度为节点深度：根节点的深度为0,其他节点的深度规定为其他节点的深度规定为父节点深度加父节点深度加1,即即dn+1=dn+1。第三页，讲稿共九十八页哦扩展节点：应用操作符将上一状态（节点扩展节点：应用操作符将上一状态（节点ni）变迁到下一变迁到下一状态（节点状态（节点nj），），ni表表示被扩展节点，示被扩展节点，nj 即是由即是由ni 扩展出的扩展出的子节点。子节点。路径：从节点路径：从节点ni到到nk的路径是由相邻节点间的弧线构成的折的路径是由相邻节点间的弧线构成的折线，通常要求路径是无环的，否则会导致搜索过程进入死循环。线，通常要求路径是无环的，否则会导致搜索过程进入死循环。搜索图：在搜索解答路径的过程中只画出搜索时直接涉及到搜索图：在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的搜索图。的节点和弧线，构成所谓的搜索图。Open表：存放已经生成但未扩展节点表：存放已经生成但未扩展节点Close表：存放已扩展或将要扩展的节点表：存放已扩展或将要扩展的节点S0表示问题的初始状态表示问题的初始状态G表示搜索过程所得到的搜索图表示搜索过程所得到的搜索图M表示当前扩展节点新生成的且不为自己先辈的子节表示当前扩展节点新生成的且不为自己先辈的子节点集。点集。第四页，讲稿共九十八页哦开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表的末端，表的末端，提供返回节点提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功图图3.1 图搜索过程框图图搜索过程框图是是是是否否否否图搜索过程图图搜索过程图树树/不修改指针不修改指针;图图/修改修改指针指针;修改指针修改指针:找最优解找最优解第五页，讲稿共九十八页哦3.2 盲目搜索 特点：不需重排特点：不需重排OPENOPEN表表种类：宽度优先、深度优先、等代价搜索等。种类：宽度优先、深度优先、等代价搜索等。3.2.1 宽度优先搜索 定义 以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。算法第六页，讲稿共九十八页哦开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的末表的末端，提供返回节点端，提供返回节点n的指针的指针失败失败成功成功图图3.2 宽度优先算法框图宽度优先算法框图是是否否是是否否3.2 盲目搜索第七页，讲稿共九十八页哦例：例：八数码难题八数码难题 33九九宫宫棋棋盘盘，放放置置数数码码为为1-8的的8个个棋棋牌牌，剩剩下下一一个个空空格格，只只能通过棋牌向空格的移动来改变棋盘的布局。能通过棋牌向空格的移动来改变棋盘的布局。求解的问题求解的问题给定初始布局（即初始状态）和目标布局（即给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局目标状态），如何移动棋牌才能从初始布局到达目标布局 解答路径解答路径就是一个合法的走步序列就是一个合法的走步序列 用宽度优先搜索方法解决该问题：用宽度优先搜索方法解决该问题：为问题状态的表示建立数据结构：为问题状态的表示建立数据结构：33的一个矩阵的一个矩阵，*矩阵元素矩阵元素S ij0,1,8；其中其中1i,j3，*数字数字0指示空格，指示空格，*数字数字1-8指示相应棋牌。指示相应棋牌。第八页，讲稿共九十八页哦制定操作算子集：制定操作算子集：*直观方法直观方法为每个棋牌制定一套可能的走步：左、上、为每个棋牌制定一套可能的走步：左、上、右、下四种移动。这样就需右、下四种移动。这样就需32个操作算子。个操作算子。*简易方法简易方法仅为空格制定这仅为空格制定这4种走步种走步，因为只有紧靠空格，因为只有紧靠空格的棋牌才能移动。的棋牌才能移动。*空格移动的唯一空格移动的唯一约束约束是不能移出棋盘。是不能移出棋盘。初始状态初始状态S S0 0：2 3 目标状态目标状态S Sg g：1 2 3 1 8 4 8 0 4 7 6 5 7 6 5第九页，讲稿共九十八页哦2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标目标82 3 41 8 7 6 54宽度优先搜索宽度优先搜索91011121314151617从图中得，解的路径是：从图中得，解的路径是：S0 3817第十页，讲稿共九十八页哦3.2.2 深度优先搜索 定义 首先扩展最新产生的(即最深的)节点。算法 防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）3.2 盲目搜索第十一页，讲稿共九十八页哦例：例：八数码难题八数码难题 2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 51 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 512341 2 3 8 47 6 5目标目标深度优先搜索深度优先搜索第十二页，讲稿共九十八页哦2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789101112131 2 3 8 47 6 5目标目标设深度界限设深度界限d dm m=4=4例：例：八数码难题八数码难题 第十三页，讲稿共九十八页哦3.2.3 等代价搜索 定义 是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。算法 若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。3.2 盲目搜索第十四页，讲稿共九十八页哦3.3 启发式搜索特点：重排OPEN表，选择最有希望的节点加以扩展种类：有序搜索(A算法)、A*算法等3.3.1 启发式搜索策略和估价函数盲目搜索可能带来组合爆炸盲目搜索可能带来组合爆炸启发式信息启发式信息 用来加速搜索过程的有关问题领域的用来加速搜索过程的有关问题领域的特征信息特征信息。包括：。包括：用于决定要扩展的下一个节点的信息；用于决定要扩展的下一个节点的信息；在扩展一个节点时，用于决定要生成哪一个或哪几个后继节点在扩展一个节点时，用于决定要生成哪一个或哪几个后继节点的信息；的信息；用于决定某些应该从搜索树中抛弃或修剪的节点的信息；用于决定某些应该从搜索树中抛弃或修剪的节点的信息；启发式搜索启发式搜索使用使用启发式信息指导启发式信息指导的搜索过程称为的搜索过程称为启发式搜索启发式搜索.第十五页，讲稿共九十八页哦 估价函数估价函数用来估算节点处于最佳求解路径上的希望程度的函数用来估算节点处于最佳求解路径上的希望程度的函数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)为不在位的棋子数为不在位的棋子数如起始节点如起始节点 2 8 31 6 47 0 5则起始节点则起始节点S0的估价函数值为的估价函数值为：f(S0)=0+4=4第十六页，讲稿共九十八页哦3.3.2 有序搜索实质 选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。3.3 启发式搜索(1)全局择优搜索全局择优搜索：选择选择OPEN表上具有最小表上具有最小f值的节点作为下一个要扩展的节值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。点，即总是选择最有希望的节点作为下一个要扩展的节点。(2)局部择优搜索局部择优搜索：从刚生成的子节点中选择具有最小从刚生成的子节点中选择具有最小f值的节点作为下一值的节点作为下一个要扩展的节点。个要扩展的节点。第十七页，讲稿共九十八页哦开始开始把把S放入放入OPEN表，计表，计算估价函数算估价函数 f(s)OPEN表为空表？表为空表？选取选取OPEN表中表中f值最小的节点值最小的节点i放入放入CLOSED表表i为目标节点吗？为目标节点吗？扩展扩展i，得后继节点，得后继节点j，计算，计算f(j)，提供返回节，提供返回节点点i的指针，利用的指针，利用f(j)对对OPEN表重新排序，调表重新排序，调整亲子关系及指针整亲子关系及指针失败失败成功成功图图3.9 有序搜索算法框图有序搜索算法框图是是否否是是否否3.3 启发式搜索算法第十八页，讲稿共九十八页哦 例子八数码难题（8-puzzle problem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：3.3 启发式搜索第十九页，讲稿共九十八页哦5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（5）（7）图3.10 八数码难题的有序搜索树123846（4）73.3 启发式搜索5第二十页，讲稿共九十八页哦3.3.3 A*算法估价函数的定义：估价函数的定义：对节点对节点n n定义定义f f*(n)=g*(n)+h*(n),(n)=g*(n)+h*(n),表示从表示从S S开始约束通过节点开始约束通过节点n n的一条最佳路径的代价。的一条最佳路径的代价。希望估价函数希望估价函数f f 定义为：定义为：f(n)=g(n)+h(n)f(n)=g(n)+h(n)g g是是g*g*的估计的估计 ，h h是是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)g(n)通常选择为当前所找到的从初始节点通常选择为当前所找到的从初始节点S S到节点到节点n n的的“最佳最佳”路路径的代价值，显然有径的代价值，显然有g(n)g(n)g*(n)g*(n)第二十一页，讲稿共九十八页哦在在A算法中，如果满足条件：算法中，如果满足条件：(1)(1)g(n)是对是对g*(n)的估计，且的估计，且g(n)0；(2)h(n)是是h*(n)的下界，即对任意节点的下界，即对任意节点n均有均有 0h(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*算法就变为有序搜索算法。算法就变为有序搜索算法。第二十二页，讲稿共九十八页哦 A*算法的可纳性算法的可纳性 对任一个图，存在从对任一个图，存在从S S到目标的路径，如果一个搜索算法到目标的路径，如果一个搜索算法总是结束在一条从总是结束在一条从S S到目标的最佳路径上，则称此算法是可采纳的。到目标的最佳路径上，则称此算法是可采纳的。算法算法A A*保证只要最短路径存在，就一定能找出这条路径，所以保证只要最短路径存在，就一定能找出这条路径，所以算法算法A A*是可纳的。是可纳的。A*算法应用举例算法应用举例 八数码难题八数码难题 估价函数：估价函数：f(n)=d(n)+w(n)f(n)=d(n)+w(n)其中：其中：d(n)d(n)为为n n的深度的深度 w(n)w(n)为为不在位的棋子数不在位的棋子数 取取h(n)=w(n),h(n)=w(n),则有则有w(n)hw(n)h*(n),h(n)(n),h(n)满足满足A*算法的限制条件。算法的限制条件。第二十三页，讲稿共九十八页哦1238476528316475初始状态初始状态目标状态目标状态 在八数码难题中在八数码难题中,令估价函数令估价函数 f(n)=d(n)+p(n)f(n)=d(n)+p(n)启发函数启发函数h(n)=p(n),h(n)=p(n),p(n)p(n)为不在位的棋子与其目标位置为不在位的棋子与其目标位置的的距离之和距离之和，则有，则有p(n)p(n)hh*(n),(n),满足满足A*算法的限制条件。算法的限制条件。第二十四页，讲稿共九十八页哦2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5目标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第二十五页，讲稿共九十八页哦w(n)w(n)不不在在位位的的棋棋子子数数，不不够够贴贴切切，错错误误选选用用节节点点加加以以扩展。扩展。p(n)p(n)更更接接近近于于h h*(n)(n)的的h(n)h(n)，其其值值是是节节点点n n与与目目标标状状态态节节点点相相比比较较，每每个个错错位位棋棋子子在在假假设设不不受受阻阻拦拦的的情情况况下下，移移动动到目标状态相应位置所需走步的总和。到目标状态相应位置所需走步的总和。p(n)p(n)比比w(n)w(n)更更接接近近于于h h*(n)(n)，因因为为p(n)p(n)不不仅仅考考虑虑了了错错位位因因素素，还考虑了错位的距离（移动次数）。还考虑了错位的距离（移动次数）。说明说明h h值越大值越大,启发功能越强启发功能越强,搜索效率越高搜索效率越高.特别地特别地(1)(1)h(n)=h*(n)h(n)=h*(n)搜索仅沿最佳路径进行搜索仅沿最佳路径进行,效率最高效率最高.(2)(2)h(n)=0h(n)=0 无启发信息无启发信息,盲目搜索盲目搜索,效率低效率低.(3)(3)h(n)h*(n)h(n)h*(n)是一般的是一般的A A算法算法,效率高效率高,但不能保证找到最佳路径但不能保证找到最佳路径.有时为求解难题取有时为求解难题取h(n)h*(n),h(n)h*(n),以提高效率以提高效率.第二十六页，讲稿共九十八页哦3.5 消解原理回顾：回顾：原子公式原子公式（atomic formulasatomic formulas）文字文字一个原子公式及其否定。一个原子公式及其否定。P(x),P(x)子句子句由文字的析取组成的合适公式。由文字的析取组成的合适公式。P(x)Q(x)空子句空子句-不包含任何子句的文字。用不包含任何子句的文字。用NIL表示表示子句集子句集-由子句或空子句所构成的集合由子句或空子句所构成的集合.消解消解对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。3.5.1 子句集的求取 步骤：共9步。第四十页，讲稿共九十八页哦v 例子:将下列谓词演算公式化为一个子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)开始：(1)消去蕴涵符号 只应用和符号，以AB替换AB。(1)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)3.5 消解原理第四十一页，讲稿共九十八页哦(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)第四十二页，讲稿共九十八页哦(4)消去存在量词 以Skolem函数代替存在量词内的约束变量，然后消去存在量词(5)化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形=前缀 母式 全称量词串 无量词公式(4)(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x)式中，式中，w=g(x)w=g(x)为一为一SkolemSkolem函数。函数。(5)(5)(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)3.5 消解原理第四十三页，讲稿共九十八页哦(6)把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(7)消去全称量词 所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。3.5 消解原理(6)(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)第四十四页，讲稿共九十八页哦(8)消去连词符号 用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(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)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3)第四十五页，讲稿共九十八页哦3.5.2 消解推理规则消解推理规则消解式的定义消解式的定义令令L L1 1，L L2 2为两任意原子公式；为两任意原子公式；L L1 1和和L L2 2具有相同的谓具有相同的谓词符号，但一般具有不同的变量。已知两子句词符号，但一般具有不同的变量。已知两子句L L1 1和和L L2 2,如果如果L L1 1和和L L2 2具有最一般合一具有最一般合一，那么通过消解可以从这两个父辈子句推导出一个新那么通过消解可以从这两个父辈子句推导出一个新子句子句()()。这个新子句叫做消解式。这个新子句叫做消解式。消解式求法取各子句的析取，然后消去互补对。3.5 消解原理第四十六页，讲稿共九十八页哦几种从父辈子句求消解式的例子几种从父辈子句求消解式的例子假言推理假言推理 A A B 则 B合并合并 P Q P Q 则 Q重言式重言式 P Q P Q空子句空子句 P P链式链式 P Q Q R 则 P R第四十七页，讲稿共九十八页哦3.5.3 含有变量的消解式含有变量的消解式 要要把把消消解解推推理理规规则则推推广广到到含含有有变变量量的的子子句句，必必须须找找到到一一个作用于父辈子句的置换，使父辈子句含有互补文字个作用于父辈子句的置换，使父辈子句含有互补文字。含有变量的子句之消解式含有变量的子句之消解式 例子Px,f(y)Q(x)Rf(a),y Pf(f(a),zR(z，w)Q f(f(a)R(f(a)，y)R(f(y)，w)=f(f(a)/x,f(y)/z3.5 消解原理第四十八页，讲稿共九十八页哦3.5.4 消解反演求解过程消解反演消解反演 给出给出SS，L L否定否定L L，得，得L L；把把L L添加到添加到S S中去；中去；把新产生的集合把新产生的集合L L，S S化成子句集；化成子句集；应用消解原理，力图推导出一个表示矛盾的空子句应用消解原理，力图推导出一个表示矛盾的空子句 例例1 1储蓄问题储蓄问题 前提：每个储蓄钱的人都获得利息。前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱结论：如果没有利息，那么就没有人去储蓄钱3.5 消解原理第四十九页，讲稿共九十八页哦(1）规定原子公式：S(x,y)S(x,y)表示“x储蓄y”M(x)M(x)表示“x是钱”I(x)I(x)表示“x是利息”E(xE(x，y)y)表示“x获得y”(2）用谓词公式表示前提和结论：用谓词公式表示前提和结论：前提：前提：(x)(x)(y)(S(x,y)M(y)y)(S(x,y)M(y)(y)(I(y)E(x,y)y)(I(y)E(x,y)结论：结论：(x)I(x)x)I(x)(x)(x)(y)(M(y)y)(M(y)S(x,y)S(x,y)(3)化为子句形化为子句形证明证明：3.5 消解原理第五十页，讲稿共九十八页哦把前提化为子句形：把前提化为子句形：1)S(x,y)S(x,y)M(y)I(f(x)M(y)I(f(x)2)S(x,y)S(x,y)M(y)E(x,f(x)M(y)E(x,f(x)把结论化为子句形：把结论化为子句形：3)I(z)I(z)4)S(a,b)S(a,b)5)M(b)M(b)(4)消解反演求消解反演求NILNIL图图3.12 3.12 储蓄问题反演树储蓄问题反演树子句子句（1）子句子句（3）f(x)/zM(b)NIL子句子句（5）子句子句（7）子句子句（4）a/x,b/yS(x,y)M(y)子句子句（6）3.5 消解原理第五十一页，讲稿共九十八页哦例例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)第五十二页，讲稿共九十八页哦将谓词转化为子句集：将谓词转化为子句集：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。归结反演过程如下：归结反演过程如下：第五十三页，讲稿共九十八页哦P6 Pass(x,computer)Win(x,prize)Happy(x)Lucky(w)Win(w,prize)Pass(w,computer)Happy(w)Lucky(w)置换置换w/x P1 Happy(zhang)Q Pass(zhang,computer)Lucky(zhang)置换置换zhang/wLucky(zhang)P5 Pass(zhang,computer)Lucky(u)Pass(u,v)P3 Lucky(zhang)置换置换zhang/u,computer/vLucky(zhang)P5NIL 归结出归结出NIL，证明结论为真。证明结论为真。第五十四页，讲稿共九十八页哦从反演树求取问题的答案从反演树求取问题的答案步骤步骤1.把问题的已知条件用谓词公式表达出来，并转换成子句集把问题的已知条件用谓词公式表达出来，并转换成子句集S；2.把问题的目标的否定用谓词公式表达出来，并转换成把问题的目标的否定用谓词公式表达出来，并转换成子句集子句集Q；3.对对Q中的每个子句，构造其重言式（包含互补文字对的子中的每个子句，构造其重言式（包含互补文字对的子句），代替相应的目标否定子句，加入到句），代替相应的目标否定子句，加入到S中，得到中，得到S；4.对对S应用消解原理求出消解树，该消解树的根子句为所求答应用消解原理求出消解树，该消解树的根子句为所求答案。案。实质实质把一棵根部有把一棵根部有NIL的反演树变换为根部带有回的反演树变换为根部带有回 答语句的一棵答语句的一棵证明树。证明树。第五十五页，讲稿共九十八页哦例例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)第五十六页，讲稿共九十八页哦把目标的否定化为子句，用重言式把目标的否定化为子句，用重言式 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/uAt(zhang,302)P2At(li,302)置换置换zhang/x置换置换302/z答案：李在答案：李在302教室。教室。第五十七页，讲稿共九十八页哦正向演绎系统的基本思想正向演绎系统的基本思想逻辑蕴涵式与子句的区别：上面二个表达式在逻辑上是等价的，但所表达的概念有区别：上面二个表达式在逻辑上是等价的，但所表达的概念有区别：强调推理性：强调推理性(即：前件为真时后件为真即：前件为真时后件为真)：只是表示了：只是表示了A、B、C中有一个为真，则公式为中有一个为真，则公式为真真可见：将蕴涵式写成与其等价的子句形式会损失一些逻辑信息。可见：将蕴涵式写成与其等价的子句形式会损失一些逻辑信息。直接利用蕴涵式所做的证明系统就是基于规则的演绎系统。直接利用蕴涵式所做的证明系统就是基于规则的演绎系统。3.6 规则演绎系统第五十八页，讲稿共九十八页哦 定义定义 基基于于规规则则的的问问题题求求解解系系统统运运用用IfThen规规则则来来建建立立，每每个个if if可可能能与与某某断断言言(assertion)(assertion)集集中中的的一一个个或或多多个个断断言言匹匹配配。有有时时把把该该断断言言集集称称为为工工作作内内存存，thenthen部部分分用用于于规规定定放放入入工工作作内内存存的的新新断断言言。这这种种基基于于规规则则的的系系统统叫叫做做规规则则演演绎绎系系统统。在在这这种种系系统统中中，通常称每个通常称每个if if部分为前项，称每个部分为前项，称每个thenthen部分为后项。部分为后项。IF A THEN B IF A THEN B IF B THEN C IF B THEN C IF C THEN D IF C THEN D 已知已知 A A 第五十九页，讲稿共九十八页哦3.6.1 规则正向演绎系统规则正向演绎系统定义定义 正向规则演绎系统是从事实到目正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动标进行操作的，即从状况条件到动作进行推理的，也就是从作进行推理的，也就是从if if到到thenthen的的方向进行推理的。方向进行推理的。3.6 规则演绎系统第六十页，讲稿共九十八页哦正向规则演绎的求解过程正向规则演绎的求解过程1.1.事实表达式的与或形变换事实表达式的与或形变换 在基于规则的正向演绎系统中，我们把事实表示在基于规则的正向演绎系统中，我们把事实表示为为非蕴涵形式的与或形非蕴涵形式的与或形，作为系统的总数据库。，作为系统的总数据库。方法：将规则前件的事实表达式从规则中分离出来，单方法：将规则前件的事实表达式从规则中分离出来，单独变换成与或形式的表达式，但是不必化简成子句。独变换成与或形式的表达式，但是不必化简成子句。第六十一页，讲稿共九十八页哦例如：一个事实表达式：例如：一个事实表达式：消去存在量词，由常量代替变元消去存在量词，由常量代替变元x，得到一个与或表达式：得到一个与或表达式：利用等价变换，得到：利用等价变换，得到：对第一个合取项进行变量换名对第一个合取项进行变量换名(w/y)，目的是保证每个合取项的变量名都不相同目的是保证每个合取项的变量名都不相同得到公式：上式不是子句，但是一个与或表达式，可以直接用于正向推理上式不是子句，但是一个与或表达式，可以直接用于正向推理系统。系统。第六十二页，讲稿共九十八页哦2.2.用与或图表示一个与或表达式：用与或图表示一个与或表达式：与或图中的节点代表子表达式与或图中的节点代表子表达式当表达式为析取式当表达式为析取式(E1E2 Ek)时，则每时，则每个子表达式表示为原表达式的一个后继节点，且个子表达式表示为原表达式的一个后继节点，且用一个用一个K连接符连接每个连接符连接每个Ei，表示为与关系。，表示为与关系。当表达式为合取式当表达式为合取式(E1E2 Ek)时，则时，则每个子表达式单独作为原表达式的一个子节每个子表达式单独作为原表达式的一个子节点，用点，用1连接符连接，表示为或关系。连接符连接，表示为或关系。第六十三页，讲稿共九十八页哦上例的事实表达式用与或图表示如下：上例的事实表达式用与或图表示如下：可以看出，每个端节点都是一个文字，所以与或图相当于把一个表达可以看出，每个端节点都是一个文字，所以与或图相当于把一个表达式按照与或关系拆分成文字表示。式按照与或关系拆分成文字表示。第六十四页，讲稿共九十八页哦讨论：讨论：利用与或图求解图：利用与或图求解图：方法与可分解系统中的解图求法相同。不同的是与或图中的节点之方法与可分解系统中的解图求法相同。不同的是与或图中的节点之间的合取、析取关系是相反的。因此，求解图是按照间的合取、析取关系是相反的。因此，求解图是按照K连接方式求解，连接方式求解，而不是按照真值求解。而不是按照真值求解。上图中的三个解图分别构成三个子句：上图中的三个解图分别构成三个子句：Q(w,A),R(y)S(A,y),P(y)S(A,y)基于规则正向推理系统中的与或图是一种知识表达方式；基于规则正向推理系统中的与或图是一种知识表达方式；可分解系统中的与或图是一种图搜索方式，二者是不同的。可分解系统中的与或图是一种图搜索方式，二者是不同的。第六十五页，讲稿共九十八页哦3.与或图的与或图的F规则变换规则变换 这些规则是建立在某个问题辖域中普通陈述性知这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：式类型限制为下列形式：L W 式中：式中：L是单文字；是单文字；W为与或形的唯一公式。为与或形的唯一公式。3.6 规则演绎系统如果规则为如果规则为(L1L2)W形式，即前提是析取形式，则将其分解成形式，即前提是析取形式，则将其分解成二条规则二条规则 L1 W，L2 W如果规则为如果规则为(L1L2)W形式，即前提是合取形式，形式，即前提是合取形式，不予讨不予讨论。论。第六十六页，讲稿共九十八页哦例：初始数据库的与或表达式为：例：初始数据库的与或表达式为：(PQ)R S (TU)规则：规则：S(XY)Z推理过程：推理过程：用与或图表示初始条件表达式用与或图表示初始条件表达式 寻找与规则前提匹配的文字寻找与规则前提匹配的文字 用匹配弧连接上述两个文字用匹配弧连接上述两个文字 将规则结论的与或图连接到前提上，扩充与或图将规则结论的与或图连接到前提上，扩充与或图 正向系