人工智能(3)复习进程.ppt
211页
人工智能人工智能2012(3)2012(3) 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 盲目搜索 例：例：八数码难题八数码难题 3×3九九宫宫棋棋盘盘，，放放置置数数码码为为1 - 8的的8个个棋棋牌牌，，剩剩下下一一个个空空格，只能通过棋牌向空格的移动来改变棋盘的布局格，只能通过棋牌向空格的移动来改变棋盘的布局·求解的问题求解的问题——给定初始布局（即初始状态）和目标布给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达局（即目标状态），如何移动棋牌才能从初始布局到达目标布局目标布局 ·解答路径解答路径——就是一个合法的走步序列就是一个合法的走步序列 ·用宽度优先搜索方法解决该问题：用宽度优先搜索方法解决该问题： 为问题状态的表示建立数据结构：为问题状态的表示建立数据结构：3×3的一个矩阵的一个矩阵，，* 矩阵元素矩阵元素S ij∈∈{0,1,…,8}；；其中其中1≤i,j≤3，，* 数字数字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 有序搜索v实质 选择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 启发式搜索lg*(n)：：从从s到到n的最小路径代价值的最小路径代价值lh*(n)：：从从n到到g的最小路径代价值的最小路径代价值lf*(n)=g*(n)+h*(n)：：从从s经过经过n到到g的最小路径的最小路径的总代价的总代价值值lg(n)、、h(n)、、f(n)分别是分别是g*(n)、、h*(n)、、f*(n)的估计值的估计值lg(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均有均有 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*算法就变为有序搜索算法算法就变为有序搜索算法 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)≤h≤h* *(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.4 3.4 博弈树的启发式搜索博弈树的启发式搜索–参与搜索的不只是一个主体，而包括对抗的多参与搜索的不只是一个主体，而包括对抗的多方方(对弈对弈) –任何一方在选择自己的行为时，都要将对方可任何一方在选择自己的行为时，都要将对方可能采取的对策考虑在内能采取的对策考虑在内–由此而产生的搜索树称为博弈树由此而产生的搜索树称为博弈树(博弈图博弈图) 博奕博奕: 两棋手按一定规则轮流走步两棋手按一定规则轮流走步, 双方都知道对方的双方都知道对方的走步走步, 当满足一定条件时当满足一定条件时, 走步结束走步结束, 这时这时, 或一方取或一方取胜胜, 或为和局或为和局.1.1.博弈问题博弈问题 我我方方（（指指程程序序方方，，叫叫MAX））每每走走一一着着棋棋（（半半回回合合）），，都都力力图图使使自自己己通通向向取取胜胜的的目目标标。
轮轮到到MAX走走棋棋时时，，由由于于它它掌掌握握着着出出棋棋的的主主动动权权，，只只要要此此时时的的各各种种走走法法中中有有一一个个能能通通向向胜胜局局，，它它就就会会毫毫不不客客气气地地出出这这一一着着因因此此由由MAX方方出出棋棋的的结结点点具具有有或或结结点点的的性性质质对对手手（（叫叫MIN，，是是一一个个回回合合的的对对棋棋者者））每每走走一一着着棋棋（（半半回回合合）），，都都力力图图干干扰扰MAX的的选选择择，，使使其其偏偏离离取取胜胜的的目目标标轮轮到到MIN走走棋棋时时，，由由于于它它掌掌握握着着对对棋棋的的主主动动权权，，因因此此只只要要此此时时的的全全部部着着法法中中有有一一个个能能导导致致败败局局，，它它就就会会毫毫不不客客气气地地出出这这一一着着因因此此由由MIN对对棋棋的的结结点点具有与终点的性质所以具有与终点的性质所以-博弈树一般都是与／或树博弈树一般都是与／或树 博弈树的特点：博弈树的特点： （（1）初始格局是初始节点）初始格局是初始节点 （（2）博弈树中或节点和与节点逐层交替出现）博弈树中或节点和与节点逐层交替出现 （（3））所所有有能能使使自自己己一一方方获获胜胜的的终终局局都都是是本本原原问问题题，，而相应使对方获胜的棋局均为不可解节点。
而相应使对方获胜的棋局均为不可解节点 例例 分火柴游戏分火柴游戏 设一堆火柴有设一堆火柴有7根，由根，由MAX（（我方）和我方）和MIN（（对手）两人轮流来分它们，要求对手）两人轮流来分它们，要求每次都要把某一堆火柴分成不相等的两每次都要把某一堆火柴分成不相等的两部分，最后不能分下去的人为负，对方部分，最后不能分下去的人为负，对方为胜 如果如果MIN先走，可以有三种选择：先走，可以有三种选择： （（6，，1）、（）、（5，，2）、（）、（4，，3）） 在每一种选择下，在每一种选择下，MAX又可以有两种走法，整个博弈又可以有两种走法，整个博弈过程的状态空间如图所示结点中的数字表示各堆火柴的过程的状态空间如图所示结点中的数字表示各堆火柴的根数分布，名字表示轮到他继续向下走棋根数分布，名字表示轮到他继续向下走棋 (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) 2.2. 极大极小过程极大极小过程 极大极小搜索策略是极大极小搜索策略是考虑双方对弈若干步考虑双方对弈若干步之后之后, , 从可能的走步中选一步相对好棋的走法来走从可能的走步中选一步相对好棋的走法来走, , 即即在有限的在有限的搜索深度范围内搜索深度范围内进行求解。
定义一个进行求解定义一个静态估计函数静态估计函数f f, , 以以便对棋局的势态便对棋局的势态( (节点节点) )作出优劣估值一般规定有利于作出优劣估值一般规定有利于MAXMAX的势态的势态, , f(p)f(p)取正值取正值, , 有利于有利于MINMIN的势态的势态, , f(p)f(p)取负值取负值, , 势均力敌的势态势均力敌的势态, , f(p)f(p)取取0 0值值, , 若若f(o)=+∞, f(o)=+∞, 则表示则表示MAXMAX赢赢, , 若若f(o)=-∞, f(o)=-∞, 则表示则表示MINMIN赢 在轮到在轮到MAXMAX走时走时, , 选择选择f(p)f(p)大的节点走大的节点走; ; 而轮到而轮到MINMIN走时走时, , 应考虑对方会选应考虑对方会选f(p)f(p)最小的节点走最小的节点走. . 因此因此, , 在博奕在博奕图搜索时图搜索时, , 可采用一步走可采用一步走f(p)f(p)值极大的节点值极大的节点( (MAXMAX走走), ), 一一步走步走f(p)f(p)值极小的节点值极小的节点( (MINMIN走走), ), 这样交替前进的方法这样交替前进的方法. . 这种搜索过程称为极大极小过程这种搜索过程称为极大极小过程. . 例例: : 一字棋一字棋 棋局中棋局中, , 我方我方( (MAX)MAX)棋子用棋子用 表示表示, , 对方对方( (MIN)MIN)棋子棋子用用°°表示表示. . 开始由我方先走开始由我方先走, ,估价函数估价函数: : 我方获胜我方获胜e(p)= - e(p)= - 对方获胜对方获胜 e(+p)-e(-p) e(+p)-e(-p) 其他情况其他情况 空格视为空格视为 时我方三连子数时我方三连子数- -空格视为空格视为 ° °时对方三连子数时对方三连子数 °°e(p)=6-4=2 为了计算非叶节点的值，必须从叶节点向上倒推，为了计算非叶节点的值，必须从叶节点向上倒推，叫倒推值。
叫倒推值MAXMAX的倒推值是其后继节点估值的最大值的倒推值是其后继节点估值的最大值MINMIN的倒推值是其后继节点估值的最小值的倒推值是其后继节点估值的最小值 °°°°°°°°°°°°1-1-211010-1-10-10-2 12 °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°11213121010201112231221100 °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°° °° °° °° °°°°°°°°°°°°°°°°°°°°°°°°°°°°111212-101001122111-------ABCD 3.3. - 剪枝剪枝 极大极小过程是把搜索树的生成和格局估值这两个极大极小过程是把搜索树的生成和格局估值这两个过程分开来进行过程分开来进行, ,即先生成全部搜索树即先生成全部搜索树, , 然后再进行端节然后再进行端节点静态估值和倒推值计算点静态估值和倒推值计算, , 这显然会导致低效率。
如果把这显然会导致低效率如果把生成和倒推估值结合起来进行生成和倒推估值结合起来进行, , 再根据一定条件判定再根据一定条件判定, , 有有可能尽早修剪掉一些无用的分枝可能尽早修剪掉一些无用的分枝, , 即即α-βα-β剪枝过程的思剪枝过程的思想 α-βα-β剪枝方法：剪枝方法：（（1 1））MAXMAX节点的节点的 值为当前子节点的最大倒推值；值为当前子节点的最大倒推值；MAX节点的节点的 值在搜索过程中永不减少值在搜索过程中永不减少（（2 2））MINMIN节点的节点的 值为当前子节点的最小倒推值；值为当前子节点的最小倒推值；MIN节点的节点的 值在搜索过程中永不增加值在搜索过程中永不增加 （（3 3）） α-βα-β剪枝规则：剪枝规则： ① ①任何任何MAXMAX节点节点n n的的 值大于或等于它的任一先辈节点值大于或等于它的任一先辈节点MINMIN的的 值值, , 则可终止该则可终止该MAXMAX节点以下的搜索节点以下的搜索, , 并可将其并可将其最终倒推值设为它的最终倒推值设为它的 值值. .这种剪枝称为这种剪枝称为ββ剪枝剪枝 ② ②任何任何MIN节点节点n的的 值小于或等于它的任一先辈节值小于或等于它的任一先辈节点点MAX的的 值值, 则可终止该则可终止该MIN节点以下的搜索节点以下的搜索, 并可并可将其最终倒推值设为它的将其最终倒推值设为它的 值。
这种剪枝称为值这种剪枝称为αα剪枝 αα剪枝：剪枝： αα（（先辈节点）先辈节点）≥ ≥ ββ（（后继节点）后继节点） β β剪枝：剪枝： αα（（后继节点）后继节点）≥ ≥ ββ（（先辈节点）先辈节点） 05-333-302-23523α≥α≥ 0 0β≤β≤ 0 0α≥α≥ 00-303α≥α≥ 3 330β≤β≤ 5 52α≥α≥ 2 2β≤β≤ -5 -5-5-522ααααββββαα剪枝：剪枝： αα（（先辈节点）先辈节点）≥ ≥ ββ（（后继节点）后继节点）ββ剪枝：剪枝： αα（（后继节点）后继节点）≥ ≥ ββ（（先辈节点）先辈节点）β≤β≤ -3 -3αα剪枝剪枝ββ剪枝剪枝2αα剪枝剪枝 481*5P80**α≥ 4β≤ 4α≥α≥ 4414α≥ 554β≤ 00α≥0β≤ -6-6-6004ααααβββββ≤ 1αα剪枝剪枝ββ剪枝剪枝S0KLM6FNGQ5HD*ABRISJEαα剪枝剪枝αα剪枝剪枝C 3.5 消解原理回顾：回顾：原子公式原子公式（（atomic formulasatomic formulas））文字文字—一个原子公式及其否定一个原子公式及其否定。
P(x), P(x)子句子句—由文字的析取组成的合适公式由文字的析取组成的合适公式 P(x) Q(x)空子句空子句------不包含任何子句的文字用不包含任何子句的文字用NIL表示表示子句集子句集------由子句或空子句所构成的集合由子句或空子句所构成的集合. 消解消解—对谓词演算公式进行分解和化简，消去一些符号，以求对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句得导出子句3.5.1 子句集的求取v 步骤：共9步 v 例子: 将下列谓词演算公式化为一个子句集(x)｛P(x)｛(y)［P(y)P(f(x,y))］∧～(y)［Q(x,y)P(y)］｝｝开始：(1)消去蕴涵符号 只应用∨和～符号，以～A∨B替换AB1) (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)为一Skolem函数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) (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}代替(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)］ 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具有最一具有最一般合一般合一σσ，那么通过消解可以从这两个父辈，那么通过消解可以从这两个父辈子句推导出一个新子句子句推导出一个新子句(α∨β)σ(α∨β)σ这个新子这个新子句叫做消解式句叫做消解式 v 消解式求法取各子句的析取，然后消去互补对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 含有变量的消解式含有变量的消解式 要要把把消消解解推推理理规规则则推推广广到到含含有有变变量量的的子子句句，，必必须须找找到到一一个作用于父辈子句的置换，使父辈子句含有互补文字个作用于父辈子句的置换，使父辈子句含有互补文字。
v 含有变量的子句之消解式含有变量的子句之消解式v 例子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 消解原理 3.5.4 消解反演求解过程•消解反演消解反演 给出给出{S}{S}，，L L–否定否定L L，得～，得～L L；；–把～把～L L添加到添加到S S中去；中去；–把新产生的集合｛～把新产生的集合｛～L L，，S S｝化成子句集；｝化成子句集；–应用消解原理，力图推导出一个表示矛盾的空子句应用消解原理，力图推导出一个表示矛盾的空子句v 例例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)/z～M(b)NIL子句（5）子句（（7））子句（4）{a/x,b/y}～S(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/w}Lucky(zhang) P5 Pass(zhang ,computer) Lucky(u) Pass(u,v) P3 Lucky(zhang) 置换置换{zhang/u,computer/v}Lucky(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/u}At(zhang,302 ) P2At(li,302)置换置换{zhang/x}置换置换{302/z}答案：李在答案：李在302教室。
教室 3.6 规则演绎系统• 定义定义 基基于于规规则则的的问问题题求求解解系系统统运运用用If→Then规规则则来来建建立立，，每每个个if if可可能能与与某某断断言言(assertion)(assertion)集集中中的的一一个个或或多多个个断断言言匹匹配配有有时时把把该该断断言言集集称称为为工工作作内内存存，，thenthen部部分分用用于于规规定定放放入入工工作作内内存存的的新新断断言言这这种种基基于于规规则则的的系系统统叫叫做做规规则则演演绎绎系系统统在在这这种种系系统统中中，，通通常常称称每每个个if if部部分分为为前前项，称每个项，称每个thenthen部分为后项部分为后项 3.6.1 规则正向演绎系统•定义定义 正向规则演绎系统是从事实到目标进行操作的，正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从即从状况条件到动作进行推理的，也就是从if if到到thenthen的方向进行推理的的方向进行推理的 •求解过程求解过程–事实表达式的与或形变换事实表达式的与或形变换 在基于规则的正向演绎系统中，我们把事实在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数表示为非蕴涵形式的与或形，作为系统的总数据库。
据库3.6 规则演绎系统 –与或图的与或图的F规则变换规则变换 这些规则是建立在某个问题辖域中普通陈这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的我们把允许用述性知识的蕴涵公式基础上的我们把允许用作规则的公式类型限制为下列形式：作规则的公式类型限制为下列形式： L W 式中：式中：L是单文字；是单文字；W为与或形的唯一公式为与或形的唯一公式3.6 规则演绎系统 1、正向演绎系统的基本思想、正向演绎系统的基本思想逻辑蕴涵式与子句的区别：上面二个表达式在逻辑上是等价的，但是所表达的概念有区别：上面二个表达式在逻辑上是等价的，但是所表达的概念有区别： ：强调推理性：强调推理性(即：前件为真时后件为真即：前件为真时后件为真) ：只是表示了：只是表示了A、、B、、C中有一个为真，则公式为真中有一个为真，则公式为真可见：将蕴涵式写成与其等价的子句形式会损失一些逻辑信息可见：将蕴涵式写成与其等价的子句形式会损失一些逻辑信息。
直接利用蕴涵式直接利用蕴涵式 所做的证明系统就是基于规则的演绎系统所做的证明系统就是基于规则的演绎系统 2 事实表达式的与或表示事实表达式的与或表示方法：将规则前件的事实表达式从规则中分离出来，单独变换成与或形式的表方法：将规则前件的事实表达式从规则中分离出来，单独变换成与或形式的表 达式，但是不必化简成子句达式，但是不必化简成子句 例如：一个事实表达式：例如：一个事实表达式：消去存在量词，由常量代替变元消去存在量词，由常量代替变元x，， 得到一个与或表达式：得到一个与或表达式：利用等价变换，得到：利用等价变换，得到：对第一个合取项进行变量换名对第一个合取项进行变量换名(w/y)，，目的是保证每个合取项的变量名都不相同目的是保证每个合取项的变量名都不相同得到公式：上式不是子句，但是一个与或表达式，可以直接用于正向推理系统上式不是子句，但是一个与或表达式，可以直接用于正向推理系统用与或图表示一个与或表达式：用与或图表示一个与或表达式：①①与或图中的节点代表子表达式与或图中的节点代表子表达式②②当表达式为析取式当表达式为析取式 (E1∨∨E2 ∨∨ … ∨∨ Ek)时，则每个子表达式表示为原表达式时，则每个子表达式表示为原表达式 的一个后继节点，且用一个的一个后继节点，且用一个K连接符连接每个连接符连接每个Ei ，表示为与关系。
表示为与关系③③当表达式为合取式当表达式为合取式 (E1∧∧E2 ∧∧ … ∧∧ Ek)时，则每个子表达式单独作为原表达时，则每个子表达式单独作为原表达 式的一个子节点，用式的一个子节点，用1连接符连接，表示为或关系连接符连接，表示为或关系… 上例的事实表达式用与或图表示如下：上例的事实表达式用与或图表示如下：可以看出，每个端节点都是一个文字，所以与或图相当于把一个表达式按照与或可以看出，每个端节点都是一个文字，所以与或图相当于把一个表达式按照与或关系拆分成文字表示关系拆分成文字表示讨论：讨论：①①利用与或图求解图：利用与或图求解图： 方法与可分解系统中的解图求法相同不同的是与或图中的节点之间的合取、方法与可分解系统中的解图求法相同不同的是与或图中的节点之间的合取、析取关系是相反的因此，求解图是按照析取关系是相反的因此，求解图是按照K连接方式求解，而不是按照真值求解连接方式求解，而不是按照真值求解 上图中的三个解图分别构成三个子句：上图中的三个解图分别构成三个子句： Q(w,A), ~R(y) ∨∨~S(A,y) , ~P(y) ∨∨~S(A,y) ②②基于规则正向推理系统中的与或图是一种知识表达方式；基于规则正向推理系统中的与或图是一种知识表达方式； 可分解系统中的与或图是一种图搜索方式，二者是不同的。
可分解系统中的与或图是一种图搜索方式，二者是不同的3 命题逻辑的正向推理命题逻辑的正向推理关于关于F规则的限制：规则的限制：F规则以单文字前提出现规则以单文字前提出现 L → W，其中：，其中：L：单文字前提：单文字前提W：用与或形式表示的任何公式：用与或形式表示的任何公式①①如果规则为如果规则为 (L1∨∨L2) →W形式，即前提是析取形式，则将其分解形式，即前提是析取形式，则将其分解成二条规则成二条规则 L1 →W，， L2 →W②②如果规则为如果规则为 (L1∧∧L2) →W形式，即前提是合取形式，形式，即前提是合取形式， 不予讨论不予讨论 例：初始数据库的与或表达式为：例：初始数据库的与或表达式为： [(P∨∨Q) ∧∧R] ∨∨[S ∧∧ (T∨∨U)] 规则：规则： S→(X∧∧Y) ∨∨Z推理过程：推理过程：①① 用与或图表示初始条件表达式用与或图表示初始条件表达式②② 寻找与规则前提匹配的文字寻找与规则前提匹配的文字③③ 用匹配弧连接上述两个文字用匹配弧连接上述两个文字④④ 将规则结论的与或图连接到前提上，扩充与或图将规则结论的与或图连接到前提上，扩充与或图⑤⑤ 正向系统的推理树根节点在下部正向系统的推理树根节点在下部上面例题的推理树见下页。
上面例题的推理树见下页 从上图的事实表达式部分可以得到四个子句：从上图的事实表达式部分可以得到四个子句：(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 从上图的规则结论部分可以得到二个子句：从上图的规则结论部分可以得到二个子句：(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 首先将事实表达式和规则写成子句形式：首先将事实表达式和规则写成子句形式：事实表达式事实表达式 [(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由此可见，用归结方法与用与或树方法得到的归结式是相同的。
由此可见，用归结方法与用与或树方法得到的归结式是相同的 例：事实表达式例：事实表达式 A∨∨B 规则规则 R1：：A→(C∧∧D) R2：：B→(E∧∧G) 目标目标 C∨∨G推理树：推理树：由此解图得到子句集：由此解图得到子句集： {C∨∨E, C∨∨G, D∨∨E, D∨∨G}其中：其中： C∨∨G是目标是目标A∨∨BCGCDEGABABR1R2 3.6.2 规则逆向演绎系统•定义定义 逆向规则演绎系统是从逆向规则演绎系统是从then向向if进行推理进行推理的，即从目标或动作向事实或状况条件进行推的，即从目标或动作向事实或状况条件进行推理的 •求解过程求解过程–目标表达式的与或形式目标表达式的与或形式–与或图的与或图的B规则变换规则变换–作为终止条件的事实节点的一致解图作为终止条件的事实节点的一致解图3.6 规则演绎系统 1 目标表达式的与或表示目标表达式的与或表示 逆向推理系统从目标开始，与正向系统相反，规则的使用是反向逆向推理系统从目标开始，与正向系统相反，规则的使用是反向的。
的目标表达式的与或形式：目标表达式的与或形式：(1) 利用利用skolem函数对目标公式进行标准化（同以前讲的标准化过程函数对目标公式进行标准化（同以前讲的标准化过程相同）相同）(2) 各析取项之间变元要各不相同（变量换名）各析取项之间变元要各不相同（变量换名）(3) 子表达式之间为析取关系时，使用子表达式之间为析取关系时，使用1连接符连接连接符连接 子表达式之间为合取关系时，使用子表达式之间为合取关系时，使用K连接符连接连接符连接(4) 与或图的根节点在上面与或图的根节点在上面例：目标公式：例：目标公式： 标准化，得到：变量换名，得到： 2 逆向推理系统逆向推理系统关于规则的限制：关于规则的限制：B规则的形式：规则的形式：W → L其中：其中：W：任何与或公式：任何与或公式 L：单文字结论：单文字结论①① 规则中的变元全部是全称量词约束规则中的变元全部是全称量词约束②② 如果规则为如果规则为W →(L1∧∧L2) 形式，则分解为两条规则：形式，则分解为两条规则： W → L1 和和 W → L2推理过程：推理过程：(1) 用与或图表示目标表达式用与或图表示目标表达式(2) 寻找与规则结论匹配的文字寻找与规则结论匹配的文字 (3) 用匹配弧连接上述的二个匹配文字用匹配弧连接上述的二个匹配文字 (4) 将规则的结论与前提连接，扩充与或图，直至出现事实表达式的文字将规则的结论与前提连接，扩充与或图，直至出现事实表达式的文字(5) 反向推理树的根节点在上面反向推理树的根节点在上面 反向推理例题：反向推理例题： 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) 得到一个解图：得到一个解图： 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} (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, MR/ y2, FIDO/x2, FIDO/x1)(4) 利用合一复合对目标公式作置换，得到置换例：利用合一复合对目标公式作置换，得到置换例： C(MR) ∧∧ D(FIDO) ∧∧ ~A(MR, FIDO)该置换例就是推理结果该置换例就是推理结果 正向和逆向组合系统是建立在两个系统相结正向和逆向组合系统是建立在两个系统相结合的基础上的。
此组合系统的总数据库由表示目合的基础上的此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成这些与或标和表示事实的两个与或图结构组成这些与或图结构分别用正向系统的图结构分别用正向系统的F F规则和逆向系统的规则和逆向系统的B B规规则来修正则来修正3.6.3 规则双向演绎系统3.6 规则演绎系统 3.7 产生式系统产生式系统•定义定义：：用来描述若干个不同的以一个基本用来描述若干个不同的以一个基本概念为基础的系统这个基本概念就是产概念为基础的系统这个基本概念就是产生式规则或产生式条件和操作对的概念生式规则或产生式条件和操作对的概念•实质：在产生式系统中，论域的知识分为实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表事件和它们之间的关系；用产生式规则表示推理过程和行为由于这类系统的知识示推理过程和行为由于这类系统的知识库主要用于存储规则，因此又把此类系统库主要用于存储规则，因此又把此类系统称为基于规则的系统称为基于规则的系统 3.7.1 产生式系统的组成产生式系统的组成图图3.22 产生式系统的主要组成产生式系统的主要组成控制系统总数据库规则库3.7 产生式系统 Ø规则库规则库•用于存放与求解问题有关的某个领域知识用于存放与求解问题有关的某个领域知识的规则集。
的规则集• 在建立规则库时，应注意如下问题：在建立规则库时，应注意如下问题： （（1）规则库知识的完整性、一致性、准）规则库知识的完整性、一致性、准确性、灵活性确性、灵活性 （（2）对知识进行合理的组织与管理）对知识进行合理的组织与管理：目：目的是使得推理避免访问与所求解的问题无的是使得推理避免访问与所求解的问题无关的知识，以提高问题求解效率关的知识，以提高问题求解效率 Ø总数据库总数据库•总数据库又称为总数据库又称为事实库、上下文、黑板事实库、上下文、黑板等它是一个用于存放问题求解过程中各种当前信息的数一个用于存放问题求解过程中各种当前信息的数据结构，例如：问题的初始状态、原始证据、推据结构，例如：问题的初始状态、原始证据、推理中得到的中间结论、最终结论等理中得到的中间结论、最终结论等•当规则库中某条产生式的前提可与总数据库中当规则库中某条产生式的前提可与总数据库中的某些已知事实匹配时，该产生式就被激活，并的某些已知事实匹配时，该产生式就被激活，并把其结论放入总数据库中，作为后面推理的已知把其结论放入总数据库中，作为后面推理的已知事实显然，事实显然，总数据库的内容是在不断变化的，总数据库的内容是在不断变化的，是动态的是动态的。
•总数据库中的总数据库中的已知事实通常用字符串、向量、集已知事实通常用字符串、向量、集合、矩阵、表等数据结构表示合、矩阵、表等数据结构表示 Ø控制系统控制系统 控制系统又称控制系统又称推理机构推理机构，由一组程序组成，负，由一组程序组成，负责整个产生式系统的运行，实现对问题的求解责整个产生式系统的运行，实现对问题的求解主要包括推理策略和搜索策略两部分主要包括推理策略和搜索策略两部分 推理策略：主要解决推理方向、冲突消解等问题推理策略：主要解决推理方向、冲突消解等问题搜索策略：主要解决搜索线路、推理效果、推理效率等搜索策略：主要解决搜索线路、推理效果、推理效率等问题 控制系统的主要工作：控制系统的主要工作：（（1）按一定的策略从规则库中）按一定的策略从规则库中选择选择与总数据库中的与总数据库中的已知事实相已知事实相匹配的规则匹配的规则2）当发生）当发生冲突冲突（即匹配成功的规则不止一条）时，（即匹配成功的规则不止一条）时，调用相应的冲突解决策略予以消解调用相应的冲突解决策略予以消解3）在执行某条规则时，若该规则的右部是一个或）在执行某条规则时，若该规则的右部是一个或多个结论，则多个结论，则把这些结论加到总数据库中把这些结论加到总数据库中；若规；若规则的右部是一个或多个操作，则则的右部是一个或多个操作，则执行这些操作执行这些操作。
（（4）对于）对于不确定性知识不确定性知识，在执行每一条规则，在执行每一条规则时，还要按一定的算法计算结论的不确定时，还要按一定的算法计算结论的不确定性5）对要执行的规则，如果该规则的后件满）对要执行的规则，如果该规则的后件满足问题的结束条件，则足问题的结束条件，则停止推理停止推理6）在问题的求解过程中，记住应用过的规）在问题的求解过程中，记住应用过的规则序列，以便最终能够给出问题的则序列，以便最终能够给出问题的解路径解路径 •选择规则到选择规则到执行操作的步骤执行操作的步骤 1 匹配匹配 把当前数据库与规则的条件部分相匹配把当前数据库与规则的条件部分相匹配 2 冲突冲突 当有一条以上规则的条件部分和当前数据库当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决称为冲突解决 3 操作操作 操作就是执行规则的操作部分操作就是执行规则的操作部分3.7 产生式系统 选取规则的原则称为控制策略（冲突消解）选取规则的原则称为控制策略（冲突消解）•不可撤回方式：属盲目性搜索不可撤回方式：属盲目性搜索, 利用问题给利用问题给出的局部知识选一条可应用规则并作用当出的局部知识选一条可应用规则并作用当前综数据库前综数据库, 接着再根据新状态继续选取规接着再根据新状态继续选取规则则, 搜索过程一直进行下去搜索过程一直进行下去, 不必考虑撤回不必考虑撤回用过的规则。
用过的规则•回溯方式：在问题求解过程中选择一条规回溯方式：在问题求解过程中选择一条规则执行时，建立其回溯点，保留搜索路径，则执行时，建立其回溯点，保留搜索路径，如以后发现此规则不合适，按原路返回，如以后发现此规则不合适，按原路返回，重新选取另一条规则，继续搜索过程重新选取另一条规则，继续搜索过程 •图搜索方式：用图表示问题求解过程，图中结点图搜索方式：用图表示问题求解过程，图中结点代表问题的状态，结点间的弧代表应用的规则代表问题的状态，结点间的弧代表应用的规则用某种方法选择应用规则，并以图结构记录状态用某种方法选择应用规则，并以图结构记录状态变化过程，直到求出问题的解答变化过程，直到求出问题的解答小结：小结： ①①不可撤回方式相当于沿着单独的一条路向下延伸不可撤回方式相当于沿着单独的一条路向下延伸搜索下去；搜索下去； ②②回溯方式不保留完整的搜索树结构，只顾当前工回溯方式不保留完整的搜索树结构，只顾当前工作的一条路径，作的一条路径， 回溯就是对这条路径进行修正；回溯就是对这条路径进行修正； ③③图搜索方式记下完整的搜索树；图搜索方式记下完整的搜索树； 3.7.2 产生式系统的推理 •正向推理正向推理：：从一组表示事实的谓词或命题出发，从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题使用一组产生式规则，用以证明该谓词公式或命题是否成立。
是否成立 •逆向推理逆向推理：：从表示目标的谓词或命题出发，使用从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设提出一批假设目标，然后逐一验证这些假设 •双向推理双向推理：：双向推理的推理策略是同时从目标向双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配某个步骤，实现事实与目标的匹配3.7 产生式系统 （（1 1）正向推理）正向推理 从已知事实出发，正向使用推理规则的推理方式，从已知事实出发，正向使用推理规则的推理方式，也称为数据驱动推理或前向链推理也称为数据驱动推理或前向链推理基本思想：基本思想：•用户将初始证据放入总数据库，用户将初始证据放入总数据库，•推理机根据总数据库中的初始己知事实，到知推理机根据总数据库中的初始己知事实，到知识库中找出当前可适用的规则，形成可用规则识库中找出当前可适用的规则，形成可用规则集，然后按照冲突消解策略，从知识集中选择集，然后按照冲突消解策略，从知识集中选择一条规则进行推理，并将推出的新事实加入到一条规则进行推理，并将推出的新事实加入到总数据库中作为下一步推理的已知事实总数据库中作为下一步推理的已知事实, •重复进行这一过程，直到求得了所要求的解或重复进行这一过程，直到求得了所要求的解或者没有规则可用者没有规则可用. 例如，有规则集如下：例如，有规则集如下： 规则规则1 1：：P P1 1→P→P2 2 规则规则2 2：：P P2 2→P→P3 3 规则规则3 3：：P P3 3→q→q3 3设已知事实设已知事实P P1 1，，正向推理推出正向推理推出q q3 3过程如图：过程如图：P1P2P3q3已知已知 规则规则1(q1)规则规则2(q2)规则规则3 推出推出 正向推理算法：正向推理算法：(1)将用户提供的初始已知事实送入总数据库将用户提供的初始已知事实送入总数据库DB；；(2)检查总数据库检查总数据库DB中是否已经包含了问题的解，若中是否已经包含了问题的解，若有有, 则求解结束，并成功退出；否则转则求解结束，并成功退出；否则转(3)；；(3)根据总数据库根据总数据库DB中的已知事实，扫描知识库中的已知事实，扫描知识库KB，，检查检查KB中是否有可适用中是否有可适用(即可与即可与DB中已知事实中已知事实匹配匹配)的规则，若有，把的规则，若有，把KB中所有的适用知识都中所有的适用知识都选出来，构成可适用的知识集选出来，构成可适用的知识集KS，否则转，否则转(5)；；(4)若若KSKS不空不空，，按某种冲突消解策略从中选出一条知按某种冲突消解策略从中选出一条知识进行推理，并将推出的新事实加入识进行推理，并将推出的新事实加入DB中，然后中，然后转〔转〔2)；若；若KS空，则转空，则转(5)；；(5)询问用户是否可进一步补充新的事实，若可补充，询问用户是否可进一步补充新的事实，若可补充，则将补充的新事实加入则将补充的新事实加入DB中，然后转中，然后转(3)；否则表；否则表示求不出解，失败退出示求不出解，失败退出; 正向推理特点：正向推理特点：优点：直观，允许用户主动提供有用的事实，适用优点：直观，允许用户主动提供有用的事实，适用于诊断、设计、预测、监控等领域。
于诊断、设计、预测、监控等领域缺点：推理无明确目标，推理效率较低缺点：推理无明确目标，推理效率较低2 2）反向推理）反向推理 以某个假设目标作为出发点的推理方法，也称为假以某个假设目标作为出发点的推理方法，也称为假设驱动推理或后向链推理设驱动推理或后向链推理 基本思想：基本思想：n首先选定首先选定—个假设目标，然后寻找支持该假设个假设目标，然后寻找支持该假设的证据，的证据，n若所需的证据都能找到，则说明原假设是成立若所需的证据都能找到，则说明原假设是成立的；的；n若无论如何都找不到所需要的证据，说明原假若无论如何都找不到所需要的证据，说明原假设不成立，此时需要另作新的假设设不成立，此时需要另作新的假设P1P2P3目标目标q3事实事实规则规则1假定假定规则规则2规则规则3假定假定假定假定结论结论q3 反向推理算法：反向推理算法：(1)(1)将要求证的假设将要求证的假设( (目标目标) )构成一个假设集；构成一个假设集；(2)(2)从假设集中选出一个假设，检查该假设是否已在总从假设集中选出一个假设，检查该假设是否已在总数据库中，若在，则该假设成立，此时，若假设集为数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则继续执行（空，则成功退出，否则继续执行（2 2）；若该假设不）；若该假设不在数据库中，转下一步；在数据库中，转下一步；(3)(3)判断该假设是否可由规则库的某个规则导出，若不判断该假设是否可由规则库的某个规则导出，若不能，则询问用户是否为可由用户证实的原始事实，若能，则询问用户是否为可由用户证实的原始事实，若是，该假设成立，并放入总数据库，重新寻找新的假是，该假设成立，并放入总数据库，重新寻找新的假设，若不是，则转（设，若不是，则转（5 5）；）；(4)(4)将规则库可以导出该假设的规则构成可用规则集将规则库可以导出该假设的规则构成可用规则集(5)(5)检查可用规则集是否为空，若空，失败退出，否则检查可用规则集是否为空，若空，失败退出，否则按冲突消解策略从可用规则集中取出一条规则，将该按冲突消解策略从可用规则集中取出一条规则，将该规则的前提中的每个子条件作为新规则的前提中的每个子条件作为新的假设放入假设集，的假设放入假设集，然后转然后转(2)(2)。
3.7.3 产生式系统举例规则规则:R1：：动物有毛动物有毛 → 哺乳类哺乳类 R2：：动物产奶动物产奶 → 哺乳类哺乳类 R3：：动物有羽毛动物有羽毛 → 鸟类鸟类 R4：：动物会飞动物会飞 ∧∧会下蛋会下蛋 → 鸟类鸟类 R5：：哺乳类哺乳类∧∧动物吃肉动物吃肉→ 食肉类食肉类 R6：：动物有犬齿动物有犬齿 ∧∧有爪有爪 ∧∧眼盯前方眼盯前方→肉食类肉食类 R7：：哺乳类哺乳类 ∧∧有蹄有蹄 →蹄类动物蹄类动物 R8：：哺乳类哺乳类 ∧∧反刍反刍 → 蹄类蹄类 R9：：食肉类食肉类 ∧∧ 黄褐色黄褐色 ∧∧ 有斑点有斑点→ 金钱豹金钱豹 R10：：食肉类食肉类 ∧∧ 黄褐色黄褐色 ∧∧ 有黑色条纹有黑色条纹→虎虎 R11：：蹄类蹄类 ∧∧ 长脖长脖 ∧∧ 长腿长腿 ∧∧ 有斑点有斑点→ 长颈鹿长颈鹿 R12：：蹄类蹄类 ∧∧ 有黑色条纹有黑色条纹→ 斑马斑马 R13：：鸟类鸟类 ∧∧长脖长脖 ∧∧ 长腿长腿 ∧∧ 不会飞不会飞 →鸵鸟鸵鸟 R14：：鸟类鸟类 ∧∧会游泳会游泳 ∧∧黑白二色黑白二色 ∧∧ 不会飞不会飞 →企鹅企鹅 R15：：鸟类鸟类 ∧∧善飞善飞 →信天翁信天翁 部分推理网络部分推理网络斑马斑马有蹄类有蹄类有蹄有蹄哺乳类哺乳类有毛有毛产奶产奶反刍反刍有斑点有斑点黑条纹黑条纹长腿长腿长颈鹿长颈鹿r2r1r7r8长脖长脖r12r11 o问题：观察到一种动物是问题：观察到一种动物是{有暗斑，长脖，长腿，有暗斑，长脖，长腿，产奶，有蹄产奶，有蹄}，问是什么动物？，问是什么动物？o推理过程：推理过程：ü初初始始化化总总数数据据库库（（有有暗暗斑斑，，长长脖脖，，长长腿腿，，产产奶奶，，有蹄）有蹄）üR2：：动物产奶动物产奶 → 哺乳类哺乳类 改改变变总总数数据据库库（（有有暗暗斑斑，，长长脖脖，，长长腿腿，，产产奶奶，，有蹄，哺乳类）有蹄，哺乳类）ü R7：：哺乳类哺乳类 ∧∧有蹄有蹄 →蹄类蹄类 改改变变总总数数据据库库（（有有暗暗斑斑，，长长脖脖，，长长腿腿，，产产奶奶，，有蹄，哺乳类，蹄类）有蹄，哺乳类，蹄类）ü R11：：蹄蹄类类 ∧∧ 长长脖脖 ∧∧ 长长腿腿 ∧∧ 有有斑斑点点→ 长长颈颈鹿鹿 3.8 系统组织技术3.8.1 议程表•系统组织技术首先将一个大系统或复杂系统中的知识划分为一组相对独立的模块，然后考虑各子模块间在求解时的合作问题。
v议程表是一个系统能够执行的任务表列与每个任务有关的有两件事，即提出该任务的理由和表示对该任务是有用的证据总权的评价 3.8.2 黑板法•黑板法由一组称为知识资源(KS)的独立模块和一块黑板组成求解系统知识资源含有系统中专门领域的知识，而黑板则是一切KS可以访问的公用数据结构3.8 系统组织技术3.8.3 Δ-极小搜索法 v提供了一种选择最有希望假设的技术 3.9 3.9 不确定性推理不确定性推理•不确定性推理是研究复杂系统不完全性和不不确定性推理是研究复杂系统不完全性和不确定性的有力工具有两种不确定性，即关确定性的有力工具有两种不确定性，即关于证据的不确定性和关于结论的不确定性于证据的不确定性和关于结论的不确定性2 2 2 2 、关于结论的不确定性、关于结论的不确定性、关于结论的不确定性、关于结论的不确定性 l关于结论的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满足时，产生某种结论的不确定程度3 3、多个规则支持同一事实时的不确定性、多个规则支持同一事实时的不确定性 1、、 关于证据的不确定性关于证据的不确定性 3.9.13.9.1不确定性推理的基本概念不确定性推理的基本概念1.1.不确定性推理的定义不确定性推理的定义 不确定性推理，就是从不确定性的初始证据（即已不确定性推理，就是从不确定性的初始证据（即已知事实）出发，通过运用不确定性的知识，最终推出具知事实）出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或近乎合理的结论的有一定程度的不确定性但却是合理或近乎合理的结论的思维过程。
思维过程2.2.造成知识不精确性的主要原因造成知识不精确性的主要原因 （（1 1）很多原因导致同一结果很多原因导致同一结果如医学上导致低烧的如医学上导致低烧的病因就很多，医生只能作出猜测性判断病因就很多，医生只能作出猜测性判断 （（2 2）信息的不完备性信息的不完备性如战场态势估计、股市波动如战场态势估计、股市波动预测等 （（3 3）背景知识的不充分性背景知识的不充分性如人类目前对癌症机理如人类目前对癌症机理还不了解还不了解 （（4 4）信息描述的模糊性信息描述的模糊性如如“今天天气比较好今天天气比较好” （（5）推理规则的模糊性推理规则的模糊性如如“若物价上涨过快，就若物价上涨过快，就要紧缩信贷要紧缩信贷”等模糊规则等模糊规则 （（6）推理能力的局限性推理能力的局限性如天气预报，气象专家只如天气预报，气象专家只能满足于时间不太长、精度尽可能好的预测算法能满足于时间不太长、精度尽可能好的预测算法 （（7）解题方案的不唯一性解题方案的不唯一性无论是政治、经济、文无论是政治、经济、文化，还是军事领域中的很多问题，一般都有多种可选方化，还是军事领域中的很多问题，一般都有多种可选方案，在无法绝对地判断各方案优劣的情况下，只好选择案，在无法绝对地判断各方案优劣的情况下，只好选择主观上认为相对较优的方案，这又是一种不精确推理。
主观上认为相对较优的方案，这又是一种不精确推理3.3.不确定性推理的基本问题不确定性推理的基本问题 除了必须解决经典推理方法中同样存在的推理方向、除了必须解决经典推理方法中同样存在的推理方向、推理方法、控制策略等基本问题外，一般还需要着重解推理方法、控制策略等基本问题外，一般还需要着重解决决不确定性的表示与度量、不确定性匹配、不确定性的不确定性的表示与度量、不确定性匹配、不确定性的传递算法，以及不确定性的合成传递算法，以及不确定性的合成等问题 （（1 1）不确定性的表示与度量）不确定性的表示与度量选择不确定性表示方法时应考虑的因素：选择不确定性表示方法时应考虑的因素：•根据领域问题的特征将其不确定性比较准确地根据领域问题的特征将其不确定性比较准确地描述出来，以满足问题求解的需要；描述出来，以满足问题求解的需要；•便于推理过程中对不确定性的推算便于推理过程中对不确定性的推算u 知识的不确定性表示知识的不确定性表示 静态强度：静态强度：表示相应知识的不确定性程度的某表示相应知识的不确定性程度的某个数值它可以是相应知识在应用中成功的概率，个数值它可以是相应知识在应用中成功的概率，也可以是该条知识的可信程度等，其值范围因其意也可以是该条知识的可信程度等，其值范围因其意义与使用方法的不同而不同。
义与使用方法的不同而不同u 证据的不确定性表示证据的不确定性表示 推理中证据的来源：用户在求解问题时提供的推理中证据的来源：用户在求解问题时提供的初始证据及推理中得到的中间结果初始证据及推理中得到的中间结果 动态强度动态强度：：表示相应证据的不确定性程度的数值表示相应证据的不确定性程度的数值初始证据的动态强度由用户给出；推理过程中所得到初始证据的动态强度由用户给出；推理过程中所得到的中间结论（或中间结果）的动态强度由不确定性传的中间结论（或中间结果）的动态强度由不确定性传递算法计算得到递算法计算得到v 不确定性的度量：不确定性的度量：对于不同的知识及不同的证据，其对于不同的知识及不同的证据，其不确定性的程度一般是不相同的，需要用不同的数据表不确定性的程度一般是不相同的，需要用不同的数据表示其不确定性程度，还需事先规定其取值范围，只有这示其不确定性程度，还需事先规定其取值范围，只有这样每个数据才会有确定的意义例如，在专家系统样每个数据才会有确定的意义例如，在专家系统MYCIN中，中，• 可信度：表示知识及证据的不确定性；可信度：表示知识及证据的不确定性；• 取值范围：取值范围：[-1, 1]；；• 当可信度当可信度>0时，其值越大表示相应的知识或证据越时，其值越大表示相应的知识或证据越接近于接近于“真真”；；• 当可信度当可信度<0时，其值越小表示相应的知识或证据越时，其值越小表示相应的知识或证据越接近于接近于“假假”。
（（2 2）不确定性的匹配）不确定性的匹配对于不确定性推理，由于知识和证据都具有对于不确定性推理，由于知识和证据都具有不确定性，而且知识所要求的不确定性程度与证据不确定性，而且知识所要求的不确定性程度与证据实际具有的不确定性程度不一定相同，因而就出现实际具有的不确定性程度不一定相同，因而就出现了了“怎样才算匹配成功？怎样才算匹配成功？”的问题 常用的解决办法：常用的解决办法：•设计一个算法用以计算匹配双方的相似程度设计一个算法用以计算匹配双方的相似程度（简称相似度）；（简称相似度）；•指定一个相似的指定一个相似的“限定限定”（即阈值），用以衡（即阈值），用以衡量匹配双方的相似度是否落在指定的限度内量匹配双方的相似度是否落在指定的限度内若相似度在阈值范围内，则表明是匹配的，相若相似度在阈值范围内，则表明是匹配的，相应知识可被应用；否则，反之应知识可被应用；否则，反之 （（3 3）组合证据不确定性的算法）组合证据不确定性的算法 在基于产生式规则的系统中，根据知识的前提条在基于产生式规则的系统中，根据知识的前提条件是简单条件还是复合条件，可分为：件是简单条件还是复合条件，可分为： 单一证据单一证据：是指知识的前提条件仅为一个简单条：是指知识的前提条件仅为一个简单条件的情况；件的情况； 复合证据复合证据：是指知识的前提条件用：是指知识的前提条件用ANDAND（（与）或与）或OROR（（或）把多个简单条件连接起来构成复合条件的情或）把多个简单条件连接起来构成复合条件的情况，即一个复合条件对应于一组证据。
况，即一个复合条件对应于一组证据 在不确定性推理中，由于结论的不确定性通常是在不确定性推理中，由于结论的不确定性通常是通过对证据及知识的不确定性进行某种运算得到的，通过对证据及知识的不确定性进行某种运算得到的，因而需要有合适的算法来计算组合证据的不确定性因而需要有合适的算法来计算组合证据的不确定性主要方法：最大最小方法、概率方法、有界方法等主要方法：最大最小方法、概率方法、有界方法等 （（4 4）不确定性的传递算法）不确定性的传递算法 包括两个子问题：包括两个子问题： （（1 1）在每一步推理中，如何把证据及知识的不确）在每一步推理中，如何把证据及知识的不确定性传递给结论；一般做法：按照某种算法由证据和定性传递给结论；一般做法：按照某种算法由证据和知识的不确定性计算出结论的不确定性知识的不确定性计算出结论的不确定性 （（2 2）在多步推理中，如何把初始证据的不确定性）在多步推理中，如何把初始证据的不确定性传递给最终结论一般做法：把当前推出的结论及其传递给最终结论一般做法：把当前推出的结论及其不确定性作为证据放入综合数据库，供以后推理使用。
不确定性作为证据放入综合数据库，供以后推理使用 （（5 5）结论不确定性的合成）结论不确定性的合成 用不同知识进行推理得到了相同结论，但不确定用不同知识进行推理得到了相同结论，但不确定性的程度却不相同，此时，需要用合适的算法对它们性的程度却不相同，此时，需要用合适的算法对它们进行合成而且在不同的不确定性推理方法中，所采进行合成而且在不同的不确定性推理方法中，所采用的合成方法也就各不相同用的合成方法也就各不相同 4 4、不确定性推理方法的分类、不确定性推理方法的分类 常常用用的的方方法法有有数数值值法法和和非非数数值值法法数数值值法法以以概概率率方方法法、、确确定定因因子子法法、、D—S证证据据理理论论和和可可能能性性理理论论为为代代表表；；非非数数值值法法则则以以批批注注理理论论和和非非单单调调逻逻辑辑为为代代表表数数值值法法是是对对不不确确定定性性的的一一种种定定量量表表示示和和处处理理方方法法，，便便于于计计算算、、比比较较，，非非数数值值法法是是指指除除数数值值方方法法外外的的其其它它各各种种处处理理不不确确定定性性的的方方法法，，便便于定性分析于定性分析。
3.9.2 3.9.2 不确定性推理的概率论基础不确定性推理的概率论基础1.1.样本空间与随机事件样本空间与随机事件 （（1 1）样本空间）样本空间 在概率论中，把试验中每一个可能出现的结果称为试在概率论中，把试验中每一个可能出现的结果称为试验的一个样本点，由全体样本点构成的集合称为样本空验的一个样本点，由全体样本点构成的集合称为样本空间用D D表示样本空间，表示样本空间，d d表示样本点表示样本点 如：如： D={dD={d1 1，，d d2 2} } （（2 2））随机事件随机事件 在概率论中，把由样本点构成的集合称为随机事件在概率论中，把由样本点构成的集合称为随机事件 对两个事件对两个事件A A与与B B，，如果事件表达的是如果事件表达的是“事件事件A A与事件与事件B B至少有一个发生至少有一个发生”，称该事件为，称该事件为A A与与B B的并事件，记：的并事件，记：A AUB B 如果事件表达的是如果事件表达的是“事件事件A A与事件与事件B B同时发生同时发生”，称该，称该事件为事件为A A与与B B的交事件，记：的交事件，记：A A∩ B B 如果事件如果事件A A与与B B之间满足之间满足“A A∩ B= B= Φ， A AUB=DB=D”，，则称则称A A与与B B为互逆事件。
为互逆事件 2.2.事件的概率事件的概率 （（1 1）统计概率）统计概率 在同一组条件下进行大量重复试验时，如果事件在同一组条件下进行大量重复试验时，如果事件A A出现出现的频率的频率f fn n（（A A））总是在区间总是在区间[0[0，，1]1]上的一个确定常数上的一个确定常数p p附附近摆动，且稳定于近摆动，且稳定于p p，，则称则称p p为事件为事件A A的统计概率的统计概率 P P（（A A））=p=p 其中：其中： f fn n（（A A））=m/n =m/n n n：：试验总次数试验总次数 m m：：试验中试验中A A发生次数发生次数 统计概率的性质：统计概率的性质：Ø 对任一事件对任一事件A A，，有有0≤0≤P P（（A A））≤1≤1Ø必然事件必然事件D D的概率的概率P(D)=1P(D)=1，，不可能事件不可能事件Φ的概率的概率 P( P(Φ)=0)=0Ø对任一事件对任一事件A A，，有有 P( P( A)=1- P(A) A)=1- P(A) Ø设事件设事件A A1 1，，A A2 2，，…A Ak k（（k k ≤≤n n））是两两互不相容的事件，是两两互不相容的事件， A Ai i∩Aj= = Φ（（i ≠ j），），则则 kP（U Ai ）= P(AP(A1 1)+ P(A)+ P(A2 2)+)+…+ P(A+ P(Ak k) ) i=1Ø设设A、、B是两个事件，则是两个事件，则 P(AP(AUB)=P(A)+P(B)-P(AB)=P(A)+P(B)-P(A∩ B)B)(2)(2)条件概率条件概率 设设A A与与B B是某个随机试验中的两个事件，如果在事件是某个随机试验中的两个事件，如果在事件B B发生的条件下考虑事件发生的条件下考虑事件A A发生的概率，就称它为事件发生的概率，就称它为事件A A的的条件概率，记为条件概率，记为P(A|B)P(A|B)。
定义：设定义：设A、、B是两个事件，是两个事件，P(B)>0P(B)>0，，称称为事件为事件B B已发生条件已发生条件下，事件下，事件A A发生的条件概率发生的条件概率 3.3.全概率公式与全概率公式与BayesBayes公式公式（（1 1）全概率公式）全概率公式设事件设事件A A1 1，，A A2 2，，……，，A An n满足：满足：(1)(1)任意两个事件都互不相容，即当任意两个事件都互不相容，即当i≠ji≠j时，有时，有A Ai i∩A∩Aj j=Φ(i=1=Φ(i=1，，2 2，，……，，n n；；j=1j=1，，2 2，，…… ，，n)n)；；(2)P(A(2)P(Ai i)>0 (i=1)>0 (i=1，，2 2，，……，，n)n)；； n n(3)D=U A(3)D=U Ai i i=1i=1则对任何事件则对任何事件B B有：有： n n P(B)=∑(P(A P(B)=∑(P(Ai i)×P(B|A)×P(B|Ai i)) )) i=1i=1 l例：例：A A1 1={={取红桃牌取红桃牌} } A A2 2={={取方块牌取方块牌} } A A3 3={={取黑桃牌取黑桃牌} } A A4 4={={取梅花牌取梅花牌} } A A5 5={={取王牌取王牌} } B={B={取花脸牌取花脸牌} } 解解: : P(B)=P(AP(B)=P(A1 1)×P(B|A)×P(B|A1 1)+P(A)+P(A2 2)×P(B|A)×P(B|A2 2) ) +P(A +P(A3 3)×P(B|A)×P(B|A3 3)+P(A)+P(A4 4)×P(B|A)×P(B|A4 4) ) +P(A +P(A5 5)×P(B|A)×P(B|A5 5) ) =(13/54×3/13)×4+2/54×0 =(13/54×3/13)×4+2/54×0 =12/54 =12/54 （（2 2））BayesBayes公式公式设事件设事件A A1 1，，A A2 2，，……，，A An n两两互不相容，且它们构成全两两互不相容，且它们构成全部样本空间，则对任何事件部样本空间，则对任何事件B B有：有：称称这这个个公公式式为为BayesBayes公公式式，，同同时时称称P(AP(Ai i) )，，P(B|AP(B|Ai i) )的的值值为为先先验验概概率率；；P(AP(Ai i|B)|B)的的值值为为后后验验概概率率。
BayesBayes公公式式就就是从先验概率推导出后验概率的公式是从先验概率推导出后验概率的公式 【注意】：【注意】：贝叶斯公式与全概率公式的区别贝叶斯公式与全概率公式的区别 （（1）全概率公式是由原因到结果的计算公式；）全概率公式是由原因到结果的计算公式； （（2））贝贝叶叶斯斯公公式式是是在在已已知知某某种种结结果果发发生生的的情情况况下下，，寻寻求求使使这这个个结结果果发发生生的的原原因因贝贝叶叶斯斯公公式式在在实实际问题中有着十分重要的应用际问题中有着十分重要的应用 3.9.3 3.9.3 确定性理论确定性理论1 1、可信度的概念、可信度的概念 可信度是指人们根据以往经验对某个事物或现象为真的可信度是指人们根据以往经验对某个事物或现象为真的程度的一个判断，即人们对某个事物或现象为真的相信程程度的一个判断，即人们对某个事物或现象为真的相信程度在确定性理论中不确定性是用可信度表示的在确定性理论中不确定性是用可信度表示的2 2、、C-FC-F模型模型（（1 1）知识的不确定性）知识的不确定性在在C-FC-F模型中，知识是用产生式规则表示的模型中，知识是用产生式规则表示的。
IF E THEN H IF E THEN H （（CF(H,E))CF(H,E))o E E是知识的前提条件（证据），可以是一个简单是知识的前提条件（证据），可以是一个简单条件，也可以是由合取和析取构成的符合条件条件，也可以是由合取和析取构成的符合条件oH H是知识的结论，可以是一个或多个结论是知识的结论，可以是一个或多个结论 oCF(H,E)CF(H,E)是知识的可信度是知识的可信度CF(H,E)CF(H,E)的具体值由领域专的具体值由领域专家给出，其取值范围为家给出，其取值范围为[ [一一1 1，，1]1]CF(H,E)CF(H,E)＞＞0 0表示证表示证据存在，增加结论为真的确定性程度，据存在，增加结论为真的确定性程度，CF(H,E)CF(H,E)越大越大结论越真，结论越真，CF(H,E)CF(H,E)＝＝1 1表示证据存在结论为真相反，表示证据存在结论为真相反，CF(H,E)CF(H,E)＜＜0 0表示证据存在，增加结论为假的确定性程表示证据存在，增加结论为假的确定性程度，度，CF(H,E)CF(H,E)越小结论越假，越小结论越假，CF(H,E)CF(H,E)＝＝一一1 1表示证据表示证据存在结论为假。
存在结论为假CF(H,E)CF(H,E)＝＝0 0时，则表示证据与结论无时，则表示证据与结论无关例如：例如： IF IF 发烧发烧 AND AND 流鼻涕流鼻涕 THEN THEN 感冒感冒 (0.8) (0.8) （（2 2）可信度的定义）可信度的定义 CF(H,E)=MB(H,E)-MD(H,E) CF(H,E)=MB(H,E)-MD(H,E) MB(H,E): MB(H,E):信任增长度，表示证据信任增长度，表示证据E E的出现，使结论的出现，使结论H H为为真的信任增长度真的信任增长度 若若P P（（H H））=1=1 否则否则 MD(H,E) MD(H,E)：：不信任增长度，表示证据不信任增长度，表示证据E E的出现，对结论的出现，对结论H H的不信任增长度的不信任增长度。
若若P P（（H H））=0=0 否则否则 P P（（H H））为为H H的先验概率，的先验概率，P P（（H|EH|E））为为H H的条件概率的条件概率 MB MB（（H H，，E E））>0>0表示因证据表示因证据E E的出现增加对结论的出现增加对结论H H为真的信为真的信任增长度，即任增长度，即P P（（H|EH|E））>P>P（（H H）） MD MD（（H H，，E E））>0>0表示因证据表示因证据E E的出现增加对结论的出现增加对结论H H为真的不为真的不信任增长度，即信任增长度，即P P（（H|EH|E））
原始证据的确定性因子由用户主观地给出，非示的原始证据的确定性因子由用户主观地给出，非原始证据的确定性因子由不确定性推理获得原始证据的确定性因子由不确定性推理获得–值域值域l当证据当证据E E以某种程度为真时，有以某种程度为真时，有0 0＜＜CF(E)≤lCF(E)≤ll当证据当证据E E以某种程度为假时，有以某种程度为假时，有-1≤-1≤CF(E)CF(E)＜＜0 0l当证据当证据E E一无所知时，有一无所知时，有CF(E)CF(E)＝＝0 0–典型值典型值l 当证据当证据E E肯定为真时，有肯定为真时，有CF(E)CF(E)＝＝l ll 当证据当证据E E肯定为假时，有肯定为假时，有CF(E)CF(E)＝＝-1-1l 当证据当证据E E一无所知时，有一无所知时，有CF(E)CF(E)＝＝0 0 （（4 4）不确定性推理算法）不确定性推理算法vE E肯定存在肯定存在 在在证证据据E E肯肯定定存存在在时时有有CF(E)CF(E)＝＝1 1，，那那么么结结论论H H的确定性因子为规则的确定性因子，即的确定性因子为规则的确定性因子，即 CF(H)CF(H)＝＝CF(HCF(H，，E)E)vE E不是肯定存在不是肯定存在 在在客客观观的的现现实实世世界界中中，，对对证证据据的的观观察察往往往往也也是是不不确确定定的的。
除除此此之之外外，，证证据据E E可可能能还还是是另另一一条条规规则则的的结结论论，，这这时时也也常常常常是是不不确确定定的的在在这这种种情情况况下下，，结结论论H H的的确确定定性性因因子子CF(H)CF(H)不不仅仅取取决决于于规规则则的的确确定定性性因因子子CF(HCF(H，，E)E)，，而而且且还还取取决决于于证据证据E E的确定性因子的确定性因子CF(E)CF(E)计算公式为计算公式为 CF(H)CF(H)＝＝CF(HCF(H，，E)×max{0E)×max{0，，CF(E)}CF(E)} v证据是多个条件的逻辑组合证据是多个条件的逻辑组合•证据是合取连接证据是合取连接 即即 E= EE= E1 1 AND E AND E2 2 AND AND．．．．．．AND EAND En n 则则 CF(E) CF(E)＝＝CF(ECF(E1 1 AND E AND E2 2 AND...AND E AND...AND En n) ) ＝＝min{CF(Emin{CF(E1 1) )，，CF(ECF(E2 2) )，，... ... ，，CF(ECF(En n)})}•证据是析取连接证据是析取连接 这时，这时，E E＝＝E E1 1 OR E OR E2 2 OR ... OR E OR ... OR En n，，有有 CF(E)CF(E)＝＝CF(ECF(E1 1 OR E OR E2 2 0R ... OR E 0R ... OR En n) ) ＝＝max{CF(Emax{CF(E1 1) )，，CF(ECF(E2 2) )，，... ... ，，CF(ECF(En n)})} （（5 5）结论不确定性的合成）结论不确定性的合成 当多条知识推出相同结论，且这些知识的前提当多条知识推出相同结论，且这些知识的前提相互独立，结论的可信度又不相同，则可用不确相互独立，结论的可信度又不相同，则可用不确定性的合成算法求出该结论的综合可信度。
定性的合成算法求出该结论的综合可信度 若有两条规则分别是若有两条规则分别是 IF EIF E1 1 THEN H (CF(H THEN H (CF(H，，E E1 1)))) IF E IF E2 2 THEN H (CF(H THEN H (CF(H，，E E2 2)))) 那末首先分别计算出那末首先分别计算出CF1(H)CF1(H)和和CF2(H)CF2(H)：： CF1(H) CF1(H)＝＝CF(HCF(H，，E E1 1) × max{0) × max{0，，CF(ECF(E1 1)})} CF2(H) CF2(H)＝＝CF(HCF(H，，E E2 2) × max{0) × max{0，，CF(ECF(E2 2)})} 然后用公式然后用公式 CF CF1 1(H)(H)十十CFCF2 2(H)-CF(H)-CF1 1(H)×CF(H)×CF2 2(H) (H) 若若CFCF1 1(H)≥0 (H)≥0 且且CFCF2 2(H)≥0(H)≥0CFCF1212(H)(H)＝＝ CF CF1 1(H)(H)十十 CFCF2 2(H)(H)十十CFCF1 1(H)×CF(H)×CF2 2(H)(H)；； 若若CFCF1 1(H)(H)＜＜0 0且且CFCF2 2(H)(H)＜＜0 0 (CF (CF1 1(H)(H)十十CFCF2 2(H))/(1-min{|CF(H))/(1-min{|CF1 1(H)|,|CF(H)|,|CF2 2(H)|})(H)|})；； 其他其他计算出由计算出由E E1 1和和E E2 2组合而导出的确定性因子组合而导出的确定性因子CFCF1212(H)(H)。
–举例举例有如下的推理规则：有如下的推理规则： Rule l：：IF E1 THEN H (0.9) Rule 2：：IF E2 THEN H (0.7) Rule 3：：IF E3 THEN H (-0.8) Rule 4：：IF E4 AND E5 THEN E1 (0.7)Rule 5：：IF E6 AND (E7 0R E8) THEN E2 (1.0)HE1E2E6E4E5ORAND0.9-0.80.71.0R1R3R4R5E3E7E80.7R2AND 在图中，在图中，E3、、E4、、E5、、E6、、E7和和E8为原始证据，其确为原始证据，其确定性因子由用户给出，假定它们的值为：定性因子由用户给出，假定它们的值为：CF(E3)＝＝0.3，， CF(E4)＝＝0.9，， CF(E5)＝＝0.6，， CF(E6)＝＝0.7，， CF(E7)＝＝-0.3，， CF(E8)＝＝0.8求求CF(H)=？？解：先求出解：先求出CF(E1)、、CF(E2)和和CF(E3) CF(E1)＝＝0．．7×max{0，，CF(E4 AND E5)} ＝＝0．．7×max{0，，min{CF(E4)，，CF(E5)}} ＝＝0．．7×max{0，，min{0．．9，，0．．6}} ＝＝0．．7×max{0，，0．．6} ＝＝o．．7×0．．6 ＝＝0.42 CF(E2)＝＝1×max{0，，CF(E6 AND (E7 OR E8))} ＝＝1×max(0，，min{CF(E6)，，max{CF(E7)，，CF(E8)}}} ＝＝1×max{0，，min{CF(E6)，，max{-0.3，，0.8}}} ＝＝1×max{0，，min{0.7，，0.8}} ＝＝1×max{0，，0.7} ＝＝1×0.7 ＝＝0.7CF(E3)＝＝0.3CF1(H)＝＝0．．9×max{0，，CF(E1)} ＝＝0．．9×max{0，，0．．42} ＝＝0．．9×0．．42 ＝＝0．．38 CF2(H)＝＝0．．7×max{0，，CF(E2)} ＝＝0．．7×max{0，，0．．7} ＝＝0．．7×0．．7 ＝＝0．．49CF3(H)＝＝ －－ 0．．8×CF(E3) ＝＝ －－ 0．．8×0．．3 ＝＝ －－ 0．．24 ∵∵CF1(H)>0 且且CF2(H)>0 CF12(H)＝＝CF1(H)十十CF2(H) －－ CF1(H)×CF2(H) ＝＝0．．38十十0．．49－－0．．38×0. 49＝＝0．．6838∵∵CF12(H)>0 且且CF3(H)<0 CF(H)＝＝CF123(H) ＝＝(CF12(H)十十CF3(H))/(1－－min{|CF12(H)|, |CF3(H)|}) ＝＝(0．．6838－－0．．24)/(1 －－ 0. 24) ＝＝0．．5839 –CFCF模型的优点是：模型的优点是：•简简单单、、直直观观。
主主要要表表现现在在组组合合假假设设和和证证据据的的不不确确定定性性的的计计算算十十分分简简单单，，而而且且不不需需要要把把信信任任和和不不信信任任的的判判断断知知识识表表示示成成概概率率的的形形式式把把某某个个值值指指派派给给一一个个假假设设的的确确定定性性因因子子要要比比把把一一个个概概率直接指派给一个假设要容易得多率直接指派给一个假设要容易得多•计计算算仅仅有有线线性性的的信信息息和和时时间间的的复复杂杂度度，，而而且且推推理的近似效果也比较理想理的近似效果也比较理想•推理的结果与证据提供的顺序无关推理的结果与证据提供的顺序无关–推理过程中的阈值推理过程中的阈值•推理所得到的结论中有的可信度很低，可以设推理所得到的结论中有的可信度很低，可以设定一个阈值，在推理过程中去掉那些可信度低定一个阈值，在推理过程中去掉那些可信度低于阈值的结论于阈值的结论•一般阈值定为一般阈值定为0.20.2，，当当CFCF＜＜0.20.2时，置时，置CFCF＝＝0 0，，当当CFCF≥0.2≥0.2时，时，CFCF有意义 3.3.带加权因子的可信度推理带加权因子的可信度推理（（1 1））知识不确定性的表示知识不确定性的表示 IF EIF E1 1(ω(ω1 1) AND E) AND E2 2 (ω(ω2 2) AND) AND．．．．．．AND EAND En n (ω(ωn n) ) THEN H CF(H,E)THEN H CF(H,E) ω ωi i为加权因子，取值范围为加权因子，取值范围[0[0，，1]1]，由领域专家给出。
由领域专家给出 加权因子取值原则：条件的独立性越强，对结论的重要加权因子取值原则：条件的独立性越强，对结论的重要程度越高，则该条件的加权因子越大且满足归一条件程度越高，则该条件的加权因子越大且满足归一条件（（2 2））组合证据不确定性的计算组合证据不确定性的计算 对于对于 E= EE= E1 1(ω(ω1 1) AND E) AND E2 2 (ω(ω2 2) AND) AND．．．．．．AND EAND En n (ω(ωn n) ) 可信度为：可信度为： 如果不满足归一条件，则可信度为：如果不满足归一条件，则可信度为：（（3 3））不确定性的更新不确定性的更新 CF(H)=CF(H,E)CF(H)=CF(H,E)××CF(E)CF(E) “××”可以是乘运算，也可以是其他合适的运算可以是乘运算，也可以是其他合适的运算 例：设有如下知识：例：设有如下知识： r1r1：：IF EIF E1 1(0.6) AND E(0.6) AND E2 2 (0.4) THEN E(0.4) THEN E5 5 (0.8) (0.8) r2 r2：：IF EIF E3 3(0.5)AND E(0.5)AND E4 4(0.3)AND E(0.3)AND E5 5(0.2) THEN H(0.9)(0.2) THEN H(0.9)已知：已知：CF(ECF(E1 1)=0.9,CF(E)=0.9,CF(E2 2)=0.8,CF(E)=0.8,CF(E3 3)=0.7,CF(E)=0.7,CF(E4 4)=0.6)=0.6求：求： CF(H)CF(H)解：解：CF(ECF(E1 1(0.6)AND E(0.6)AND E2 2(0.4))= (0.4))= ωω1 1×CF(×CF(E E1 1)+ )+ ωω2 2×CF(×CF(E E2 2) ) =0.6 =0.6×0.9+0.4 ×0.8×0.9+0.4 ×0.8 =0.86 =0.86 CF( CF(E E5 5)=0.8)=0.8×0.86=0.69×0.86=0.69 CF(E CF(E3 3(0.5)AND E(0.5)AND E4 4(0.3)AND E(0.3)AND E5 5(0.2))(0.2)) =0.5 =0.5×0.7+0.3 ×0.6+ 0.2 ×0.69×0.7+0.3 ×0.6+ 0.2 ×0.69 =0.67 =0.67 CF( CF(H)=0.9H)=0.9×0.67=0.70×0.67=0.70 3.9.4 3.9.4 主观主观BayesBayes方法方法1.1.知识不确定性的表示知识不确定性的表示 v 知识表示知识表示 IF E THEN H IF E THEN H （（LSLS，，LNLN））v几率函数几率函数O(x)O(x) –几率函数定义为几率函数定义为O(x)O(x)＝＝P(x)/(1-P(x))P(x)/(1-P(x))。
–它表示它表示x x出现的概率与不出现概率之比，随着出现的概率与不出现概率之比，随着P(x)P(x)的增大，的增大，O(x)O(x)也增大 当当P(x)P(x)＝＝0 0时，有时，有O(x)O(x)＝＝0 0 当当P(x)P(x)＝＝1 1时，有时，有O(x)O(x)＝＝∞∞这样，取值为这样，取值为[0[0，，1]1]的的P(x)P(x)被放大为取值为被放大为取值为[0, ∞][0, ∞]的的O(x)O(x)v充分性度量充分性度量LSLS：：LSLS＝＝P(E|H)/P(E|P(E|H)/P(E| H)H)v必要性度量必要性度量LNLN：：LNLN＝＝P(P( E|H)/P(E|H)/P( E|E| H)H)–LSLS、、LNLN的取值范围的取值范围[0, ∞][0, ∞] v规则不确定性描述规则不确定性描述ü根据根据BayesBayes公式有公式有 P(H|E)P(H|E)＝＝P(E|H)P(H)/P(E) (1)P(E|H)P(H)/P(E) (1) P( P( H|E)H|E)＝＝P(E|P(E| H)P(H)P( H)|P(E) (2)H)|P(E) (2)将上述两式相除，得将上述两式相除，得P(H|E)/P(P(H|E)/P( H/E)H/E)=[P(E|H)/P(E|=[P(E|H)/P(E| H)]×[P(H)/P(H)]×[P(H)/P( H)]H)] 再利用几率函数和再利用几率函数和LSLS，，上式可表示为上式可表示为 O(H|E)O(H|E)＝＝LS×O(H)LS×O(H) 当当LS>1LS>1时时，，O(H|E)>O(H)O(H|E)>O(H)，，说说明明E E支支持持H H，，LSLS越越大大，，O(H|E)O(H|E)就就越越大大，，即即P(H|E)P(H|E)越越大大，，说说明明E E对对H H的的支支持持越越强强。
当当LS→∞LS→∞时时，，O(H|E)→∞O(H|E)→∞，，从从而而有有P(H|E)→1P(H|E)→1，，说说明明E E的存在导致的存在导致H H为真 当当LS=1LS=1时，时，O(H|E)O(H|E)＝＝O(H)O(H)，，说明说明E E对对H H没有影响没有影响 当当LS<1LS<1时，时，O(H|E)
当当 LN→∞LN→∞时时 ，， O(H|O(H| E)→∞E)→∞，， 从从 而而 有有P(H|P(H| E)→1E)→1，，说明说明 E E的存在导致的存在导致H H为真 当当LN=1LN=1时，时，O(H|O(H| E)E)＝＝O(H)O(H)，，说明说明 E E对对H H没有影响没有影响 当当LN<1LN<1时，时，O(H|O(H| E)
给出2.2.证据不确定性的描述证据不确定性的描述 在主观在主观BayesBayes方法中，证据方法中，证据E E的不确定性采用概率的不确定性采用概率P P的的等价形式等价形式——几率来描述几率来描述 P(E) 0 P(E) 0 当当E E为假时为假时 O(E)= O(E)= ———— = ∞ = ∞ 当当E E为真时为真时 1-P(E) 1-P(E) （（0 0，，+ ∞+ ∞）） 当当E E非真也非假时非真也非假时3.3.组合证据不确定性的计算组合证据不确定性的计算证据合取情况：证据合取情况：E= EE= E1 1 AND E AND E2 2 AND AND．．．．．．AND EAND En n设设在在观观察察S S之之下下，，证证据据E E1 1，，E E2 2，，…，，E En n的的概概率率为为P(EP(E1 1|S)|S)、、P(EP(E2 2|S)|S)、、…、、P(EP(En n|S)|S)，，那么有那么有 P(E|S)P(E|S)＝＝Min{P(EMin{P(E1 1|S)|S)，，P(EP(E2 2|S)|S)，，......，，P(EP(En n|S)}|S)} 4. 4. 不确定性的更新不确定性的更新 根据证据根据证据E E的概率的概率P P（（E E））及及LSLS，，LNLN的值，把的值，把H H的先的先验概率验概率P P（（H H））或先验几率或先验几率O O（（H H））更新为后验概率或后更新为后验概率或后验几率验几率（（1 1）当证据）当证据E E肯定为真时肯定为真时( (P(E)P(E)＝＝1)1)可直接使用公式可直接使用公式 O(H|E)O(H|E)＝＝LSLS××O(H)O(H) 以求得使用规则以求得使用规则E→HE→H后，后，O(H)O(H)的更新值的更新值O(H|E)O(H|E)。
–证据析取情况证据析取情况 E= EE= E1 1 OR E OR E2 2 0R 0R…OR EOR En n设在观察设在观察S S之下，证据之下，证据E E1 1，，E E2 2，，......，，E En n的概率为的概率为P P(E(E1 1|S)|S)、、P(EP(E2 2|S)|S)、、......、、P(EP(En n|S)|S)，，那么有那么有P(E|S)P(E|S)＝＝max{P(Emax{P(E1 1|S)|S)，，P(EP(E2 2|S)|S)，，…，，P(EP(En n| |S)} 若需要以概率的形式表示，则对上式反复应用若需要以概率的形式表示，则对上式反复应用公式公式 P(E)= O(E)/(1+O(E))P(E)= O(E)/(1+O(E))计算出计算出P(H|E)=(LS×P(H))/((LS-1)×P(H)+1)P(H|E)=(LS×P(H))/((LS-1)×P(H)+1)（（2 2）当证据）当证据E E肯定为假时肯定为假时( (P(P( E)E)＝＝1)1)可直接使用公式可直接使用公式 O(H|O(H| E)E)＝＝LNLN××O(H)O(H) 以求得使用规则以求得使用规则E→HE→H后，后，O(H)O(H)的更新值的更新值O(H|O(H| E)E)。
若以概率的形式表示若以概率的形式表示P(H|P(H| E)=(LNE)=(LN××P(H))/((LN-1)×P(H)+1)P(H))/((LN-1)×P(H)+1) (3)(3)当证据当证据E E不确定时不确定时( (P(E)≠1)P(E)≠1) 设设 S S是与是与 E E有关的所有观察，对规则有关的所有观察，对规则 E→HE→H来说有公式来说有公式 P(H|S)P(H|S)＝＝P(H|E)×P(E|S)P(H|E)×P(E|S)十十P(H|P(H| E)×P(E)×P( E|S)E|S)•当当P(E|S)P(E|S)＝＝1 1时，时，P(P( E|S)=0,E|S)=0,证据证据E E必然出现，有必然出现，有 P(H|S)P(H|S)＝＝P(H|E)P(H|E)＝＝LS×P(H)/((LS-1)×P(H)+1)LS×P(H)/((LS-1)×P(H)+1)•当当P(E|S)＝＝0时，时，P(P( E|S)=1,E|S)=1,证据证据E必然不出现必然不出现有有 P(H|S)=P(H| E)=LN××P(H)/((LN-1) ××P(H)+1)•当当P(E|S)＝＝P(E)时，即观察时，即观察S对对E无影响无影响有有 P(H|S)=P(H|E) ××P(E)+P(H| E) ××P( E) =P(H)•当当P(E|S)P(E|S)为其他值时为其他值时 可以从可以从P(E|S)P(E|S)分别为分别为0 0，，P(E)P(E)和和1 1这这3 3个特殊点采用分个特殊点采用分段线性插值的方法，确定与其相应的段线性插值的方法，确定与其相应的P(H|S)P(H|S)值。
值 P(H| E)+(P(H)-P(H| E))/P(E)XP(E|S)P(H|S)= 若0≤P(E|S)＜P(E) P(H)+(P(H|E)-P(H))/(1-P(E))X(P(E|S)-P(E)) 若P(E)≤P(E|S)≤1称为称为EH公式公式P(H|S)P(H|E)P(H)P(H| E)P(E)P(E|S)01 如如证证据据的的非非确确定定性性用用可可信信度度C(E|S)C(E|S)描描述述，，则则把把P(E|S)P(E|S)转换为转换为C(E|S),C(E|S),可得公式：可得公式： P(H| E)+[P(H)-P(H| E)]×[1/5XC(E|S)+1]P(H/S)= 若C(E|S) ≤0 P(H)+[P(H/E)-P(H)] X1/5X C(E/S) 若C(E|S)>0称为称为CP公式公式5. 5. 结论不确定性的合成结论不确定性的合成设一组相互独立的证据设一组相互独立的证据E E1 1、、E E2 2…E En n的观察分别为的观察分别为S S1 1、、S S2 2…S Sn n，，且有规则且有规则E E1 1→H→H，，E E2 2→H→H，，…，，E En n→H→H。
假定由这假定由这些规则得到的结论些规则得到的结论H H的后验几率分别是的后验几率分别是O(H|SO(H|S1 1) )、、O(H|SO(H|S2 2) )…O(H|SO(H|Sn n) )，，那么由这些独立证据的组合相应得那么由这些独立证据的组合相应得到的结论到的结论H H的后验几率为的后验几率为O(H|SO(H|S1 1,S,S2 2…,S,Sn n)= )= O(H|SO(H|S1 1) )X O(H|S O(H|S2 2) )X… O(H|S O(H|Sn n) ) X O（（H）） O(H) O(H) O(H) O(H) O(H) O(H) –例例 PROSPECTOR专专家家系系统统中中的的部部分分推推理理网网络络如如图图所所示示图图中中各各结结点点的的先先验验概概率率标标在在结结点点的的右右上上方方，，规规则则的的LS和和LN值值标标在在该该规规则则连连线线的的一一侧侧用用户户给给出出的的各各原原始始证证据据在在各各自自的的观察之下概率为：观察之下概率为： P(E1|S1)＝＝0.7，， P(E2|S2)＝＝0.6，， P(E3|S3)＝＝0.02。
现现要要求求计计算算结结论论H2的的后后验验概概率率P(H2|S1∧ ∧S2∧ ∧S3)H2H1E3E1E265,0.01300,0.00012,0.000001100,0.0000010.010.030.10.40.2 即有如下规则：即有如下规则：R1: IF ER1: IF E1 1 THEN H THEN H1 1 (2, 0.000001) (2, 0.000001) R2: IF ER2: IF E2 2 THEN H THEN H1 1 (100, 0.000001) (100, 0.000001) R3: IF HR3: IF H1 1 THEN H THEN H2 2 (65, 0.01) (65, 0.01) R4: IF ER4: IF E3 3 THEN H THEN H2 2 (300, 0.0001) (300, 0.0001) 和专家给出的先验概率：和专家给出的先验概率：P(EP(E1 1)=0.2, P(E)=0.2, P(E2 2)=0.4, P(E)=0.4, P(E3 3)=0.03,)=0.03,P(HP(H1 1)=0.1, P(H)=0.1, P(H2 2)=0.01)=0.01用户给出的在观察用户给出的在观察S S下证据下证据E E的概率：的概率：P(EP(E1 1|S|S1 1)=0.7, P(E)=0.7, P(E2 2|S|S2 2)=0.6, P(E)=0.6, P(E3 3|S|S3 3)=0.02)=0.02 解解 1．根据．根据P(E1|Sl)计算计算P(H1|Sl) 由于由于P(E1|S1)＝＝0.7＞＞0.2＝＝P(E1)，，所以所以P(H1|E1)＝＝ LS × P(H1) (LS一一1) × P(H1)十十1 ＝＝ 2×0.1 ＝＝0.1818 (2—1)×0.1十十1 P(H1|S1)＝＝P(H1)十十P(H1|E1)-P(H1) 1-P(E1) ×[P(E1|S1)-P(E1)] ＝＝0.1十十 0.1818-0.1 ×(0.7—0.2) 1-0.2 ＝＝0.151125 P(H|S)P(H|E)P(H)P(H| E)P(E)P(E|S)01P(E1|S1)P(H1|S1) 2．根据．根据P(E2|S2)计算计算P(H1|S2)。
由于由于P(E2|S2)＝＝0.8＞＞0.4＝＝P(E2)，，所以所以 P(H1|E2)＝＝ LS × P(H2) (LS-1) × P(H2)+1 ＝＝ 100×0.1 ＝＝ 0.9174311 99×0.1+1 P(H1|S2)＝＝P(H1)+P(H1|E2)-P(H1) 1-P(E2) ×[P(E2|S2)-P(E2)] ＝＝ 0.1 + 0.9174311-0.1 × (0.6-0.4) 1-0.4 ＝＝ 0.372477 3.根据独立证据根据独立证据E1和和E2计算计算P(H1|S1∧∧S2) 先计算后验几率先计算后验几率O(H1|S1∧∧S2)，，由于由于 O(H1) ＝＝ P(H1) ＝＝ 0.1 ＝＝ 0.1111111 1-P(H1) 1-0.1 O(H1|S1)＝＿＝＿P(H1|S1) ＝＿＝＿0.151125 1-P(H1|S1) 1-0.151125 ＝ ＝ 0.1780297 O(H1|S2)＝＿＝＿P(H1 |S2) ＝＿＝＿0.372477 1-P(H1|S2) 1-0.372477 ＝＝ 0.593567 由此得：由此得： O(H1|S1∧∧S2)＝＝O(H1|S1) × O(H1|S2) × O(H1) O(H1) O(H1) ＝ ＝ 0.1780297 × 0.593567 × 0.111111 ＝＝0.9510532 0.111111 0.111111 然后计算后验概率然后计算后验概率P(H1|Sl∧∧S2)，得，得 P(H1|S1∧∧S2) ＝＝ O(H1|S1∧∧S2) ＝＝ 0.9520532 1+O(H1|S1∧∧S2) 1.9510532 ＝ ＝0.4874563 4．根据．根据P(H1|Sl∧∧S2)计算计算P(H2|S1∧∧S2)由于由于P(H1|S1∧∧S2)＝＝0.4874563＞＞0.1＝＝P(H1)，，所以所以 P(H2|H1) ＝＝ LS×P(H2) ＝＝ 65 × 0.01 (LS-1) × P(H2)+1 64×0.01+1 ＝ ＝ 0.3963414P(H2|S1∧∧S2)＝＝P(H2) × P(H2|H1)-P(H2) 1-P(H1) × [P(H1|Sl∧∧S2)-P(H1)] ＝＝ 0.01十十0.3963414-0.01 × (0.4874563-0.1) 1-0.1 ＝＝0.1763226 5．根据．根据P(E3|S3)计算计算P(H2|S3)。
由于由于P(E3|S3)＝＝0.02＜＜0.03，，所以所以 P(H2| E3) ＝＝ LN×P(H2) (LN-1) ×P(H2)+1 ＝＝ 0.0001×0.01 ＝＝ 0.000001 -0.9999×0.1+1P(H2|S3)＝＝P(H2| E3)+P(H2)-P(H2| E3) × P(E3|S3) P(E3) ＝＝0.000001十十0.01-0.000001×0.02 0.03 ＝＝0.006667 ＜＜P(H2) P(H|S)P(H|E)P(H)P(H| E)P(E)P(E|S)01P(E3|S3)P(H2|S3) 6．根据独立证据．根据独立证据H1和和E3计算计算P(H2|S1∧∧S2∧∧S3) 先计算后验几率先计算后验几率O(H2|Sl∧∧S2∧∧S3)，，由于由于 O(H2) ＝＝ P(H2) ＝＝ 0.01 ＝＝ 0.010l0l 1-P(H2) 1-0.01 O(H2|S1∧∧S2) ＝＝ P(H2|S1∧∧S2) 1-P(H2|S1∧∧S2) ＝＝ 0.1763226 ＝＝ 0.2140675 0.8236774 O(H2|S3) ＝＝ P(H2|S3) 1-P(H2|S3) ＝＝ 0.006667 ＝＝ 0.00671174 0.993333 因此得因此得O(H2|S1∧∧S2∧∧S3)＝＝O(H2|S1∧∧S2) × O(H2|S3) × O(H2) O(H2) O(H2) ＝＝ 0.2140675×0.00671174×0.010101 0.010101 0.010101 ＝＝ 0.142239最后得到后验概率最后得到后验概率 P(H2|S1∧∧S2∧∧S3) ＝＝ O(H2|S1∧∧S2∧∧S3) 1+O(H2|S1∧∧S2∧∧S3) ＝＝ 0.142239 ＝＝ 0.1245264 1+0.142239以上计算表明，经推理后假设以上计算表明，经推理后假设H2的概率已从先验概率的概率已从先验概率0.01增大到后验概率增大到后验概率0.1245264。
•主观主观Bayes方法的优点是：方法的优点是：–1．基于．基于Bayes规则的计算方法具有理论基础规则的计算方法具有理论基础和易于理解的数学性质，它提供了两个规则强和易于理解的数学性质，它提供了两个规则强度，恰当地处理了证据存在和不存在两种情况度，恰当地处理了证据存在和不存在两种情况对假设的影响，以及分段线性插值方法较好地对假设的影响，以及分段线性插值方法较好地处理了主观概率的数学不一致性处理了主观概率的数学不一致性.–2．该方法的计算工作量适中．该方法的计算工作量适中 •主观主观Bayes方法的缺点是：方法的缺点是：–1．要求大量的先验概率（各种假设和推理过程．要求大量的先验概率（各种假设和推理过程中各级的证据的概率），专家不易给出另外，中各级的证据的概率），专家不易给出另外，由于概率的分派具有主观性，所以在一个系统由于概率的分派具有主观性，所以在一个系统中很难保证由领域专家给出的概率具有前后的中很难保证由领域专家给出的概率具有前后的一致性–2．要求所有假设的概率都是独立的，这在一个．要求所有假设的概率都是独立的，这在一个大型的专家系统中，要求把解空间分解为相互大型的专家系统中，要求把解空间分解为相互排斥的子集可能是不实际的。
排斥的子集可能是不实际的–3．在系统中增加或删除一个假设时，要对事件．在系统中增加或删除一个假设时，要对事件的概率进行修改为了保证系统的相关性和一的概率进行修改为了保证系统的相关性和一致性，还必须重新计算所有的概率致性，还必须重新计算所有的概率–4．系统中的先验概率高度地依赖于上下文例．系统中的先验概率高度地依赖于上下文例如，某种疾病的发生概率要依赖于地域位置和如，某种疾病的发生概率要依赖于地域位置和时间的变化，这给系统的处理带来困难时间的变化，这给系统的处理带来困难 3.9.5 3.9.5 证据理论证据理论1.1.D-SD-S理论的基本概念理论的基本概念D-SD-S证据理论是由证据理论是由DempsterDempster提出，由他的学生提出，由他的学生ShaferShafer发展起来的该理论将概率论中的单点赋值发展起来的该理论将概率论中的单点赋值扩展为集合赋值，引进了信任函数，可以满足比概扩展为集合赋值，引进了信任函数，可以满足比概率函数的公理还要弱的公理，因而可以用来处理由率函数的公理还要弱的公理，因而可以用来处理由“不知道不知道”所引起的不确定性所引起的不确定性1 1））概率分配函数概率分配函数 设设ΩΩ为变量为变量x x的所有可能取值的有限集合，且的所有可能取值的有限集合，且ΩΩ中的每个元素都相互独立，则由中的每个元素都相互独立，则由ΩΩ的所有子集构成的所有子集构成的幂集记为的幂集记为2 2ΩΩ。
当当ΩΩ中的元素个数为中的元素个数为N N时，则其幂时，则其幂集集2 2ΩΩ的元素个数为的元素个数为2 2N N，，且其中的每一个元素都对应且其中的每一个元素都对应于一个关于于一个关于x x取值情况的命题取值情况的命题 例：例： 设设Ω={Ω={红，黄，白红，黄，白} }，求，求ΩΩ的幂集的幂集2 2ΩΩ解：解： A A0 0=φ=φ，， A A1 1={={红红} }，， A A2 2={={黄黄} }，， A A3 3={={白白} }，，A A4 4={={红，黄红，黄} }，， A A5 5={={红，白红，白} }，， A A6 6={={黄，白黄，白} }，， A A7 7={={红，黄，白红，黄，白} }子集个数：子集个数： 2 2N N= = 2 23 3=8=8定义：定义： 设函数设函数m m：：2 2ΩΩ→[0→[0，，1]1]，，且满足且满足 m(φ)=0m(φ)=0 则称则称m m是是2 2ΩΩ上的概率分配函数，上的概率分配函数，m(A)m(A)为为A A的基本概率数的基本概率数 m m（（{}{}，，{ {红红} }，，{ {黄黄} }，，{ {白白} }，，{ {红，黄红，黄} }，，{ {红，白红，白} }，，{ {黄，白黄，白} }，，{ {红，黄，白红，黄，白} }））= =（（0 0，，0.30.3，，0 0，，0.10.1，，0.20.2，，0.20.2，，0 0，，0.20.2））为概率分配函数。
为概率分配函数 说明：说明： 1 1）概率分配函数的作用是把）概率分配函数的作用是把ΩΩ的任意一个子集都的任意一个子集都映射为映射为[0[0，，1]1]上的一个数上的一个数m(A)m(A)当当A ΩA Ω，，且且A A由单个由单个元素组成时，元素组成时， m(A)m(A)表示对表示对A A的精确信任度；当的精确信任度；当A ΩA Ω、、A≠ΩA≠Ω，，且且A A由多个元素组成时，由多个元素组成时，m(A)m(A)也表示对也表示对A A的精确的精确信任度，但不知道信任度该分给信任度，但不知道信任度该分给A A中哪些元素；当中哪些元素；当A=ΩA=Ω时，则时，则m(A)m(A)也表示不知道该如何分配也表示不知道该如何分配 2 2））概率分配率不是概率概率分配率不是概率2 2））信任函数信任函数 信任函数信任函数BelBel定义为定义为 BelBel：：2 2ΩΩ→[0→[0，，1] 1] 且且 对所有的对所有的A ΩA Ω即命题即命题A A的信任函数的值是的信任函数的值是A A的所有子集的概率分配函的所有子集的概率分配函数数m(B)(B A)m(B)(B A)的数值和，用信任函数的数值和，用信任函数Bel(A)Bel(A)表示对表示对A A的总信任度。
的总信任度 根据定义有：根据定义有： Bel(Bel(φ)=0φ)=0 Bel(Ω)=1 Bel(Ω)=1例：例： Bel(Bel({ {红红})=})=m({m({红红})=0.3})=0.3 Bel( Bel({ {红，白红，白})=})=m({m({红红})+})+m(m({ {白白})+})+m(m({ {红，白红，白})}) =0.3+0.1+0.2=0.6 =0.3+0.1+0.2=0.6（（3 3））似然函数似然函数 似然函数似然函数PlPl定义为定义为 PlPl：：2 2ΩΩ→[0→[0，，1] 1] 且且 Pl(A)=1-Bel(Pl(A)=1-Bel( A)A) 对所有的对所有的A ΩA Ω 其中其中 A=Ω-AΩ-A Pl(A)Pl(A)表示对表示对A A为非假的信任度为非假的信任度 Pl(Pl({ {红红})=1-})=1-Bel(Bel( { {红红})=1-})=1-Bel({Bel({黄，白黄，白})})=1-(=1-(m({m({黄黄} }））+ +m({m({白白} }））+ +m({m({黄，白黄，白}))}))=1-(0+0.1+0)=0.9=1-(0+0.1+0)=0.9 Pl(A) Pl(A)是所有与是所有与A A相交子集的概率分配函数相交子集的概率分配函数m(B)(B∩A≠Φ)m(B)(B∩A≠Φ)的数值和。
的数值和Pl(Pl({ {红红})=})=m({m({红红})+ })+ m({m({红红, ,黄黄})+ })+ m({m({红，白红，白})+ })+ m m({({红，黄，白红，黄，白})}) =0.3+0.2+0.2+0.2=0.9 =0.3+0.2+0.2+0.2=0.9（（4 4））信任函数与似然函数的关系信任函数与似然函数的关系 Pl(A)≥Bel( Pl(A)≥Bel(A)A) Bel(Bel(A)A)为对为对A A的信任度的下限，的信任度的下限， Pl(A)Pl(A)为对为对A A的信任的信任度的上限，可表示为度的上限，可表示为 A[Bel(A[Bel(A)A) , , Pl(A)]Pl(A)] 如如 { {红红}[0.3,0.9]}[0.3,0.9] 关于关于信任度的典型值信任度的典型值 A[0A[0 , , 1]1]：：说明对说明对A A一无所知一无所知BelBel（（A)=0,A)=0,说明对说明对A A不不信任；信任； Bel(Bel( A) =1- Pl(A)=0A) =1- Pl(A)=0，，说明对说明对 A A也不信任。
也不信任 A[0 A[0 , , 0]0]：：说明说明A A为假BelBel（（A)=0,A)=0,说明对说明对A A不信任；不信任； Bel(Bel( A) =1- Pl(A)=1A) =1- Pl(A)=1，，说明对说明对 A A信任 A[1 A[1 , , 1]1]：：说明对说明对A A为真BelBel（（A)=1,A)=1,说明对说明对A A信任；信任； Bel(Bel( A) =1- Pl(A)=0A) =1- Pl(A)=0，，说明对说明对 A A不信任 A[0.6 A[0.6 , ,1]1]：：说明对说明对A A部分信任部分信任BelBel（（A)=0.6,A)=0.6,说明对说明对A A有一定程度的信任；有一定程度的信任； Bel(Bel( A) =1- Pl(A)=0A) =1- Pl(A)=0，，说明对说明对 A A不信任 A[0 A[0 , ,0.4]0.4]：：说明对说明对 A A部分信任部分信任BelBel（（A)=0,A)=0,说明对说明对A A不信任；不信任； Bel(Bel( A) =1- 0.4=0.6A) =1- 0.4=0.6，，说明对说明对 A A有一定程度有一定程度的信任。
的信任 A[0.3 A[0.3 ,0.9 ,0.9] ]：：说明对说明对A A和和 A A都有部分信任都有部分信任 Bel(A)=0.3,Bel(A)=0.3,说明对说明对A A部分信任；部分信任；Bel(Bel( A) =1- Pl(A) = 0.1 A) =1- Pl(A) = 0.1 ，，说明对说明对 A A也部分信任也部分信任 （（5 5））概率分配函数的正交和概率分配函数的正交和 设设m m1 1和和m m2 2是两个不同的概率分配函数，则其正交是两个不同的概率分配函数，则其正交和和m= mm= m1 1⊕⊕m m2 2满足满足 m(Φm(Φ）＝）＝0 0其中：其中： K≠0K≠0，，则正交和则正交和m m是一个概率分配函数是一个概率分配函数 K K＝＝0 0，，则不存在正交和则不存在正交和m m，，m m1 1与与m m2 2矛盾矛盾 例：设例：设ΩΩ＝｛＝｛a a，，b b｝，｝，且从不同知识源得到的概率分且从不同知识源得到的概率分配函数分别为：配函数分别为： m m1 1（｛｝（｛｝, ,｛｛a},a},｛｛b},{a,b}b},{a,b}）＝（）＝（0 0，，0.30.3，，0.50.5，，0.20.2）） m m2 2（｛｝（｛｝, ,｛｛a},a},｛｛b},{a,b}b},{a,b}）＝（）＝（0 0，，0.60.6，，0.30.3，，0.10.1））求正交和求正交和m= mm= m1 1⊕⊕m m2 2解：解： ＝＝1-(m1-(m1 1({a})× m({a})× m2 2({b})+ m({b})+ m1 1({b})× m({b})× m2 2({a}))({a})) =1-(0.3 ×0.3+0.3 ×0.6)=0.61 =1-(0.3 ×0.3+0.3 ×0.6)=0.61 m({a})=1/0.61 ×(m m({a})=1/0.61 ×(m1 1({a})× m({a})× m2 2({a})+ m({a})+ m1 1({a})× ({a})× m m2 2({a,b})+ m({a,b})+ m1 1({a,b})× m({a,b})× m2 2({a}))({a})) =1/0.61×(0.3×0.6+0.3×0.1+0.2×0.6)=0.54 =1/0.61×(0.3×0.6+0.3×0.1+0.2×0.6)=0.54同理：同理：m({b})=0.43m({b})=0.43 m({a,b})=0.03 m({a,b})=0.03所以：所以：m({},{a},{b},{a,b})={0,0.54,0.43,0.03}m({},{a},{b},{a,b})={0,0.54,0.43,0.03} 2.2.D-SD-S理论的推理模型理论的推理模型（（1 1））特殊的概率分配函数特殊的概率分配函数 设设ΩΩ＝｛＝｛s s1 1，， s s1 1，，… s sn n},m},m为定义在为定义在2 2ΩΩ上的概上的概率分配函数，且率分配函数，且m m满足满足 （（1)1)m({sm({si i})≥0 })≥0 对任何对任何s si i∈ Ω∈ Ω （（2 2）） （（3 3）） （（4 4）当）当A ΩA Ω且且| |A|A|＞＞1 1或或| |A|=0A|=0时，时，m(A)=0 m(A)=0 其中，其中，| |A|A|表示命题表示命题A A所对应的集合中的元素个数。
所对应的集合中的元素个数只有单元素集的基本概率分配函数值才有可能大于只有单元素集的基本概率分配函数值才有可能大于0,0,由一个以上元素组成的子集的基本概率分配函数由一个以上元素组成的子集的基本概率分配函数值均为值均为0.0. 特殊的概率分配函数的信任函数、似然函数、正交和特殊的概率分配函数的信任函数、似然函数、正交和 对任何命题对任何命题A Ω A Ω ，，其信任函数为其信任函数为 对任何命题对任何命题A Ω A Ω ，，其似然函数为其似然函数为Pl(A)=Pl(A)=1-Bel(1-Bel( A)A)＝＝＝＝1-[1-1-[1-m m（（ΩΩ）－）－Bel(ABel(A）〕）〕＝＝m(Ω)+Bel(A)m(Ω)+Bel(A)Pl(Ω)=1-Bel(Pl(Ω)=1-Bel( Ω)=1-Bel(Φ)=1Ω)=1-Bel(Φ)=1对任何命题对任何命题A ΩA Ω和和B ΩB Ω均有均有 Pl(A)-Bel(A)=Pl(B)-Bel(B)=m(Ω)Pl(A)-Bel(A)=Pl(B)-Bel(B)=m(Ω)表示对表示对A A（（或或B B））不知道的程度。
不知道的程度 设设m m1 1和和m m2 2是是2 2ΩΩ上的基本概率分配函数，其正交和为上的基本概率分配函数，其正交和为其中其中例：例：设设Ω={Ω={红，黄，白红，黄，白} }，有如下概率分配函数，有如下概率分配函数m m（（{}{}，，{ {红红} }，，{ {黄黄} }，，{ {白白} }，，{ {红，黄，白红，黄，白} }））= =（（0 0，，0.60.6，，0.20.2，，0.10.1，，0.10.1））A A＝｛＝｛红，黄｝，求红，黄｝，求m(Ωm(Ω）、）、BelBel（（A)A)和和Pl(A)Pl(A)的值 m(Ω)=1-[m({m(Ω)=1-[m({红｝红｝)+ )+ m({m({黄｝黄｝)+ )+ m({m({白｝白｝) )〕〕＝＝1-1-（（0.6+0.2+0.10.6+0.2+0.1）＝）＝0.10.1 Bel({Bel({红，黄红，黄})})＝＝ m({m({红红})+ })+ m({m({黄黄})})＝＝0.6+0.20.6+0.2＝＝0.80.8 Pl({Pl({红，黄红，黄})=})=m(Ω)+Bel({m(Ω)+Bel({红，黄红，黄})=0.1+0.8=0.9})=0.1+0.8=0.9或或Pl({Pl({红，黄红，黄})=1-})=1-Bel(Bel( { {红，黄红，黄})=1-})=1-Bel({Bel({白白})}) =1-0.1=0.9 =1-0.1=0.9 （（2 2））类概率函数类概率函数 设设ΩΩ为有限域，对任何命题为有限域，对任何命题A ΩA Ω，，命题命题A A的类概的类概率函数为率函数为 f(A)=Bel(A)+|A|/|Ω| f(A)=Bel(A)+|A|/|Ω| ×[Pl(A)-Bel(A)]×[Pl(A)-Bel(A)]其中，其中，| |A|A|和和| |Ω|Ω|分别是分别是A A及及ΩΩ中元素的个数。
中元素的个数 类概率函数类概率函数f(A)f(A)具有如下性质具有如下性质1)1) 2)2)对任何对任何A ΩA Ω，，有有Bel(A)≤f(A) ≤Pl(A)Bel(A)≤f(A) ≤Pl(A)3)3)对任何对任何A ΩA Ω，，有有f(f( A)=1-f(A)A)=1-f(A)推论：推论：1 1））f(Φf(Φ））=0=02 2））f(f(Ω)=1Ω)=13)3)对任何对任何A Ω,A Ω,有有0≤0≤f(A) ≤1f(A) ≤1 例：设例：设Ω={Ω={红，黄，白红，黄，白} }，概率分配函数，概率分配函数m m（（{}{}，，{ {红红} }，，{ {黄黄} }，，{ {白白} }，，{ {红，黄，白红，黄，白} }））= =（（0 0，，0.60.6，，0.20.2，，0.10.1，，0.10.1）若）若A A＝｛＝｛红，黄｝，求红，黄｝，求f(A)f(A)的值的值 f(A)=Bel(A)+|A|/|Ω| f(A)=Bel(A)+|A|/|Ω| ×[Pl(A)-Bel(A)]×[Pl(A)-Bel(A)] ＝＝m({m({红红})+ })+ m({m({黄｝黄｝) )＋＋2/32/3××m({m({红，黄，白｝红，黄，白｝) ) ＝＝0.6+0.2+2/30.6+0.2+2/3×0.1×0.1＝＝0.870.87（（3)3)知识不确定性的表示知识不确定性的表示 IF E THEN H={hIF E THEN H={h1 1,h,h2 2, ,…,h,hn n} CF={c} CF={c1 1,c,c2 2, ,…,c,cn n} } 其中：其中：E E是前提是前提 H H是结论是结论 CFCF是可信度因子是可信度因子（（4)4)证据不确定性的表示证据不确定性的表示 在证据理论中，所有输入的已知数据，规则前提条件在证据理论中，所有输入的已知数据，规则前提条件及结论部分的命题都称为证据。
及结论部分的命题都称为证据 设设A A是规则条件部分的命题，是规则条件部分的命题，E E’是外部输入的证据和已是外部输入的证据和已证实的命题，在证据证实的命题，在证据E E’的条件下，命题的条件下，命题A A与证据与证据E E’的匹的匹配程度为配程度为 1 1 如果如果A A的所有元素都出现在的所有元素都出现在E E’中中 MD(A/EMD(A/E’)= 0 )= 0 否则否则 条件部分命题条件部分命题A A的确定性为的确定性为 CER(A)=MD(A/ECER(A)=MD(A/E’) ×f(A) ) ×f(A) CER(A)∈[0,1]CER(A)∈[0,1](5)(5)组合证据非精确性的表示组合证据非精确性的表示证据合取情况：证据合取情况：E= EE= E1 1 AND E AND E2 2 AND AND．．．．．．AND EAND En n CER(E)=min{CER(ECER(E)=min{CER(E1 1),CER(E),CER(E2 2),),…CER(ECER(En n)})}证据析取情况证据析取情况: : E= EE= E1 1 OR E OR E2 2 0R 0R…OR EOR En n CER(E)=max{CER(E CER(E)=max{CER(E1 1),CER(E),CER(E2 2),),…CER(ECER(En n)})} (6)(6)不确定性的更新不确定性的更新 设有知识设有知识 IF E THEN H={hIF E THEN H={h1 1,h,h2 2, ,…,h,hn n} CF={c} CF={c1 1,c,c2 2, ,…,c,cn n} } 则求结论则求结论H H确定性确定性CER(H)CER(H)的方法如下：的方法如下： 1) 1)求求H H的概率分配函数的概率分配函数 m({hm({h1 1},{h},{h2 2},},…,{h,{hn n})}) =(CER(E)×c =(CER(E)×c1 1,CER(E)×c,CER(E)×c2 2, ,… CER(E)×c CER(E)×cn n) ) m( m(Ω)=1-Ω)=1- 如有两条知识支持同一结论如有两条知识支持同一结论H H IF EIF E1 1 THEN H={h THEN H={h1 1,h,h2 2, ,…,h,hn n} CF} CF1 1={c={c1 1,c,c2 2, ,…,c,cn n} } IF E IF E2 2 THEN H={h THEN H={h1 1,h,h2 2, ,…,h,hn n} CF} CF2 2={c={c1 1,c,c2 2, ,…,c,cn n} } 则先求每一知识的概率分配函数：则先求每一知识的概率分配函数： m m1 1= =m({hm({h1 1},{h},{h2 2},},…,{h,{hn n})}) m m2 2= =m({hm({h1 1},{h},{h2 2},},…,{h,{hn n})}) 再求再求H H的概率分配函数：的概率分配函数：m= mm= m1 1⊕⊕m m2 2 如有多条知识支持同一结论如有多条知识支持同一结论H H 则用公式则用公式 : :m= mm= m1 1⊕⊕m m2 2⊕⊕…⊕⊕m mn n 求求H H的概率分配函数的概率分配函数 2) 2)求求Bel(H),Pl(H)Bel(H),Pl(H)及及f(H)f(H) Pl(H)=1-Bel( Pl(H)=1-Bel( H)H) f(H)=Bel(H)+|H|/|Ω| f(H)=Bel(H)+|H|/|Ω| ×[Pl(H)-Bel(H)]×[Pl(H)-Bel(H)] = =Bel(H)+|H|/|Ω| Bel(H)+|H|/|Ω| ×m(×m(Ω) ) 3) 3)求求CER(H)CER(H) CER(H)=MD(H/ECER(H)=MD(H/E’)×f(H))×f(H) 例：设有如下规则例：设有如下规则 r r1 1:IF E:IF E1 1 AND EAND E2 2 THEN A={a THEN A={a1 1,a,a2 2} CF={0.3,0.5}} CF={0.3,0.5} r r2 2:IF E:IF E3 3 AND (EAND (E4 4 OR E OR E5 5) THEN B={b) THEN B={b1 1} CF={0.7}} CF={0.7} r r3 3:IF A:IF A THEN H={hTHEN H={h1 1,h,h2 2,h,h3 3} CF={0.1,0.5,0.3}} CF={0.1,0.5,0.3} r r4 4:IF B THEN H= {h:IF B THEN H= {h1 1,h,h2 2,h,h3 3} CF={0.4,0.2,0.1}} CF={0.4,0.2,0.1}已知初始证据的确定性为：已知初始证据的确定性为： CER(ECER(E1 1)=0.8 CER(E)=0.8 CER(E2 2)=0.6 CER(E)=0.6 CER(E3 3)=0.9 )=0.9 CER(E CER(E4 4)=0.5 CER(E)=0.5 CER(E5 5)=0.7 )=0.7 假设假设ΩΩ中的元素个数中的元素个数| |Ω|Ω|＝＝1010 求：求：CER(H)CER(H) HABE1E2={ {h h1 1,h,h2 2,h,h3 3} } = {a{a1 1,a,a2 2} } = {b{b1 1} } E3E4E5解：解：（（1 1）求）求CER(A)CER(A) CER(E CER(E1 1 AND E AND E2 2) )=min{CER(E=min{CER(E1 1),CER(E),CER(E2 2)})}=min(0.8,0.6}=min(0.8,0.6}=0.6=0.6m({am({a1 1},{a},{a2 2})})={0.6 ×0.3,0.6 ×0.5}={0.6 ×0.3,0.6 ×0.5}={0.18,0.3}={0.18,0.3}Bel(A)=m({aBel(A)=m({a1 1})+m({a})+m({a2 2})=0.18+0.3=0.48 })=0.18+0.3=0.48 Pl(A)=1-Bel(Pl(A)=1-Bel( A)=1-0=1A)=1-0=1f(A)= f(A)= Bel(A)+|A|/|Ω|Bel(A)+|A|/|Ω|×[Pl(A)-Bel(A)]×[Pl(A)-Bel(A)] =0.48+2/10×0.52=0.584 =0.48+2/10×0.52=0.584CER(A)=MD(A/ECER(A)=MD(A/E’)×f(A)=0.584)×f(A)=0.584 （（2 2）求）求CER(B)CER(B) CER(E CER(E3 3 AND (E AND (E4 4 OR E OR E5 5))))=min{CER(E=min{CER(E3 3), max{CER(E), max{CER(E4 4),CER(E),CER(E5 5)}})}}=min(0.9,max(0.5,0.7}}=0.7=min(0.9,max(0.5,0.7}}=0.7m({bm({b1 1})=0.7×0.7=0.49})=0.7×0.7=0.49Bel(B)=m({bBel(B)=m({b1 1}) =0.49 }) =0.49 Pl(B)=1-Bel(Pl(B)=1-Bel( B)=1-0=1B)=1-0=1f(B)= f(B)= Bel(B)+|B|/|Ω|Bel(B)+|B|/|Ω|×[Pl(B)-Bel(B)]×[Pl(B)-Bel(B)] =0.49+1/10×[1-0.49]=0.541 =0.49+1/10×[1-0.49]=0.541CER(B)=MD(B/ECER(B)=MD(B/E’)×f(B)=0.541)×f(B)=0.541(3)(3)求求CER(H)CER(H)由由r r3 3: :m m1 1({h({h1 1},{h},{h2 2},{h},{h3 3})}) ={CER(A)×0.1,CER(A)×0.5,CER(A)×0.3} ={CER(A)×0.1,CER(A)×0.5,CER(A)×0.3} ={0.058,0.292,0.175} ={0.058,0.292,0.175} m m1 1( (Ω)=1-[Ω)=1-[m m1 1({h({h1 1})+ m})+ m1 1({h({h2 2})+m})+m1 1({h({h3 3})]})] =1-[0.058+0.292+0.175]=0.475 =1-[0.058+0.292+0.175]=0.475 由由r r4 4: :m m2 2({h({h1 1},{h},{h2 2},{h},{h3 3})}) ={CER(B)×0.4,CER(B)×0.2,CER(B)×0.1} ={CER(B)×0.4,CER(B)×0.2,CER(B)×0.1} ={0.216,0.108,0.054} ={0.216,0.108,0.054}m m2 2( (Ω)=1-[Ω)=1-[m m2 2({h({h1 1})+ m})+ m2 2({h({h2 2})+m})+m2 2({h({h3 3})]})] =1-[0.216+0.108+0.054]=0.622 =1-[0.216+0.108+0.054]=0.622求正交和求正交和m= mm= m1 1⊕⊕m m2 2 K=mK=m1 1( (Ω)Ω)× m× m2 2( (Ω)Ω)+ +m m1 1({h({h1 1} }) )×m×m2 2({h({h1 1} })+ )+ m m1 1({h({h1 1} }) )×m×m2 2( (Ω)+Ω)+m m1 1( (Ω)Ω)×m×m2 2({h({h1 1} }) )+ +m m1 1({h({h2 2} }) )×m×m2 2({h({h2 2} })+ )+ m m1 1({h({h2 2} }) )×m×m2 2( (Ω)+Ω)+m m1 1( (Ω)Ω)×m×m2 2({h({h2 2} }) )+ +m m1 1({h({h3 3} }) )×m×m2 2({h({h3 3} })+ )+ m m1 1({h({h3 3} }) )×m×m2 2( (Ω)+Ω)+m m1 1( (Ω)Ω)×m×m2 2({h({h3 3} }) )=0.855=0.855 m( m(h h1 1)=)=1/K1/K×[m×[m1 1({h({h1 1} }) )×m×m2 2({h({h1 1} })+ )+ m m1 1({h({h1 1} }) )×m×m2 2( (Ω)+Ω)+m m1 1( (Ω)Ω)×m×m2 2({h({h1 1} }) ) =0.178 =0.178同理同理 m(m(h h2 2)=)=1/K1/K×[m×[m1 1({h({h2 2} }) )×m×m2 2({h({h2 2} })+ )+ m m1 1({h({h2 2} }) )×m×m2 2( (Ω)+Ω)+m m1 1( (Ω)Ω)×m×m2 2({h({h2 2} }) ) =0.309 =0.309 m( m(h h3 3)=)=1/K1/K×[m×[m1 1({h({h3 3} }) )×m×m2 2({h({h3 3} })+ )+ m m1 1({h({h3 3} }) )×m×m2 2( (Ω)+Ω)+m m1 1( (Ω)Ω)×m×m2 2({h({h3 3} }) ) =0.168 =0.168m(m(Ω)=1-[Ω)=1-[m({hm({h1 1} })+)+m({hm({h2 2} })+ )+ m({hm({h3 3} })])] =0.345 =0.345根据根据m m可得可得Bel(H)= m({hBel(H)= m({h1 1} })+)+m({hm({h2 2} })+ )+ m({hm({h3 3} }) ) =0.655 =0.655 Pl(H)=m(Pl(H)=m(Ω)+Ω)+Bel(Bel(H)=0.345+0.655=1H)=0.345+0.655=1f(H)= f(H)= Bel(H)+|H|/|Ω|Bel(H)+|H|/|Ω|×[Pl(H)-Bel(H)]×[Pl(H)-Bel(H)] =0.655+3/10×[1-0.655]=0.759 =0.655+3/10×[1-0.655]=0.759CER(H)=MD(H/ECER(H)=MD(H/E’)×f(H)=0.759)×f(H)=0.759 证据理论的优点：证据理论的优点： 满足比满足比Bayes概率理论更弱的条件，即不必满足概率理论更弱的条件，即不必满足概率可加性；概率可加性； 具有直接表达具有直接表达“不确定不确定”和和“不知道不知道”的能力；的能力； 证据理论不但允许人们将置信度赋予假证据理论不但允许人们将置信度赋予假设空间的单个元素，而且还能赋予它的子集，更有设空间的单个元素，而且还能赋予它的子集，更有利于领域专家在不同层次上进行知识表示。
利于领域专家在不同层次上进行知识表示 由于在证据理论中需要的先验数据比概率推理由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得，合成公式可以综理论中的更为直观、更容易获得，合成公式可以综合不同专家或数据源的知识或数据，这使得证据理合不同专家或数据源的知识或数据，这使得证据理论在专家系统、数据融合等领域中得到了广泛应用论在专家系统、数据融合等领域中得到了广泛应用证据理论的局限性：证据理论的局限性： 要求证据必须是独立的，而这有时不易满足；要求证据必须是独立的，而这有时不易满足； 证据合成规则没有非常坚固的理论支持，其合证据合成规则没有非常坚固的理论支持，其合理性和有效性还存在较大的争议；理性和有效性还存在较大的争议； 计算上存在着潜在的指数爆炸问题计算上存在着潜在的指数爆炸问题 3.9.6 3.9.6 可能性理论和模糊推理可能性理论和模糊推理 可可能能性性理理论论的的基基础础是是Zadeh本本人人的的模模糊糊集集合合理理论论正正如如概概率率论论处处理理的的是是由由随随机机性性引引起起的的不不确确定定性性一一样样，，可可能能性性理理论论处处理理的的是是由由模模糊糊性性引引起起的的不不确确定定性性。
该该方方法法弥弥补补了了概概率率统统计计方方法法无无法法处处理理知知识识和和证证据据中中存存在在的的模模糊糊性性问问题题，，对对由由模模糊糊性性引引起起的的不不确确定定性性的的表表示示及及处处理理开开辟辟了了一一种种新新途途径径，，目目前前已已经经广广泛泛应应用用于于不确定性推理领域不确定性推理领域 1.1.模糊逻辑基础模糊逻辑基础 模糊性是指客观事物在形态和属性方面的不确定模糊性是指客观事物在形态和属性方面的不确定（（1 1）模糊性与随机性）模糊性与随机性–随机性所描述的事件或现象本身含义是清楚的，随机性所描述的事件或现象本身含义是清楚的，可以明确地判定该事件在某特定的时刻发生了还可以明确地判定该事件在某特定的时刻发生了还是没有发生随机性用概率来度量，并要求所有是没有发生随机性用概率来度量，并要求所有可能事件的概率总和为可能事件的概率总和为1 1–模糊性所描述的现象或概念本身的模糊性所描述的现象或概念本身的“边界边界”是不是不清楚的模糊性是用清楚的模糊性是用“可能性可能性”（介于（介于0 0和和1 1之间）之间）来度量的，并且不要求可能性总和为来度量的，并且不要求可能性总和为1 1。
（（2 2）模糊集与隶属函数）模糊集与隶属函数 定义：设定义：设U U是给定论域，是给定论域， 是把任意是把任意μ∈Uμ∈U映射为映射为[0[0，，1]1]上某个值的函数，即上某个值的函数，即 ：：U→[0U→[0，，1]1] u→ (u) u→ (u) 则称则称 为定义在为定义在U U上的一个隶属函数，由上的一个隶属函数，由 （（u)(u)(对所有对所有u ∈U)u ∈U)所构成的集合所构成的集合F F称为称为U U上的一个模糊集，上的一个模糊集， （（u)u)称为称为u u对对F F的隶属度的隶属度 隶属函数表示该元素隶属于隶属函数表示该元素隶属于U U的程度或可能性，值越的程度或可能性，值越大表示隶属的程度越高大表示隶属的程度越高 这种方法在具体实现时，应把隶属度为零的元素剔除这种方法在具体实现时，应把隶属度为零的元素剔除掉，否则消耗资源太多掉，否则消耗资源太多 例：设论域例：设论域 U={20U={20，，3030，，4040，，5050，，60}60}给出的是年龄，确定一个刻画模糊概念给出的是年龄，确定一个刻画模糊概念“年轻年轻”的模糊集的模糊集F.F. 假设对论域假设对论域U U中的元素，其隶属函数值分别为中的元素，其隶属函数值分别为 μμF F(20)=1, μ(20)=1, μF F(30)=0.8, μ(30)=0.8, μF F(40)=0.4, (40)=0.4, μ μF F(50)=0.1, μ(50)=0.1, μF F(60)=0(60)=0 则其模糊集为则其模糊集为 F={1,0.8,0.4,0.1,0}F={1,0.8,0.4,0.1,0}定义：设定义：设U U是给定论域，是给定论域，x x是在是在U U上取值的变量，则可能性上取值的变量，则可能性分布函数分布函数 ππx x:U →[0:U →[0，，1]1] 表示表示x x取取u u（（u∈U)u∈U)值的可能性。
值的可能性 用用poss{x=u}poss{x=u}表示，即表示，即poss{x=u}= πposs{x=u}= πx x(u)(u) 可能性分布函数与隶属函数之间的关系：可能性分布函数与隶属函数之间的关系： ππx x(u)= μ(u)= μF F(u) u∈U(u) u∈U 即即 poss(x=u)= μposs(x=u)= μF F(u) (u) （（3 3）模糊集的表示方法）模糊集的表示方法 对离散且为有限论域对离散且为有限论域 U={uU={u1 1, u, u2 2, ,… u un n} } 其模糊集可表示为其模糊集可表示为 F={μF={μF F(u(u1 1), μ), μF F(u(u2 2),),… μ μF F(u(un n) }) } 为表示出论域中的元素与其隶属度之间的对应关系，可为表示出论域中的元素与其隶属度之间的对应关系，可用如下表示方法：用如下表示方法： F= μF= μF F(u(u1 1)/u)/u1 1+μ+μF F(u(u2 2)/u)/u2 2+ +… +μ +μF F(u(un n)/u)/un n F= {μ F= {μF F(u(u1 1)/u)/u1 1,μ,μF F(u(u2 2)/u)/u2 2, ,… ,μ ,μF F(u(un n)/u)/un n } } F={( μ F={( μF F(u(u1 1),u),u1 1),(μ),(μF F(u(u2 2),u),u2 2) )… (μ (μF F(u(un n),u),un n)} )} 如：如：F=1/20+0.8/30+0.4/40+0.1/50F=1/20+0.8/30+0.4/40+0.1/50 对连续论域，模糊集可用实函数表示。
对连续论域，模糊集可用实函数表示 如：如： U=[1U=[1，，100]100] 当当0≤0≤u≤25u≤25 当当2525＜＜u≤100u≤100 当当0≤0≤u≤50u≤50 当当5050＜＜u≤100u≤100 模糊集的一般表示形式：模糊集的一般表示形式： （（4 4）模糊集的运算）模糊集的运算v 设设F F、、G G分别是分别是U U上的两个模糊集，若对任意上的两个模糊集，若对任意u∈Uu∈U，，都有都有 μμF F(u)=μ(u)=μG G(u)(u) 成立，则称成立，则称F F等于等于G G，，记为记为F=G.F=G.v设设F F、、G G分别是分别是U U上的两个模糊集，若对任意上的两个模糊集，若对任意u∈Uu∈U，，都有都有 μμF F(u)≤μ(u)≤μG G(u)(u) 成立，则称成立，则称F F含于含于G G，，记为记为F G.F G.v设设F F、、G G分别是分别是U U上的两个模糊集，则上的两个模糊集，则F∪GF∪G、、F∩GF∩G分别称分别称为为F F与与G G的并集、交集，其隶属函数分别为：的并集、交集，其隶属函数分别为： F∪G:μF∪G:μF∪GF∪G(u)=max{μ(u)=max{μF F(u),μ(u),μG G(u)}= μ(u)}= μF F(u)∨μ(u)∨μG G(u)(u) u∈Uu∈U F∩G:μ F∩G:μF∩GF∩G(u)=min{μ(u)=min{μF F(u),μ(u),μG G(u)}= μ(u)}= μF F(u)∧μ(u)∧μG G(u)(u) u∈Uu∈Uv设设F F是是U U上的模糊集，称上的模糊集，称~ ~F F为为F F的补集，其隶属函数为：的补集，其隶属函数为： ~ ~F: μF: μ~F~F(u)1- μ(u)1- μF F(u)(u) 例：设例：设U={1,2,3},FU={1,2,3},F和和G G分别是分别是U U上的两个模糊集，即上的两个模糊集，即 F=F=小小=1/1+0.6/2+0.1/3=1/1+0.6/2+0.1/3 G=G=大大=0.1/1+0.6/2+1/3=0.1/1+0.6/2+1/3 F∪G=(1∨0.1)/1+(0.6∨0.6)/2+(0.1∨1)/3F∪G=(1∨0.1)/1+(0.6∨0.6)/2+(0.1∨1)/3 =1/1+0.6/2+1/3 =1/1+0.6/2+1/3 F∩G=(1∧0.1)/1+(0.6∧0.6)/2+(0.1∧1)/3 F∩G=(1∧0.1)/1+(0.6∧0.6)/2+(0.1∧1)/3 =0.1/1+0.6/2+0.1/3 =0.1/1+0.6/2+0.1/3 ~F=(1-1)/1+(1-0.6)/2+(1-0.1)/3 ~F=(1-1)/1+(1-0.6)/2+(1-0.1)/3 =0.4/2+0.9/3 =0.4/2+0.9/3 两个模糊集之间的运算是逐点对隶属函数做相应的运算。
两个模糊集之间的运算是逐点对隶属函数做相应的运算 （（5 5）模糊关系）模糊关系v 设设V V与与W W是两个普通集合，是两个普通集合，V V与与W W的笛卡儿乘积是由的笛卡儿乘积是由V V与与W W上所有可能的序偶（上所有可能的序偶（v v，，w w））构成的一个集合，即：构成的一个集合，即： V×W={(v,w)|V×W={(v,w)|任意任意v∈V, v∈V, 任意任意w∈W}w∈W} 从从V V到到W W的关系的关系R R，，是指是指V×WV×W上的一个子集，即上的一个子集，即R V×WR V×W 记为：记为： V→ WV→ W 若（若（v v，，w w））∈R,∈R,则则v v与与w w有关系；有关系； 若（若（v v，，w w）） R, R,则则v v与与w w无关系；无关系； 例：设例：设V={1V={1班，班，2 2班，班，3 3班班} } W={W={男队，女队男队，女队} } 则则 V×W={(1V×W={(1班，男队）班，男队）,(2,(2班，男队）班，男队）,(3,(3班，男队）班，男队）, , (1 (1班，女队）班，女队）,(2,(2班，女队）班，女队）,(3,(3班，女队）班，女队）} }R v设设F Fi i是是U Ui i(i=1,2,(i=1,2,…,n),n)上的模糊集，则称上的模糊集，则称 为为F F1 1,F,F2 2, ,…F Fn n的笛卡尔乘积，是的笛卡尔乘积，是U U1 1×U×U2 2××…×U×Un n上的一个上的一个模糊集。
模糊集v在在U U1 1×U×U2 2××…×U×Un n上的一个上的一个n n元模糊关系元模糊关系R R指以指以U U1 1×U×U2 2××…×U×Un n为论域的一个模糊集，记为为论域的一个模糊集，记为 u uR R(u(u1 1,u,u2 2, ,…u un n) )是模糊关系是模糊关系R R的隶属函数，它把的隶属函数，它把U U1 1×U×U2 2××…×U×Un n上的每一个元素（上的每一个元素（ u u1 1,u,u2 2, ,…u un n) )都映射为都映射为[0[0，，1]1]上的一个实数，反映上的一个实数，反映u u1 1,u,u2 2, ,…u un n具有关系具有关系R R的程度 例：设有一组学生例：设有一组学生U={uU={u1 1,u,u2 2}={}={秦学，郝万秦学，郝万} } 一些在计算机上的活动一些在计算机上的活动 V={V={编程，上网，玩游戏编程，上网，玩游戏} } u uR R( (秦学，编程）秦学，编程）=0.9=0.9，，u uR R( (秦学，上网）秦学，上网）=0.6=0.6，，u uR R( (秦学，秦学，玩游戏）玩游戏）=0=0，，u uR R( (郝万，编程）郝万，编程）=0.2=0.2，， u uR R( (郝万，上网）郝万，上网）=0.3=0.3，， u uR R( (郝万，玩游戏）郝万，玩游戏）=0.8 =0.8 则则U×VU×V上的模糊关系上的模糊关系R R为为 R= 0.9 0.6 0R= 0.9 0.6 0 0.2 0.3 0.8 0.2 0.3 0.8 （（6 6）模糊关系的合成）模糊关系的合成v 设设R R1 1与与R R2 2是分别是是分别是U×VU×V与与V×WV×W上的两个模糊关系，则上的两个模糊关系，则R R1 1与与R R2 2的合成是从的合成是从U U到到W W的一个模糊关系，记为的一个模糊关系，记为 R R1 1 。
R R2 2 其隶属函数为其隶属函数为 u uR1 R1 R2R2(u,w)= ∨{u(u,w)= ∨{uR1R1(u,v)∧ u(u,v)∧ uR2R2(v,w)}(v,w)} 例：设有以下两个模糊关系例：设有以下两个模糊关系 0.9 0.6 0 0.7 0.9 0.9 0.6 0 0.7 0.9 R R1 1= 0.2 0.3 0.8 R= 0.2 0.3 0.8 R2 2= 0.2 0.8= 0.2 0.8 0.5 0.3 0.5 0.3 则则R R1 1与与R R2 2的合成是的合成是 R=RR=R1 1 R R2 2= 0.5 0.5= 0.5 0.5 0.7 0.8 0.7 0.8 （（7 7）模糊变换）模糊变换v 设设F={uF={uF F(u(u1 1), u), uF F(u(u2 2),),… u uF F(u(un n)},)},是论域是论域U U上的模糊集，上的模糊集，R R是是U×VU×V上的模糊关系，则上的模糊关系，则 F F 。
R=GR=G称为模糊变换称为模糊变换 例：设例：设F={1,0.6,0.2)F={1,0.6,0.2) 1 0.5 0 0 1 0.5 0 0 R= 0.5 1 0.5 0 R= 0.5 1 0.5 0 0 0.5 1 0.5 0 0.5 1 0.5则则 G=FG=F R= {1∧1∨0.6∧0.5∨0.2∧0, R= {1∧1∨0.6∧0.5∨0.2∧0, 1∧0.5∨0.6∧1∨0.2∧0.5, 1∧0∨0.6∧0.5∨0.2∧1, 1∧0.5∨0.6∧1∨0.2∧0.5, 1∧0∨0.6∧0.5∨0.2∧1, 1∧0∨0.6∧0∨0.2∧0.5}={1,0.6,0.5,0.2}1∧0∨0.6∧0∨0.2∧0.5}={1,0.6,0.5,0.2} 2.2.模糊知识表示模糊知识表示（（1 1）语言变量）语言变量 模糊逻辑中使用的变量是语言变量，指用自然语言中的模糊逻辑中使用的变量是语言变量，指用自然语言中的词或句子表示的变量。
词或句子表示的变量2 2）模糊命题的描述）模糊命题的描述Ø 模糊谓词模糊谓词 设设x x为在为在U U中取值的变量，中取值的变量，F F为模糊谓词，则命题可以表为模糊谓词，则命题可以表示为示为 x IS Fx IS F其中其中F F可以是描述关系的词语，如大，小，年轻，年老等可以是描述关系的词语，如大，小，年轻，年老等Ø模糊量词模糊量词 模糊量词可以是表示不定数词的词语，如多数，经常等模糊量词可以是表示不定数词的词语，如多数，经常等 如多数歌手是年轻人如多数歌手是年轻人 Ø模糊概率、模糊可能性和模糊真值模糊概率、模糊可能性和模糊真值 设设λ为模糊概率，为模糊概率，π为模糊可能性，为模糊可能性，τ为模糊真值，则可为模糊真值，则可对命题加以限定对命题加以限定 (x is F) is λ (x is F) is π (x is F) is τ λ可以是或许，未必等，可以是或许，未必等，π可以是非常可能，很不可能等，可以是非常可能，很不可能等，τ可以是有些真，非常假等可以是有些真，非常假等Ø模糊修饰语模糊修饰语 设设m是模糊修饰语，是模糊修饰语，x是变量，是变量，F为模糊谓词，则模糊命题为模糊谓词，则模糊命题可表示为可表示为 x is mF m可以是非常、很、有些等。
可以是非常、很、有些等 模糊修饰语的表示模糊修饰语的表示 1）求补）求补 :表示否定时（不，非），其隶属函数为表示否定时（不，非），其隶属函数为 u u非非F F(u(u））=1- u=1- uF F(u) u∈[0(u) u∈[0，，1]1] 2 2））集中：表示集中：表示“很很”、、“非常非常”等，其效果是减少隶等，其效果是减少隶属函数的值：属函数的值： u u非常非常F F(u(u））=u=uF F2 2(u) u∈[0(u) u∈[0，，1]1] 3) 3)扩张：表示扩张：表示“有些有些”、、“稍微稍微”等，其效果是增加隶等，其效果是增加隶属函数的值：属函数的值： u u有些有些F F(u(u））=u=uF F1/21/2(u) u∈[0(u) u∈[0，，1]1] 4 4））加强对比：表示加强对比：表示“明确明确”、、“确定确定”等，其效果是增等，其效果是增加加0.50.5以上隶属函数的值，减少以上隶属函数的值，减少0.50.5以下隶属函数的值：以下隶属函数的值： 2 2u uF F2 2(u) (u) 若若0≤0≤u uF F(u)(u)≤ 0.5≤ 0.5 u u确实确实F F(u(u））= 1-2= 1-2（（1-u1-uF F(u)(u)））2 2 若若0.5≤0.5≤u uF F(u)(u)≤ 1≤ 1 l把条件模糊化：即条件用一个模糊谓词公式来代替，把条件模糊化：即条件用一个模糊谓词公式来代替，并定义一种模糊匹配原则，当该规则的条件被目前已知并定义一种模糊匹配原则，当该规则的条件被目前已知的对象模糊地匹配上以后，就可应用该规则的对象模糊地匹配上以后，就可应用该规则l把动作或结论模糊化：使动作或结论具有一种可信度把动作或结论模糊化：使动作或结论具有一种可信度（以（以[0，，1]之间的数表示）。
或结论就是一个模糊谓词，之间的数表示）或结论就是一个模糊谓词，表示一个模糊概念；或动作本身就是一个模糊动作表示一个模糊概念；或动作本身就是一个模糊动作l设置阈值设置阈值τ（（0< τ<1）：）：只有当条件谓词公式的真值大只有当条件谓词公式的真值大于等于于等于τ时，该规则才可应用时，该规则才可应用（（3 3）模糊规则）模糊规则 规则的一般形式是：规则的一般形式是： IF IF 条件条件 THEN THEN 动作（结论）动作（结论） l设置规则的可信度设置规则的可信度CFCF（（0 判别可否应用该规则的阈值 3.3.模糊概念的匹配模糊概念的匹配 模糊概念的匹配指对两个模糊概念相似程度的比较模糊概念的匹配指对两个模糊概念相似程度的比较与判断1 1）语义距离）语义距离 海明距离：海明距离：• 设设U={uU={u1 1, u, u2 2, ,… u un n} }是一个离散有限论域，是一个离散有限论域，F F和和G G分别是论域分别是论域U U上的两个模糊概念的模糊集，则上的两个模糊概念的模糊集，则F F和和G G的海明距离为：的海明距离为：•如果论域如果论域U U是实数域上的某个闭区间是实数域上的某个闭区间[ [a,b]a,b]，，则海则海明距离为：明距离为： 例：设论域例：设论域U={-10U={-10，，0 0，，1010，，2020，，30}30}表示温度，模糊表示温度，模糊集集 F=0.8/-10+0.5/0+0.1/10F=0.8/-10+0.5/0+0.1/10 G=0.9/-10+0.6/0+0.2/10 G=0.9/-10+0.6/0+0.2/10表示表示“冷冷”和和“比较冷比较冷”，则，则 d(F,G)=0.2×d(F,G)=0.2×（（|0.8-0.9|+|0.5-0.6|+|0.1-|0.8-0.9|+|0.5-0.6|+|0.1-0.2|0.2|））=0.2 ×0.3=0.06=0.2 ×0.3=0.06 匹配度：匹配度：1-1-d(F,G)d(F,G) 语义距离越小，说明两者越相似。 语义距离越小，说明两者越相似 贴近度：指两个概念的接近程度贴近度：指两个概念的接近程度 设设F F和和G G分别是论域分别是论域U={uU={u1 1, u, u2 2, ,… u un n} }上的两个模糊上的两个模糊概念的模糊集，则它们的贴近度定义为概念的模糊集，则它们的贴近度定义为 ( (F,G)= (F F,G)= (F . .G+(1-F⊙G))G+(1-F⊙G)) 其中：其中： F F . .G= ∨(uG= ∨(uF F(u(ui i)∧ u)∧ uG G(u(ui i)) F)) F与与G G的内积的内积 U U F⊙G= ∧(u F⊙G= ∧(uF F(u(ui i)∨ u)∨ uG G(u(ui i)) F)) F与与G G的外积的外积 U U例：论域例：论域U U及其上的模糊集及其上的模糊集F F和和G G如上例，则如上例，则 F F . .G=0.8∧0.9∨0.5∧0.6∨0.1∧0.2∨0∧0∨0∧0G=0.8∧0.9∨0.5∧0.6∨0.1∧0.2∨0∧0∨0∧0 =0.8∨0.5∨0.1∨0∨0=0.8 =0.8∨0.5∨0.1∨0∨0=0.8F⊙G=F⊙G=（（0.8∨0.90.8∨0.9））∧∧（（0.5∨0.60.5∨0.6））∧∧（（0.1∨0.20.1∨0.2））∧∧（（0∨00∨0））∧∧（（0∨00∨0）） =0.9∧0.6∧0.2∧0∧0=0 =0.9∧0.6∧0.2∧0∧0=0（（F,G)=0.5×(0.8+(1-0))=0.5×1.8=0.9F,G)=0.5×(0.8+(1-0))=0.5×1.8=0.9 贴近度越大，说明两者越相似。 贴近度越大，说明两者越相似12 4.4.模糊推理模糊推理模糊推理是按照给定的推理模式通过模糊集的合成来模糊推理是按照给定的推理模式通过模糊集的合成来实现的1 1）模糊关系的构造）模糊关系的构造Ø 模糊关系模糊关系R Rm m 设设F F、、G G分别是分别是U U和和V V上的两个模糊集，则上的两个模糊集，则R Rm m定义为定义为 例：设例：设U=V={1,2,3},FU=V={1,2,3},F和和G G分别是分别是U U和和V V上的两个模糊集，上的两个模糊集， F=1/1+0.6/2+0.1/3F=1/1+0.6/2+0.1/3 G=0.1/1+0.6/2+1/3 G=0.1/1+0.6/2+1/3 则则R Rm m为为 0.1 0.6 1 0.1 0.6 1 R Rm m = 0.4 0.6 0.6 = 0.4 0.6 0.6 0.9 0.9 0.9 0.9 0.9 0.9 Ø模糊关系模糊关系R Rc c 设设F F、、G G分别是分别是U U和和V V上的两个模糊集，则上的两个模糊集，则R Rc c定义为定义为 上例中上例中R Rc c为为 0.1 0.6 1 0.1 0.6 1 R Rc c = 0.1 0.6 0.6 = 0.1 0.6 0.6 0.1 0.1 0.1 0.1 0.1 0.1Ø模糊关系模糊关系R Rg g设设F F、、G G分别是分别是U U和和V V上的两个模糊集，则上的两个模糊集，则R Rg g定义为定义为 其中其中 μμF F(u)→ μ(u)→ μG G(v)= 1 (v)= 1 当当μμF F(u)≤ μ(u)≤ μG G(v)(v) μ μG G(u) (u) 当当μμF F(u)(u)＞＞ μ μG G(v)(v) 上例中上例中R Rg g为为 0.1 0.6 1 0.1 0.6 1 R Rg g = 0.1 1 1 = 0.1 1 1 1 1 1 1 1 1(2(2））模糊推理的基本方法模糊推理的基本方法Ø模糊假言推理模糊假言推理设设F F、、G G分别是分别是U U和和V V上的两个模糊集，且有知识上的两个模糊集，且有知识 IF x is F THEN y is GIF x is F THEN y is G若有若有U U上的一个模糊集上的一个模糊集F F’, ,且且F F可以和可以和F F’匹配，则匹配，则可以推出可以推出 y is Gy is G’，，且且G G’是是V V上的一个模糊集。 上的一个模糊集 表现形式：表现形式： 知识：知识：IF x is F THEN y is GIF x is F THEN y is G 证据：证据：x is Fx is F’ 结论：结论： y is Gy is G’ F F与与G G之间的因果关系为之间的因果关系为R,R,当当F F’可以和可以和F F匹配时，匹配时，则可通过则可通过F F’与与R R的合成得到的合成得到G G’，，即即 G G’=F=F’ R R 例例: :设设U=V={1,2,3},FU=V={1,2,3},F和和G G分别是分别是U U和和V V上的两个模糊上的两个模糊集，集，F=1/1+0.6/2+0.1/3, G=0.1/1+0.6/2+1/3F=1/1+0.6/2+0.1/3, G=0.1/1+0.6/2+1/3 0.1 0.6 1 0.1 0.6 1 R Rm m = 0.4 0.6 0.6 = 0.4 0.6 0.6 0.9 0.9 0.9 0.9 0.9 0.9设有已知事实设有已知事实 x is x is 较小较小并设并设“较小较小”的模糊集为的模糊集为 较小较小=1/1+0.7/2+0.2/3=1/1+0.7/2+0.2/3求在此已知事实下的模糊结论。 求在此已知事实下的模糊结论解：解： 0.1 0.6 1 0.1 0.6 1 G G’=F=F’ R Rm m={1,0.7,0.2} ={1,0.7,0.2} 0.4 0.6 0.60.4 0.6 0.6 0.9 0.9 0.9 0.9 0.9 0.9 ={0.4,0.6,1} ={0.4,0.6,1} 模糊结论模糊结论G G’为为 G G’=0.4/1+0.6/2+1/3=0.4/1+0.6/2+1/3 求求G G’的一般公式：的一般公式： Ø模糊拒取式推理方法模糊拒取式推理方法 设设F F、、G G分别是分别是U U和和V V上的两个模糊集，且有知识上的两个模糊集，且有知识 IF x is F THEN y is GIF x is F THEN y is G 若有若有V V上的一个模糊集上的一个模糊集G G’, ,且且G G可以和可以和G G’匹配，则可以匹配，则可以推出推出 x is Fx is F’，，且且F F’是是U U上的一个模糊集。 上的一个模糊集 表现形式：表现形式： 知识：知识：IF x is F THEN y is GIF x is F THEN y is G 证据：证据： y is Gy is G’ 结论：结论：x is Fx is F’F F与与G G之间的因果关系为之间的因果关系为R,R,当已知模糊事实当已知模糊事实G G’可以和模糊可以和模糊假设假设G G匹配时，则可通过匹配时，则可通过R R 与与G G’的合成得到的合成得到F F’，，即即 F F’= R = R G G’ 例例: :设设U=V={1,2,3},FU=V={1,2,3},F和和G G分别是分别是U U和和V V上的两个模糊上的两个模糊集，集，F=1/1+0.6/2+0.1/3, G=0.1/1+0.6/2+1/3F=1/1+0.6/2+0.1/3, G=0.1/1+0.6/2+1/3 0.1 0.6 1 0.1 0.6 1 R Rc c = 0.1 0.6 0.6 = 0.1 0.6 0.6 0.1 0.1 0.1 0.1 0.1 0.1设有已知事实设有已知事实 y is y is 较大较大并设并设“较大较大”的模糊集为的模糊集为 较大较大=0.2/1+0.7/2+1/3=0.2/1+0.7/2+1/3若已知事实与若已知事实与G G匹配，在此已知事实下推出匹配，在此已知事实下推出F F’。 解：解： 0.1 0.6 1 0.2 1 0.1 0.6 1 0.2 1 F F’= R= Rc cG G’ = = 0.1 0.6 0.6 0.1 0.6 0.6 0.7 = 0.60.7 = 0.6 0.1 0.1 0.1 1 0.1 0.1 0.1 0.1 1 0.1 F F’为为 F F’=1/1+0.6/2+0.1/3=1/1+0.6/2+0.1/3 求求F F’的一般公式：的一般公式： Ø模糊假言三段论推理模糊假言三段论推理 设设F F、、G G、、H H分别是分别是U U、、V V、、W W上的上的3 3个模糊集，且由知识个模糊集，且由知识 IF x is F THEN y is GIF x is F THEN y is G IF y is G THEN z is H IF y is G THEN z is H 可推出可推出 IF x is F THEN z is HIF x is F THEN z is H 表现形式：表现形式： 知识：知识：IF x is F THEN y is GIF x is F THEN y is G 证据：证据：IF y is G THEN z is HIF y is G THEN z is H 结论：结论：IF x is F THEN z is HIF x is F THEN z is H F F与与G G之间的因果关系为之间的因果关系为R R1 1, G, G与与H H之间的因果关系为之间的因果关系为R R2 2, ,则则F F与与H H之间的因果关系可通过之间的因果关系可通过R R1 1与与R R2 2的合成得到的合成得到, ,即即 R R3 3= R= R1 1 。 R R2 2 例例: :设设U=V=W={1,2,3}U=V=W={1,2,3} E=1/1+0.6/2+0.2/3 E=1/1+0.6/2+0.2/3 F=0.8/1+0.5/2+0.1/3 F=0.8/1+0.5/2+0.1/3 G=0.2/1+0.6/2+1/3 G=0.2/1+0.6/2+1/3按按R Rg g求求E×F×GE×F×G上的关系上的关系R.R.解解: :先求先求E×FE×F上的关系上的关系R R1 1 0.8 0.5 0.1 0.8 0.5 0.1 R R1 1 = 1 0.5 0.1 = 1 0.5 0.1 1 1 0.1 1 1 0.1 求求F×GF×G上的关系上的关系R R2 2 0.2 0.6 1 0.2 0.6 1 R R2 2 = 0.2 1 1 = 0.2 1 1 1 1 1 1 1 1 求求E×F×GE×F×G上的关系上的关系R R 0.2 0.6 0.80.2 0.6 0.8 R = R R = R1 1 。 R R2 2= 0.2 0.8 1= 0.2 0.8 1 0.2 1 1 0.2 1 1 3.10 非单调推理• 定义 非单调推理用来处理那些不适合用谓词逻辑表示的知识 它能够较好地处理不完全信息、不断变化的情况以及求解复杂问题过程中生成的假设，具有较为有效的求解效率 3.10.1 缺省推理•定义1：：如果X不知道，那么得结论Y•定义2：：如果X不能被证明，那么得结论Y •定义3：：如果X不能在某个给定的时间内被证明，那么得结论Y 3.10 非单调推理3.10.2 非单调推理系统v正确性维持系统用以保持其它程序所产生的命题 之间的相容性一旦发现某个不相容，它就调出 自己的推理机制，面向从属关系的回溯，并通过 修改最小的信念集来消除不相容 6 6、谓词逻辑表示的应用、谓词逻辑表示的应用 机器人移盒子问题机器人移盒子问题要求：机器人从要求：机器人从c c出发，把出发，把盒子从盒子从a a桌上拿到桌上拿到b b桌上，桌上，返回返回c c处。 处 定义谓词：定义谓词：TABLE(x):xTABLE(x):x是桌子是桌子EMPTY(y):yEMPTY(y):y手中是空的手中是空的AT(y,z):yAT(y,z):y在在z z附近附近HOLDS(y,w):yHOLDS(y,w):y拿着拿着w wON(w,x):wON(w,x):w在在x x桌面上其中：其中：x:{a,b},y:{robot},z:{a,b,c},w:{box}x:{a,b},y:{robot},z:{a,b,c},w:{box} 初始状态：初始状态：AT(robot,c)AT(robot,c)EMPTY(robot) EMPTY(robot) ON(box,a)ON(box,a)TABLE(a)TABLE(a)TABLE(b)TABLE(b)目标状态：目标状态：AT(robot,c)AT(robot,c)EMPTY(robot) EMPTY(robot) ON(box,b)ON(box,b)TABLE(a)TABLE(a)TABLE(b)TABLE(b)目标是把问题的初始状态变换为目标状态，需完成一系目标是把问题的初始状态变换为目标状态，需完成一系列操作每个操作分为条件和动作两部分。 列操作每个操作分为条件和动作两部分条件：必备的先决条件，用谓词公式表示条件：必备的先决条件，用谓词公式表示动作：该操作对问题状态的改变情况，通过在执行该操动作：该操作对问题状态的改变情况，通过在执行该操作前的问题状态中删除和增加相应谓词实现作前的问题状态中删除和增加相应谓词实现本问题中，需要以下三个操作：本问题中，需要以下三个操作： Goto(x,y):Goto(x,y):从从x x到到y y处处 Pickup(x):Pickup(x):从从x x处拿起盒子处拿起盒子 Setdown(x):Setdown(x):在在x x处放下盒子处放下盒子 Goto(x,y)Goto(x,y) 条件：条件： AT(robot,x)AT(robot,x) 动作：删除表：动作：删除表： AT(robot,x)AT(robot,x) 添加表：添加表： AT(robot,y)AT(robot,y) Pickup(x)Pickup(x) 条件：条件：ON(box,x),TABLE(x), ON(box,x),TABLE(x), AT(robot,x),EMPTY(robot)AT(robot,x),EMPTY(robot) 动作：删除表：动作：删除表：EMPTY(robot),ON(box,x)EMPTY(robot),ON(box,x) 添加表：添加表：HOLDS(robot,box)HOLDS(robot,box) Setdown(x)Setdown(x) 条件：条件： AT(robot,x)AT(robot,x),TABLE(x),TABLE(x), , HOLDS(robot,box)HOLDS(robot,box) 动作：删除表：动作：删除表： HOLDS(robot,box)HOLDS(robot,box) 添加表：添加表：EMPTY(robot)EMPTY(robot) ,ON(box,x),ON(box,x) 机器人行动规划问题的求解过程：在检查先决条件是否机器人行动规划问题的求解过程：在检查先决条件是否满足时进行必要的变量代换。 满足时进行必要的变量代换状态状态1 1（初始状态）（初始状态）AT(robot,c)AT(robot,c)EMPTY(robot) EMPTY(robot) ON(box,a)ON(box,a)TABLE(a)TABLE(a)TABLE(b)TABLE(b) 开始开始= = = => Goto(x,y)= = = =>用用c代换代换x,a代换代换y状态状态2 2AT(robot,a)AT(robot,a)EMPTY(robot) EMPTY(robot) ON(box,a)ON(box,a)TABLE(a)TABLE(a)TABLE(b)TABLE(b)状态状态3 3AT(robot,a)AT(robot,a)HOLDS(robotHOLDS(robot，，box) box) TABLE(a)TABLE(a)TABLE(b)TABLE(b) Pickup(x)= = = =>用用a代换代换x Goto(x,y)= = = =>用用a代换代换x,b代换代换y状态状态4 4AT(robot,b)AT(robot,b)HOLDS(robotHOLDS(robot，，box)box)TABLE(a)TABLE(a)TABLE(b)TABLE(b)状态状态5 5AT(robot,b)AT(robot,b)EMPTY(robot) EMPTY(robot) ON(box,b)ON(box,b)TABLE(a)TABLE(a)TABLE(b)TABLE(b) Setdown(x)= = = =>用用b代换代换x Goto(x,y)= = = =>用用b代换代换x,c代换代换y状态状态6 6（目标状态）（目标状态）AT(robot,c)AT(robot,c)EMPTY(robot) EMPTY(robot) ON(box,b)ON(box,b)TABLE(a)TABLE(a)TABLE(b)TABLE(b) 结束结束 。
医疗卫生人才供需分析-详解洞察.docx血液制品管理条例（2016修订）培训解读课件.pptx2024年1月浙江省高考英语真题试卷含答案.pdf岗位价值评估工具-美世2.0PPT课件.ppt2023-2024学年秋季小学三年级上册语文部编版课时练第4课《古诗三首》01（含答案）.doc税收会统核算及相关操作.pptLNG储罐施工关键控制点总结.ppt影视视听语言3色彩光线影调.ppt高级无损检测技术资格人员超声检测培训复习题汇编.docx2024年江苏省南京市建邺区小升初语文试卷（原卷全解析版）.docx电路图与实物图的相互转化课件.ppt医疗影像数据的加密传输与存储-详解洞察.docx
