第3章 推理技术1

1、2022-2-2人工智能12022-2-2人工智能23.1 3.1 消解原理消解原理3.2 3.2 规则演绎系统规则演绎系统3.3 3.3 产生式系统产生式系统3.4 3.4 基于概率的推理基于概率的推理3.5 3.5 可信度方法可信度方法3.6 3.6 证据理论证据理论3.7 3.7 模糊推理模糊推理3.8 3.8 非单调推理非单调推理本章主要内容：2022-2-2人工智能3 上一章中我们讨论了一些简单搜索的基本原理。但上一章中我们讨论了一些简单搜索的基本原理。但对于许多比较复杂的系统和问题，如果采用上一章讨论对于许多比较复杂的系统和问题，如果采用上一章讨论过的搜索方法，那么很难甚至无法使问

2、题获得解决的。过的搜索方法，那么很难甚至无法使问题获得解决的。需要应用一些更先进的推理技术和系统求解这种比较复需要应用一些更先进的推理技术和系统求解这种比较复杂的问题。杂的问题。 所谓推理就是按某种策略由已知判断推出另一判断的所谓推理就是按某种策略由已知判断推出另一判断的思维过程。一般来说，推理都包括两种判断：一种是已思维过程。一般来说，推理都包括两种判断：一种是已知的判断，包括已知的知识和已知事实；另一种是由已知的判断，包括已知的知识和已知事实；另一种是由已知判断推出的新判断，即推理的结论。知判断推出的新判断，即推理的结论。 下面我们首先讨论一下与推理相关的一些概念。下面我们首先讨论一下与推

3、理相关的一些概念。2022-2-2人工智能4推理方式及其分类推理方式及其分类1. 演绎推理、归纳推理、默认推理演绎推理：从一般到特殊。例如三段论。归纳推理：从个体到一般。默认推理：缺省推理，在知识不完全的情况下假设某些条件已经具备所进行的推理。2. 确定性、不确定性推理3. 单调性、非单调推理推出的结论是否单调增加。4. 启发式、非启发式推理所谓启发性知识是指与问题有关且能加快推理进程、求得问题最优解的知识。5. 基于知识的推理、统计推理、直觉推理从方法论的角度划分。2022-2-2人工智能5推理的控制策略推理的控制策略n推理的控制策略主要包括：推理方向、搜索策略、冲突消解策略、求解策略及限制

4、策略。1.、正向推理 正向推理的基本思想是：从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用知识集KS，然后按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实。如此重复进行这一过程，直到求得了所要求的解或者知识库中再无可使用的知识为止。2、 逆向推理 逆向推理的基本思想是：首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需要的证据，则说明原假设不成立，此时需要另作新的假设。2022-2-2人工智能6推理的控制策略（推理的控制策略（2 2）3. 混合推理

5、 先正向后逆向推理 先逆向后正向推理4. 双向推理 正向推理与逆向推理同时进行，且在推理过程中的某一步上“碰头”。5. 求解策略 只求一个解，还是求所有解以及最优解。6. 限制策略 限制推理的深度、宽度、时间、空间等等。2022-2-2人工智能7冲突消解策略冲突消解策略n冲突：多个知识都匹配成功。n在产生式系统中对于正向推理：q多条产生式前件都与已知事实匹配成功q多组不同事实都与同一规则前件匹配成功n对于逆向推理：q多条规则后件都和同一个假设匹配成功q多条规则后件可与多个假设匹配成功n冲突消解的基本思想都是对知识进行排序。2022-2-2人工智能8几种冲突消解策略几种冲突消解策略w按针对性排序

6、前件中条件详细(多)的规则先推。w按已知事实的新鲜性排序新鲜事实(刚得到的局部结论)越多(越新鲜)的规则先推。w按匹配度排序在不确定性匹配中，计算两个知识模式的相似度(匹配度)，并对其排序，相似度高的规则先推。w按领域问题特点排序w按上下文限制排序把规则按照下上文分组，并只能选取组中的规则。w按冗余限制排序冗余知识越少的规则先推。w按条件个数排序条件少的规则先推。2022-2-2人工智能9n所谓模式匹配是指对两个知识模式(例如两个谓词公式、框架片断、语义网络片断)的比较与耦合，及检查这两个知识模式是否完全一致或者近似一致。n按匹配时两个知识模式的相似程度，模式匹配可分为确定性匹配与不确定性匹配

