Xie-AI-第4章-推理技术(1).ppt

1、主 讲：谢 榕 武汉大学国际软件学院第四章第四章 知识推理技术知识推理技术内容提要：知识推理技术概述消解原理例：储蓄问题规则演绎系统例：猎犬问题不确定性推理知识推理技术的运用知识推理技术进一步研究4.1 4.1 知识推理技术概述知识推理技术概述u什么是知识推理(Knowledge Inference) ？在计算机或智能机器中，在知识表示的基础上，利用形式化的知识模型(与问题有关的知识的符号体系)，进行机器思维，求解问题，从而实现知识推理的智能操作过程。u智能系统的推理过程是通过推理机来完成的。所谓推理机推理机就是智能系统用来实现推理的那些程序。4.1.1 4.1.1 推理的概念推理的概念u所谓

2、推理推理是指按照某种策略从已知事实出发去推出结论的过程。u推理所用的事实可分为两种：p与求解问题有关的初始证据p推理过程中所得到的中间结论例：医疗诊断专家系统例：医疗诊断专家系统u所有与诊断有关的医疗常识和专家经验都被保存在知识库中。u系统开始诊断疾病时，首先把病人症状和检查结果放到事实库中，再从事实库中的这些初始证据出发，按照某种策略在知识库中寻找可以匹配的知识。u如果得到的是一些中间结论，则把它们作为已知事实放入事实库中，并继续寻找可以匹配的知识，如此反复，直到推出最终结论为止。u智能系统的推理包括两个基本问题：p推理的方法p推理的控制策略4.1.2 4.1.2 推理的方法及其类型推理的方

3、法及其类型u可以有多种方法对推理进行分类按推理的逻辑基础分类按知识的确定性分类按推理过程的单调性推理1.1.按推理的逻辑基础分类按推理的逻辑基础分类u按照推理的逻辑基础，推理方法分为p演绎推理p归纳推理演绎推理演绎推理u从已知的一般性知识出发，推理出适合于某种个别情况的结论的过程，即一般到个别的推理。例如，有如下三个判断：（1）理工科学生都要学习高等数学；(大前提)（2）刘永丰是一名理工科学生；(小前提)（3）刘永丰要学习高等数学。 (结论)这就是一个典型的三段论推理。利用已知的大前提利用已知的大前提(一般性知识一般性知识)和小和小前提（某个具体实例的判断前提（某个具体实例的判断)经过推理得到

4、结论。经过推理得到结论。u最常见演绎推理形式是三段论，包括大前提大前提、小小前提前提和结论结论三个部分。 大前提：已知一般性知识或推理过程可以得到的判断 小前提：关于某种具体情况或某个具体实例的判断 结论：由大前提推出的，并且适合于小前提的判断归纳推理归纳推理u从大量特殊事例出发，归纳出一般性结论的推理过程，是一种由个别到一般的推理方法。例：人们为什么会发现能治好某种疾病的药草呢？例：人们为什么会发现能治好某种疾病的药草呢？ 先人无数次（成功的或失败的）经验积累的。由于某一种草无意中治好了某一种病，第二次、第三次，.都治好了这一种病，于是人们就把这几次经验积累起来，做出结论：这种药草能治好某一

5、种病。这样，一次次个别个别经验性的认识就上升到一般性认识经验性的认识就上升到一般性认识。u基本思想基本思想：先从已知事实件猜测出一个结论，然后对该结论的正确性加以证明确认。典型例子:数学归纳法归纳推理归纳推理u按照所选事例的广泛性可分为：u完全归纳推理完全归纳推理 归纳时考察相应事物的全部对象考察相应事物的全部对象，并根据这些对象是否具有某种属性来推出该类事物是否具有属性的过程。u不完全归纳推理不完全归纳推理 归纳时只考察相应的部分对象只考察相应的部分对象，就得出关于该事物的结论的过程。p例如，某公司购进一批计算机，如果对每台机器都进行了质量检验并且都合格，则可得出结论：这批计算机的质量是合格

