人工智能与知识工程-搜索推理技术2

1、1l3.5 消解原理消解原理l3.6 规则演绎系统规则演绎系统l3.7 产生式系统产生式系统l3.8 系统组织技术系统组织技术2l推理是指按照某种策略从已知事实出发去推出结论的过程。推理是指按照某种策略从已知事实出发去推出结论的过程。其中，推理所用的事实可分为两种：一种是与求解问题有其中，推理所用的事实可分为两种：一种是与求解问题有关的初始证据；另一种是推理过程中所得到的中间结论。关的初始证据；另一种是推理过程中所得到的中间结论。通常，智能系统的推理过程是通过推理机来完成的。所谓通常，智能系统的推理过程是通过推理机来完成的。所谓推理机就是智能系统用来实现推理的那些程序。推理机就是智能系统用来实

2、现推理的那些程序。l例，在医疗诊断专家系统中，所有与诊断有关的医疗常识例，在医疗诊断专家系统中，所有与诊断有关的医疗常识和专家经验都被保存在知识库中。当系统开始诊断疾病时，和专家经验都被保存在知识库中。当系统开始诊断疾病时，首先把病人的症状和检查结果放到事实库中，然后再从事首先把病人的症状和检查结果放到事实库中，然后再从事实库中的这些初始证据出发，按照某种策略在知识库中寻实库中的这些初始证据出发，按照某种策略在知识库中寻找可以匹配的知识，如果得到的是一些中间结论，则需要找可以匹配的知识，如果得到的是一些中间结论，则需要把它们作为已知事实放入事实库中，并继续寻找可以匹配把它们作为已知事实放入事实

3、库中，并继续寻找可以匹配的知识，如此反复进行，直到推出最终结论为止。由初始的知识，如此反复进行，直到推出最终结论为止。由初始事实出发到推出最终结论的过程就是推理，实现这一推理事实出发到推出最终结论的过程就是推理，实现这一推理过程的程序称为推理机。过程的程序称为推理机。3l智能系统的推理包括两个基本问题：一个是智能系统的推理包括两个基本问题：一个是推理的方法；另一个是推理的控制策略。推理的方法；另一个是推理的控制策略。l推理方法主要解决在推理过程中前提与结论推理方法主要解决在推理过程中前提与结论之间的逻辑关系，以及在非精确性推理中不之间的逻辑关系，以及在非精确性推理中不确定性的传递问题。确定性的

4、传递问题。4l1. 按推理的逻辑基础分类按推理的逻辑基础分类 l按照推理的逻辑基础，常用的推理方法可分为演绎按照推理的逻辑基础，常用的推理方法可分为演绎推理、归纳推理和默认推理。推理、归纳推理和默认推理。l(1)演绎推理。演绎推理。l演绎推理是从已知的一般性知识出发，去推出组合演绎推理是从已知的一般性知识出发，去推出组合在这些已知知识中适合于某种个别情况的结论的过在这些已知知识中适合于某种个别情况的结论的过程。它是一种由一般到个别的推理方法，其核心是程。它是一种由一般到个别的推理方法，其核心是三段论，即假言推理、拒取式推理和假言三段论。三段论，即假言推理、拒取式推理和假言三段论。常用的三段论是

5、由一个大前提、一个小前提和一个常用的三段论是由一个大前提、一个小前提和一个结论三部分组成的。其中，大前提是由已知的一般结论三部分组成的。其中，大前提是由已知的一般性知识或推理过程得到的判断；小前提是关于某种性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。推出的，并且适合于小前提的判断。5l（2）归纳推理）归纳推理l归纳推理的前提是一些关于个别事物或现象的命题，归纳推理的前提是一些关于个别事物或现象的命题，而结论则是关于该类事物或现象的普遍性命题。归而结论则是关于该类事物或现象的普

6、遍性命题。归纳推理的结论所断定的知识范围超出了前提所断定纳推理的结论所断定的知识范围超出了前提所断定的知识范围，因此，归纳推理的前提与结论之间的的知识范围，因此，归纳推理的前提与结论之间的联系不是必然性的，而是或然性的。也就是说，其联系不是必然性的，而是或然性的。也就是说，其前提真而结论假是可能的，所以，归纳推理是一种前提真而结论假是可能的，所以，归纳推理是一种或然性推理。或然性推理。l基本思想：先从已知事实中猜测出一个结论，然后基本思想：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认。对这个结论的正确性加以证明确认。l如果按照所选事例的广泛性可分为完全归纳推理和如果按照所选

7、事例的广泛性可分为完全归纳推理和不完全归纳推理。不完全归纳推理。6l3)默认推理。默认推理。l默认推理是在知识不完全的情况下假设某些默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理，因此也称为缺条件已经具备所进行的推理，因此也称为缺省推理。在推理过程中，如果发现原先的假省推理。在推理过程中，如果发现原先的假设不正确，就撤销原来的假设以及由此假设设不正确，就撤销原来的假设以及由此假设所推出的所有结论，重新对新情况进行推理。所推出的所有结论，重新对新情况进行推理。由于默认推理容许在推理过程中假设某些条由于默认推理容许在推理过程中假设某些条件是成立的，这就解决了在一个不完备的知件是成立