7、。n确定性匹配是指两个知识模式完全一致，或者经过变量代换后变得完全一致。例如：P1:father(李四，李小四) and man(李小四)P2:father(x,y) and man(y)n不确定性匹配是指两个知识模式不完全一致，但是它们的相似程度又在规定的限度内。 模式匹配模式匹配2022-2-2人工智能101、变量代换定义 代换是一个形如t1/x1,t2/x2,tn/xn的有限集合。 其中是t1,t2,tn项； x1,x2,xn是互不相同的变元；ti/xi表示用ti代换xi，不允许ti与xi相同，也不允许变元xi循环地出现在另一个tj中。例如：a/x,f(b)/y,w/z是一个代换g(y)

8、/x,f(x)/y不是代换g(a)/x,f(x)/y是代换2022-2-2人工智能112、代换的复合定义： 设= t1/x1,t2/x2,tn/xn= u1/y1,u2/y2,um/ym是两个代换，则此两个代换的复合也是一个代换，它是从t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,um/ym 中删去如下两种元素： ti/xi当ti=xi ui/yi当yix1,x2,xn 后剩下的元素所构成的集合，记为 。n注： ti表示对ti运用代换。实际上就是对一个公式先运用代换，然后再运用代换。2022-2-2人工智能123、代换的例子例如，设有代换= f(y)/x,z/y= a/x,b/y

