人工智能确定性推理8课件2.ppt

1、第三章第三章 确定性推理确定性推理1需要掌握的问题需要掌握的问题l应用归结原理求解下列问题：应用归结原理求解下列问题：任何兄弟都有同一个父亲，任何兄弟都有同一个父亲，John和和Peter是兄弟，且是兄弟，且John的父亲是的父亲是David，问，问Peter的父亲是谁？的父亲是谁？2 按照推理过程所用知识的确定性，推理可分为确定性推理和不确定性推理。自然演绎推理和归结推理是经典的确定性推理，它们以数理逻辑的有关理论、方法和技术为理论基础，是机械化的、可在计算机上加以实现的推理方法。本章在讨论有关推理的一般概念以及命题和谓词逻辑的基础上，介绍自然演绎推理方法和基于一阶谓词逻辑的归结推理方法。3

2、3.1 推理概述 3.1.1 推理的基本概念推理的基本概念 推理是指从已知事实出发，运用已掌握的知识，推导出其中蕴含的事实性结论或归纳出某些新的结论的过程。其中，推理所用的事实可分为两种情况，一种是与求解问题有关的初始证据；另一种是推理过程中所得到的中间结论，这些中间结论可以作为进一步推理的已知事实或证据。人工智能系统的构成：推理机一些程序来完成的；综合数据库存放有用于推理的事实或证据；知识库存放有用于推理所必须的知识。43.1 推理概述 3.1.2 推理的方法及其分类 1.按照推理的逻辑基础分类 可分为演绎推理、归纳推理和默认推理。（1）演绎推理 演绎推理是从已知的一般性知识出发，推理出适合

3、于某种个别情况的结论的过程。它是一种由一般到个别的推理方法。53.1 推理概述（2）归纳推理 归纳推理是从大量特殊事例出发，归纳出一般性结论的推理过程，是一种由个别到一般的推理方法。其基本思想是：首先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认，数学归纳法就是归纳推理的一种典型例子。归纳推理又可分为：从特殊事例考察范围看：完全归纳推理、不完全归纳推理；从使用的方法看：枚举归纳推理、类比归纳推理。63.1 推理概述（3）默认推理 默认推理又称缺省推理，是在知识不完全的情况下假设某些条件已经具备所进行的推理。也就是说，在进行推理时，如果对某些证据不能证明其不成立的情况下，先假设它

4、是成立的，并将它作为推理的依据进行推理，但在推理过程中，当由于新知识的加入或由于所推出的中间结论与已有知识发生矛盾时，就说明前面的有关证据的假设是不正确，这时就要撤消原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理73.1 推理概述 2.按所用知识的确定性分类 按推理时所用知识的确定性来划分，推理可分为确定性推理、不确定性推理。3.按推理过程的单调性 按照推理过程中所推出的结论是否单调地增加，或者说按照推理过程所得到的结论是否越来越接近最终目标来分类，推理可分为单调推理与非单调推理。83.1 推理概述 3.1.3 推理的控制策略 推理过程不仅依赖于所用的推理方法，同时也依赖于推理的

5、控制策略。控制策略包括推理方向、搜索策略、冲突消解策略等；而推理方法则是指在推理控制策略确定之后，在进行具体推理时所要采取的匹配方法或不确定性传递算法等方法。推理方向用来确定推理的驱动方式，即是数据（证据）驱动或是目标驱动。所谓数据驱动即指推理过程从初始证据开始直到目标结束，而目标驱动则是指推理过程从目标开始进行反向推理，直到出现与初始证据相吻合的结果。按照对推理方向的控制，推理可分为正向推理、反向推理、混合推理及双向推理四种情况。93.1 推理概述 l 正向推理是一种从已知事实出发、正向使用推理规则的推理方式，它是一种数据（或证据）驱动的推理方式，又称前项链推理或自底向上推理。l反向推理是一

6、种以某个假设目标为出发点，反向运用推理规则的推理方式，它是一种目标驱动的推理方式，又称反向链推理或自顶向下推理。l混合推理是把正向推理和反向推理结合起来所进行的推理。l所谓双向混合推理是指正向推理和反向推理同时进行，使推理过程在中间的某一步骤相汇合而结束的一种推理方法。103.1 推理概述 3.1.4 推理的冲突消解策略 推理过程中的冲突消解策略，就是确定如何从多条匹配规则中选出一条规则作为启用规则，将它用于当前的推理。目前已有的多种冲突消解策略的基本思想都是对匹配的知识或规则进行排序，以决定匹配规则的优先级别，优先级高的规则将作为启用规则。常用排序方法有如下几种:113.1 推理概述(1)按