8、的，这就解决了在一个不完备的知识集中进行推理的问题。识集中进行推理的问题。7l2. 按照按照所用知识的确定性分类所用知识的确定性分类 l确定性推理和不确定性推理确定性推理和不确定性推理l3. 按推理过程的单调性分类按推理过程的单调性分类 l按照推理过程的单调性，或者说按照推理过程所得到的结论是按照推理过程的单调性，或者说按照推理过程所得到的结论是否越来越接近目标，推理可分为单调推理与非单调推理两类。否越来越接近目标，推理可分为单调推理与非单调推理两类。l4. 按照方法论分类按照方法论分类 l按照方法论，常见的推理有基于知识的推理、统计推理和直觉按照方法论，常见的推理有基于知识的推理、统计推理和

9、直觉推理等。推理等。l基于知识的推理，是指根据已掌握的事实，通过运用知识进行基于知识的推理，是指根据已掌握的事实，通过运用知识进行的推理。例如：医生诊断疾病时，根据病人症状及检验结果，的推理。例如：医生诊断疾病时，根据病人症状及检验结果，运用医学知识进行推理，给出诊断结论及治疗方案。运用医学知识进行推理，给出诊断结论及治疗方案。l统计推理，是指根据对某事物的数据统计进行的推理。例如，统计推理，是指根据对某事物的数据统计进行的推理。例如，农民根据对农作物产量统计得出是否增产的结论，从而找出增农民根据对农作物产量统计得出是否增产的结论，从而找出增产或者减产的原因。产或者减产的原因。l直觉推理又称为

10、常识性推理，是指根据常识进行的推理。例如，直觉推理又称为常识性推理，是指根据常识进行的推理。例如，当你猛然发现头上有一物体掉落时，立即会意识到危险，并立当你猛然发现头上有一物体掉落时，立即会意识到危险，并立即躲开，这就是直觉推理。即躲开，这就是直觉推理。8l推理的控制策略推理的控制策略l智能系统的推理过程相当于人类的思维过程，即求智能系统的推理过程相当于人类的思维过程，即求解问题的过程。问题求解的质量与效率不仅依赖于解问题的过程。问题求解的质量与效率不仅依赖于所采用的求解方法，而且还依赖于求解问题的策略，所采用的求解方法，而且还依赖于求解问题的策略，即推理的控制策略。即推理的控制策略。l推理的

11、控制策略是指如何使用领域知识使推理过程推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。由于智能系统的推理过程一尽快达到目标的策略。由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又般表现为一种搜索过程，因此，推理的控制策略又可分为推理策略和搜索策略。其中，推理策略主要可分为推理策略和搜索策略。其中，推理策略主要解决推理方向、冲突消解等问题，如推理方向控制解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等，策略、求解策略、限制策略、冲突消解策略等，9l推理方向用来确定推理的控制方式，即用来确定推理过程是推理方向用来确定推理的控制

12、方式，即用来确定推理过程是从初始证据开始到目标，还是从目标开始到初始证据。按照从初始证据开始到目标，还是从目标开始到初始证据。按照对推理方向的控制，推理可分为正向推理、逆向推理、混合对推理方向的控制，推理可分为正向推理、逆向推理、混合推理及双向推理等推理及双向推理等4种。种。l求解策略是指仅求一个解，还是求所有解或最优解等。求解策略是指仅求一个解，还是求所有解或最优解等。l限制策略是指为了防止无穷的推理，以及推理过程太长而对限制策略是指为了防止无穷的推理，以及推理过程太长而对推理的深度、宽度、时间、空间等进行限制的策略。推理的深度、宽度、时间、空间等进行限制的策略。l冲突消解策略是指当推理过程

13、有多条知识可用时，如何从这冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。目前已多条可用知识中选出一条最佳知识用于推理的策略。目前已有多种消解冲突的策略，其基本思想都是对知识进行排序，有多种消解冲突的策略，其基本思想都是对知识进行排序，比如：按针对性排序；按已知事实的更新程度排序；按匹配比如：按针对性排序；按已知事实的更新程度排序；按匹配程度排序；按产生知识冗余大小排序；按产生结论的条件个程度排序；按产生知识冗余大小排序；按产生结论的条件个数排序等。数排序等。10消解原理l3.5.1 子句集的求取子句集的求取l3.5.2 消解推理规则消解推理规

14、则l3.5.3 含有变量的消解式含有变量的消解式l3.5.4 消解反演求解过程消解反演求解过程11消解原理(续)l知识表示方式知识表示方式:谓词公式谓词公式l解决问题解决问题:定理的自动证明定理的自动证明问题的自动求解问题的自动求解l消解原理消解原理由由Robinson于于1965年提出，又称为年提出，又称为归结归结原理原理。 将要证明的前提及结论合并在一起将要证明的前提及结论合并在一起, 化为子化为子句集句集,利用消解原理对子句集进行消解利用消解原理对子句集进行消解, 如果得到空如果得到空子句则成立子句则成立,否则失败否则失败.l例例:如果存在某个公理如果存在某个公理 E1E2 和另一公理和

