人工智能基础04--推理技术

1、1/101目录o 第一章第一章绪论绪论o 第二章第二章知识表示知识表示 o 第三章搜索技术第三章搜索技术o 第四章第四章推理技术推理技术o 第五章机器学习第五章机器学习 o 第六章专家系统第六章专家系统 o 第七章第七章自动规划系统自动规划系统o 第八章第八章 自然语言理解自然语言理解o 第九章第九章 智能控制智能控制o 第十章第十章 人工智能程序设计人工智能程序设计2/1014.0 推理的基本概念4.0.1 推理的定义推理的定义 从初始证据出发，按某种策略不断应用知识库中的已从初始证据出发，按某种策略不断应用知识库中的已知知识，逐步推出结论的过程称为知知识，逐步推出结论的过程称为推理推理。

2、在人工智能系统中，推理是由程序实现的，称为在人工智能系统中，推理是由程序实现的，称为推理推理机机。 已知已知事实事实和和知识知识是构成推理的两个基本要素。是构成推理的两个基本要素。 事实又称为证据，用以指出推理的出发点及推理时应事实又称为证据，用以指出推理的出发点及推理时应该使用的知识。该使用的知识。 知识是使推理得以向前推进，并逐步达到最终目标的知识是使推理得以向前推进，并逐步达到最终目标的依据。依据。3/1014.0 推理的基本概念4.0.2 推理方式及其分类推理方式及其分类（1） 按推出结论的途径来划分，推理可分为：按推出结论的途径来划分，推理可分为： 演绎推理演绎推理（deductiv

3、e resoning）：是从全称判断推导）：是从全称判断推导出单称判断的过程，即由一般性知识推出适合某一具体情出单称判断的过程，即由一般性知识推出适合某一具体情况的结论。况的结论。一般到个别一般到个别。 归纳推理归纳推理（inductive resoning）：是从足够多的事例）：是从足够多的事例中归纳出一般性结论的推理过程。中归纳出一般性结论的推理过程。个别到一般个别到一般。 默认推理默认推理（default resoning）：是在知识不完全的情）：是在知识不完全的情况下假设某些条件已经具备所进行的推理。况下假设某些条件已经具备所进行的推理。4/1014.0 推理的基本概念4.0.2 推理

4、方式及其分类推理方式及其分类（2） 按推理时所用的知识的确定性来划分，推理可分为：按推理时所用的知识的确定性来划分，推理可分为： 确定性推理确定性推理：是指推理时所用的知识与证据都是确定的：是指推理时所用的知识与证据都是确定的，退出的结论也是确定的，其真值或者为真或者为假，没有，退出的结论也是确定的，其真值或者为真或者为假，没有第三种情况出现。第三种情况出现。 不确定性推理不确定性推理：是指推理时所用的知识与证据不都是确：是指推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。定的，推出的结论也是不确定的。 5/1014.0 推理的基本概念4.0.2 推理方式及其分类推理方式及其分类（

5、3） 按推理过程中推出的结论是否越来越接近最终目标来按推理过程中推出的结论是否越来越接近最终目标来划分，推理可分为：划分，推理可分为： 单调推理单调推理：是指在推理过程中随着推理向前推进及新知：是指在推理过程中随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。识的加入，推出的结论越来越接近最终目标。 非单调推理非单调推理：是指在推理过程中由于新知识的加入，不：是指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，然后重新开始。面的某一步，然后重新开始。 6/1014.0 推理的基本概念

6、4.0.2 推理方式及其分类推理方式及其分类（4） 按推理中是否运用与推理有关的启发性知识来划分，按推理中是否运用与推理有关的启发性知识来划分，推理可分为：推理可分为： 启发性推理启发性推理：是指在推理过程中运用与推理有关的启发：是指在推理过程中运用与推理有关的启发性知识。性知识。 非启发性推理非启发性推理：是指在推理过程中未运用与推理有关的：是指在推理过程中未运用与推理有关的启发性知识。启发性知识。 7/1014.0 推理的基本概念4.0.3 推理的方向推理的方向（1）正向推理）正向推理 是以事实作为出发点的一种推理。是以事实作为出发点的一种推理。 基本思想基本思想：从用户提供的初始已知事实

7、出发，在知识库：从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用知识集中找出当前可适用的知识，构成可适用知识集KS，然后按，然后按某种冲突消解策略从某种冲突消解策略从KS中选出一条知识进行推理，并将推出中选出一条知识进行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实，此后的新事实加入到数据库中作为下一步推理的已知事实，此后再在再在KB中选取可适用的知识进行推理，如此重复这一过程，中选取可适用的知识进行推理，如此重复这一过程，直到求得了问题的解或者知识库中再无可适用的知识为止。直到求得了问题的解或者知识库中再无可适用的知识为止。8/1014.0 推理的基