9、,y/z则=f(y)/x,z/y,a/x,b/y,y/z=f(b)/x,y/y,a/x,b/y,y/z=f(b)/x,y/z2022-2-2人工智能134、公式集的合一定义： 设有公式集F=F1,F2,Fn，若存在一个代换使得 F1=F2=Fn则称为公式集F的一个合一，且称F1,F2,Fn是可合一的。n例如，设有公式集F=P(x,y,f(y),P(a,g(x),z) 则下式是它的一个合一：=a/x,g(a)/y,f(g(a)/zn一个公式集的合一一般不唯一。定义： 设是公式集F的一个合一，如果对任一个合一都存在一个代换，使得=，则称是一个最一般的合一。n最一般合一是唯一的。2022-2-2人工

10、智能14求取最一般合一n差异集：两个公式中相同位置处不同符号的集合。例如：F1:P(x,y,z), F2:P(x,f(a),h(b) 则D1=y,f(a), D2=z,h(b)求取最一般合一的算法：w令k=0,Fk=F, k=。 是空代换。w若Fk只含一个表达式，则算法停止，k就是最一般合一。w找出Fk的差异集Dk。w若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk中出现，则置：K+1=ktk/xk Fk+1=Fktk/xk k=k+1然后转(2)。若不存在这样的xk和tk则算法停止。1.算法终止，F的最一般合一不存在。2022-2-2人工智能15求取最一般合一的例子例如，

11、设F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般合一。w令F0=F, 0=。 F0中有两个表达式，所以0不是最一般合一。w差异集D0=a,z 。w1=0a/z=a/zwF1=P(a,x,f(g(y),P(a,f(a),f(u) 。wD1=x,f(a) 。w2=1f(a)/x=a/z,f(a)/xwF2=F1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u) 。wD2=g(y),u 。w3=2g(y)/u=a/z,f(a)/x,g(y)/uwF3=F2g(y)/u=P(a,f(a),f(g(y),P(a,f(a),f(g(y) 。因为F3中只有一个表达式

12、，所以就是最一般合一，即1.a/z,f(a)/x,g(y)/u2022-2-2人工智能16 消解原理消解原理是针对谓词逻辑表示的问题进行求解方法，也叫是针对谓词逻辑表示的问题进行求解方法，也叫做做归结原理归结原理。主要内容包括子句集的求取、消解推理的规则。主要内容包括子句集的求取、消解推理的规则和消解反演问题求解方法。和消解反演问题求解方法。消解原理的基础知识：消解原理的基础知识：u谓词公式、某些推理规则以及置换合一等概念。谓词公式、某些推理规则以及置换合一等概念。u在谓词逻辑中，把原子谓词公式及其否定统称为在谓词逻辑中，把原子谓词公式及其否定统称为文字文字。u任何文字的析取式称为任何文字的析

13、取式称为子句子句。 例如：例如： P(x)Q(x), P(x,f(x)Q(x,g(x)u不包含任何文字的子句称为不包含任何文字的子句称为空子句空子句。u空子句不含有文字，不能被任何解释满足，所以空子句是永空子句不含有文字，不能被任何解释满足，所以空子句是永假的，假的，不可满足不可满足的。的。2022-2-2人工智能173.1.1 3.1.1 化为子句集化为子句集 (1)(1)消去蕴涵符号：只应用消去蕴涵符号：只应用和符号，以和符号，以ABAB替换替换A=BA=B。 例如：例如：(2)(2)减少否定符号的辖域：每个否定符号最多只用到一减少否定符号的辖域：每个否定符号最多只用到一个谓词符号上，并反

14、复应用狄个谓词符号上，并反复应用狄摩根定律。例如：上摩根定律。例如：上式经等价变换后式经等价变换后()() ( , )()( ( , )( , )xy P x yy Q x yR x y ()( () ( , )()( , )( , )xy P x yyQ x yR x y ()()( , ) ()( ( , )( , )xyP x yy Q x yR x y 在说明消解过程之前在说明消解过程之前, ,我们首先说明任一谓词演算公式可我们首先说明任一谓词演算公式可以化成一个子句集。其变换过程由下列九个步骤组成：以化成一个子句集。其变换过程由下列九个步骤组成：2022-2-2人工智能18(3)(3

15、)对变量标准化对变量标准化 ：使不同量词约束的变元有不同的名字，：使不同量词约束的变元有不同的名字，通过变量更名来完成。例如，上式经变换后通过变量更名来完成。例如，上式经变换后()()( , ) ()( ( , )( , )xyP x yz Q x zR x z (4)(4)消去存在量词：分两种情况消去存在量词：分两种情况 a a）存在量词不出现在全称量词的辖域内，则只要用一个新）存在量词不出现在全称量词的辖域内，则只要用一个新的个体常量替换受该量词约束的变元。的个体常量替换受该量词约束的变元。 b b）存在量词位于一个或者多个全称量词的辖域内，此时要用）存在量词位于一个或者多个全称量词的辖域

16、内，此时要用SkolemSkolem函数函数f(x1,x2,xn)f(x1,x2,xn)替换受该存在量词约束的变元。替换受该存在量词约束的变元。上式中存在量词上式中存在量词( ( y)y)及及( ( z)z)都位于都位于( ( x)x)的辖域内，所以需要的辖域内，所以需要用用SkolemSkolem函数替换，设替换函数替换，设替换y y和和z z的的SkolemSkolem函数分别是函数分别是f(x)f(x)和和g(x)g(x)，则替换后得到，则替换后得到()( , ( ) ( ( , ( )( , ( )xP x f xQ x g xR x g x3.1.1 3.1.1 化为子句集（化为子句

17、集（2 2） 2022-2-2人工智能19(5)(5)化为前束形化为前束形 ：把所有全称量词移到公式的左边，并使：把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。所得公式称为前束形。 3.1.1 3.1.1 化为子句集（化为子句集（3 3） (6)(6)化为合取范式化为合取范式 ：任何公式都可写成由一些谓词和：任何公式都可写成由一些谓词和( (或或) )谓词的否定的析取的有限集组成的合取式。这种公式谓词的否定的析取的有限集组成的合取式。这种公式叫做合取范式。我们可以反复应用分配律。把任一公叫做合取

18、范式。我们可以反复应用分配律。把任一公式化成合取范式。前面的公式经变换得式化成合取范式。前面的公式经变换得 ()( , ( )( , ( ) ( , ( )( , ( )xP x f xQ x g xP x f xR x g x (7)(7) 消去全称量词消去全称量词 ：到了这一步，所有余下的量词均被：到了这一步，所有余下的量词均被全称量词量化了。同时全称量词的次序也不重要了。全称量词量化了。同时全称量词的次序也不重要了。因此，我们可以消消去全称量词。因此，我们可以消消去全称量词。 2022-2-2人工智能20(8)(8)消去合取词：用消去合取词：用“，”代替符号代替符号，最后得到一个有，最后

19、得到一个有限集，其中每个公式是文字的析取。任一个只由文字限集，其中每个公式是文字的析取。任一个只由文字的析取构成的合式公式叫做一个子句。例如，上式经的析取构成的合式公式叫做一个子句。例如，上式经变换后得变换后得3.1.1 3.1.1 化为子句集（化为子句集（4 4） (9)(9)更换变量名称：使一个变量符号不出现在一个以上的更换变量名称：使一个变量符号不出现在一个以上的子句中子句中。上式在更改变量名后，可以得到子句集：上式在更改变量名后，可以得到子句集：)(,()(,(,)(,()(,(xgxRxfxPxgxQxfxP)(,()(,(,)(,()(,(ygyRyfyPxgxQxfxP2022-

20、2-2人工智能21定义：定义：设设L1L1为任一原子公式，为任一原子公式，L2L2为另一原子公式，且具为另一原子公式，且具有相同的谓词符号，但一般具有不同的变量。已知两有相同的谓词符号，但一般具有不同的变量。已知两子句子句L1L1和和L2L2，如果，如果L1L1和和L2L2具有最一般合一具有最一般合一者者，那么通过消解可以从这两个父辈子句推导出一，那么通过消解可以从这两个父辈子句推导出一个新子句个新子句()()。这个新子句叫做。这个新子句叫做消解式消解式。它是。它是由取这两个子句的析取，然后消去互补对而得到的。由取这两个子句的析取，然后消去互补对而得到的。如：如： 3.1.2 3.1.2 消解

21、推理规则消解推理规则 a)假言推理假言推理b)合并合并2022-2-2人工智能22c)重言式重言式d)重言式重言式e)三段论三段论f)空子句（矛盾）空子句（矛盾） 从以上各例可见，消解可以合并几个运算为一简从以上各例可见，消解可以合并几个运算为一简单的推理规则。单的推理规则。 2022-2-2人工智能23定理定理 若C12是子句C1与C2的消解式，则C12是C1与C2逻辑结论。证明：设 C1=LC1, C2=LC2, 则C12=C1C2111222()()1212()()12121212121212CCLCLCLCLCCCCLLCCLLCCCCCCCCCCC 由 假 言 三 段 论消解推理规则

22、的正确性消解推理规则的正确性 2022-2-2人工智能24推论推论1 设C1与C2是子句集S中的两个子句，C12是它们的消解式。若用C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性，即 S1的不可满足性S的不可满足性推论推论2 设C1与C2是子句集S中的两个子句，C12是它们的消解式。若把C12加入S中得到新子句集S2，则S与S2在不可满足的意义上是等价的，即S2的不可满足性S的不可满足性两个推论两个推论 2022-2-2人工智能25 为了对含有变量的子句使用消解规则，必须找到一为了对含有变量的子句使用消解规则，必须找到一个置换，作用于父辈子句使其含有互

23、补文字。个置换，作用于父辈子句使其含有互补文字。 消解两个子句时，可能有一个以上的消解式。不过，在消解两个子句时，可能有一个以上的消解式。不过，在任何情况下，它们最多具有有限个消解式。作为例子，我们任何情况下，它们最多具有有限个消解式。作为例子，我们考虑两个子句考虑两个子句: : Py,f(y) 进一步消解得消解式为: Px,f(A)Px,f(y)Py,f(A) 那么得到消解式: Q(y)，Q(z) 如果取 Pz,f(y)Q(z)Q(y) 那么得到消解式: Px,f(A)，Pz,f(A) 如果取 Px,f(A)Px,f(y)Q(y) 和 Pz,f(A)Q(z)2022-2-2人工智能261 基

24、本思想基本思想 把要解决的问题作为一个要证明的命题，其目标公式被否定并化把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去成子句形，然后添加到命题公式集中去, ,把消解反演系统应用于联合把消解反演系统应用于联合集，并推导出一个空子句集，并推导出一个空子句(NIL)(NIL)，产生一个矛盾，这说明目标公式的，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决。这与否定式不成立，即有目标公式成立，定理得证，问题得到解决。这与数学中反证法的思想十分相似。数学中反证法的思想十分相似。 2 2 消解反演消解反演给出一个公式集给出一

25、个公式集S S和自标公式和自标公式L L，通过反证或反演来求证目标公式，通过反证或反演来求证目标公式L L，其证明步骤如下：，其证明步骤如下： (1) (1)否定否定L L，得，得L L； (2)(2)把把L L添加到添加到S S中去；中去； (3)(3)把新产生的集合把新产生的集合L L，S S化成子句集；化成子句集； (4)(4)应用消解原理，力图推导出一个表示矛盾的空子句应用消解原理，力图推导出一个表示矛盾的空子句NILNIL。 3.1.3 3.1.3 消解反演求解过程消解反演求解过程 2022-2-2人工智能27(3) 消解反演举例消解反演举例 下面举个例子来说明消解反演过程： 前提：

26、每个储蓄钱的人都获得利息。 结论：如果没有利息，那么就没有人去储蓄钱。证明：令S(x,y)表示x储蓄y , M(x)表示“x是钱”， I(x)表示“x是利息”， E(x,y)表示x获得y 于是上述命题写成下列形式：结论：2022-2-2人工智能28用化为子句集方法，可把前提化为下列的子句集：S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x)其中，f(x)为Skolem函数。 而结论的否定可化为： L =I(z),S(a,b),M(b)把 L添加到S中去，得 S=L，S，即： S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x),I(z),S(a,b),

27、M(b)该消解反演可以表示为一棵反演树，如下图所示。 2022-2-2人工智能29(4) 反演求解过程反演求解过程用反演树求取对某个问题的答案，其过程如下：把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。用根部的子句作为一个回答语句。 答案求取涉及到把一棵根部有NIL的反演树变换为在根部带有可用作答案的某个语句的一颗证明树。由于变换关系涉及到把由目标公式的否定产生的每个子句变换为一个重言式，所以被变换的证明树就是一棵消解的证明树，其在根部的语句在逻辑上遵循公理加上重言式，因而也单独地遵循公理。因此被变换的证明树本身

28、就证明了求取办法是正确的。2022-2-2人工智能30下面通过一个简单的例子说明消解反演求解过程“如果无论约翰(John)到哪里去，菲多(Fido)也就去那里，那么如果约翰在学校里，菲多在哪里呢?” 这个问题说明了两个事实，然后提出一个问题，而问题的答案大概可从这两个事实推导出。这两个事实可以解释为下列公式集S：),(),()(xFidoATxJohnATx),(SchoolJohnAT 求解的目标为：),()(xFidoATx 如果我们首先证明目标公式在逻辑上遵循S，然后寻求一个存在x的例，那么就能解决“菲多在哪里”的问题。关键想法是把问题化为一个包含某个存在量词的目标公式，使得此存在量词量

29、化变量表示对该问题的一个解答。2022-2-2人工智能31对本例应用消解反演求解过程，我们有：(1)目标公式否定的子句形式为 :AT(Fido,x)，把它添加至目标公式的否定之否定的子句中去，得到重言式 ：AT(Fido,x)AT(Fido,x)(2) 用反演树进行消解，并在根部得到子句: AT (Fido，School) (3) 从根部求得答案AT(Ffido，School) 2022-2-2人工智能32 (5) 消解策略消解策略消解的一般过程：消解的一般过程：设子句集S=C1,C2,Cn，则消解的一般过程是：S内任意子句两两逐一进行归结，得到一组归结式，称为第一级归结式，记为S1。把S与S

30、1内的任意子句两两逐一进行归结，得到一组归结式，称为第二级归结式，记为S2。S和S1内的子句与S2内的任意子句两两逐一进行归结，得到一组归结式，称为第三级归结式，记为S3。1.如此继续，直到出现了空子句或者不能再继续归结为止。2022-2-2人工智能33 可以通过一些策略来提高消解推理的效率，这些策略称为消解策略。策略可分为两大类：1、删除策略：删除某些无用的子句来缩小归结的范围。2、限制策略：通过对参加归结的子句进行种种限制，尽可能减小归结的盲目性，使其尽快地归结出空子句。2022-2-2人工智能34n纯文字删除法 如果某文字L在子句集中不存在可与之互补的文字L，则称该文字为纯文字。包含纯文

31、字的子句可以删除。n重言式删除法 如果一个子句中同时包含互补文字对，则该字句称为重言式。重言式是永远为真的子句，可以删除。n包孕删除法 设有子句C1和C2，如果存在一个代换，使得： C1C2 ，则称C1包孕于C2。此时把包孕的子句C2删除，不会影响子句集的不可满足性。删除策略删除策略2022-2-2人工智能35n支持集策略 限制：每一次归结时，亲本子句中至少有一个是由目标公式的否定所得到的子句，或者是它们的后裔。可以证明，支持集策略是完备的。n线性输入策略 限制：参加归结的两个子句中必须至少有一个是初始子句集中的子句。线性输入策略是不完备的。n单文字子句策略 限制：参加归结的两个子句中必须至少

32、有一个是单文字子句。单文字子句策略是不完备的。n祖先过滤策略 限制：参加归结的子句满足：(1)C1和C2中至少有一个是初始子句集中的子句。或(2)C1和C2中一个是另外一个的祖先子句。祖先过滤策略是完备的。限制策略限制策略2022-2-2人工智能36 对于许多公式来说，子句形是一种低效率的表达式，因对于许多公式来说，子句形是一种低效率的表达式，因为一些重要信息可能在求取子句形过程中丢失。本节将研究为一些重要信息可能在求取子句形过程中丢失。本节将研究采用易于叙述的采用易于叙述的if-then(if-then(如果如果- -那么那么) )规则来求解问题。规则来求解问题。 在所有基于规则系统中，每个

33、if可能与某断言集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rule based deduction system)。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。 基于规则的演绎系统和产生式系统，均有正向推理和逆向推理两种推理方式。2022-2-2人工智能371.事实表达式的与或形变换事实表达式的与或形变换在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换

34、为叫做与或形的非蕴涵形式。要把一个公式化为与或形，可采用下列步骤： 3.2.1 3.2.1 规则正向演绎系统规则正向演绎系统 n利用(W1W2)和(W1W2)的等价关系，消去符号(如果存在该符号的话)。实际上，在事实中间很少有符号出现，因为可把蕴涵式表示为规则。n用狄摩根定律把否定符号移进括号内，直到每个否定符号的辖域最多只含有一个谓词为止。n对所得到的表达式进行Skolem化和前束化。n对全称量词辖域内的变量进行改名和变量标准化，而存在量词量化变量用Skolem函数代替。n删去全称量词，而任何余下的变量都被认为具有全称量化作用。2022-2-2人工智能38例如，有事实表达式 对变量更名标准化

35、，使得同一变量不出现在事实表达式的不同主要合取式中。更名后得表达式： Q(w,A)R(v)P(v)S(A,v) 必须注意到Q(v,A)中的变量v可用新变量w代替，而合取式R(v)P(v)中的变量v却不可更名，因为后者也出现在析取式S(A,v)中。把它可化为：Q(v,A)R(v)P(v)S(A,v) ),()()(),()(vuSvPvRuvQvu 与或形表达式是由符号和连接的一些文字的子表达式组成的。呈与或形的表达式并不是子句形，而是接近于原始表达式形式，特别是它的子表达式不是复合产生的。2022-2-2人工智能392. 事实表达式的与或图表示事实表达式的与或图表示 将上例与或形的事实表达式用

36、与或图来表示。 表示某个事实表达式的与或图的叶节点均由表达式中的文字来标记。图中标记有整个事实表达式的节点，称为根节点，它在图中没有祖先。 注意与或标记与普通与或图的区别2022-2-2人工智能403. 与或图的与或图的F规则变换规则变换 把允许用作规则的公式类型限制为下列形式： LW 式中：L是单文字；W为与或形的唯一公式。 把形式为L W的规则应用到任一个具有叶节点n并由文字L标记的与或图上，可以得到一个新的与或图。在新的图上，节点n由一个单线连接符接到后继节点(也由L标记)，它是表示为W的一个与或图结构的根节点。例如，把规则S =(XY)Z应用于图1中标有S的叶节点上。所得到的新与或图结

37、构表示于图2。图图1图图22022-2-2人工智能41 4. 目标公式与终止条件目标公式与终止条件 在正向演绎系统中，要求目标公式用子句来表示，即文字的析取形式。可用用文字集表示此目标公式 。 当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止。 例如：已知事实：AB 规则：A=CD，B=EG 目标: CG 推理过程如图所示。2022-2-2人工智能42 基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实的操作过程，从then到if的推理过程。 1. 目标表达式的与或形式目标表达式的与或形式 逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事

38、实表达式同样的过程，把目标公式化成与或形。即消去蕴涵符号，把否定符号移进括号内，对全称量词Skolem化并删去存在量词。留在目标表达式与或形中的变量假定都已存在量词量化。 3.2.2 3.2.2 规则逆向演绎系统规则逆向演绎系统 设目标表达式被化成与或形：P(f(y)Q(f(y),y)P(f(y)S(y) 式中，f(y)为一Skolem函数。对目标的主要析取式中的变量分离标准化可得 P(f(z)Q(f(y),y)P(f(y)S(y) )()(),()()(ysxPyxQxPxy2022-2-2人工智能43 与或形的目标公式也可以表示为与或图。不过，与事实表达式的与或图不同的是，对于目标表达式，

39、与或图中的k线连接符用来分开合取关系的子表达式。 上面所用的目标公式的与或图如图所示 2022-2-2人工智能44 B规则是建立在确定的蕴涵式基础上的，正如正向系统的F规则一样。不过，在正向演绎系统中把这些B规则限制为： W=L 其中，W为任一与或形公式，L为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。 其次，把B规则限制为这种形式的蕴涵式还可以简化匹配，使之不会引起重大的实际困难。 此外，可以把像W =(L1L2)这样的蕴涵式化为两个规则W=L1和W= L2。 2. 与或图的与或图的B规则变换规则变换2022-2-2人工智能45 逆向系统中的事实表达式均限制为文字合取形，它可以表示为一

40、个文字集。 逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。 3.事实表示与终止条件事实表示与终止条件 已知事实：F1: DOG(FIDO)；狗的名字叫 Fido F2: BARKS(FIDO)；Fido是不叫的 F3: WAGS TAIL(FIDO)；Fido摇尾巴 F4: MEOWS(MYRTLE)；猫咪的名字叫Myrtle 规则： R1: WAGS TAIL(x1)DOG(x1)= FRIENDLY(x1)； R2: FRIENDLY(x2)BARKS(x2)=AFRAID(y2,x2)； R3: DOG(x3)= ANIMAL(x3)；狗为动物 R4: CAT(x4

41、) =ANIMAL(x4)；猫为动物 R5: MEOWS(x5) =CAT(x5)；猫咪是猫 问题：是否存在这样的一只猫和一条狗，使得这只猫不怕这条狗? 2022-2-2人工智能46用目标表达式表示此问题为: CAT(x)DOG(y)AFRAID(x,y) 我们就得到该问题的回答语句为： CAT(MYRTLE)DOG(FIDO) AFRAID(MYRTLE,FIDO)2022-2-2人工智能47 正向演绎系统能够处理任意形式的if表达式，但被限制在then表达式为由文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式。我们希望能

42、够构成一个组合的系统，使它具有正向和逆向两系统的优点，以求克服各自的缺点(局限性)。 正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图最初用来表示给出的事实和目标的某些表达式集合，现在这些表达式的形式不受约束。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。 组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。 3.2.3 3.2.3 双向演绎系统双向演绎系统 2022-2-2人工智能48 产生式系统产生式系统(production system)首先是由波斯特首先是由波斯特(P

43、ost)于于1943年提出的产生式规则年提出的产生式规则(production rule)而得名的。他们用这种规则而得名的。他们用这种规则对符号串进行置换运算。后来，美国的纽厄尔和西蒙利用这个原对符号串进行置换运算。后来，美国的纽厄尔和西蒙利用这个原理建立一个人类的认知模型理建立一个人类的认知模型(1965年年)。同时，斯坦福大学利用产。同时，斯坦福大学利用产生式系统结构设计出第一个专家系统生式系统结构设计出第一个专家系统DENDRAL。产生式系统用来描述若干个不同的以一个基本概念为基础的产生式系统用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的

44、概系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。在产生式系统中，论域的知识分为两部分：用事实表示静态念。在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统把此类系统称为基于规则的系统(rule based system)。 2022-2-2人工智能49 产生式系统由产生式系统由3 3个部分组成，即总数据库个部分组成，即总数据库( (或全局数据库或全局数据库) )、产、产生式规则和控制策略。各部分间的关系如图所示。生式规则和控制策略。各部分间的关系如图所示。 3.3.1 3.3.1