7、就近原则排序(2)按知识特殊性排序(3)按上下文限制排序(4)按知识的新鲜性排序(5)按知识的差异性排序(6)按领域问题的特点排序(7)按规则的次序排序(8)按前提条件的规模排序 123.2 3.2 命题逻辑命题逻辑 3.2.1 命题 定义 3.1 能够分辨真假的语句称作命题。定义3.2 一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为原子命题。原子命题是命题中最基本的单位。我们一般用P、Q、R、大写拉丁字母表示命题，而命题的真与假分别用“T”与“F”表示。用大写英文字母表示的命题既可以是一个特定的命题，也可以是一个抽象的命题。前者称为命题常量，后者称为命题变量。对于

8、命题变量而言，只有把确定的命题代入后，它才可能有明确的逻辑值（T或F）。133.2 3.2 命题逻辑命题逻辑3.2.2 命题公式 1.连接词：称为“非”或“否定”。：称为“析取”。：称为“合取”。：称为“条件”或者“蕴含”。：称为“双条件”。P Q表示“P当且仅当Q”。表3.1 命题逻辑真值表P QPQPQPQP QPT TTTTTFT FTFFFFF TTFTFTF FFFTTT143.2 3.2 命题逻辑命题逻辑2.命题公式定义3.3 以下面的递归形式给出命题公式的定义：l（1）原子命题是命题公式。l（2）A是命题公式，则A也是命题公式。l（3）若A和B都是命题公式，则AB、AB、AB、A

9、Bl（4）只有按（1）（3）所得的公式才是命题公式。153.2 3.2 命题逻辑命题逻辑命题公式的缺点：l 无法把所描述的客观事物的结构和逻辑特征反映出来l 不能把不同事物的共同特征反映出来P:“张三是李四的老师”；仅用字母P看不出张三和李四之间的师生关系。为了克服命题逻辑的局限性，引入了下面的谓词逻辑163.3 3.3 谓词逻辑谓词逻辑3.3.1 谓词与个体 在谓词逻辑中，将原子命题分解为谓词与个体两部分。个体是指可以独立存在的物体，可以是抽象的或具体的。谓词则是用于刻画个体的性质、状态或个体间的关系的。例如：“李白是诗人”可表示为：poet(LiBai)poet称为谓词，用以刻画“是诗人”