8、本概念4.0.3 推理的方向推理的方向（2）逆向推理）逆向推理 是以某个假设目标为出发点的一种推理。是以某个假设目标为出发点的一种推理。 基本思想基本思想：首先选择一个假设目标，然后寻找支持该假：首先选择一个假设目标，然后寻找支持该假设的证据，若需的证据都能找到，则说明原假设是成立的；设的证据，若需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需的证据，则说明原假设不成立，为若无论如何都找不到所需的证据，则说明原假设不成立，为此需要另作新的假设。此需要另作新的假设。9/1014.0 推理的基本概念4.0.3 推理的方向推理的方向（3）混合推理）混合推理 正向推理具有盲目、效率低等缺

9、点，推理过程中可能会正向推理具有盲目、效率低等缺点，推理过程中可能会推出许多与问题无关的子目标。逆向推理中，若提出的假设推出许多与问题无关的子目标。逆向推理中，若提出的假设目标不符合实际，也会降低系统效率。可以把正向推理与逆目标不符合实际，也会降低系统效率。可以把正向推理与逆向推理结合起来，使其各自发挥自己的优势，取长补短。这向推理结合起来，使其各自发挥自己的优势，取长补短。这种既有正向推理又有逆向推理称为种既有正向推理又有逆向推理称为混合推理混合推理。10/1014.0 推理的基本概念4.0.3 推理的方向推理的方向（4）双向推理）双向推理 双向推理双向推理：是指正向推理与逆向推理同时进行，

10、且在推：是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上理过程中的某一步骤上“碰头碰头”的一种推理。的一种推理。 基本思想基本思想：一方面根据已知事实进行正向推理，但并不：一方面根据已知事实进行正向推理，但并不推倒最终目标；另一方面从某假设目标出发进行逆向推理，推倒最终目标；另一方面从某假设目标出发进行逆向推理，但不推至原始事实，而是让它们在中途相遇，即由正向推理但不推至原始事实，而是让它们在中途相遇，即由正向推理所得到的中间结论恰好是逆向推理此时所需求的证据，这时所得到的中间结论恰好是逆向推理此时所需求的证据，这时推理就可以结束，逆向推理时所做的假设就是推理的最终结推理就可以结束，

11、逆向推理时所做的假设就是推理的最终结论。论。11/1014.0 推理的基本概念4.0.4 冲突消解策略冲突消解策略 系统将当前已知事实与系统将当前已知事实与KB中知识匹配的三种情况：中知识匹配的三种情况： （1）已知事实恰好只与）已知事实恰好只与KB中的一个知识匹配成功。中的一个知识匹配成功。 （2）已知事实不能与）已知事实不能与KB中的任何知识匹配成功。中的任何知识匹配成功。 （3）已知事实可与）已知事实可与KB中的多个知识匹配成功；或者多个（中的多个知识匹配成功；或者多个（组）事实都可与组）事实都可与KB中的某一个知识匹配成功；或者多个（组中的某一个知识匹配成功；或者多个（组）事实都可与）

12、事实都可与KB中的多个知识匹配成功；中的多个知识匹配成功； 第第3种情况称为发生了冲突。种情况称为发生了冲突。12/1014.0 推理的基本概念4.0.4 冲突消解策略冲突消解策略 消解冲突的基本思想：对知识进行排序：消解冲突的基本思想：对知识进行排序： （1）按针对性排序：优先选择针对性强的知识（规则），）按针对性排序：优先选择针对性强的知识（规则），即要求条件多的规则。即要求条件多的规则。 （2）按已知事实的新鲜性排序：后生成的事实具有较大的）按已知事实的新鲜性排序：后生成的事实具有较大的新鲜性。新鲜性。 （3）按匹配度排序：在不确定推理中，需要计算已知事实）按匹配度排序：在不确定推理中，

13、需要计算已知事实与知识的匹配度。与知识的匹配度。 （4）按条件个数排序：优先应用条件少的产生式规则。）按条件个数排序：优先应用条件少的产生式规则。13/1014.1 消解原理4.1.1 子句集的求取子句集的求取 消解原理是针对谓词逻辑知识表示的问题求解方法。消解原理是针对谓词逻辑知识表示的问题求解方法。消解原理的基础知识：消解原理的基础知识： （1）谓词公式、某些推理规则以及置换合一等概念。）谓词公式、某些推理规则以及置换合一等概念。 （2）子句：由文字的析取组成的公式）子句：由文字的析取组成的公式(一个原子公式和原子一个原子公式和原子公式的否定都叫做文字公式的否定都叫做文字)。（3）消解：当

14、消解可使用时，消解过程被应用于母体子句）消解：当消解可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。例如，如果存在某个公理对，以便产生一个导出子句。例如，如果存在某个公理E1E2和另一公理和另一公理E2E3，那么，那么E1E3在逻辑上成立。在逻辑上成立。这就是消解，而称这就是消解，而称E1 E3为为E1E2和和E2E3的消解式。的消解式。 14/1014.1 消解原理4.1.1 子句集的求取子句集的求取步骤步骤 (1) 消去蕴涵符号消去蕴涵符号只应用只应用和符号，以和符号，以AB替换替换AB。 (AB) B C = (AB) B C = (AB) B C = (A B) B C =

