1、第四章 推理方法 要使计算机具有智能，仅仅使它拥有知识还不够，还必须使其具有运用知识进行推理，实现问题求解的能力。因此有关推理方法的研究是人工智能的重要课题之一。4.1 推理概述推理概述4.1 推理概述推理概述4.1.1 推理的基本概念推理的基本概念 所谓推理是指从已知事实出发，运用已所谓推理是指从已知事实出发，运用已掌握的知识，推导出其中蕴涵的事实性结掌握的知识，推导出其中蕴涵的事实性结论或归纳出某些新的结论的过程。论或归纳出某些新的结论的过程。 推理过程实际上也就是一个问题求解的推理过程实际上也就是一个问题求解的过程。过程。推理概述推理概述4.1.2 推理的方法及其分类推理的方法及其分类1
2、. 按照推理的逻辑基础分类按照推理的逻辑基础分类（1）演绎推理）演绎推理 演绎推理是从已知的一般性知识出发，演绎推理是从已知的一般性知识出发，推理出适合于某种个别情况的结论的过程。推理出适合于某种个别情况的结论的过程。它是一种由一般到个别的推理方法。它是一种由一般到个别的推理方法。例如：例如：A. 音乐系的学生至少会弹奏一种乐器；音乐系的学生至少会弹奏一种乐器；B. 李聪是音乐系的学生；李聪是音乐系的学生；C. 李聪至少会弹奏一种乐器。李聪至少会弹奏一种乐器。（2）归纳推理）归纳推理 归纳推理是从大量特殊事例出发，归纳归纳推理是从大量特殊事例出发，归纳出一般性结论的推理过程，是一种由个别出一般
3、性结论的推理过程，是一种由个别到一般的推理方法。其基本思想是：首先到一般的推理方法。其基本思想是：首先从已知事实中猜测出一个结论，然后对这从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认，数学归纳个结论的正确性加以证明确认，数学归纳法就是归纳推理的一种典型例子。法就是归纳推理的一种典型例子。（3）默认推理）默认推理 默认推理又称缺省推理，是在知识不默认推理又称缺省推理，是在知识不完全的情况下假设某些已经具备所进行的完全的情况下假设某些已经具备所进行的推理。推理。2. 按所用知识的确定性分类按所用知识的确定性分类3. 按推理过程的单调性分类按推理过程的单调性分类 4.1.3 推理的
4、控制策略推理的控制策略 智能系统的推理过程其实就是问题求解的过智能系统的推理过程其实就是问题求解的过程，它不仅依赖于所用的推理方法，同时也依赖程，它不仅依赖于所用的推理方法，同时也依赖于推理的控制策略。推理的控制策略包括推理方于推理的控制策略。推理的控制策略包括推理方向、搜索策略、冲突消解策略、求解策略、限制向、搜索策略、冲突消解策略、求解策略、限制策略；而推理方法则是推理控制策略确定之后，策略；而推理方法则是推理控制策略确定之后，在进行具体推理时所要采取的匹配方法或不确定在进行具体推理时所要采取的匹配方法或不确定性传递算法等方法。性传递算法等方法。1.正向推理正向推理正向推理又称为正向链接推
5、理，它是一种数据驱动的推理方式，其推理基础是逻辑演绎的推理链，它从一组表示事实的谓词或命题出发，使用一组推理规则，来证明目标谓词公式或命题是否成立。 正向推理过程的算法描述：（1）把用户提供的初始数据或已知事实放入到综合数据库。（2）检查综合数据库中是否包含了问题的解，若有，则求解结束，并成功推出；否则执行（3）；（3）检查知识库中是否有与综合数据库中已有事实相匹配的知识，若有，则将所有的匹配知识构成当前匹配知识集，转（4）；否则转（5）；（4）按照某种冲突消解策略，从当前匹配知识集中选出一条知识作为启用知识用于进行推理，并将推出的新事实或证据加入到综合数据库中，然后转（2）；（5）询问用户是
6、否可以进一步补充新的事实或证据，若可补充，则将补充的事实或证据加入综合数据库中，然后转（3）；否则表示无解，失败退出。例如，有规则集如下： 规则1： IF P1 THEN P2 规则2： IF P2 THEN P3 规则3： IF P3 THEN q3 规则中的P1、P2、P3、q3可以是谓词公式或命题。设总数据库（工作存储器）中已有事实P1，则应用这三条规则进行正向推理，即从P1出发推导出q3的过程如下图所示。2.反向推理 （逆向推理）反向推理又称为后向链接推理，它是一种目标驱动的推理方式，其基本原理是从表示目标的谓词或命题出发，使用一组规则证明事实谓词或命题成立，即提出一批假设（目标），然
7、后逐一验证这些假设。 首先假定目标q3成立，由规则（P3q3），为证明q3成立，须先验证P3是否成立；但总数据库没有事实P3，所以假定子目标P3成立；由规则（P2P3），应验证P2；同样，由于数据库中没有事实P2，假定子目标P2成立；由规则（P1P2），为验证P2成立，须先验证P1。因为数据库中有事实P1，所以假定的目标P2成立，因而P3成立，最终导出结论q3确实成立。举例如下：仍用上述的三条规则为例，应用反向推理方法，从P1出发推导出q3的过程如下图所示： 总之，反向推理的具体实现策略是：先假定一个可能的目标，系统试图证明它，看此假设目标是否在总数据库中，若在，则假设成立。否则，看这些假设是
8、否证据（叶子）结点，若是，向用户询问，若不是，则再假定另一个目标，即找出结论部分中包含此假设的那些规则，把它们的前提作为新的假设，试图证明它。这样周而复始，直到所有目标被证明，或所有路径被测试。3.双向推理双向推理 又称为正反向混合推理，它综合了正向推理和逆向推理的长处，克服了了两者的短处。 双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。 具体的推理策略有多种。例如，通过数据驱动帮助选择某个目标，即从初始证据（事实）出发进行正向推理，同时以目标驱动求解该目标，通过交替使用正逆向混合推理对问题进行求解。双方推理的控制策略比前两种方法都
9、要复杂。美国斯坦福研究所人工智能中心研制的基于规则的专家系统工具KAS，就是采用正、逆向混合推理的产生式系统的一个典型例子。下图给出双向混合推理过程的示意图。 4.1.2 推理的冲突消解策略推理的冲突消解策略 在利用推理求解问题的过程中，如果综在利用推理求解问题的过程中，如果综合数据库中的已知事实与知识库中的多条合数据库中的已知事实与知识库中的多条知识相匹配，或者有多个已知事实都可与知识相匹配，或者有多个已知事实都可与知识库中的某一条知识相匹配，或者有多知识库中的某一条知识相匹配，或者有多个已知事实与知识库中的多条知识相匹配，个已知事实与知识库中的多条知识相匹配，则称这种情况为知识冲突。此时，
10、需要按则称这种情况为知识冲突。此时，需要按照某种策略从这多条匹配的知识中选择一照某种策略从这多条匹配的知识中选择一条最佳知识用于推理，这种解决冲突的过条最佳知识用于推理，这种解决冲突的过程称为冲突消解。程称为冲突消解。（1）按就近原则排序（2）按知识特殊性排序（3）按上下文限制排序（4）按知识的新鲜性排序（5）按知识的差异性排序（6）按领域知识的特点排序（7）按规则的次序排序（8）按前提条件的规模排序 4.2 命题逻辑命题逻辑 命题逻辑与谓词逻辑是最先应用于人工命题逻辑与谓词逻辑是最先应用于人工智能的两种逻辑，对于知识的形式化表示，智能的两种逻辑，对于知识的形式化表示，特别是定理的自动证明发挥
11、了重要作用，特别是定理的自动证明发挥了重要作用，在人工智能的发展史中占有重要地位。在人工智能的发展史中占有重要地位。 谓词逻辑是在命题逻辑的基础上发展起谓词逻辑是在命题逻辑的基础上发展起来的，命题逻辑可看作是谓词逻辑的一种来的，命题逻辑可看作是谓词逻辑的一种特殊形式，在讨论谓词逻辑之前，先来介特殊形式，在讨论谓词逻辑之前，先来介绍命题逻辑的基本概念。绍命题逻辑的基本概念。4.2.1 命题命题 定义定义3.1 能够分辨真假的语句称做命题。能够分辨真假的语句称做命题。 定义定义3.2 一个语句如果不能再进一步分解一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称成更简单的语句，并且
12、又是一个命题，则称此命题为原子命题。此命题为原子命题。 原子命题是命题中的基本单位。原子命题是命题中的基本单位。 命题，比如命题，比如“太阳从东边升起太阳从东边升起”，“雪是雪是白的白的”4.2.2 命题公式命题公式1. 连接词连接词 命题逻辑中，可以通过连接词将一些原子命题命题逻辑中，可以通过连接词将一些原子命题连接起来，构成复合命题，以表示复杂的定义。连接起来，构成复合命题，以表示复杂的定义。 称为称为“非非”或或“否定否定”。 称为称为 “析取析取”。表示被它连接的两个命题具。表示被它连接的两个命题具有有“或或”的关系。的关系。 称为称为 “合取合取”。表示被它连接的两个。表示被它连接的
13、两个命题具有命题具有“与与”的关系。的关系。 称为称为“条件条件”或或“蕴涵蕴涵”. PQ表示表示“P蕴涵蕴涵Q”，即即“如果如果P，则则Q”，其中其中P为为条件的前提，条件的前提，Q为条件的后件。为条件的后件。 称为称为“双条件双条件”. PQ表示表示“P当且仅当且仅当当Q”AI的产生及主要学派2. 命题公式命题公式定义定义4.3 下面的递归形式给出命题公式的定义：下面的递归形式给出命题公式的定义：（1）原子公式是命题公式原子公式是命题公式（2）A是命题公式，则是命题公式，则A也是命题公式；也是命题公式；（3）若）若A和和B都是命题公式，则都是命题公式，则AB，AB，A B，A B也都是命题
14、公式也都是命题公式（4）只有（）只有（1）（）（3）所得的公式才是命题公）所得的公式才是命题公式。式。4.3 谓词逻辑谓词逻辑3.3.1 谓词与个体谓词与个体 在谓词逻辑中，将原子命题分解为谓词与个体两在谓词逻辑中，将原子命题分解为谓词与个体两部分。部分。 例如，例如，“贝多芬是作曲家贝多芬是作曲家”中，中，“是作曲家是作曲家”是是谓词，谓词， “贝多芬贝多芬”是个体。所谓个体是指可以独立是个体。所谓个体是指可以独立存在的物体，它可以是抽象的，也可以是具体的。存在的物体，它可以是抽象的，也可以是具体的。 例如，例如，“李白是诗人李白是诗人”这个命题，若用这个命题，若用poet表示表示“是诗人是
15、诗人”，用，用Libai表示个体表示个体“李白李白”，则得到的，则得到的谓词是谓词是poet(Libai). 又如，又如，53,这个不等式可用谓词表示为这个不等式可用谓词表示为greater(5,3) 谓词的一般形式是：谓词的一般形式是： P（x1,x2,xn）其中其中P是谓词，是谓词，x1,x2,xn是个体。是个体。 例如，例如，“小刘的哥哥是工人小刘的哥哥是工人”，可以表，可以表示为示为worker(brother(Liu),其中其中brother(Liu)是一个函数。个体常数，变量和函数统称是一个函数。个体常数，变量和函数统称为为项项。 谓词中包含的个体数目称为谓词的元数，例谓词中包含的
16、个体数目称为谓词的元数，例如如P(x)是一元谓词，是一元谓词，P(x,y)是二元谓词，而是二元谓词，而P(x1,x2,xn)是是n元谓词。元谓词。 在谓词在谓词P(x1,x2,xn)中，若中，若xi(i=1,2,n)都是都是个体常量、变元或函数，则称它为一阶谓词。如个体常量、变元或函数，则称它为一阶谓词。如果果xi本身又是一个一阶谓词，则称它为二阶谓词，本身又是一个一阶谓词，则称它为二阶谓词，依次类推。依次类推。 谓词和函数从形式上看很相似，其实它们有谓词和函数从形式上看很相似，其实它们有着本质的区别，是两个完全不同的概念。谓词具着本质的区别，是两个完全不同的概念。谓词具有逻辑值有逻辑值“真真
17、”或或“假假”，而函数则是某个个体，而函数则是某个个体到另一个个体之间的映射。到另一个个体之间的映射。3.3.2 谓词公式谓词公式 1. 连接词连接词 与命题逻辑中相同。与命题逻辑中相同。 2. 量词量词 全称量词（全称量词（x）表示）表示“对于个体域中的对于个体域中的所有个体所有个体x”；存存在量词在量词( (x)x)表示表示“在个体在个体域中存在个体域中存在个体x”.x”. 3. 谓词演算公式谓词演算公式 定义定义4.4 谓词演算中，由某个谓词构成谓词演算中，由某个谓词构成的不含任何连接词的公式，叫做原子谓词的不含任何连接词的公式，叫做原子谓词公式。一般一个形如公式。一般一个形如F(x1,
18、x2,xn)的谓词的谓词公式，称作公式，称作原子谓词公式原子谓词公式，或简称，或简称原子原子，其中其中F为为n元谓词，而元谓词，而x1,x2,xn为个体变为个体变元。元。定义定义4.5 可按下列规则得到谓词演算的合式公式可按下列规则得到谓词演算的合式公式如下：如下：(1) 原子谓词公式是合式公式；原子谓词公式是合式公式；(2) A是合式公式，则是合式公式，则A也是合式公式；也是合式公式；(3) 若若A和和B都是合式公式，则都是合式公式，则AB，AB，A B，AB也都是合式公式也都是合式公式(4) 若若A是合式公式，是合式公式，x是一个体变元，则是一个体变元，则(x)A和和(x)A也都是合式公式
19、也都是合式公式(5) 只有只有(1)(4)所得的公式才是合式公式。所得的公式才是合式公式。 谓词演算公式就是一个按照一定规谓词演算公式就是一个按照一定规则由原子公式、连接词、量词及圆括则由原子公式、连接词、量词及圆括号所组成的字符串。号所组成的字符串。 例如： ( (x)P(x,y), x)P(x,y), ( (x)(P(x)x)(P(x)P(y) P(y) 4. 谓词辖域与约束变元谓词辖域与约束变元 在一个公式中，如果有量词出现，位于在一个公式中，如果有量词出现，位于量词后面的单个量词或者用括弧括起来的量词后面的单个量词或者用括弧括起来的合式公式称为合式公式称为量词的辖域量词的辖域。在辖域内
20、与量。在辖域内与量词中同名的变元称为词中同名的变元称为约束变元约束变元，不受约束，不受约束的变元称为的变元称为自由变元自由变元。 3.3.3 谓词公式的永真性与可满足性谓词公式的永真性与可满足性1. 谓词公式的解释谓词公式的解释定义4.6 设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按照下列规定赋值：（1）为每个个体常量指派D中的一个元素；（2）为每个n元函数指派一个从Dn到D的映射，其中 Dn(x1,x2,xn)| x1,x2,xnD（3）为每个n元谓词指派一个从Dn到F,T的映射；则称这些指派为公式P在D上的一个解释。 一般情况下，谓词公式的真值都是一般情况下，谓词公式的真值都
21、是针对某一解释而言的。同一个公式可针对某一解释而言的。同一个公式可能在一种解释下其真值是能在一种解释下其真值是T，而在另而在另一种解释下，其真值是一种解释下，其真值是F。 2. 谓词公式的永真性谓词公式的永真性定义定义4.7 如果谓词公式如果谓词公式P，对个体域对个体域D上的任何一上的任何一个解释都取得真值个解释都取得真值T，则称则称P在在D上是永真的上是永真的；如；如果果P在每个非空个体域上均永真，则称在每个非空个体域上均永真，则称P永真永真。定义定义4.8 如果谓词公式如果谓词公式P，对个体域对个体域D上的任何一上的任何一个解释都取得真值个解释都取得真值F，则称则称P在在D上是永假的上是永
22、假的；如；如果果P在每个非空个体域上均永假，则称在每个非空个体域上均永假，则称P永假永假。谓词公式的永假性又称为不可满足性或不相容性。谓词公式的永假性又称为不可满足性或不相容性。3. 谓词公式的可满足性谓词公式的可满足性定义定义4.9 对于谓词公式对于谓词公式P，如果至少存在一如果至少存在一个解释使得公式个解释使得公式P在此解释下的真值为在此解释下的真值为T，则称公式则称公式P是可满足的。是可满足的。 如果不存在任何解释，使得如果不存在任何解释，使得P的取值的取值为为T，则称公式则称公式P是不可满足的。是不可满足的。3.3.4 谓词公式的等价性与永真蕴涵谓词公式的等价性与永真蕴涵定义4.10
23、设P和Q是两个谓词公式，D为它们共同的个体域。若对D上的任何一个解释，P与Q的取值都相同，则公式P和Q在域D上是等价的。如果D是任意个体域，则称P和Q是等价的，记做PQ。常用的等价式：交换律 PQ QP PQ QP结合律 (PQ)R P(QR) (PQ)R P(QR) 分配律 P(QR) (PQ)(PR) P(QR) (PQ)(PR)狄.摩根定律 (PQ) PQ (PQ) PQ否定之否定定律 ( P) P 吸收律 P(PQ) P P(PQ) P补余律 PP T PP F逆否定律 PQQP 连接词化归律 PQPQ PQ(PQ)(QP) PQ(PQ)(PQ)量词转换律 (x )P (x )(P)
24、(x )P (x )(P)量词分配律 (x) (PQ) (x )P(x )Q (x) (PQ) (x )P(x )Q定义4.11 对于谓词公式P和Q，如果P Q永真，则称P永真蕴涵Q，且称Q为P的逻辑结论，称P为Q的前提，记作PQ。下面是一些常用到的永真蕴涵式：化简式 PQP PQQ附加式 PPQ QPQ 析取三段论 P，PQQ 假言推理 P，P QQ 拒取式 Q，P QP 假言三段论 PQ，QRPR 二难推论 PQ，PR，QRR 全称固化 (x) (P (x)P(y),其中y是个体域上的任一个体，利用此永真蕴涵式可以消去公式中的全称量词 存在固化 (x) (P (x)P(y),其中y是个体域
25、中某个使P(y)为真的个体，利用此式可以消去公式中的存在量词3.3.5 置换与合一置换与合一1. 置换置换定义定义4.12 置换是形如置换是形如t1/x1, t2/x2,tn/xn的一个有限集。其中，的一个有限集。其中，xi是变量，是变量，ti是不是不同于同于xi的项（常量、变量、函数），且的项（常量、变量、函数），且xixj(i j),i,j=1,2,n.例如：例如：a/x, b/y, f(x)/z, f(z)/x, y/z 2. 合一合一定义定义4.13 设有公式集设有公式集E1,E2,En和置换和置换，使使E1 = E2 = En 便称便称E1，E2， En是可合一的，且是可合一的，且称
26、为合一称为合一置换。置换。定义定义4.14 若若E1，E2， En有合一置换有合一置换，且对E1，E2， En的任一置换的任一置换都存在一个置换都存在一个置换，使得使得 = ，则称则称为E1，E2， En的的最一般合一置换，记为最一般合一置换，记为mgu。例例 若若E1Q(y)，E2=Q(z), 对对E1和和E2来说，来说，=y/z=y/z和和=z/y=z/y都是它们的最一般都是它们的最一般合一置换。合一置换。4.5.1 谓词公式与字句集谓词公式与字句集1. 范式范式（1）前束形范式）前束形范式一个谓词公式，如果它的所有量词均非否定地出一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面
27、，且它的辖域一直延伸到公式现在公式的最前面，且它的辖域一直延伸到公式之末，同时公式中不出现连接词之末，同时公式中不出现连接词及及，这种形，这种形式的公式称做前束形范式。式的公式称做前束形范式。例如：例如：(x)(x)(x)(z)(P(x)(P(x) F(y,x)(y,x)Q(y,x)(y,x)（2）斯克林（）斯克林（skolem）范式范式 为了克服前束性范式的缺点，斯可林对为了克服前束性范式的缺点，斯可林对它进行了改进，使前束性范式的首标不出它进行了改进，使前束性范式的首标不出现存在量词。从前束性范式中消去全部存现存在量词。从前束性范式中消去全部存在量词所得到公式即为在量词所得到公式即为斯克林
28、（斯克林（skolem）范式，或称范式，或称skolem标准型。标准型。将谓词公式G化为skolem标准型的步骤如下：(1) 消去谓词公式G中的蕴涵及双条件及双条件，以以AB代替代替A B，以（以（A B）（ A B ）替换）替换A B(2) 减少否定负号的辖域，使否定符号最多只作用到一个谓词上。(3) 重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。(4) 消去存在量词。分两种情况，一种使存在量词不出现在全称量词的辖域内，此时，只要用一个新的个体变量替换该存在量词约束的变元，就可以消去存在量词；另一中情况是，存在量词位于一个或多个全称量词的辖域内，比如 (x1)(x2
29、)x2)( (xn)(y y)P(x1,x2,)P(x1,x2, ,xnxn, ,y y) )此时变元此时变元y y实际受前面的变元实际受前面的变元x1,x2,x2, ,xn的约束，需要用Skolem函数f(x1,x2,x2, ,xn)替换y即可将存在量词y消去，得到 (x1)(x2)x2)( (xn)(y)P(x1,x2,y)P(x1,x2, ,xnxn, , f(x1,x2,x2, ,xn) ) )(5) 把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。(6) 母式化为合取范式：任何母式都可以写成由一些谓词公式否定的析取的有限集组成的合取。例： 将谓词公式G
30、= (x)(y)P(x,y)P(x,y) (y)(Q(x,y)(x,y) R(x,y)(x,y)化为化为SkolemSkolem标准型。标准型。解解：（：（1 1）消去及及连接词。连接词。(x)(y)P(x,y)P(x,y) (y)(Q(x,y)(x,y)R(x,y)(x,y)（2）把的辖域减少到最多只作用于一个谓词。）把的辖域减少到最多只作用于一个谓词。(x)(y) P(x,y)P(x,y) (y)(Q(x,y)(x,y)R(x,y)(x,y)（3 3）变量更名变量更名(x)(y) P(x,y)P(x,y) (z z)(Q(x,z)(x,z)R(x,z)(x,z)（4 4）消去存在量词。因为
31、存在量词消去存在量词。因为存在量词(y)和和(z z)都在辖域都在辖域(x)内，属于上述所讲的第二种情况，内，属于上述所讲的第二种情况，所以分别用所以分别用skolem函数函数f(x)和和g(x)替换替换y和和z。(x)( P(x,P(x,f(x) ) (Q(x,(x,g(x) )R(x,(x,g(x)（5 5）全称量词移到左边。由于只有一个全称量全称量词移到左边。由于只有一个全称量词词(x)，已在左边，所以不移。已在左边，所以不移。（6 6）将母式化为合取范式。将母式化为合取范式。(x)( P(x,P(x,f(x) ) (Q(x,(x,g(x)( P(x,P(x,f(x) )R(x,(x,g
32、(x)2. 字句与字句集字句与字句集 定义定义4.16 不含有任何连接词的谓词公式称作不含有任何连接词的谓词公式称作原原子公式子公式，简称，简称原子原子，而原子或原子的否定统称为，而原子或原子的否定统称为文字文字。例如：例如：P(x), P(x,c), R(x,y)定义定义4.17 字句就是由一些文字组成的析取式。字句就是由一些文字组成的析取式。例如：例如：P(x)Q(x,y), P(x,c)R(x,y,f(x)定义定义4.18 不含有任何文字的字句称为不含有任何文字的字句称为空子句空子句，记，记做做NIL。 由于空子句不含有任何文字，它不能被任何由于空子句不含有任何文字，它不能被任何解释所满
33、足，所以空子句是永假的，不可满足的。解释所满足，所以空子句是永假的，不可满足的。定义定义4.19 由字句构成的集合称为由字句构成的集合称为字句集字句集。 谓词公式谓词公式skolem标准型的母式是由一些标准型的母式是由一些字句的合取组成的。字句的合取组成的。 如果将谓词公式如果将谓词公式G的的skolem标准型前面标准型前面的全称量词全部消去，并用逗号代替合取的全称量词全部消去，并用逗号代替合取符号，便可得到谓词公式符号，便可得到谓词公式G的字句集的字句集S。3. 不可满足意义下的一致性不可满足意义下的一致性 公式公式G与其字句集与其字句集S并不等价，但它们在并不等价，但它们在不可满足的意义下
34、是一致的。不可满足的意义下是一致的。定理定理4.2 设有谓词公式设有谓词公式G，而其相应的字句而其相应的字句集为集为S，则则G是不可满足的充分必要条件是是不可满足的充分必要条件是S是不可满足的。是不可满足的。4.5.2 Herbrand理论理论1. H域域定义定义4.20 设谓词公式设谓词公式G的字句集为的字句集为S，则按下述则按下述方法构造的个体变元域方法构造的个体变元域H称为公式集或字句集称为公式集或字句集S的的Herbrand域，简称域，简称H域。域。（1）令）令H0为为S中所出现的常量的集合。若中所出现的常量的集合。若S中没中没有常量出现，就任取一个常量有常量出现，就任取一个常量aD,
35、规定规定H0a。（2）令令Hi+1=HiS中所有的形如中所有的形如f(t1,t2,tn)的的元素元素其中，其中，f(t1,t2,tn)是出现于是出现于G中的任一函数负号，中的任一函数负号，而而t1,t2,tn是是Hi中的元素。这里中的元素。这里i=1,2,n4.5.3 归结原理归结原理 归结原理又称为消解原理，是归结原理又称为消解原理，是Robinson提出的证明字句集不可满足性，从而实现提出的证明字句集不可满足性，从而实现了定理证明的一种理论和方法。了定理证明的一种理论和方法。 定义定义4.25 若若P是原子谓词公式或原子命题，是原子谓词公式或原子命题，则称则称P与与P为互补文字。为互补文字
36、。1. 命题逻辑中的归结原理命题逻辑中的归结原理(1) 归结与归结式 定义3.26 设C1与C2式字句集中的任意两个子句，如果C1中的文字L1与C2中文字L2互补，则从C1和C2中可以分别消去L1和L2，并将两个子句余下的部分做析取构成一个新的子句C12，称这一过程为归结，所得到的子句C12为C1和C2的归结式，而称C1和C2为C12的亲本子句。 归结过程是一种推理规则，即C1C2 C12定理3.6 归结式C12是其亲本子句C1和C2的逻辑结论。推论 设C1和C2是子句集S上的子句，C12是C1和C2的归结式。如果把C12加入到子句集S得到新的子句集S1，则S1和S在不可满足的意义下是等价的。
37、(2) 归结推理过程由上面的推论以及空子句的不可满足性，可以得出证明子句集S不可满足性的推理过程如下：A 对子句集S中的各子句间使用归结推理规则。B 将归结所得的归结式放入子句集S中，得到新的子句集S。C 检查子句集S中是否有空子句，若有，则停止推理；否则转步骤D。D 置SS，转步骤A。例 4.14 证明子句集S=PQ, Q, P是不可满足的。证明：(1) PQ(2) Q(3) P(4) P (1)和(2) 归结(5) NIL (3)和(4) 归结2. 一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理 在一阶谓词逻辑中，由于子句中含有变元，所以不能像命题逻辑中那样可以直接消去互补文字进行子句归
38、结。而是要首先使用置换与合一的思想，对子句中的某些变元进行合一置换，对置换后的新子句再次使用归结规则。定义4.27 设C1与C2是两个没有相同变元的子句，L1和L2分别为C1和C2的文字，如果L1与L2有mgu ,则把 C12(C1-L1)(C2-L2 )，称作子句C1和C2的一个二元归结式，而L1和L2是被归结的文字。 在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：（1）若被归结的子句C1和C2中具有相同的变元，则需要将其中一个子句的变元更名；否则可能无法作合一置换，从而没有办法进行归结。（2）在求归结式时，不能同时消去两个互补文字时，消去两个互补文字对所得的结果不是两个亲本子句的
39、逻辑推论。例：C1PQ C2PQ（3）如果在参加归结的子句内含有可合一的文字，则在进行归结之前，应对这些文字进行合一，以实现这些子句内部的简化。例：C1=P(x)P(f(a)Q(x) C2= P(x) R(b) 用它们最一般合一=f(a)/x进行置换得到 C1 = P(f(a) Q(f(a) ) 再对C1和C2进行归结，选用mgu为=f(a)/x,得到C1和C2的二元归结式为 C12R(b) Q(f(a) )定义4.28 设C1与C2是没有相同变元的子句，则下列四种二元归结式都叫做C1与C2的归结式，仍记做C12。（1）C1与C2的二元归结式。（2）C1的因子C11与C2的二元归结式。（3）C
40、1与C2的因子C22的二元归结式。（4）C1的因子C11与C2的因子C22的二元归结式。4.5.4 利用归结原理进行定理证明利用归结原理进行定理证明 设要证明的定理可用谓词公式表示为如下的形设要证明的定理可用谓词公式表示为如下的形式式A1A2AnAn B B ，应用归结原理进行定，应用归结原理进行定理证明的步骤如下：理证明的步骤如下： (1) 首先否定结论首先否定结论B，并将否定后的公式并将否定后的公式B与前与前提公式集组成如下形式的谓词公式：提公式集组成如下形式的谓词公式：G=A1A2AnAnB B (2) 求谓词公式求谓词公式G的子句集的子句集S。(3) 应用归结原理，证明子句集应用归结原
41、理，证明子句集S的不可满足性，的不可满足性，从而证明谓词公式从而证明谓词公式G的不可满足性。这就说明对的不可满足性。这就说明对结论结论B的否定是错误的，推断出定理的成立。的否定是错误的，推断出定理的成立。例4.18 已知：A：(x)(y) P(x,y)P(x,y)Q(y)(y) (y)(R(y)(y)T(x,y)(x,y)B: B: (x) R(x)(x)(y) P(x,y)P(x,y)Q(y) (y) (x)(y)P(x,y)P(x,y)Q(y)Q(y)证明：证明：首先将A和B化为子句集。(1) P(x,y)P(x,y)Q(y)(y)R(f(x)(f(x)(2) (2) P(x,y)P(x,
42、y)Q(y)(y)TT(x,f(x)(x,f(x)(3) (3) R(z)(z)(4) P(a,b)(4) P(a,b)(5) Q(b)(5) Q(b)下面进行归结：下面进行归结：(6) (6) P(x,y)P(x,y)Q(y) (1)(y) (1)与与(3)(3)进行归结进行归结(7) (7) Q(b) (4)(b) (4)与与(6)(6)进行归结进行归结(8) NIL (5)(8) NIL (5)与与(7)(7)进行归结进行归结4.5.5 利用归结原理进行问题求解利用归结原理进行问题求解 归结原理不仅可以应用于定理证明，而且也归结原理不仅可以应用于定理证明，而且也可以用来求取问题的答案，其
43、步骤如下：可以用来求取问题的答案，其步骤如下：(1) 把已知前提条件用谓词公式表示出来，并化把已知前提条件用谓词公式表示出来，并化为相应的子句集，设该子句集的名字为为相应的子句集，设该子句集的名字为S1。(2) 把待求解的问题也用谓词公式表示出来，然把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词后将其否定，并与一谓词ANSWER构成析取式。构成析取式。谓词谓词ANSWER是一个专为求解问题而设置的谓是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致。词，其变量必须与问题公式的变量完全一致。(3) 把问题公式与谓词把问题公式与谓词ANSWER构成的析构成的析取式化为
44、子句集，并把该子句集取式化为子句集，并把该子句集与与S1后后并构成子句并构成子句集集S。(4) 对子句集对子句集S应用谓词归结原理进行归结，应用谓词归结原理进行归结，再归结过程中，通过合一置换，改变再归结过程中，通过合一置换，改变ANSWER中的变元。中的变元。(5) 如果得到归结式如果得到归结式ANSWER，则问题的则问题的答案即在答案即在ANSWER谓词中。谓词中。例：某人被盗，公安局派出所派出5个侦察员去调查。研究案情时，侦察员A说“赵与钱中至少有一人作案”；侦察员B说“钱与孙中至少有一人作案”；侦察员C说“孙与李中至少有一人作案”；侦察员D说“赵与孙中至少有一人与此案无关”；侦察员E说
45、“钱与李中至少有一人与此案无关”。如果5个侦察员的话都是可信的，试问谁是盗窃犯呢？解：第一步 将5个侦察员的话表示成谓词公式，为此先定义谓词。设谓词P(x)表示作案者，则根据题意：A：P(zhao) P(qian) B：P(qian) P(sun) C：P(sun) P(li) D：P(zhao) P(sun) E：P(qian) P(li)第二步 将待求问题表示成谓词。设y为盗窃犯，则 P(y)ANSWERANSWER(y)第三步 求前提条件及P(y)ANSWERANSWER(y)的子句集，并将各子句列表如下：(1) P(zhao) P(qian) (2) P(qian) P(sun)(3)
46、 P(sun) P(li)(4) P(zhao) P(sun)(5) P(qian) P(li)(6) P(y)ANSWERANSWER(y)第四步 应用归结原理进行推理(7) P(qian) P(sun) (1)和(4)归结(8) P(zhao) P(li) (1)和(5)归结(9) P(qian) P(zhao) (2)和(4)归结(10) P(sun) P(li) (2)和(5)归结(11) P(zhao) P(li) (3)和(4)归结(12) P(sun) P(qian) (3)和(5)归结(13) P(qian) (2)和(7)归结(14) P(sun) (2)和(12)归结(15
47、) ANSWER(qian) (6)和(13)归结(16) ANSWER(sun) (6)和(14)归结所以，本题的盗窃犯是两个人：钱和孙4.6 归结过程中的控制策略4.6.1 引入控制策略1.引入控制策略的原因 对子句集S进行归结时，首先要从子句集中找出可进行归结的一对子句进行归结。如果采用盲目的归结策略，会产生大量的无用的归结式，而且归结式还会重复出现，这不仅浪费计算机的存储空间，而且要浪费大量的计算时间，如果子句集的规模较大的情况下，这种浪费是惊人的。2. 控制策略分类 归结策略大致可以分为两大类：第一类是删除策略。主要是通过删除某些无用的子句来缩小归结的范围，从而提高归结效率；另一类是
48、限制策略，是通过对参加归结的子句进行种种限制，尽可能地减少归结的盲目性，使其尽快归结出空子句。4.6.2 归结控制策略1.删除策略（1）纯文字删除法 如果文字L出现在S中，而L不出现在S中，便说L为S的纯文字。 显然归结过程中，纯文字是不可能被消去的，因而包含它的子句进行归结时，不可能得到空子句，即这样的子句对归结是毫无意义的，所以可以把它所在的子句从子句集中删除。（2）重言式删除法 如果一个子句中同时包含互补文字时，则称该子句为重言式。重言式是取值用真的子句。因此可以从子句集中删除。（3）包孕删除法 设有子句C1和C2，如果存在一个置换，使C1 C2，则称C1包孕于C2。 把子句集中包孕的子
49、句删去后，不会影响子句集的不可满足性，因而可从子句集中删去那些被包孕的子句。2. 线性归结策略 线性归结策略对参加归结的子句提出如下限制：首先从子句集S中先取一个称作顶子句的的子句C0开始作归结；其次将归结过程中所得到的归结式Ci立即同另一子句Bi进行归结，得归结式Ci+1,而Bi是原子子句S中一个子句或是已经归结出的某个归结式Cj（ji）。3. 单文字（单元）归结策略 如果一个子句只含有一个文字，则称该子句为单文字子句或单元子句。 如果归结过程中，每次归结都有一个子句是单文字子句，则称这种归结就是单文字归结。也就是说，单文字归结策略要求参加归结的两个子句中至少有一个是单文字子句。 用单文字归结策略时，归结式将比亲本子句含有较少的文字，这有利于朝着空子句的方向前进，因此它有较高的效率。4. 输入归结策略 输入归结策略对参加归结的子句有如下限制：参加归结的两个子句中，必须至少有一个子句是初始子句集中的子句。 本归结策略是不完备的，也就是说，该子句集S是不可满足的，用该归结原理进行归结时，也不一定能归结出空子句。但是，输入归结策略具有简单高效的优点。