10、；LiBai称为个体 173.3 3.3 谓词逻辑谓词逻辑 一个谓词可以与一个个体相关联，此种谓词称作一元谓词，它刻画了个体的性质。一个谓词也可以与多个个体相关联，此种谓词称为多元谓词，它刻画了个体间的“关系”。183.3 3.3 谓词逻辑谓词逻辑谓词的一般形式：P(x1,x2,xn)其中P是谓词，而x1,x2,xn是个体。谓词通常用大写字母表示，个体通常用小写字母表示。项：在谓词中，个体可以是常量，也可以是变量，还可以是一个函数。例如，“小刘的哥哥是个工人”，可以表示为worker(brother(Liu)，其中brother(Liu)是一个函数。个体常数、变量和函数统称为项。谓词的语义：由

11、使用者根据需要人为地定义.193.3 3.3 谓词逻辑谓词逻辑谓词的元数：谓词中包含的个体数目称为谓词的元数，例如P(x)是一元谓词，P(x,y)是二元谓词，而P(x1,x2,xn)则是n元谓词。谓词的阶数：在谓词P(x1,x2,xn)中，若xi(i=1,2,n)都是个体常量、变元或函数，则称它为一阶谓词。如果某个xi本身又是一个一阶谓词，则称它为二阶谓词，依次类推。谓词和函数的区别：谓词具有逻辑值“真”或“假”，而函数则是某个个体到另一个个体（按数学上的概念是自变量到因变量）之间的映射。203.3 3.3 谓词逻辑谓词逻辑3.3.2 谓词公式 1.连接词 ，2.量词 为刻画谓词与个体间的关系

12、，引入了两个量词：全称量词（x）,和存在量词（x）。3.谓词演算公式定义3.4 谓词演算中，由单个谓词构成的不含任何连接词的公式，叫做原子谓词公式。213.3 3.3 谓词逻辑谓词逻辑由原子公式的定义出发，可定义谓词演算的合式公式如下。定义3.5 可按下述规则得到谓词演算的合式公式：（1）原子谓词公式是合式公式。（2）若A是合式公式，则A也是合式公式。（3）若A和B都是合式公式，则AB、AB、AB、AB也都是合式公式。（4）若A是合式公式，x是任一个体变元，则(x)A和(x)A也都是合式公式。（5）只有按（1）（4）所得的公式才是合式公式。223.3 3.3 谓词逻辑谓词逻辑4.量词辖域与约束

13、变元 在一个公式中，如果有量词出现，位于量词后面的单个谓词或者用括弧括起来的合式公式称为量词的辖域。在辖域内与量词中同名的变元称为约束变元。233.3 3.3 谓词逻辑谓词逻辑3.3.3 谓词公式的永真性和可满足性谓词公式的永真性和可满足性1谓词公式的解释定义3.6 设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按照如下规定赋值：（1）为每个个体常量指派D中的一个元素；（2）为每个n元函数指派一个从Dn到D的映射，其中 Dn=(x1,x2,xn)|x1,x2,xn D（3）为每个n元谓词指派一个从Dn到F,T的映射；则称这些指派为公式P在D上的一个解释。243.3 3.3 谓词逻辑谓

14、词逻辑例3.1 设个体域D=1,2，求公式A=(x)(P(x)Q(f(x),b)在D上的某一个解释，并指出在此解释下公式A的真值。详细的求解过程参见教材253.3 3.3 谓词逻辑谓词逻辑2谓词公式的永真性定义3.7 如果谓词公式P，对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P永真。定义3.8 如果谓词公式P对于个体域D上的所有解释都取得假值F，则称P在D上是永假的；如果P在每个非空个体域上均永假，则称P永假。谓词公式的永假性又称为不可满足性或不相容性。263.3 3.3 谓词逻辑谓词逻辑3谓词公式的可满足性 定义3.9 对于谓词公式P，

15、如果至少存在一个解释使得公式P在此解释下的真值为T，则称公式P是可满足的。按照定义3.9，对谓词公式P，如果不存在任何解释，使得P的取值为T，则称公式P是不可满足的。所以，谓词公式P永假与不可满足是等价的。若P永假，则也可称P是不可满足的。273.3 3.3 谓词逻辑谓词逻辑3.3.4 谓词公式的等价性与永真蕴含 定义3.10 设P与Q是两个谓词公式，D是它们共同的个体域。若对D上的任何一个解释，P与Q的取值都相同，则公式P和Q在域D上是等价的。如果D是任意个体域，则称P和Q是等价的，记作P Q。常用的一些等价式参见教材 定义3.11 对于谓词公式P和Q，如果PQ永真，则称P永真蕴含Q，且称Q

16、为P的逻辑结论，称P为Q的前提，记作P=Q。以后要用到的一些永真蕴含式参见教材283.3 3.3 谓词逻辑谓词逻辑谓词逻辑中还有如下一些推理规则：（1）P规则：在推理的任何步骤上都可引入前提。（2）T规则：推理时，如果前面步骤中有一个或多个永真蕴含公式S，则可把S引入推理过程中。（3）CP规则：如果能从R和前提集合中推出S来，则可从前提集合推出RS来。（4）反证法：P=Q，当且仅当PQF，即Q为P的逻辑结论，当且仅当PQ 是不可满足的。推广之，可得如下定理。定理3.1 Q为P1，P2，Pn的逻辑结论，当且仅当 (P1P2Pn)Q是不可满足的。293.3 3.3 谓词逻辑谓词逻辑3.3.5 置换

17、与合一 1.置换 置换的定义定义3.12 置换是形如t1/x1,t2/x2,tn/xn的一个有限集。其中xi是变量，ti是不同于xi的项（常量，变量，函数），且xi xj（Ij），i，j=1,2,n。303.3 3.3 谓词逻辑谓词逻辑例如，a/x,b/y,f(x)/z，f(z)/x,y/z都是置换。不含任何元素的置换称为空置换，以 表示。置换乘法 置换乘法作用是将两个置换合成为一个置换。定义3.13假设=t1/x1,t2/x2,tn/xn =u1/y1,u2/y2,um/ym是两个置换，则它们的乘积是一个新置换，其作用于公式E时，相当于先后对E的作用。它的定义如下：313.3 3.3 谓词逻

18、辑谓词逻辑先作置换t1 /x1,t2 /x2,tn /xn,u1/y1,u2/y2,um/ym。若yi x1,xn时，先从上述集合中删除ui/yi 。若 ti =xi时，再从上述集合中删除ti /xi 。删除以后剩下元素所构成的集合称作与的乘积，记作 。置换结合率一般地说，下列的置换结合律成立()=()但除了空置换外，置换的交换律不成立。即只有=。323.3 3.3 谓词逻辑谓词逻辑2.合一 合一的概念定义3.14 设有公式集E1,E2,En和置换，使 E1 =E2 =En 便称E1，E2，En是可合一的，且称为合一置换。定义3.15 若E1，E2，En 有合一置换，且对E1，E2，En 的任

19、一置换都存在一个置换，使得=，则称是E1，E2，En 的最一般合一置换，记为mgu。333.3 3.3 谓词逻辑谓词逻辑 最一般合一置换的求取算法设有两个谓词公式：E1：P(x,y,z);E2：P(x,f(a),g(b)分别从E1与E2的第一个符号开始逐个向右比较，此时发现E1中的y与E2中的f(a)不同，则它们构成了一个不一致集：D1=y,f(a)当继续向右比较时，又发现中E1中的z与E2中g(b)不同，则又得到一个不一致集：D2=z,g(b)下面给出求公式E1,E2的最一般合一置换的算法：343.3 3.3 谓词逻辑谓词逻辑（1）令W=E1,E2。（2）令 k=0，Wk=W，k=；是空置换

20、，它表示不作置换。（3）如果Wk只有一个表达式，则算法停止，k就是所要求的mgu。（4）找出Wk的不一致集Dk。（5）若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk中 出现，则置：k+1=k tk/xk Wk+1=wktk/xk k=k+1 然后转（3）。（6）算法终止，W的mgu不存在。可以证明，如果E1和E2可合一，则算法必停止于第（3）步。353.3 3.3 谓词逻辑谓词逻辑例3.5 设E1=P(a,v,f(g(y)，E2=P(z,f(a),f(u)，求E1 和E2的mgu。解题请参见教材 答案为：3=a/z,f(a)/v,g(y)/u 3就是E1 和E2的mgu。

21、363.4 3.4 自然演绎推理方法自然演绎推理方法 3.4.1 自然演绎推理的概念自然演绎推理的概念 自然演绎推理是指从一组已知为真的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程。假言三段论的基本形式为 PQ，QRPR 它表示如果谓词公式PQ和QR均为真，则谓词公式PR也为真。假言推理可用下列形式表示 P，PQ Q它表示如果谓词公式P和PQ都为真，则可推得Q为真结论。373.4 3.4 自然演绎推理方法自然演绎推理方法 拒取式的一般形式为 PQ，Q P它表示如果谓词公式PQ为真且Q为假，则可推得P为假的结论。2.4.2 2.4.2 利用演绎推理解决问题利用演绎推理解决问题

22、在利用自然演绎推理方法求解问题时，一定要注意避免两种类型的错误：肯定后件的错误和否定前件的错误。383.4 3.4 自然演绎推理方法自然演绎推理方法 肯定后件的错误是指当PQ为真时，希望通过肯定后件Q为真来推出前件P为真。这显然是错误的推理逻辑，因为当 PQ及 Q为真时，前件 P既可能为真，也可能为假。否定前件的错误是指当PQ为真时，希望通过否定前件P来推出后件Q为假。这也是不允许的，因为当PQ及P为假时，后件Q既可能为真，也可能为假。相关的例题请参见教材393.4 3.4 自然演绎推理方法自然演绎推理方法 3.4.3 演绎推理的特点演绎推理的特点 参见教材403.5 3.5 归结推理方法归结

23、推理方法 研究用计算机实现定理证明的机械化，已是人工智能研究的一个重要领域。对于定理证明问题，如果用一阶谓词逻辑表示的话，就是要求对前提P和结论Q证明PQ是永真的。然而，要证明这个谓词公式的永真性，必须对所有个体域上的每一个解释进行验证，这是极其困难的。为了化简问题，和数学上常采用的方法一样，我们考虑反证法。即，我们先否定逻辑结论Q，再由否定后的逻辑结论Q及前提条件P出发推出矛盾，即可证明原问题。413.5 3.5 归结推理方法归结推理方法 3.5.1谓词公式与子句集谓词公式与子句集 1范式 前束形范式 一个谓词公式，如果它的所有量词均非否定地出现在公式的最前面，且它的辖域一直延伸到公式之末，

24、同时公式中不出现连接词及 ，这种形式的公式称作前束形范式。例如，公式(x)(y)(z)(P(x)F(y,z)Q(y,z)即是一个前束形的公式。423.5 3.5 归结推理方法归结推理方法 斯克林范式 从前束形范式中消去全部存在量词所得到的公式即为Skolem范式，或称Skolem标准型。例如，如果用f(x)代替上面前束形范式中的y即得到Skolem范式：(x)(z)(P(x)F(f(x),z)Q(f(x),z)Skolem标准型的一般形式是(x1)(x2)(xn)M(x1,x2,xn)其中，M(x1,x2,xn)是一个合取范式，称为Skolem标准型的母式。433.5 3.5 归结推理方法归结

25、推理方法 将谓词公式G化为Skolem标准型的步骤如下：（1）消去谓词公式G中的蕴涵（）和双条件符号（），以AB代替AB，以(AB)(AB)替换AB。（2）减少否定符号（）的辖域，使否定符号“”最多只作用到一个谓词上。（3）重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。443.5 3.5 归结推理方法归结推理方法 （4）消去存在量词。这里分两种情况，一种情况是存在量词不出现在全称量词的辖域内，此时，只要用一个新的个体常量替换该存在量词约束的变元，就可以消去存在量词；另一种情况是，存在量词位于一个或多个全称量词的辖域内，这时需要用一个Skolem函数替换存在量词而将其消

26、去。（5）把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。（6）母式化为合取范式：任何母式都可以写成由一些谓词公式和谓词公式否定的析取的有限集组成的合取。需要指出的是，由于在化解过程中，消去存在量词时作了一些替换，一般情况下，G的Skolem标准型与G并不等值。453.5 3.5 归结推理方法归结推理方法 2子句与子句集定义3.16 不含有任何连接词的谓词公式叫原子公式，简称原子，而原子或原子的否定统称文字。定义3.17 子句就是由一些文字组成的析取式。定义3.18 不包含任何文字的子句称为空子句，记为NIL。定义3.199 由子句构成的集合称为子句集。463.

27、5 3.5 归结推理方法归结推理方法 3不可满足意义下的一致性定理3.2 设有谓词公式G，而其相应的子句集为S，则G是不可满足的充分必要条件是S是不可满足的。要再次强调：公式G与其子句集S并不等值，只是在不可满足意义下等价。相关的例子参见教材中的例3.9473.5 3.5 归结推理方法归结推理方法 4PP1P2Pn的子句集 当PP1P2Pn时，若设P的子句集为SP，Pi的子句集为Si，则一般情况下，SP并不等于S1S2S3Sn，而是要比S1S2S3Sn复杂得多。但是，在不可满足的意义下，子句集SP与S1S2S3Sn是一致的，即 SP不可满足S1S2S3Sn不可满足483.5 3.5 归结推理方

28、法归结推理方法 3.5.2 3.5.2 HerbrandHerbrand理论理论 1H域 定义3.20 设谓词公式G的子句集为S，则按下述方法构造的个体变元域H。称为公式G或子句集S的Herbrand域，简称H域。（1）令H0是S中所出现的常量的集合。若S中没有常量出现，就任取一个常量aD，规定H0=a。（2）令Hi+1=HiS中所有的形如f(t1,tn)的元素其中f(t1,tn)是出现于G中的任一函数符号，而t1，tn是Hi中的元素。i=0，1，2，。493.5 3.5 归结推理方法归结推理方法 例3.10 求子句集ST(x)Q(z),R(f(y)的H域。解 此例中没有个体常量，任意指定一个

29、常量a作为个体常量；只有一个函数f(y)，有：H0=aH1=a,f(a)H2=a,f(a),f(f(a)H=a,f(a),f(f(a),f(f(f(a),503.5 3.5 归结推理方法归结推理方法 2原子集定义3.21 下列集合称为子句集S的原子集：A所有形如P(t1,t2,tn)的元素其中，P(t1,t2,tn)是出现在S中的任一谓词符号，而t1，t2，tn则是S的H域上的任意元素。513.5 3.5 归结推理方法归结推理方法 定义3.22 将没有变元出现的原子、文字、子句和子句集分别称作基原子、基文字、基子句和基子句集。定义3.23 当子句集S中的某个子句C中的所有变元符号均以其H域中的

30、元素替换时，所得到的基子句称作C的一个基例。例如，对于子句集 SP(a),P(x)P(f(x)它的H域为a,f(a),f(f(a),。对于子句P(a)，因为其中不含有变元，所以它已是基子句，而且aH，所以它也是基例。523.5 3.5 归结推理方法归结推理方法 3H域上的解释定义3.24 如果子句集S的原子集为A，则对A中各元素的真假值的一个具体设定都是S的一个H解释。可以证明，在给定域D上的任一个解释I，总能在H域上构造一个解释I*与之对应，使得如果D域上的解释能满足子句集S，则在H域的解释I*也能满足S（即若S|I=T，就有S|I*=T）。相关举例参见教材533.5 3.5 归结推理方法归

31、结推理方法 定理3.3 设I是子句集S在域D上的一个解释，则存在对应于I的H域解释I*，使得若有 S|I=T，就必有S|I*=T。定理3.4 子句集S不可满足的充要条件是S对H域上的一切解释都为假。证明 充分性：若S在一般域D上是不可满足的，必然在H域上是不可满足的，从而对H域上的一切解释都为假。必要性：若S在任一H解释I*下均为假，必然会使S在D域上的每一个解释为假。否则，如果存在一个解释I0使S为真，那么依据定理3.3可知，一定可以在H域找到相对应的一个解释I*0使S为真。这与S在所有H解释下均为假矛盾。543.5 3.5 归结推理方法归结推理方法 定理3.5 子句集S不可满足的充分必要条

32、件是存在一个有限的不可满足的基例集S。该定理称为Herbrand定理，下面给出它的简要证明。证明 充分性：设子句集S有一个不可满足的基例集S，因为它不可满足，所以一定存在一个解释I使S为假。根据H域上的解释与D域上的解释的对应关系，可知在D域上一定存在一个解释使S不可满足，从而证明了子句集S是不可满足的。553.5 3.5 归结推理方法归结推理方法 必要性：设子句集S不可满足，由定理3.4可知，S对H域上的所有解释均为假。这样，就至少会存在一个S中的某子句Ci的基例Ci为假。既然至少有一个基例Ci为假，因而S的基例集S是不可满足的。另外，由于S中的子句是有限的，而每个子句又由有限的文字组成，因

33、而S的不可满足的基例集也是有限的。563.5 3.5 归结推理方法归结推理方法 3.5.3 归结原理归结原理定义3.25 若P是原子谓词公式或原子命题，则称P与P为互补文字。1命题逻辑中的归结原理归结与归结式 定义3.26 设C1与C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，则从C1和C2中可以分别消去L1和L2，并将二子句中余下的部分做析取构成一个新的子句C12，称这一过程为归结，所得到的子句C12称为C1和C2的归结式，而称C1和C2为C12的亲本子句。573.5 3.5 归结推理方法归结推理方法 定理3.6 归结式C12是其亲本子句C1和C2的逻辑结论。推论

34、 设C1和C2是子句集S上的子句，C12是C1和C2的归结式。如果把C12加入子句集S后得到新子句集S1，则S1和S在不可满足的意义下是等价的。即：S是不可满足的 S1是不可满足的 归结推理过程归结推理过程 子句集S不可满足性的推理过程如下：(1)对子句集S中的各子句间使用归结推理规则。(2)将归结所得的归结式放入子句集S中，得新子句集S。(3)检查子句集S中是否有空子句(NIL),若有则停止推理;否则转（4）。(4)置S=S，转步骤（1）。583.5 3.5 归结推理方法归结推理方法 2一阶谓词逻辑中的归结原理 下面是谓词逻辑关于归结的定义。定义定义3.27 设C1和C2是两个没有相同变元的

35、子句，L1 和L2分别是C1 和C2的文字，如果L1与 L2有mgu ，则把 C12=(C1L1)(C2 L2)称作子句C1 和C2的一个二元归结式，而L1 和L2是被归结的文字。为了说明的方便。将Ci和Li写成集合形式，如P(x)Q(y)P(x),Q(y)。在集合的表示下做减法或做并运算，然后再写成子句形，如集合运算结果为P(x),Q(y)，可改写为P(x)Q(y)。593.5 3.5 归结推理方法归结推理方法 在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：（1）若被归结的子句C1 和C2中具有相同的变元时，需要将其中一个子句的变元更名，否则可能无法做合一置换。从而没有办法进行归结

36、。（2）在求归结式时，不能同时消去两个互补文字对，消去两个互补文字对所得的结果不是两个亲本子句的逻辑推论。（3）如果在参加归结的子句内含有可合一的文字，则在进行归结之前，应对这些文字进行合一，以实现这些子句内部的化简。603.5 3.5 归结推理方法归结推理方法 应用因子的概念，可对谓词逻辑中的归结原理定义如下。定义3.28 设C1和 C2是没有相同变元的子句，则下列四种二元归结式都叫做C1和C2的归结式，仍记作C12。（1）C1与C2的二元归结式。（2）C1的因子C11与C2的二元归结式。（3）C1与C2的因子C22的二元归结式。（4）C1的因子C11与C2的因子C22的二元归结式。613.

37、5 3.5 归结推理方法归结推理方法 例例 设C1=P(a)Q(x)R(x)，C2=P(y)Q(b)，求其二元归结式。解解 若选L1=P(a)，L2=P(y)，则L1和L2的mgu是=a/y，于是由定义3.27得C1和C2 的二元归结式为C12=(C1-L1)(C2-L2)=(P(a),Q(x),R(x)-P(a)(P(a),Q(b)-P(a)=(Q(x),R(x)(Q(b)=Q(x)R(x)Q(b)若选L1=Q(x)，L2=Q(b)，则二者的mgu=b/x，C12=P(a)R(b)P(y)623.5 3.5 归结推理方法归结推理方法 3归结原理的完备性归结原理的完备性 对于一阶谓词逻辑，从不

38、可满足的意义上说，归结原理是完备的。即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结推理过程；反之，若从子句集到空子句存在一个归结推理过程，则该子句集必是不可满足的。633.5 3.5 归结推理方法归结推理方法 3.5.4 利用归结原理进行定理证明利用归结原理进行定理证明 应用归结原理进行定理证明的步骤如下：应用归结原理进行定理证明的步骤如下：设要被证明的定理可用谓词公式表示为如下的形式：A1A2AnB(1)首先否定结论B，并将否定后的公式B与前提公式集组成如下形式的谓词公式：G=A1A2AnB(2)求谓词公式G的子句集S。(3)应用归结原理，证明子句集S的不可满足性，从而证明谓词

39、公式G的不可满足性。这就说明对结论B的否定是错误的，推断出定理的成立。643.5 3.5 归结推理方法归结推理方法 例例 已知：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的逻辑结论。证明证明 首先将A和B化为子句集(1)P(x,y)Q(y)R(f(x)(2)P(x,y)Q(y)T(x,f(x)/(1)(2)为A(3)R(z)(4)P(a，b)(5)Q(b)/(3)(4)(5)为B653.5 3.5 归结推理方法归结推理方法 下面进行归结：（6）P(x,y)Q(y)（1）与（3）归结，=f(x)/z （7）Q

40、(b)（4）与（6）归结，=a/x,b/y （8）NIL（空子句）（5）与（7）归结所以B是A的逻辑结论。663.5 3.5 归结推理方法归结推理方法 3.5.5 应用归结原理进行问题求解应用归结原理进行问题求解下面是利用归结原理求取问题答案的步骤：（1）把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为S1。（2）把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词ANSWER构成析取式。谓词ANSWER是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致。（3）把问题公式与谓词ANSWER构成的析取式化为子句集，并把该子句集与S1合并构成子句集S

41、。673.5 3.5 归结推理方法归结推理方法 （4）对子句集S应用谓词归结原理进行归结，在归结的过程中，通过合一置换，改变ANSWER中的变元。（5）如果得到归结式ANSWER，则问题的答案即在ANSWER谓词中。683.5 3.5 归结推理方法归结推理方法 例例 任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问Peter的父亲是谁？解解 第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。（1）定义谓词：设Father(x,y)表示x是y的父亲。Brother(x,y)表示x和y是兄弟。693.5 3.5 归结推理方法归结推理方法 （2

42、）将已知事实用谓词公式表示出来。F1：任何兄弟都有同一个父亲。(x)(y)(z)(Brother(x,y)Father(z,x)Father(z,y)F2：John和Peter是兄弟。Brother(John,Peter)F3：John的父亲是David。Father(David,John)（3）将它们化成子句集得：S1=Brother(x,y)Father(z,x)Father(z,y),Brother(John,Peter),Father(David,John)703.5 3.5 归结推理方法归结推理方法 第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER作析取。设Peter的

43、父亲是u，则有：Father(u,Peter)。将其否定与ANSWER作析取，得：G：Father(u,Peter)ANSWER(u)713.5 3.5 归结推理方法归结推理方法 第三步：将上述公式G化为子句集S2，并将S1和S2合并到S。S2=Father(u,Peter)ANSWER(u)S=S1S2将S中各子句列出如下：（1）Brother(x,y)Father(z,x)Father(z,y)。（2）Brother(John,Peter)。（3）Father(David,John)。（4）Father(u,Peter)ANSWER(u)。723.5 3.5 归结推理方法归结推理方法 第四

44、步：应用归结原理进行归结（5）Brother(John,y)Father(David,y)（1）与（3）归结=David/z,John/x（6）Brother(John,Peter)ANSWER(David)（4）与（5）归结=David/u,Peter/y（7）ANSWER(David)（2）与（6）归结第五步：得到了归结式ANSWER(David)，答案即在其中，所以u=David。即Peter的父亲是David。733.6 归结过程的控制策略3.6.1 引入控制策略引入控制策略1引入控制策略的原因 对子句集S进行归结时，首先要从子句集中找出可进行归结的一对子句进行归结。由于事先并不知道子

45、句集中的哪两个子句可以进行归并不知道子句集中的哪两个子句可以进行归结，也不知道通过对哪些子句的归结可尽快得到空子句结，也不知道通过对哪些子句的归结可尽快得到空子句，所以就必须对子句集中的所有子句逐一进行比较，以对所有可能归结的子句对进行归结，并将归结式加入S中，再做第二层这样的归结，直到产生空子句（NIL）为止。这是一种盲目全面的归结盲目全面的归结，其结果是产生大量的不必要的归结式，况且这种不必要的归结式在下一轮归结时，会以幂次方幂次方的增长速度快速增长，从而产生组合爆炸组合爆炸。743.6 归结过程的控制策略 为了解决这一问题，研究如何选择合适的子句进行归选择合适的子句进行归结结，以避免多余

46、的、不必要的归结式的出现，已显得非常重要。在解决上述问题的过程中，人们研究出了许多归结策略。753.6 归结过程的控制策略2控制策略的分类 归结策略大致可分为两大类两大类：一类是删除策略删除策略，删除策略包括：纯文字删除法、重言式删除法、包孕删除法。另一类是限制策略限制策略，限制策略主要是通过对参加归结的子句进行种种限制，尽可能地减小归结的盲目性，使其尽快归结出空子句。包括：线性归结策略、单元（单文字）归结策略、输入归结策略、支持集策略等。763.6 归结过程的控制策略3.6.2 归结控制策略及其应用举例归结控制策略及其应用举例1删除策略删除策略 纯文字删除法 如果文字L出现在S中，而L不出现

47、于S中，便说L为S的纯文字。例如，设有子句集，S=TQR,R,Q,RQ其中T是纯文字，因此可将子句TQR删去，只用剩余的子句集进行归结，不会影响S的不可满足性。773.6 归结过程的控制策略 重言式删除法 如果一个子句中同时包含互补文字时，则称该子句为重言式。例如，Q(x)Q(x)，P(x)Q(x)P(x)都是重言式。重言式是取值为永真的子句。可以从子句集中删去重言式。包孕删除法 设有子句C1和C2，如果存在一个置换，使得C1C2，则称C1包孕于C2。例如，P(x)Q(a)包孕于P(f(a)Q(a)R(y)，=f(a)/x T(x)S(y)包孕于T(b)S(v)R(x)，=b/x，v/y。可从

48、子句集中删去那些被包孕的子句。783.6 归结过程的控制策略2线性归结策略线性归结策略 线性归结策略对参加归结的子句提出如下限制：首先从子句集S中先取一个称作顶子句的子句C0开始作归结；其次是将归结过程中所得到的归结式Ci立即同另一子句Bi进行归结，得归结式Ci+1，而Bi是原子句集S中的一个子句或是已经归结出的某个归结式Cj（ji）。793.6 归结过程的控制策略3单文字（单元）归结策略单文字（单元）归结策略 如果一个子句只包含一个文字，则称该子句为单文字子句或单元子句。如果在归结过程中，每次归结都有一个子句是单文字子句，则称这种归结就是单文字归结。用单文字归结策略时，归结式将比亲本子句含有较少的文字。这有利于朝着空子句的方向前进，因此它有较高的归结效率。但是，这种归结策略是不完备的。因为假设子句集S是不可满足的，但其中却不含有单文字子句，则单元归结就无法进行。803.6 归结过程的控制策略4输入归结策略输入归结策略 输入归结策略对参加归结的子句有如下限制：参加归结的两个子句中，必须至少有一个子句是初始子句集中的子句。5支持集策略支持集策略 支持集策略对参加归结的子句提出如下限制：每一次归结时，参加归结的两个子句中至少应有一个是由目标公式的否定所得到的子句，或者是它们的后裔。81 82