15、 （A B） （ B B） C = （A B） C 15/1014.1 消解原理4.1.1 子句集的求取子句集的求取(2) 减少否定符号的辖域减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用每个否定符号最多只用到一个谓词符号上，并反复应用狄狄摩根定律。例如：摩根定律。例如： 以以AB代替代替(AB) 以以AB代替代替(AB) 以以A代替代替(A) 以以 (彐彐x)A代替代替( x)A 以以( x)A代替代替(彐彐x)A16/1014.1 消解原理4.1.1 子句集的求取子句集的求取(3) 对变量标准化对变量标准化在任一量词辖域内，受该量词约束的变量为一哑元在任一量词辖域内，

16、受该量词约束的变量为一哑元(虚构虚构变量变量)，它可以在该辖域内处处统一地被另一个没有出现过的，它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替，而不改变公式的真值。合适公式中变量的任意变量所代替，而不改变公式的真值。合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑标准化意味着对哑元改名以保证每个量词有其自己唯一的哑元。元。 如，对如，对 ( x)P(x)(彐彐x)Q(x) 标准化可得：标准化可得： ( x)P(x)(彐彐y)Q(y)17/1014.1 消解原理4.1.1 子句集的求取子句集的求取(4) 消去存在量词消去存在量词 Skolem函数：函数： ( y

17、)(彐彐x)P(x, y)中，存在量词是在全称量中，存在量词是在全称量词的辖域内，允许所存在的词的辖域内，允许所存在的x可能依赖于可能依赖于y值。令这种依赖关值。令这种依赖关系明显地有函数系明显地有函数g(y)所定义，它把每个所定义，它把每个y值映射到存在的那个值映射到存在的那个x。这种函数叫做。这种函数叫做Skolem函数。函数。 如果用如果用Skolem函数代替存在的函数代替存在的x，就可以消去全部存在量，就可以消去全部存在量词，并写成：词，并写成： ( y)P(g(y), y)18/1014.1 消解原理4.1.1 子句集的求取子句集的求取从一个公式消去一个存在量词的一般规则是以一个从一

18、个公式消去一个存在量词的一般规则是以一个Skolem函数代替每个出现的存在量词的量化变量，而这个函数代替每个出现的存在量词的量化变量，而这个Skolem函数函数的变量就是由那些全称量词所约束的全称量词量化变量，这些的变量就是由那些全称量词所约束的全称量词量化变量，这些全称量词的辖域包括要被消去的存在量词的辖域在内。全称量词的辖域包括要被消去的存在量词的辖域在内。Skolem函数所使用的函数符号必须是新的，即不允许是公式中已经出函数所使用的函数符号必须是新的，即不允许是公式中已经出现过的函数符号。现过的函数符号。如果要消去的存在量词不在任何一个全称量词的辖域内，如果要消去的存在量词不在任何一个全

19、称量词的辖域内，则用不含变量的则用不含变量的Skolem函数即常量。例如，函数即常量。例如，(彐彐x) P(x)化为化为P(A)，其中常量符号，其中常量符号A用来表示人们知道的存在实体。用来表示人们知道的存在实体。A必须必须是个新的常量符号，它未曾在公式中其它地方使用过。是个新的常量符号，它未曾在公式中其它地方使用过。 19/1014.1 消解原理4.1.1 子句集的求取子句集的求取(5) 化为前束形化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。括这个量词后面公式的整个部分。所得公

20、式称为前束形。 前束形前束形=（前（前 缀）缀） （母（母 式）式） 全称量词串全称量词串 无量词公式无量词公式(6) 把母式化为合取范式把母式化为合取范式任何母式都可写成由一些谓词公式和任何母式都可写成由一些谓词公式和(或或)谓词公式的否定谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。的析取的有限集组成的合取。这种母式叫做合取范式。 如：如：A B C 化为化为 A BB C 20/1014.1 消解原理4.1.1 子句集的求取子句集的求取(7) 消去全称量词消去全称量词消去明显出现的全称量词。消去明显出现的全称量词。(8) 消去连词符号消去连词符号用用A，B代替代替(AB)