6、的。p例如，某公司购进一批计算机后，只是随机地抽查了其中部分机器，并根据这些机器的质量来推出整批的质量 完全归纳 不完全归纳2.2.按所用知识的确定性分类按所用知识的确定性分类u按照推理时所用知识的确定性，可分为u确定性推理（精确推理）确定性推理（精确推理）推理时所用知识和推出的结论都是可以精确表示的，真值为真或为假，不会有第三种情况出现。u不确定性推理（不精确推理）不确定性推理（不精确推理）推理时所用知识和推出的结论不都是完全确定的，其真值位于真和假之间。u人们通常是在知识不完全、不精确情况下进行多方思考及推理的，不确定性推理是人工智能一个不确定性推理是人工智能一个重要研究课题。重要研究课题

7、。 确定性推理不确定性推理3.3.按推理过程的单调性分类按推理过程的单调性分类u按照推理过程中推出的结论是否越来越接近最终目标来分类，可分为：u单调推理单调推理在推理过程中，不会由于新知识的加入而否定前不会由于新知识的加入而否定前面推出的结论面推出的结论而使得推理过程又退回到前面的某一步。u非单调推理非单调推理在推理过程中，当某些新的知识加入后，随着推理的向前推进，会否定原来推出的结论，使得推推理过程退回到先前一步理过程退回到先前一步，重新开始。 单调推理 非单调推理u非单调推理至少在以下场合可以使用。 信息缺乏信息缺乏。在问题求解之前，因信息缺乏先对情况作假设再对假设进行修正。 非完全知识库

8、非完全知识库。随着知识的不断获取，知识数目渐增，则可能出现非单调现象。 动态变化的知识库动态变化的知识库。例如，设初始知识库有规则：所有的鸟都能飞 x(bird(x)fly(x)又得到以下事实：鸵鸟是一种鸟 bird(ostrich)如果将该知识加入知识库，出现矛盾，因为鸵鸟不会飞。这就需要对原来的知识进行修改。常用推理技术常用推理技术u搜索推理u消解反演求解u规则演绎系统u产生式系统u系统组织技术u不确定性推理u非单调推理4.2 4.2 消解原理消解原理u在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。u定理证明的实质就是要对前提前提P P和结论结论Q Q，证明P PQ Q永真永真

9、。如何证明PQ永真？证明PQ在任何一个非空的个体域上都是永真的。u采用反证法反证法的思想。把关于永真性的证明转化为关于不可满足性的证明。即要证明PQ永真，只要能够证明P P Q Q是不可满足不可满足的。4.2 4.2 消解原理消解原理u最有成效的工作是HerbrandHerbrand理论理论和RobinsonRobinson归结归结原理原理。u归结原理或称消解原理（resolution principle） J.A.Robinson于1965年在Herbrand理论的基础上提出的一种基于逻辑的“反证法反证法”。 Robinson归结原理使定理证明的机械化成为现实。uHerbrand定理为自动定

10、理证明奠定了理论基础，从理论上给出证明子句集不可满足性的可行性和方法，但要在计算机上实现其证明过程却是非常困难的。u什么是消解消解？一种可用于一定的子句公式的重要推理规则。u消解过程就是如何从合式表达的母体中，导出一组子导出一组子句集句集。 例如，如果存在某个公理E1E2和另一公理E2E3，那么E1E3在逻辑上成立，这就是消解。 E1E3称为E1E2和E2E3的消解式(resolvent)。u一子句子句（clause）定义为由文字(一个原子公式和原子公式的否定)的析取析取“ ”组成的公式。当消解可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。消解反演求解过程消解反演求解过程Step

11、 1：子句集的求取Step 2：运用消解推理规则Step 3：对含有变量的子句运用消解推理规则Step 4：对问题进行消解反演求解谓词公式谓词公式u等价关系(Equivalence)如果两个合式公式，无论如何解释，其真值表都是相同的,那么我们就称此两个合式公式是等价等价的的。u等价关系等价关系(Equivalence)(Equivalence)p 否定之否定否定之否定 (P) 等价于 Pp PQ 等价于 P=Qp 狄狄. .摩根定律摩根定律(PQ) 等价于 PQ(PQ) 等价于 PQp 分配律分配律P(QR) 等价于 (PQ)(PR)P(QR) 等价于 (PQ)(PR)u交换律交换律PQ 等价

12、于 QPPQ 等价于 QPu结合律结合律(PQ)R 等价于 P(QR)(PQ)R 等价于 P(QR)u逆否律逆否律P = Q 等价于 Q = Pu其它等价关系其它等价关系(x)P(x) 等价于（x)P(x)(x)P(x) 等价于（x)P(x)（x）P(x)Q(x) 等价于（x）P(x)(x)Q(x）（x）P(x)Q(x) 等价于（x）P(x)（x）Q(x) （x)P(x) 等价于（y)P(y) （x)P(x) 等价于（y)P(y) 4.2.1 4.2.1 子句集的求取子句集的求取u任一谓词演算公式可以化成一个子句集。u变换过程由下列九个步骤组成。pStep 1: 消去蕴涵符号pStep 2:

13、减少否定符号的辖域pStep 3: 对变量标准化pStep 4: 消去存在量词pStep 5: 化为前束形pStep 6: 把母式化为合取范式pStep 7: 消去全称量词pStep 8: 消去连词符号 pStep 9: 更换变量名称uStep 1Step 1: 消去蕴涵符号只使用和符号，AB 等价于AB。uStep 2Step 2: 减少否定符号的辖域每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(AB) 等价于 AB(AB) 等价于 AB(x)A 等价于 (x)A(x)A 等价于 (x)A(A) 等价于 AuStep 3Step 3: 对变量标准化 在任一量词辖域内，受该量词

14、约束的变量为一哑元(虚构 变量)，它可以在该辖域内处统一地被另一个没有出现 过的任意变量所代替，而不改变公式的真值。(x)P(x)(x)Q(x) 经标准化而得到: (x)P(x)(y)Q(y)uStep 4Step 4: 消去存在量词用SkolemSkolem函数代替存在量词内的约束变量，可消去存在量词。规则规则1 1： Skolem函数以一个Skolem函数代替每个出现存在量词的量化变量；Skolem函数的变量由全称量词所约束的全称量词量化变量；全称量词辖域包括要被消去的存在量词的辖域在内。例如，(y)(x)P(x,y)被(y)P(g(y),y)代替，其中g(y)为Skolem函数规则规则2

15、 2：如果要消去的存在量词不在任何一个全称量词的辖域，就用不含变量的Skolem函数即常量。例如，(x)P(x)可被P(A)代替，其中常量符号A用来表示人们知道的存在实体。uStep 5Step 5: 化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分，所得公式称为前束形。 前束形公式由前缀和母式组成，前缀由全称量词串组成，母式由没有量词的公式组成，即前束形 = (前缀) (母 式) 全称量词串 无量词公式u Step 6Step 6: 把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。 反复应用分配律，把

16、任一母式化成合取范式。ABC 化为 ABACuStep 7Step 7: 消去全称量词消去前缀，即消去明显出现的全称量词。u Step 8Step 8: 消去连词符号 (AB)(AC)等价于(AB), (AC)u Step 9Step 9: 更换变量名称 更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。P(x)P(y)Pf(x,y), P(x)Qx,g(x),P(x)Pg(x)P(x1)P(y)Pf(x1,y),P(x2)Qx2,g(x2),P(x3)Pg(x3)4.2.1 4.2.1 子句集的求取子句集的求取u任一谓词演算公式可以化成一个子句集。u变换过程由下列九个步骤组成。pS