15、另一公理E2 E3 ，那么，那么 E1E3 在逻辑上成立。这就是消解，在逻辑上成立。这就是消解，而称而称 E1 E3 为为 E1E2 和和E2 E3 的消解式的消解式（resolvent ）。）。 12子句集的求取l相关概念相关概念文字文字: 原子谓词公式及其否定统称为文字原子谓词公式及其否定统称为文字。子句子句: 任何文字的析取式称为子句任何文字的析取式称为子句。空子句空子句: 不包含任何文字的子句称为空子句。不包含任何文字的子句称为空子句。记为：或记为：或NIL子句集子句集:由子句和空子句所构成的集合称为子由子句和空子句所构成的集合称为子句集句集例例: P(x, y)Q(x, y),P(x

16、,y)U(x)V(y),Q(x, y)U(y)在谓词逻辑中，任一谓词演算公式可以化成在谓词逻辑中，任一谓词演算公式可以化成一个子句集一个子句集13子句集的求取（续）l子句集的化简步骤子句集的化简步骤:例例: (z)(x)(y)(P(x)Q(x)R(y)U(z)（1）利用等价关系消去蕴涵和双条件符利用等价关系消去蕴涵和双条件符(“”或或“”)PQ PQ ,PQ ( PQ)( QP )对于本例有对于本例有:( P(x)Q(x) R(y) ( P(x)Q(x)R(y)(z)(x)(y) (P(x)Q(x)R(y)U(z)14子句集的求取（续）l（2）减小否定符号的辖域使得否定符只作用于谓减小否定符号

17、的辖域使得否定符只作用于谓词符号词符号(原子公式原子公式)。狄狄摩根定律和量词转换率摩根定律和量词转换率( PQ ) PQ，( PQ ) PQ(x) P (x) P，(x) P (x)P对于本例有对于本例有:(z)(x)(y) (P(x)Q(x)R(y)U(z)15子句集的求取（续）l（3）对变量标准化（变元换名）对变量标准化（变元换名）在任一量词辖域内，受该量词约束的变量为一哑元在任一量词辖域内，受该量词约束的变量为一哑元(虚构变量虚构变量)，它可以在该辖域内处处统一地被另一，它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替，而不改变公式的个没有出现过的任意变量所代替，而不改变公

18、式的真值。合式公式中变量的标准化，意味着对哑元改真值。合式公式中变量的标准化，意味着对哑元改名以保证每个量词有其自己唯一的哑元。名以保证每个量词有其自己唯一的哑元。(x) P (x) (y) P (y)(x) P (x) (y) P (y)例：例： (x)A(x)(x)B(x)化为化为：(x)A(x)(y)B(y)16子句集的求取（续）l（4）消去存在量词）消去存在量词( skolem化化)Skolem函数函数: 在公式在公式( y)( x)P(x,y)中，存在量词是在中，存在量词是在全称量词的辖域内，我们允许所存在的全称量词的辖域内，我们允许所存在的x可能依赖于可能依赖于y值。值。令这种依赖

19、关系明显地由函数令这种依赖关系明显地由函数g(y)所定义，它把每个所定义，它把每个y值映值映射到存在的那个射到存在的那个x。这种函数叫做。这种函数叫做Skolem函数。函数。 如果用如果用Skolem函数代替存在的函数代替存在的x,我们就可以消去全部我们就可以消去全部存在量词，并写成：存在量词，并写成： ( y)P(g(y),y)不在任何全称量词辖域内的存在量词约束的变元用具体不在任何全称量词辖域内的存在量词约束的变元用具体没有出现过的常量代替没有出现过的常量代替。( x)P(x)化为化为P(A)在全称量词辖域内的存在量词约束的变元用新的在全称量词辖域内的存在量词约束的变元用新的skolem函

20、数符号代替函数符号代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)化为化为 (x)(P(x)Q(x)R(g(x)U(a)17子句集的求取（续）l（5）化为前束范式（量词左移）化为前束范式（量词左移）到这一步，已不留下任何存在量词，而且每个全称到这一步，已不留下任何存在量词，而且每个全称量词都有自己的变量。把所有全称量词移到公式的量词都有自己的变量。把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。前束形公式由的整个部分。所得公式称为前束形。前束形公式由前缀和母式组成，前缀由全称量词串组成，母

21、式由前缀和母式组成，前缀由全称量词串组成，母式由没有量词的公式组成，即没有量词的公式组成，即 前束形前束形 = (前缀前缀) (母母 式式) 全称量词串全称量词串 无量词公式无量词公式18子句集的求取（续）l（6）化为合取范式）化为合取范式(Skolem标准形标准形)合取范式合取范式: 谓词公式或谓词公式的否定的析取的有限集合组谓词公式或谓词公式的否定的析取的有限集合组成的合取成的合取, 叫做合取范式叫做合取范式。结合律结合律, 分配率分配率( PQ )R P( QR )( PQ ) R P( QR )P( QR ) ( PQ ) ( PR )P( QR ) ( PQ ) ( PR )对于本例

22、有对于本例有:(x)(P(x)Q(x)R(g(x)U(a)化为化为 (x)P(x)Q(x)R(g(x)U(a)结合结合律律化为化为 (x)P(x)R(g(x)U(a)Q(x)R(g(x)U(a)19子句集的求取（续）l（7）消去全称量词）消去全称量词:每个全称量词的辖域都是整个公式每个全称量词的辖域都是整个公式。P(x)R(f(x)U(a)Q(x)R(f(x)U(a)l（8）消去连词符号）消去连词符号（表示为子句集）（表示为子句集）方法方法: 用用A,B代替代替(AB)对于本例有对于本例有：P(x)R(f(x)U(a),Q(x)R(f(x)U(a)20子句集的求取（续）l（9）更换变量名称更换

23、变量名称使任意两个子句不出现同名的变量使任意两个子句不出现同名的变量。对于本例有对于本例有：P(x)R(f(x)U(a),Q(y)R(f(y)U(a)21子句集的求取（续）l例例：(x) P(x) (y) P(y) P(f(x, 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)3:对变量标准化对变量标准化(x) P(x) (y) P(y) P(f(x, y)( q)Q(x,

24、q) P(q)4：消去存在变量：消去存在变量(Skolem函数函数:q=W(x)(x) P(x) (y) P(y) P(f(x, y)Q(x, W(x) P(W(x)5:化为前束形化为前束形(x) (y) P(x) P(y) P(f(x, y)Q(x, W(x) P(W(x)6:化为合取范式化为合取范式(x) (y) (P(x) P(y) P(f(x, y)(P(x) Q(x, W(x) ) (P(x) P(W(x)22子句集的求取（续）7:消去全称变量消去全称变量(P(x) P(y) P(f(x, y)(P(x) Q(x, W(x) ) (P(x) P(W(x)8:消去合取符消去合取符P(x

25、) P(y) P(f(x, y)，P(x) Q(x, W(x) , P(x) P(W(x)9: 更换变量名更换变量名P(x) P(y) P(f(x, y)，P(x1) Q(x1, W(x1) , P(x2) P(W(x2)23子句集的求取（续）l经上述步骤化简得到的标准式是经过经上述步骤化简得到的标准式是经过Skolem化的前束范式，通常也称为化的前束范式，通常也称为S-标准形。要注意标准形。要注意S-标准形不是唯一的，若把它记为标准形不是唯一的，若把它记为Fs，则，则Fs仅仅是仅仅是F（未（未Skolem化的前束式）的一个特例，取用不同的化的前束式）的一个特例，取用不同的Skolem函数会得

26、到函数会得到不同的结果。当不同的结果。当F为非永假公式时，为非永假公式时，Fs与与F并不等价，但当并不等价，但当F为永假时，为永假时，Fs也一定是永假的，即也一定是永假的，即Skolem化并不影响化并不影响F的永假特性。这个结论很重的永假特性。这个结论很重要，可用定理形式描述如下：要，可用定理形式描述如下：l定理：若定理：若S是合式公式是合式公式F的的S-标准形之子句集，则标准形之子句集，则F为永假的充要条件是为永假的充要条件是S为不可满足的。为不可满足的。子句集中所有元素（即子句）的合取式不为真，则称该子句集为不可满子句集中所有元素（即子句）的合取式不为真，则称该子句集为不可满足的。足的。l

27、谓词演算体系中还有一些很重要的概念，如谓词演算的可判定性问题、谓词演算体系中还有一些很重要的概念，如谓词演算的可判定性问题、逻辑推论、推理规则的有效性、推理规则系统的完备性等等，对人工智逻辑推论、推理规则的有效性、推理规则系统的完备性等等，对人工智能推理机制的研究都很有用。能推理机制的研究都很有用。 24消解推理规则l消解式消解式:设设C1=L1和和C2= L2是两个没有公共是两个没有公共变元的子句变元的子句, L1和和L2分别是原子公式分别是原子公式（具有相（具有相同的谓词符号，但一般具有不同的变量）。同的谓词符号，但一般具有不同的变量）。如果如果L1和和L2存在最一般合一者存在最一般合一者

28、 , 那么消解那么消解C1和和C2推导出一个新子句推导出一个新子句() 称为称为C1和和C2的消解式的消解式。它是由取这两个子句的析取，然后消去互补它是由取这两个子句的析取，然后消去互补对而得到的对而得到的25消解推理规则(续)la) 假言推理假言推理P PQ(即即P Q) 消解式消解式Qlb) 合并合并PQ PQ 消解式消解式QQ=Qlc) 重言式重言式PQ PQ 消解式消解式QQ 或或PPld) 空子句空子句P P 消解式消解式NILle) 链式链式(三段论三段论)PQ(即即P Q) QR(即即Q R)消解式消解式PR(即即P R)26含有变量的消解式l对于含有变量的子句对于含有变量的子句

29、, 如果谓词符号相同如果谓词符号相同,而变而变量名不同量名不同, 则需要找一个置换作用于父辈子句则需要找一个置换作用于父辈子句, 使其含有互补文字使其含有互补文字, 再进行消解再进行消解。例例1: B(x) B(x)C(x) 消解式消解式C(x)例例2: P(x) Q(x) Q(f(y) 置换置换 =f(y)/x 消解式消解式P(f(y)例例3: Px, f(y)Q(x) Rf(a),y Pf(f(a),z R(z,w) 置换置换 =f(f(a)/x, f(y)/z消解式消解式: Qf(f(a) Rf(a),y Rf(y),w27消解反演求解过程l基本思想基本思想:反证法反证法:在反证法中首先

30、假定要证明的结论不成立，然后通过推导出存在反证法中首先假定要证明的结论不成立，然后通过推导出存在矛盾的方法，反证出结论成立。在归结法中首先对结论求反，在矛盾的方法，反证出结论成立。在归结法中首先对结论求反，然后将已知条件和结论的否定合在一起用子句集表达。如果该然后将已知条件和结论的否定合在一起用子句集表达。如果该子句集存在矛盾，则证明了结论的正确性。子句集存在矛盾，则证明了结论的正确性。思路：思路：设设S是已知条件和结论的否定合并后所对应的子句集。假是已知条件和结论的否定合并后所对应的子句集。假定有一种变换方法，可以对定有一种变换方法，可以对S实施一系列的变换。而且该变换实施一系列的变换。而且

31、该变换能够保证变换前后的子句集，在不可满足的意义下是等价的。能够保证变换前后的子句集，在不可满足的意义下是等价的。这样，如果最终得到的子句集是不可满足的，就证明了子句集这样，如果最终得到的子句集是不可满足的，就证明了子句集S是不可满足的，从而证明结论成立。是不可满足的，从而证明结论成立。由前面谓词公式转化为子句集的过程可知，子句集中的子由前面谓词公式转化为子句集的过程可知，子句集中的子句是句是与与的关系，如果在子句集中出现了空子句，则说明该子的关系，如果在子句集中出现了空子句，则说明该子句集是不可满足的。因此，归结过程就是句集是不可满足的。因此，归结过程就是寻找寻找空子句的过程。空子句的过程。

32、如果把这一过程看作是搜索的话，初始状态就是已知条件和结如果把这一过程看作是搜索的话，初始状态就是已知条件和结论的否定对应的子句集，而目标就是空子句，规则就是归结。论的否定对应的子句集，而目标就是空子句，规则就是归结。28消解反演求解过程l1. 消解反演消解反演已知一个公式集已知一个公式集S和目标公式和目标公式L, 通过反证或反通过反证或反演来求证目标公式演来求证目标公式L, 证明步骤如下证明步骤如下: 否定否定L, 得到得到L; 把把L添加到添加到S中去中去; 把新产生的集合把新产生的集合L, S化成子句集化成子句集; 应用消解原理应用消解原理, 力图推导出一个表示矛盾的力图推导出一个表示矛盾

33、的空子句。空子句。29消解反演求解过程（续）l反演求解的正确性反演求解的正确性 设公式设公式L在逻辑上遵循公式集在逻辑上遵循公式集S，那么按照定义，那么按照定义满足满足S的每个解释也满足的每个解释也满足L。决不会有满足。决不会有满足S的解释的解释能够满足能够满足L的，所以不存在能够满足并集的，所以不存在能够满足并集SL的解释。的解释。如果一个公式集不能被任一解释所满足，那么这如果一个公式集不能被任一解释所满足，那么这个公式是不可满足的。因此，如果个公式是不可满足的。因此，如果L在逻辑上遵循在逻辑上遵循S，那么那么SL是不可满足的。是不可满足的。可以证明，如果消解反演反复应用到不可满足的可以证明

34、，如果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句子句集，那么最终将要产生空子句NIL。因此，如果。因此，如果L在逻辑上遵循在逻辑上遵循S，那么由并集，那么由并集SL消解得到消解得到的子句，最后将产生空子句；反之，可以证明，如的子句，最后将产生空子句；反之，可以证明，如果从果从SL的子句消解得到空子句，那么的子句消解得到空子句，那么L在在逻辑上遵循逻辑上遵循S。 30消解反演求解过程（续）例例: 已知已知: 每个储蓄钱的人都获得利息每个储蓄钱的人都获得利息结论结论: 如果没有利息如果没有利息, 那么就没有人去储蓄钱。那么就没有人去储蓄钱。证明证明: 定义谓词定义谓词:S(x,y)

35、: 表示表示”x储蓄储蓄y”M(x): 表示表示”x是钱是钱”I(x): 表示表示”x是利息是利息”E(x,y): 表示表示”x获得获得y”已知已知: (x)(y)(S(x,y) M(y) (y)(I(y) E(x,y)结论结论: (x)I(x) (x) (y)(M(y) S(x,y)31消解反演求解过程（续）1. 否定结论否定结论: (x)I(x) (x) (y)(M(y) S(x,y)2. 把结论加入已知把结论加入已知, 构成新集合构成新集合G:(x)(y)(S(x,y) M(y) (y)(I(y) E(x,y), (x)I(x)(x) (y)(M(y) S(x,y)3. 将集合将集合G化

36、为子句集（化为子句集（y=f(x)为为Skolem函数函数 ）(1) S(x,y)M(y) I(f(x)(2) S(x,y) M(y) E(x,f(x)(3) I(z)(4) S(a,b)(5) M(b)32消解反演求解过程（续）4. 应用消解原理进行推导。应用消解原理进行推导。(1) S(x,y)M(y) I(f(x)(2) S(x,y) M(y) E(x,f(x)(3) I(z)(4) S(a,b)(5) M(b)(6) S(x,y)M(y) (1)和和(3)消解消解=f(x)/z(7) M(b) (6)和和(4)消解消解=a/x,b/y(8) NIL (5)和和(7)消解消解33消解反演

37、求解过程（续）消解反演可以表示为一棵反演树消解反演可以表示为一棵反演树34消解反演求解过程（续）l归结方法很简单，但是即便是对于一个比较简单的归结方法很简单，但是即便是对于一个比较简单的问题，往往可以进行归结的子句也比较多。如何从问题，往往可以进行归结的子句也比较多。如何从众多的可归结的子句中选择两个子句，即为搜索策众多的可归结的子句中选择两个子句，即为搜索策略问题。不同的搜索策略，会影响到系统的效率和略问题。不同的搜索策略，会影响到系统的效率和开销，同时也会涉及到完备性问题。开销，同时也会涉及到完备性问题。l搜索策略的目标就是要找到一棵归结反演树。一个搜索策略的目标就是要找到一棵归结反演树。

38、一个反演系统当存在一个矛盾时，如果使用的一种策略，反演系统当存在一个矛盾时，如果使用的一种策略，最终都将找到一棵反演树（即能找到矛盾），则这最终都将找到一棵反演树（即能找到矛盾），则这种策略是完备的。在实际应用中，有些策略虽不完种策略是完备的。在实际应用中，有些策略虽不完备，但具有极高的效率，也是可取的。备，但具有极高的效率，也是可取的。l提高策略效率的一些作法是：只归结含有互补对的提高策略效率的一些作法是：只归结含有互补对的文字；及时删去出现的重言式和被其他子句所包含文字；及时删去出现的重言式和被其他子句所包含的子句；每次归结都取与目标公式否定式有关的子的子句；每次归结都取与目标公式否定式有

39、关的子句作为母子句之一进行归结等等。句作为母子句之一进行归结等等。35消解反演求解过程（续）l2. 反演求解过程反演求解过程问题的求解问题的求解利用消解反演除了可以实现定理的自动证明利用消解反演除了可以实现定理的自动证明之外，也可以对简单问题进行求解。之外，也可以对简单问题进行求解。例例: 张和李是同班同学，如果张和李是同班同学，如果x和和y是同班同学，是同班同学，则则x的教室也是的教室也是y的教室，现在张在的教室，现在张在302教室上教室上课。问现在李在哪里上课？课。问现在李在哪里上课？36消解反演求解过程（续）l从反演树求问题答案的过程从反演树求问题答案的过程：1. 把问题的已知条件用谓词

40、公式表示出来把问题的已知条件用谓词公式表示出来，并化为相，并化为相应的子句集应的子句集；2. 把问题的目标的否定用谓词公式表示出来，并化为把问题的目标的否定用谓词公式表示出来，并化为子句集子句集；3. 对目标否定子句集中的每个子句，构造该子句的重对目标否定子句集中的每个子句，构造该子句的重言式（即把该目标否子句和此目标否定子句的否定言式（即把该目标否子句和此目标否定子句的否定之间再进行析取所得到的子句），用这些重言式代之间再进行析取所得到的子句），用这些重言式代替相应的目标否定子句，并把这些重言式加入到前替相应的目标否定子句，并把这些重言式加入到前提子句集中，得到一个新的子句集提子句集中，得到

41、一个新的子句集。37消解反演求解过程（续）4. 对这个新的子句集，应用消解原理求出其反对这个新的子句集，应用消解原理求出其反演证明树，这时证明树的根子句不为空，称演证明树，这时证明树的根子句不为空，称这个证明树为修改证明树这个证明树为修改证明树；5. 用修改证明树的根子句作为回答语句，则答用修改证明树的根子句作为回答语句，则答案就在此根子句中案就在此根子句中。38消解反演求解过程（续）l例：如果无论约翰例：如果无论约翰(JOHN)到哪里去到哪里去,菲多菲多(FIDO)也也就去那里就去那里,那么如果约翰在学校里那么如果约翰在学校里,菲多在哪里呢菲多在哪里呢?解：解：定义谓词定义谓词：AT（x,

42、y）:表示表示x在在y处处1. 已知的谓词表示已知的谓词表示:(x)AT(JOHN,x) AT(FIDO,x),AT(JOHN, SCHOOL)化为子句集化为子句集: AT(JOHN,y)AT(FIDO, y),AT(JOHN, SCHOOL) 39消解反演求解过程（续）2. 目标否定的谓词表示目标否定的谓词表示：(x)AT(FIDO, x), (x) AT(FIDO, x)化为子句集化为子句集: AT(FIDO, x) 3. 构造目标否定子句的重言式构造目标否定子句的重言式,并代替原子句并代替原子句 AT(FIDO, x)AT(FIDO, x) 4. 将将3得到的子句集加入前提子句集中得到的

43、子句集加入前提子句集中:G= AT(JOHN,y)AT(FIDO, y),AT(JOHN,SCHOOL) ,AT(FIDO,x)AT(FIDO, x)40消解反演求解过程（续）5. 对新子句集对新子句集G应用消解原理求出反演树应用消解原理求出反演树:G= AT(JOHN,y)AT(FIDO, y),AT(JOHN, SCHOOL) ,AT(FIDO,x)AT(FIDO, x)41消解反演求解过程（续）例：张某被盗，公安局派出五个侦察员去调查。例：张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员研究案情时，侦察员A说说“赵与钱中至少有一赵与钱中至少有一人作案人作案”；侦察员；侦察员B说说

44、“钱与孙中至少有一人钱与孙中至少有一人作案作案”；侦察员；侦察员C说说“孙与李中至少有一人作孙与李中至少有一人作案案”；侦察员；侦察员D说说“赵与孙中至少有一人与此赵与孙中至少有一人与此案无关案无关”；侦察员；侦察员E说说“钱与李中至少有一人钱与李中至少有一人与此案无关与此案无关”。如果这五个侦察员的话都是。如果这五个侦察员的话都是可信的，试用消解反演推理求出谁是盗窃犯。可信的，试用消解反演推理求出谁是盗窃犯。定义谓词：定义谓词：P（x）：）：x作案。作案。42消解反演求解过程（续）由五个侦察员的话为真，有由五个侦察员的话为真，有P（z） P（q） （1）P（q） P（s） （2）P（s） P

45、（l） （3） P（z） P（s） （4） P（q） P（l） （5）把结论的否定加入结论的否定的否定的子句中去，得：把结论的否定加入结论的否定的否定的子句中去，得： P（x）v P（x） （6）因为这些全都是子句，所以化为子句集的步骤可以省略了。因为这些全都是子句，所以化为子句集的步骤可以省略了。（1），（），（4）归结得：）归结得：P（q） P（s） （7）（2），（），（7）归结得：）归结得：p（q） （8）即：钱是盗窃犯。即：钱是盗窃犯。43规则演绎系统l消解反演的局限消解反演的局限:实际应用中实际应用中, 很多的事实更直观地表现为若干的规则很多的事实更直观地表现为若干的规则 If T

46、hen ( 如果那么如果那么)其中其中If 部分称为前项部分称为前项, Then部分称为后项部分称为后项。其中，。其中，If部分部分可能由几个可能由几个if组成，而组成，而Then部分可能由一个或一个以上的部分可能由一个或一个以上的then组成组成例例: 表示为蕴含式表示为蕴含式:ABC, ACB,ABC, BAC都与子句都与子句: ABC 等价等价一些重要信息在求取子句集过程中丢失一些重要信息在求取子句集过程中丢失;问题描述方式不自然问题描述方式不自然。44规则演绎系统（续）l规则演绎系统规则演绎系统: 基于规则求解问题的系统叫做规则演基于规则求解问题的系统叫做规则演绎系统绎系统.两种推理方

47、向两种推理方向 正向推理正向推理: 从从if部分向部分向then部分推理的过程部分推理的过程, 叫做正向推理叫做正向推理。 逆向推理逆向推理: 从从then部分向部分向if部分推理的过程部分推理的过程, 叫做逆向推理叫做逆向推理。按推理方向分类按推理方向分类 规则正向演绎系统规则正向演绎系统: 从事实出发利用规则推从事实出发利用规则推导出结论导出结论。 规则逆向演绎系统规则逆向演绎系统: 从目标出发利用规则推从目标出发利用规则推导出事实导出事实。 规则双向演绎系统规则双向演绎系统45规则正向演绎系统l规则正向演绎系统规则正向演绎系统: 是从已知事实出发是从已知事实出发,正向使正向使用规则对事实

48、表达式的与或树进行变换，直用规则对事实表达式的与或树进行变换，直到找到一个含有目标节点的一致解树为止到找到一个含有目标节点的一致解树为止。已知事实已知事实: 事实表达式的与或树事实表达式的与或树目标表达式：限制为文字的析取式目标表达式：限制为文字的析取式F规则规则: LW, 其中其中L为单文字为单文字, W为与或形为与或形。结束条件结束条件: 目标表达式是析取式目标表达式是析取式。 得到结束于得到结束于目标节点的一致解树目标节点的一致解树。46规则正向演绎系统（续）l1. 事实表达式的与或形变换事实表达式的与或形变换l2. 事实表达式的与或树表示事实表达式的与或树表示l3. 与或与或图的图的F

49、规则规则变换变换l4. 目标公式的表示形式目标公式的表示形式l5. 规则正向演绎推理过程规则正向演绎推理过程47规则正向演绎系统（续）l1. 事实表达式的与或形变换事实表达式的与或形变换规则正向演绎系统中要求事实表达式化简为与或形规则正向演绎系统中要求事实表达式化简为与或形。(1) 消去消去”蕴含蕴含”和和”双条件双条件”符号符号;(2) 减小否定符号的辖域减小否定符号的辖域, 使否定符号只作用于原子公使否定符号只作用于原子公式式;(3) 利用利用Skolem函数消去存在量词函数消去存在量词;(4) 对变量进行换名对变量进行换名，使得不同的使得不同的主要合取式中主要合取式中，具有具有不同的变量

50、名不同的变量名; ;(5) 隐去全称量词，默认公式中的变量受全称量词约束隐去全称量词，默认公式中的变量受全称量词约束。48规则正向演绎系统（续）例例: (x) (y) (Q( y, x) (R(y) P(y)S(x, y)消去量词化为消去量词化为:Q( y, a) (R(y) P(y) S(a, y)再变量更名化为再变量更名化为:Q( z, a) (R(y) P(y) S(a, y)49规则正向演绎系统（续）l2. 事实表达式的与或树事实表达式的与或树(图图)表示表示子表达式间的与、或关系规定如下子表达式间的与、或关系规定如下:当母表达式为当母表达式为E1E2E3Ek时，则每时，则每一个子表达

51、式一个子表达式Ei被表示成一个后继节点，并由被表示成一个后继节点，并由一个一个k-连接符来连接，即表示成与关系；连接符来连接，即表示成与关系；当母表达式为当母表达式为E1E2E3Ek时，则每时，则每一个子表达式一个子表达式Ei均由均由1-连接符连接，即表示成连接符连接，即表示成或关系。或关系。50规则正向演绎系统（续）l与或形表达的是一个事实，其逻辑值应该为与或形表达的是一个事实，其逻辑值应该为“真真”。对于与或形中用符号。对于与或形中用符号“”连接的部连接的部分，其逻辑值如果为真的话，其每一子部分分，其逻辑值如果为真的话，其每一子部分单独也必须为真。因此在与或图中可以表示单独也必须为真。因此

52、在与或图中可以表示为为“或或”，表示每一子部分是独立的。，表示每一子部分是独立的。l而对于与或形中用符号而对于与或形中用符号连接的部分，其连接的部分，其逻辑值如果为真的话，并不说明其每一子部逻辑值如果为真的话，并不说明其每一子部分也必须为真。只有它们分也必须为真。只有它们共同共同在一起才为在一起才为真，这些子部分之间是相互关联的。因此在真，这些子部分之间是相互关联的。因此在与或图中用与或图中用k连接符表示为连接符表示为与与。51规则正向演绎系统（续）lQ( z, a) (R(y) P(y) S(a, y)事实表达的与或树表达式事实表达的与或树表达式52规则正向演绎系统（续）l与或树所有结束于叶

53、节点的解树的求法与或树所有结束于叶节点的解树的求法从根节点从根节点(初始结点初始结点)开始，正确选择一个外向开始，正确选择一个外向连接符，再从该连接符所指的每一个后继节连接符，再从该连接符所指的每一个后继节点出发，继续选一个外向连接符，如此进行点出发，继续选一个外向连接符，如此进行下去直到结束在叶结点上为止下去直到结束在叶结点上为止。例例: 求上例中的事实表达式的与或树的解树求上例中的事实表达式的与或树的解树53规则正向演绎系统（续）54规则正向演绎系统（续）l与或树的性质与或树的性质:事实表达式的子句集与事实表达式的与或树解树集事实表达式的子句集与事实表达式的与或树解树集是一一对应的关系是一

54、一对应的关系。事实表达式的与或树解树集中的每个解树都对应着事实表达式的与或树解树集中的每个解树都对应着子句集中的一个子句子句集中的一个子句。解树集中每个解树的叶节点上的文字的析取就是子解树集中每个解树的叶节点上的文字的析取就是子句集中的一个子句句集中的一个子句。例例: Q( z, a) (R(y) P(y) S(a, y)化为子句集化为子句集:Q( z, a), R(y)S(a, y), P(y)S(a, y)55规则正向演绎系统（续）l3. 与或与或图的图的F规则变换规则变换规则是建立在某个问题辖域中普通陈述性知识的蕴规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。把允许用作规则

55、的公式类型限制涵公式基础上的。把允许用作规则的公式类型限制为下列形式为下列形式 F规则规则: LW其中其中, L为单文字为单文字, W为与或形唯一公式。为与或形唯一公式。假设出现在蕴涵式中的任何变量都有全称量化作假设出现在蕴涵式中的任何变量都有全称量化作用于整个蕴涵式。这些事实和规则中的一些变量被用于整个蕴涵式。这些事实和规则中的一些变量被分离标准化，使得没有一个变量出现在一个以上的分离标准化，使得没有一个变量出现在一个以上的规则中，而且使规则变量不同于事实变量。单文字规则中，而且使规则变量不同于事实变量。单文字前项的任何蕴涵式，不管其量化情况如何都可以化前项的任何蕴涵式，不管其量化情况如何都

56、可以化为某种量化辖域为整个蕴涵式的形式为某种量化辖域为整个蕴涵式的形式56规则正向演绎系统（续）F规则的化简规则的化简例例: (x) (y) (z) P(x, y, z)(u) Q(x, u)(1) 暂时消去蕴涵符号暂时消去蕴涵符号;(x) (y) (z) P(x, y, z) (u) Q(x, u)(2) 减少否定符号的辖域减少否定符号的辖域, 使仅作用于文字使仅作用于文字;(x) (y) (z) P(x, y, z) (u) Q(x, u)(3) 消去存在量词消去存在量词Skolem化化;(x) (y) P(x, y, f(x,y) (u) Q(x, u)(4) 化成前束式并消去全称量词化

57、成前束式并消去全称量词; P(x, y, f(x,y) Q(x, u)(5) 恢复蕴涵式表示恢复蕴涵式表示。化简为化简为: P(x, y, f(x, y) Q(x, u)57规则正向演绎系统（续）对规则作单文字前项的限制将大大简化了应用时的对规则作单文字前项的限制将大大简化了应用时的匹配过程，对非单文字前项的情况，匹配过程，对非单文字前项的情况，(L1L2) W转换成转换成: L1 W, L2 Wl4. 目标公式的表示形式目标公式的表示形式 目标公式要求目标公式要求: 子句形即文字的析取式子句形即文字的析取式 子句形的化简步骤子句形的化简步骤: 消去蕴涵符消去蕴涵符; 减小否定符号的辖域减小否

58、定符号的辖域;对变元标准化对变元标准化（变元换名（变元换名）; 化为前束范式（量词左移化为前束范式（量词左移）; 消去全称量词消去全称量词( 对偶形式的对偶形式的skolem化化); 进行变元换名进行变元换名, 使不同的主析取元具有不同的变元使不同的主析取元具有不同的变元; 消去存在量词消去存在量词, 变量都受存在量词的约束变量都受存在量词的约束;58规则正向演绎系统（续）例例: (y) (x) (P (x, y)Q (x, y)用用Skolem函数消去全称量词有函数消去全称量词有:(y) (P ( f (y), y)Q ( f (y), y)进行变量更名有进行变量更名有:(y) (P ( f

59、 (y), y)(z) Q ( f (z), z)消去存在量词消去存在量词:P ( f (y), y) Q ( f (z), z)59规则正向演绎系统（续）l5. 规则正向演绎推理过程规则正向演绎推理过程 规则正向演绎推理过程规则正向演绎推理过程: 就是不断的就是不断的对事实表达式的与或树施以对事实表达式的与或树施以F规则变换规则变换,直到找直到找到一个一致解树到一个一致解树, 该解树中的所有叶节点全部该解树中的所有叶节点全部都与目标公式中的文字匹配为止。都与目标公式中的文字匹配为止。如何进行如何进行F规则变换规则变换?如何判断终止如何判断终止?60规则正向演绎系统（续）l 命题逻辑的规则正向

60、演绎过程命题逻辑的规则正向演绎过程 F规则变换规则变换: 如果在与或树中有一个叶如果在与或树中有一个叶节点刚好与某节点刚好与某F规则规则LW的前件的前件L匹配，则将匹配，则将该叶节点与该叶节点与L用一个匹配弧连接起来，将规则用一个匹配弧连接起来，将规则后件后件W添加到与或树中。这样添加到与或树中。这样, 就对与或树用就对与或树用规则规则LW实施了一次变换实施了一次变换, 得到了一个得到了一个“更新更新”了的与或树了的与或树。例例: 事实表达式的与或形为事实表达式的与或形为:(PQ)R)(S(TU)规则规则: S (XY)Z61规则正向演绎系统（续）应用应用F规则得到的新与或树规则得到的新与或树