21、，以消去明显的符号，以消去明显的符号。反复代替。反复代替的结果，最后得到一个有限集，其中每个公式是文字的析取。的结果，最后得到一个有限集，其中每个公式是文字的析取。任一个只由文字的析取构成的合适公式叫做一个子句。任一个只由文字的析取构成的合适公式叫做一个子句。(9) 更换变量名称更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。以上的子句中。21/1014.1 消解原理4.1.1 子句集的求取子句集的求取例：将下列谓词演算公式化为一个子句集例：将下列谓词演算公式化为一个子句集( x)P(x)( y)P(y)P(f(x,

22、y)( y)Q(x,y)P(y)（1）消去蕴涵符号）消去蕴涵符号 ( x)P(x) ( y)P(y) P(f(x,y)( y)Q(x,y) P(y)（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）对变量标准化）对变量标准化 ( x)P(x) ( y)P(y) P(f(x,y) (彐彐w) Q(x,w) P(w)22/1014.1 消解原理4.1.1 子句集的求取子句集的求取（4）消去存在量词）消去存在量词 ( x)P(

23、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)（6）把母式化为合取范式）把母式化为合取范式 ( x) ( y)P(x) P(y) P(f(x,y)P(x) Q(x,g(x) P(x) P(g(x)23/1014.1 消解原理4.1.1 子句集的求取子句集的求取（7）消去全称量词）消去全称量词 P(x) P(y) P(f(x,y)P(x) Q(x,g(x) P(x) P(g(x)（8）消去连词符号）消去连词

24、符号 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)24/1014.1 消解原理4.1.2 消解推理规则消解推理规则 令令L1为任一原子公式，为任一原子公式，L2为另一原子公式；为另一原子公式；L1和和L2具有相具有相同的谓词符号，但一般具有不同的变量。已知两子句同的谓词符号，但一般具有不同的变量。已知两子句L1和和L2,如果如果L1和和L2具有最一般合一者具有最一般合一者，那么通过消解可以从这，那么通过消解可

25、以从这两个父辈子句推导出一个新子句两个父辈子句推导出一个新子句()。这个新子句叫做消解。这个新子句叫做消解式。它是由取这两个子句的析取，然后消去互补对而得到的。式。它是由取这两个子句的析取，然后消去互补对而得到的。 25/1014.1 消解原理4.1.2 消解推理规则消解推理规则 常用消解规则常用消解规则(1) 假言推理假言推理父辈子句父辈子句 P PQ(即即PQ) 消解式消解式 Q26/1014.1 消解原理4.1.2 消解推理规则消解推理规则 常用消解规则常用消解规则(2) 合并合并父辈子句父辈子句 PQ PQ 消解式消解式 QQ=Q27/1014.1 消解原理4.1.2 消解推理规则消解

26、推理规则 常用消解规则常用消解规则(3) 重言式重言式 P Q P Q P Q P Q 消解式消解式 Q Q P P28/1014.1 消解原理4.1.2 消解推理规则消解推理规则 常用消解规则常用消解规则(4) 空子句空子句(矛盾矛盾) P P 消解式消解式 NIL29/1014.1 消解原理4.1.2 消解推理规则消解推理规则 常用消解规则常用消解规则(5) 链式链式(三段论三段论) P Q Q R 消解式消解式 P R30/1014.1 消解原理4.1.3 含有变量的消解式含有变量的消解式 为了对含有变量的子句使用消解规则，必须找到一个置为了对含有变量的子句使用消解规则，必须找到一个置换

27、，作用于父辈子句使其含有互补文字。换，作用于父辈子句使其含有互补文字。 例：例：设有两个字句设有两个字句 P(x)Q(x)Q（f(y)）置换置换 =f(y)/x消解可得：消解可得：P（f(y)） 31/1014.1 消解原理4.1.3 含有变量的消解式含有变量的消解式 令父辈子句由令父辈子句由Li和和Mi给出，假设这两个子句中的变给出，假设这两个子句中的变量已经分别标准化。设量已经分别标准化。设li是是 Li的一个子集，的一个子集，mi是是Mi的的一个子集，若一个子集，若是是 li和和 mi的最一般的合一，消解两个子的最一般的合一，消解两个子句句Li和和Mi，得到新子句，得到新子句 Li- l

28、i Mi- mi 就是这两个子句的消解式。就是这两个子句的消解式。 消解两个子句时，可能有一个以上的消解式，因为有多消解两个子句时，可能有一个以上的消解式，因为有多种选择种选择li和和 mi的方法。的方法。32/1014.1 消解原理4.1.3 含有变量的消解式含有变量的消解式 例例：考虑两个子句：考虑两个子句： Px,f(A) Px,f(y) Q(y) pz,f(A) Q(z)取取 li= Px,f(A)， mi= pz,f(A)可得消解式可得消解式 Pz,f(y) Q(y) Q(z) =z/x33/1014.1 消解原理4.1.3 含有变量的消解式含有变量的消解式如果取如果取 li= Q(

29、y) ， mi= Q(z)则可得消解式则可得消解式 Px,f(A) Px,f(y) py,f(A) 进一步消解的消解式进一步消解的消解式 Py,f(y) =y/z34/1014.1 消解原理4.1.3 含有变量的消解式含有变量的消解式几个含有变量的子句使用消解的例子：几个含有变量的子句使用消解的例子：B(x)B(x) C(x)C(x)35/1014.1 消解原理4.1.3 含有变量的消解式含有变量的消解式几个含有变量的子句使用消解的例子：几个含有变量的子句使用消解的例子：P(x) Q(x)Qf(y)Pf(y) =f(y)/x36/1014.1 消解原理4.1.3 含有变量的消解式含有变量的消解

30、式几个含有变量的子句使用消解的例子：几个含有变量的子句使用消解的例子：P(x,f(y) Q(x) Rf(a),yPf(f(a),z R(z,w)Q(f(f(a) Rf(a),y R(f(y),w) =f(f(a)/x, f(y)/z37/1014.1 消解原理4.1.4 消解反演求解过程消解反演求解过程 1. 基本思想基本思想 把要解决的问题作为一个要证明的命题，其目标公式被把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去，把消解反否定并化成子句形，然后添加到命题公式集中去，把消解反演系统应用于联合集，并推导出一个空子句演系统应用于联合集，并推导出一个

31、空子句(NIL)，产生一，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决，与数学中反证法的思想十分立，定理得证，问题得到解决，与数学中反证法的思想十分相似。相似。 38/1014.1 消解原理4.1.4 消解反演求解过程消解反演求解过程 2、消解反演、消解反演反演求解的步骤反演求解的步骤给出一个公式集给出一个公式集S和目标公式和目标公式L，通过反证或反演来求证，通过反证或反演来求证目标公式目标公式L，其证明步骤如下：，其证明步骤如下：(1)否定否定L，得，得L；(2)把把L添加到添加到S中去；中去；(3)

32、把新产生的集合把新产生的集合L，S化成子句集；化成子句集；(4)应用消解原理，力图推导出一个表示矛盾的空子句应用消解原理，力图推导出一个表示矛盾的空子句NIL。39/1014.1 消解原理4.1.4 消解反演求解过程消解反演求解过程反演求解的正确性反演求解的正确性设公式设公式L在逻辑上遵循公式集在逻辑上遵循公式集S，那么按照定义满足，那么按照定义满足S的的每个解释也满足每个解释也满足L。决不会有满足。决不会有满足S的解释能够满足的解释能够满足L的，的，所以不存在能够满足并集所以不存在能够满足并集SL的解释。如果一个公式的解释。如果一个公式集不能被任一解释所满足，那么这个公式是不可满足的。因集不

33、能被任一解释所满足，那么这个公式是不可满足的。因此，如果此，如果L在逻辑上遵循在逻辑上遵循S，那么，那么SL是不可满足的是不可满足的。可以证明，如果消解反演反复应用到不可满足的子句集，。可以证明，如果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句那么最终将要产生空子句NIL。因此，如果。因此，如果L在逻辑上遵循在逻辑上遵循S，那么由并集，那么由并集SL消解得到的子句，最后将产生空子消解得到的子句，最后将产生空子句；反之，可以证明，如果从句；反之，可以证明，如果从SL的子句消解得到空的子句消解得到空子句，那么子句，那么L在逻辑上遵循在逻辑上遵循S。40/1014.1 消解原理4.1.

34、4 消解反演求解过程消解反演求解过程反演求解举例反演求解举例 例：储蓄问题例：储蓄问题 前提：每个储蓄钱的人都获得利息。前提：每个储蓄钱的人都获得利息。 结论：如果没有利息，那么就没有人去储蓄钱结论：如果没有利息，那么就没有人去储蓄钱 证明：令证明：令S(x, y)表示表示“x储蓄储蓄y” M(x)表示表示“x是钱是钱” I(x)表示表示“x是利息是利息” E(x, y)表示表示“x获得获得y” 于是上述命题写成：于是上述命题写成：41/1014.1 消解原理4.1.4 消解反演求解过程消解反演求解过程 ( x)(x)(彐彐y)(S(x,y) M(y) =(彐彐y )(I(y) E(x,y)

35、结论：结论： (彐彐x)I(x) = ( x)(x)( y)(M(y) =(S(x,y) 化为子句集：化为子句集： S=S(x,y) M(y)I(f(x), S(x,y)M(y) E(x,f(x)其中，其中，y=f(x)为为Skolem函数。函数。 而而 L= (彐彐x)I(x) = ( x)(x)( y)(s(x,y)= M(y) = I(z),S(a,b),M(b)P=Q等价等价Q=P 42/1014.1 消解原理4.1.4 消解反演求解过程消解反演求解过程 按按4个步骤进行反演求解个步骤进行反演求解 （1）否定）否定L，即有，即有L= I(z),S(a,b),M(b) （2）将）将L添加

36、到添加到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),M(b) （3）把新产生的集合化成子句集，即）把新产生的集合化成子句集，即 S=S(x,y) M(y)I(f(x), S(x,y)M(y) E(x,f(x), I(z),S(a,b),M(b) （4）应用消解原理，推导出一个表示矛盾的空子句）应用消解原理，推导出一个表示矛盾的空子句NIL。 43/1014.1 消解原理4.1.4 消解反演求解过程消解反演求解过程S(x,y)M(y) I(f(x)I(z)S(x,y)M(y) = f(x)/zM(b)S(

37、a,b) = a/x, b/yNILM(b)44/1014.1 消解原理4.1.4 消解反演求解过程消解反演求解过程反演求解过程反演求解过程步骤：步骤：(1)把由目标公式的否定产生的每个子句添加到目标公式把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。否定之否定的子句中去。(2)按照反演树，执行和以前相同的消解，直至在根部得按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。到某个子句止。(3)用根部的子句作为一个回答语句。用根部的子句作为一个回答语句。45/1014.1 消解原理4.1.4 消解反演求解过程消解反演求解过程分析：分析：答案求取涉及到把一棵根部有答案

38、求取涉及到把一棵根部有NIL的反演树变换为在根的反演树变换为在根部带有可用作答案的某个语句的一颗证明树。由于变换关系部带有可用作答案的某个语句的一颗证明树。由于变换关系涉及到把由目标公式的否定产生的每个子句变换为一个重言涉及到把由目标公式的否定产生的每个子句变换为一个重言式，所以被变换的证明树就是一棵消解的证明树，其在根部式，所以被变换的证明树就是一棵消解的证明树，其在根部的语句在逻辑上遵循公理加上重言式，因而也单独地遵循公的语句在逻辑上遵循公理加上重言式，因而也单独地遵循公理。因此被变换的证明树本身就证明了求取办法是正确的。理。因此被变换的证明树本身就证明了求取办法是正确的。46/1014.

39、1 消解原理4.1.4 消解反演求解过程消解反演求解过程例例4.3 如果无论约翰如果无论约翰(John)到哪里去，菲多到哪里去，菲多(Fido)也就去那里，也就去那里，那么如果约翰在学校里，菲多在哪里呢那么如果约翰在学校里，菲多在哪里呢? 事实公式集：事实公式集： S=( x)AT(JOHN, x)=AT(FIDO, x), AT(JOHN, SCHOOL) 目标公式目标公式L： ( (彐彐x)AT(FIDO,x) 首先证明首先证明 L在逻辑上遵循公式集在逻辑上遵循公式集S L=( (彐彐x)AT(FIDO,x)= ( x)AT(FIDO,x) 其子句为其子句为AT(FIDO,x)47/101

40、4.1 消解原理4.1.4 消解反演求解过程消解反演求解过程例例4.3 的反演树的反演树AT(FIDO,x) AT(JOHN, y) AT(FIDO, y), AT(JOHN, x) = x/yNILAT(JOHN, SCHOOL) = SCHOOL/x48/1014.1 消解原理4.1.4 消解反演求解过程消解反演求解过程例例4.3从消解求取答案的反演树从消解求取答案的反演树AT(FIDO,x) AT(FIDO,y) AT(JOHN, y) AT(FIDO, y), AT(JOHN, x ) AT(FIDO,x) = x/yAT(FIDO,SCHOOL)AT(JOHN, SCHOOL) =

41、SCHOOL/x目标公式的重言式目标公式的重言式 49/1014.2 规则演绎系统 规则演绎系统的定义：规则演绎系统的定义：基于规则的问题求解系统运用下述规则来建立：基于规则的问题求解系统运用下述规则来建立： IfThen 其中，其中，If部分可能由几个部分可能由几个if组成，而组成，而Then部分可能由一个或一部分可能由一个或一个以上的个以上的then组成。组成。 在所有基于规则系统中，每个在所有基于规则系统中，每个if可能与某断言可能与某断言(assertion)集集中的一个或多个断言匹配。有时把该断言集称为工作内存。在中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统

42、中，许多基于规则系统中，then部分用于规定放入工作内存的新断部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统言。这种基于规则的系统叫做规则演绎系统(rule based deduction system)。在这种系统中，通常称每个。在这种系统中，通常称每个if部分为前项部分为前项(antecedent)，称每个，称每个then部分为后项部分为后项(consequent)。50/1014.2 规则演绎系统4.2.1 正向规则演绎系统正向规则演绎系统 正向规则演绎系统是从事实到目标进行操作的，即从状正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是

43、从况条件到动作进行推理的，也就是从if到到then的方向进行推的方向进行推理的。理的。1. 事实表达式的与或形变换事实表达式的与或形变换 把事实表示为非蕴涵形式的与或形，作为系统的总数据把事实表示为非蕴涵形式的与或形，作为系统的总数据库。具体变换步骤与前述化为子句形类似。库。具体变换步骤与前述化为子句形类似。注意：我们不想把这些事实化为子句形，而是把它们表示注意：我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式。形式。51/1014.2 规则演绎系统4.2.1 正向规则演绎系统正向规则演绎系

44、统例：有事实表达式例：有事实表达式(彐彐u)( v)Q(v, u)(R(v)P(v)S(u, v)把它化为把它化为Q(v,A)R(v)P(v)S(A,v)对变量更名标准化，使得同一变量不出现在事实表达式的对变量更名标准化，使得同一变量不出现在事实表达式的不同主要合取式中，得：不同主要合取式中，得：Q(w,A)R(v)P(v)S(A,v) 52/1014.2 规则演绎系统4.2.1 正向规则演绎系统正向规则演绎系统2. 事实表达式的与或图表示事实表达式的与或图表示将上例与或形的事实表达式用与或图来表示将上例与或形的事实表达式用与或图来表示 Q(w,A)R(v)P(v)S(A,v)Q(w,A)R(

45、v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)53/1014.2 规则演绎系统4.2.1 正向规则演绎系统正向规则演绎系统3. 与或图的与或图的F规则变换规则变换这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。把允许用作规则的公式类型限制为下列形式公式基础上的。把允许用作规则的公式类型限制为下列形式 LW式中：式中：L是单文字；是单文字；W为与或形的唯一公式。为与或形的唯一公式。54/1014.2 规则演绎系统4.2.1 正向规则演绎系统正向规则演绎系统3. 与或图的与或图的F规则变换规则变换将这类规则应用

46、于与或图进行推演。假设有一条规则将这类规则应用于与或图进行推演。假设有一条规则L=W，根据此规则及事实表达式，根据此规则及事实表达式F(L)，可以推出表达式，可以推出表达式F(W)。F(W)是用是用W代替代替F中的所有中的所有L而得到的。当用规则而得到的。当用规则L=W来变来变换以上述方式描述的换以上述方式描述的F(L)的与或图表示时，就产生一个含有的与或图表示时，就产生一个含有F(W)表示的新图；也就是说，它的以叶节点终止的解图集以表示的新图；也就是说，它的以叶节点终止的解图集以F(W)子句形式代表该子句集。这个子句集包括在子句形式代表该子句集。这个子句集包括在F(L)的子句形的子句形和和L

47、=W的子句形间对的子句形间对L进行所有可能的消解而得到的整集。该进行所有可能的消解而得到的整集。该过程以极其有效的方式达到了用其它方法要进行多次消解才能过程以极其有效的方式达到了用其它方法要进行多次消解才能达到的目的。达到的目的。55/1014.2 规则演绎系统4.2.1 正向规则演绎系统正向规则演绎系统 4. 作为终止条件的目标公式作为终止条件的目标公式应用应用F规则的目的在于从某个事实公式和某个规则集出发来规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。在正向推理系统中，这种目标表达式只限证明某个目标公式。在正向推理系统中，这种目标表达式只限于可证明的表达式，尤其是可证明的

48、文字析取形的目标公式表于可证明的表达式，尤其是可证明的文字析取形的目标公式表达式。用文字集表示此目标公式，并设该集各元都为析取关系达式。用文字集表示此目标公式，并设该集各元都为析取关系。结论：结论：当正向演绎系统产生一个含有以目标节点作为终止的解图当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止。时，此系统就成功地终止。56/1014.2 规则演绎系统4.2.2 逆向规则演绎系统逆向规则演绎系统 基于规则的逆向演绎系统，其操作过程与正向演绎系统相基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实的操作过程，从反，即为从目标到事实的操作过程，从then

49、到到if的推理过程。的推理过程。逆向推理过程逆向推理过程1. 目标表达式的与或形式目标表达式的与或形式逆向演绎系统能够处理任意形式的目标表达式。首先，采逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事实表达式同样的过程，把目标公式化成与或形。用与变换事实表达式同样的过程，把目标公式化成与或形。57/1014.2 规则演绎系统4.2.2 逆向规则演绎系统逆向规则演绎系统 2. 与或图的与或图的B规则变换规则变换B规则是建立在确定的蕴涵式基础上的，正如正向系统的规则是建立在确定的蕴涵式基础上的，正如正向系统的F规则一样。不过，我们现在把这些规则一样。不过，我们现在把这些B规则限制为规则

50、限制为 WL形式的表达式。其中，形式的表达式。其中，W为任一与或形公式，为任一与或形公式，L为文字，而且为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。蕴涵式中任何变量的量词辖域为整个蕴涵式。 3. 作为终止条件的事实节点的一致解图作为终止条件的事实节点的一致解图逆向系统成功的终止条件是与或图包含有某个终止在事实逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。节点上的一致解图。58/1014.2 规则演绎系统4.2.2 双向规则演绎系统双向规则演绎系统基于规则的正向演绎系统和逆向演绎系统的特点和局限性基于规则的正向演绎系统和逆向演绎系统的特点和局限性 正向演绎系统能够处

51、理任意形式的正向演绎系统能够处理任意形式的if表达式，但被限制在表达式，但被限制在then表达式为由文字析取组成的一些表达式。逆向演绎系统能表达式为由文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的够处理任意形式的then表达式，但被限制在表达式，但被限制在if表达式为文字合取表达式为文字合取组成的一些表达式。双向组成的一些表达式。双向(正向和逆向正向和逆向)组合演绎系统具有正向组合演绎系统具有正向和逆向两系统的优点，克服各自的缺点。和逆向两系统的优点，克服各自的缺点。 59/1014.2 规则演绎系统4.2.2 双向规则演绎系统双向规则演绎系统双向双向(正向和逆向正向和逆向)组合演绎

52、系统的构成组合演绎系统的构成 正向和逆向组合系统是建立在两个系统相结合的基础上正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成，并分别用或图结构组成，并分别用F规则和规则和B规则来修正。规则来修正。60/1014.2 规则演绎系统4.2.2 双向规则演绎系统双向规则演绎系统终止条件终止条件 组合演绎系统的主要复杂之处在于其终止条件，终止涉及组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。当用两个图结构之间的适当交接处。当用F规则和规则和B规则对图进行

53、扩规则对图进行扩展之后，匹配就可以出现在任何文字节点上。展之后，匹配就可以出现在任何文字节点上。在完成两个图间的所有可能匹配之后，目标图中根节点上在完成两个图间的所有可能匹配之后，目标图中根节点上的表达式是否已经根据事实图中根节点上的表达式和规则得到的表达式是否已经根据事实图中根节点上的表达式和规则得到证明的问题仍然需要判定。只有当求得这样的一个证明时，证证明的问题仍然需要判定。只有当求得这样的一个证明时，证明过程才算成功地终止。若能够断定在给定方法限度内找不到明过程才算成功地终止。若能够断定在给定方法限度内找不到证明时过程则以失败告终。证明时过程则以失败告终。61/1014.3 产生式系统

54、在基于规则系统中，每个在基于规则系统中，每个if可能与某断言可能与某断言(assertion)集中的一个或多个断言匹配，集中的一个或多个断言匹配，then部分用于部分用于规定放入工作内存的新断言。当规定放入工作内存的新断言。当then部分用于规定动部分用于规定动作时，称这种基于规则的系统为反应式系统作时，称这种基于规则的系统为反应式系统(reaction system)或产生式系统或产生式系统(production system)。 62/1014.3 产生式系统4.3.1 产生式系统的结构产生式系统的结构产生式系统由产生式系统由3个部分组成，即总数据库个部分组成，即总数据库(或全局数据库或全

55、局数据库)、产、产生式规则和控制策略。生式规则和控制策略。 控制策略控制策略产生式规则产生式规则总数据库总数据库63/1014.3 产生式系统4.3.1 产生式系统的结构产生式系统的结构 总数据库有时也被称作上下文总数据库有时也被称作上下文，当前数据库或暂时存储器。，当前数据库或暂时存储器。总数据库是产生式规则的注意中心。产生式规则的左边表示在总数据库是产生式规则的注意中心。产生式规则的左边表示在启用这一规则之前总数据库内必须准备好的条件。例如在上述启用这一规则之前总数据库内必须准备好的条件。例如在上述例子中，在得出该动物是食肉动物的结论之前，必须在总数据例子中，在得出该动物是食肉动物的结论之

56、前，必须在总数据库中存有库中存有“该动物是哺乳动物该动物是哺乳动物”和和“该动物吃肉该动物吃肉”这两个事实这两个事实。执行产生式规则的操作会引起总数据库的变化，这就使其他。执行产生式规则的操作会引起总数据库的变化，这就使其他产生式规则的条件可能被满足。产生式规则的条件可能被满足。产生式规则是一个规则库产生式规则是一个规则库，用于存放与求解问题有关的某个领，用于存放与求解问题有关的某个领域知识的规则之集合及其交换规则。规则库知识的完整性、一域知识的规则之集合及其交换规则。规则库知识的完整性、一致性、准确性、灵活性和知识组织的合理性，将对产生式系统致性、准确性、灵活性和知识组织的合理性，将对产生式

57、系统的运行效率和工作性能产生重要影响。的运行效率和工作性能产生重要影响。 64/1014.3 产生式系统4.3.1 产生式系统的结构产生式系统的结构 控制策略为一推理机构控制策略为一推理机构，由一组程序组成，用来控制产生式，由一组程序组成，用来控制产生式系统的运行，决定问题求解过程的推理线路，实现对问题的求系统的运行，决定问题求解过程的推理线路，实现对问题的求解。产生式系统的控制策略随搜索方式的不同可分为可撤回策解。产生式系统的控制策略随搜索方式的不同可分为可撤回策略、回溯策略、图搜索策略等。略、回溯策略、图搜索策略等。 控制策略的作用是说明下一步应该选用什么规则，也就是如控制策略的作用是说明

58、下一步应该选用什么规则，也就是如何应用规则。通常从选择规则到执行操作分何应用规则。通常从选择规则到执行操作分3步：匹配、冲突解步：匹配、冲突解决和操作。决和操作。65/1014.3 产生式系统4.3.1 产生式系统的结构产生式系统的结构（1）匹配）匹配在这一步，把当前数据库与规则的条件部分相匹配。如果在这一步，把当前数据库与规则的条件部分相匹配。如果两者完全匹配，则把这条规则称为触发规则。当按规则的操作两者完全匹配，则把这条规则称为触发规则。当按规则的操作部分去执行时，称这条规则为启用规则。被触发的规则不一定部分去执行时，称这条规则为启用规则。被触发的规则不一定总是启用规则，因为可能同时有几条

59、规则的条件部分被满足，总是启用规则，因为可能同时有几条规则的条件部分被满足，这就要在解决冲突步骤中来解决这个问题。在复杂的情况下，这就要在解决冲突步骤中来解决这个问题。在复杂的情况下，在数据库和规则的条件部分之间可能要进行近似匹配。在数据库和规则的条件部分之间可能要进行近似匹配。66/1014.3 产生式系统4.3.1 产生式系统的结构产生式系统的结构（2）冲突解决）冲突解决当有一条以上规则的条件部分和当前数据库相匹配时，就当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。需要决定首先使用哪一条规则，这称为冲突解决。（3）操作）操作操作就是执行规则的

60、操作部分，经过操作以后，当前数据操作就是执行规则的操作部分，经过操作以后，当前数据库将被修改。然后，其他的规则有可能被使用。库将被修改。然后，其他的规则有可能被使用。 67/1014.3 产生式系统4.3.2 产生式系统的表示产生式系统的表示 1. 事实的表示事实的表示 （1）孤立事实的表示）孤立事实的表示 三元组三元组 (AGE ZHAO-LING 43) (FATHER ZHAO-YIN ZHAO-LING) (MAN ZHAO-LING TRUE) (WOMAN ZHAO-LING FALSE) 不完全知识不完全知识 置信度置信度68/1014.3 产生式系统4.3.2 产生式系统的表示