17、tep 1: 消去蕴涵符号pStep 2: 减少否定符号的辖域pStep 3: 对变量标准化pStep 4: 消去存在量词pStep 5: 化为前束形pStep 6: 把母式化为合取范式pStep 7: 消去全称量词pStep 8: 消去连词符号 pStep 9: 更换变量名称经上述步骤，可将谓词公式化简为一个标准子句集标准子句集。举例说明举例说明u 将将( ( x)P(x)x)P(x)( y)P(y)y)P(y)P(f(x,y)P(f(x,y)( ( y)Q(x,y)y)Q(x,y)P(y)P(y)化为子句集。化为子句集。1.1.消去蕴含符号消去蕴含符号(x)P(x)(y)P(y)P(f(x

18、,y)(y)Q(x,y)P(y)2.2.减少否定符号的辖域减少否定符号的辖域(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)3.3.重新命名变量名，使变量标准化重新命名变量名，使变量标准化(x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w)4.4.消去存在量词消去存在量词(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)P(g(x), w=g(x)为一个Skolem函数5.5.化为前束形化为前束形(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)6.6.

19、把母式化为合取范式把母式化为合取范式(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)7.7.消去全称量词消去全称量词P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)8.8.消去连接词消去连接词 P(x)P(y)P(f(x,y),P(x)Q(x,g(x),P(x)P(g(x)9.9.更改变量名更改变量名 P(x1)P(y)P(f(x1,y),P(x2)Q(x2,g(x),P(x3)P(g(x3) 课堂练习课堂练习 I Iu将下列谓词公式化为相应的子句集1.(x)(y)(P(x,y)Q(x,y)2.(x)(y)(z)(P(x,y)

20、Q(x,y)R(x,z)u将下列谓词公式化为相应的子句集 (x)(y)(P(x,y)Q(x,y)u解：将谓词公式(x)(y)(P(x,y)Q(x,y)化为Skolem标准型。(1)消去符号(x)(y)(P(x,y)Q(x,y)(2)将母式化为子句集。 S=P(x,y)Q(x,y)u将下列谓词公式化为相应的子句集(x)(y)(z)(P(x,y)Q(x,y)R(x,z)u解：将谓词公式(x)(y)(z)(P(x,y)Q(x,y)R(x,z)化为Skolem标准型。(1)消去符号(x)(y)(z)(P(x,y)Q(x,y)R(x,z)(2)消去存在量词，用Skolem函数f(x,y)代替z。(x)(

21、y)(P(x,y)Q(x,y)R(x,f(x,y)(3)消去全称量词，并将母式化为子句集。 S=P(x,y)Q(x,y)R(x,f(x,y)4.2.2 4.2.2 消解推理规则消解推理规则u令L1为任一原子公式，L2为另一原子公式；L1和L2具有相同谓词符号，但一般具有不同的变量。u已知两子句L1L1和L2L2u如果L1和L2具有最一般合一合一者，则通过消解可从这两个父辈子句推导出一个新子句()()。u该新子句叫做消解式消解式,它由这两个子句的析取，然后消去互补对而得到的。置换置换u置换置换p 假元推理假元推理，是由合式公式W1和W1W2产生合式公式W2的运算。p 全称化推理全称化推理，是由合

22、式公式(x)W(x)产生合式公式W(A)，其中A为任意常量符号。u举例：表达式Px，f(y)，B的一个置换为s1=z/x，w/y，则Px，f(y)，Bs1 = Pz，f(w)，B一个表达式的置换就是在该表达式中用置换项置换变量。合一合一u合一合一p 寻找项对变量的置换，以使两表达式一致，叫做合一。如果一个置换s作用于表达式集Ei的每个元素，则用Eis来表示置换例的集。称表达式集Ei是可合一的。如果存在一个置换s使得：E1s=E2s=E3s=那么称此s为Ei的合一者，因为s的作用是使集合Ei成为单一形式。u 举例：表达式Px，f(y)，B和表达式Px，f(B)，B的合一者p 表达式Px，f(y)

23、，B的一个置换为s=A/x，B/y，则 Px，f(y)，Bs = PA，f(B)，Bp 表达式Px，f(B)，B的一个置换为s=A/x，B/y，则：Px，f(B)，Bs = PA，f(B)，B , s为二者的合一者。从父辈子句求消解式从父辈子句求消解式u重言式重言式u链式链式( (三段论三段论) )u空子句空子句( (矛盾矛盾) )u假言推理假言推理u合并合并u 计算下述各子句对的归结式。(1)C1:PR, C2:PQ(2)C1:PQ, C2:P(3)C1:PQR, C2:QR(4)C1:PQ, C2:PR(5)C1:Q, C2:Q课堂练习课堂练习 IIIIu计算下述各子句对的归结式。(1)C

24、1:PR, C2:PQ(2)C1:PQ, C2:P(3)C1:PQR, C2:QR(4)C1:PQ, C2:PR(5)C1:Q, C2:Qu解：(1)RQ(2)Q(3)PRR, PQQ(4)C1和C2不存在归结式。(5)空子句4.2.3 4.2.3 含有变量的消解式含有变量的消解式u对子句的消解推理规则可推广到含有变量的子句。4.2.4 4.2.4 消解反演求解过程消解反演求解过程u由谓词公式转化为子句集，子句集中子句之间是合取关系。只要有一个子句为不可满足,则整个子句集就是不可满足的。空子句是不可满足的，因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。uRobinson归结

25、原理就是基于上述认识提出来的。u基本思想: 把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去,把消解反演系统应用于联合集，并推导出一个空子句(NIL)，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决。这与数学中反证法的思想十分相似。消解反演消解反演u给出一个公式集公式集S S和目标公式目标公式L L，通过反证或反演来求证目标公式L。L L 证明步骤为：Step1:否定L，得LStep2:把L添加到S中去Step3:把新产生的集合L，S化成子句集Step4:应用消解原理，推导出一个表示矛盾的空子句NIL反演求解的举例

26、：储蓄问题反演求解的举例：储蓄问题u前提前提：每个储蓄钱的人都获得利息。u结论结论：如果没有利息，那么就没有人去储蓄钱。u前提前提：每个储蓄钱的人都获得利息。u结论结论：如果没有利息，那么就没有人去储蓄钱。u证明过程：Step1Step1: 令S(x,y)表示x储蓄y M(x)表示x是钱I(x)表示x是利息E(x,y)表示x获得y”Step2Step2:上述命题写成下列形式： 上述结论写成下列形式：Step3Step3:用子句集求取九步法，把前提和结论化为下列的子句集：其中，y=f(x)为Skolem函数。u前提前提：每个储蓄钱的人都获得利息。u结论结论：如果没有利息，那么就没有人去储蓄钱。结

27、论的否定为：Step4Step4: 按以下4个步骤来对问题进行反演求解：(1)否定L，即有 L I(z),S(a,b),M(b)(2)把 L添加到S中去，即 (3)把新产生的集合S化成子句集,即 (4)应用消解原理，力图推导出一个表示矛盾的空子句NIL。图: 储蓄问题反演树u因此，储蓄问题的结论获得证明储蓄问题的结论获得证明。u前提前提：每个储蓄钱的人都获得利息。u结论结论：如果没有利息，那么就没有人去储蓄钱。u该消解反演可以表示为一棵反演树。u已知：A:(x)(y)(P(x,y)Q(y) (y)(R(y)T(x,y)B:(x)R(x)(x)(y)(P(x,y)Q(y)求证: B是A的逻辑结论

28、。课堂练习课堂练习 IIIIIIu已知：A:(x)(y)(P(x,y)Q(y) (y)(R(y)T(x,y)B:(x)R(x)(x)(y)(P(x,y)Q(y)求证: B是A的逻辑结论。u 证明：首先将A和B化为子句集（1）P(x,y)Q(y)R(f(x)（2）P(x,y)Q(y)T(x,f(x)（3）R(z)（4）P(a,b)（5）Q(b)ABu 下面进行归纳（6）P(x,y)Q(y) （1）与（3）归结，=f(x)/z（7）Q(b) （4）与（6）归结， =a/x,b/y（8）NIL（空子句） （5）与（7）归结u 所以，B是A的逻辑结论4.3 4.3 规则演绎系统规则演绎系统u对于许多公

29、式来说，子句形是一种低效率表达式。If ThenIf if1 if2 .Then then1 then2 .u基于规则的问题求解系统运用下述规则:其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的then组成。u研究采用易于叙述的if-thenif-then(如果-那么)规则来求解问题。u“P PQ Q” vs.” P P Q Q”，因为一些重要信息可能在求取子句形过程中丢失。 4.3 4.3 规则演绎系统规则演绎系统u基于规则的演绎系统和产生式系统，有两种推理方式：p正向推理(forward chaining)p逆向推理(backward chaining)u正向推理正向

30、推理：从if部分向then部分推理的过程，它是从事实或状况向目标或动作进行操作的。u逆向推理逆向推理：从then部分向if部分推理的过程，它是从目标或动作向事实或状况进行操作的。4.3.1 4.3.1 规则正向演绎系统规则正向演绎系统u演绎步骤：Step 1.事实表达式的与或形变换Step 2.事实表达式的与或图表示Step 3.与或图的F规则变换Step 4.作为终止条件的目标公式1.1.事实表达式的与或形变换事实表达式的与或形变换u把事实表示为与或形的非蕴涵形式与或形的非蕴涵形式。u具体步骤为： p Step1Step1:利用(W1W2)和(W1W2)的等价关系，消去符号。p Step2S

31、tep2:用狄摩根(De Morgan)定律把否定符号移进括号内，直到每个否定符号的辖域最多只含有一个谓词为止。 p Step3Step3:对所得到的表达式进行Skolem化和前束化。p Step4Step4:对全称量词辖域内的变量进行改名和变量标准化，而存在量词量化变量用Skolem函数代替。p Step5Step5:删去全称量词，而任何余下的变量都被认为具有全称量化作用。2.2.事实表达式的与或图表示事实表达式的与或图表示u与或形的事实表达式可用与或图与或图来表示。u每个节点表示该事实表达式的一个子表达式。图: 一个事实表达式的与或树表示u事实表达式(E1E1EkEk)的析取关系子表达式E

32、1，Ek是用后继节点表示的，并由一个k线连接符把它们连接到父辈节点上。u事实表达式(E1En)E1En)的每个合取子表达式E1，En是由单一的后继节点表示的，并由一个单线连接符接到父辈接点。3.3.与或图的与或图的F F规则变换规则变换u这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。u我们把允许用作规则的公式类型限制为下列形式：LW可通过下列步骤加以变换：(1)暂时消去蕴涵符号(2)把否定符号移进第一个析取 式内，调换变量的量词(3)进行Skolem化(4)把所有全称量词移至前面然后消去 (5)恢复蕴涵式u例：公式4.3.1 4.3.1 规则正向演绎系统规则正向演绎系统u演绎

33、步骤：1.事实表达式的与或形变换2.事实表达式的与或图表示3.与或图的F规则变换4.作为终止条件的目标公式图: 不含变量的与或图图: 应用一条规则得到的与或图4.4.作为终止条件的目标公式作为终止条件的目标公式图: 满足中终止条件的与或图举例：猎犬问题举例：猎犬问题u如何利用事实、规则和目标的关系进行正向演绎的操作，以及与或树的表示方法。u设有如下的事实、规则和目标：事实事实：FIDO又叫(BARKS)又咬(BITS)，或者FIDO不是狗。 DOG(FIDO)BARKS(FIDO)BITES(FIDO)规则规则：1.所有的猎犬(TERRIES)都是狗 R1: DOG(x)TERRIERS(x)

34、 2.叫声都是喧闹的（NOISE）。 R2: BARKS(y)NOISY(y)证明目标证明目标：存在某种或者不是猎犬或者是喧闹的。TERRIER(z)NOISY(z)图：猎犬问题的正向演绎过程u问题的与或图表示为：问题的与或图表示为：u结束于目标节点的一致解图有置换FIDO/x,FIDO/y,FIDO/z,这些置换的一致复合为FIDO/x，FIDO/y，FIDO/z,因此得到证明。事实事实：DOG(FIDO)BARKS(FIDO)BITES(FIDO)规则规则：R1: DOG(x)TERRIERS(x)R2: BARKS(y)NOISY(y)证明目标证明目标：存在某种或者不是猎犬或者是喧闹的。

35、TERRIER(z)NOISY(z)4.3.2 4.3.2 规则逆向演绎系统规则逆向演绎系统u演绎步骤：Step 1.目标表达式的与或形式Step 3.与或图的B规则变换Step 4.作为终止条件的事实节点的一致解图Step 2.目标表达式的与或图表示1.1.目标表达式的与或形式目标表达式的与或形式u逆向演绎系统能够处理任意形式的目标表达式。u首先，采用与变换事实表达式同样的过程，把目标公式化成与或形，即消去蕴涵符号，把否定符号移进括号内，对存在量词Skolem化并删去存在量词。u留在目标表达式与或形中的变量假定都已存在量词量化。1.1.目标表达式的与或形式目标表达式的与或形式u举例如下：目标

36、表达式被化成与或形式中，f(y)为一Skolem函数。图: 一个目标公式的与或图表示2.2.与或图的与或图的B B规则变换规则变换u应用B规则即逆向推理规则来变换逆向演绎系统的与或图结构。uB规则限制为: W WL L 形式的表达式。其中，W为任一与或形公式，L为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。u其次，把B规则限制为该形式蕴涵式还可以简化匹配，使之不会引起重大的实际困难。u把W(L1L2) 化为两个规则WL1和WL2。3.3.作为终止条件的事实节点的一致解图作为终止条件的事实节点的一致解图u逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。4.4 4.4 知

37、识推理技术的运用知识推理技术的运用u利用计算机制订机器人的行动制订机器人的行动规划规划，安排机器人从出发地点到目的地点所需的操作序列相和行动路线。u利用计算机证明数学定理证明数学定理，给出从已知条件开始到定理证明完毕，所需的算子序列和演算步骤。u利用人工智能专家系统进行医疗诊医疗诊断断，提供从病人症状、化验结果出发，到作出病情诊断和医疗处方。4.5 4.5 知识推理技术的进知识推理技术的进步研究步研究u1 1如何实现最经济推理（搜索）如何实现最经济推理（搜索）如何适当地利用启发性知识，制订有效而简便的搜索和控制策略（包括评价函数、生成函数、求解规划)，一方面，提高搜索效率，降低执行搜索过程(应

38、用搜索策略)的费用，另方面，又简化控制策略，节约制订控制策略的费用，从而，使整个推理过程的总费用(或总代价)最少。u2 2如何实现并行推理如何实现并行推理已有的许多搜索方法都是串行操作的，即推理系统中只有一个推理机，每次只执行一步操作，所以搜索效率和推理速度不高目前，微处理器、微计算机技术及分布式计算机网络技术的进展很快，应考虑利用多台推理机并行工作，分布式存储与并行处理。应研究并行推理与合作解题方法，如并行树搜索，每次同时扩展各个结点，从而大大提高搜索速度。u3 3改善推理复杂性改善推理复杂性进一步研究推理过程的复杂性，各种搜索方法的“组合爆炸”规律；研究启发函数的误差对搜索复杂性的影响，如

39、启发误差对A算法的影响，当相对误差为常数，具有指数复杂性，当绝对误差为常数，具有线性增长的复杂性，研究如何将指数复杂性改进为多项式复杂性问题等。u4 4研究非确定性推理研究非确定性推理n在现实世界中许多实际问题的求解，往往处在非确定的、不完全的、部分信息环境中，需要研究非确定性知识推理的方法和技术。n有两类非确定性问题，即： 随机性一偶然事件发生与否的不确定性，可用概率统计方法进行描述 模糊性事物概念内涵的不确定性，可用模糊集合论方法描述相应地需要开发推断和模糊逻辑等非确定性知识推理技术。u5 5研究自组织推理机研究自组织推理机探讨与模拟人脑利用知识推理求解问题的思维活动的自组织过程，研究自组织推理机的原理、设计和实现方法。自组织推理机将根据问题求解的目的、条件和环境，自动选取推理方法与控制策略，灵活运用启发与算法，并行与串行、演绎与归纳，适当选择推理方向，制订解题规划，进行分解与变换，组织最佳或最经济的推理过程。