《知识的一阶谓词逻辑表示法.ppt》由会员分享，可在线阅读，更多相关《知识的一阶谓词逻辑表示法.ppt（161页珍藏版）》请在金锄头文库上搜索。
1、河南理工大学计算机学院河南理工大学计算机学院陈峰陈峰人工智能中的谓词演人工智能中的谓词演人工智能中的谓词演人工智能中的谓词演算及应用算及应用算及应用算及应用人工智能中的谓词演算及应用人工智能中的谓词演算及应用1 1 学习目标：学习目标：了解一阶谓词演算的基本体系，掌握命题逻辑和谓了解一阶谓词演算的基本体系，掌握命题逻辑和谓词逻辑的归结方法，以及基于归结的提取问题回答的方词逻辑的归结方法，以及基于归结的提取问题回答的方法，掌握基于规则的正向演绎方法和逆向演绎方法。法，掌握基于规则的正向演绎方法和逆向演绎方法。2 2 学习指南：学习指南：本章内容是在一阶谓词逻辑的基础上介绍有关的方本章内容是在一阶
2、谓词逻辑的基础上介绍有关的方法，假定读者已经学习过一阶谓词逻辑的有关内容。在法，假定读者已经学习过一阶谓词逻辑的有关内容。在学习的同时，自己尝试重新做一遍例题，将有助于你的学习的同时，自己尝试重新做一遍例题，将有助于你的学习。在有条件的情况下，可以尝试用程序实现本章介学习。在有条件的情况下，可以尝试用程序实现本章介绍的一些主要方法，不过有一定的难度。绍的一些主要方法，不过有一定的难度。人工智能中的谓词演算及应用人工智能中的谓词演算及应用3 3 难重点：难重点：命题逻辑的归结方法，谓词逻辑的归结方法，命题逻辑的归结方法，谓词逻辑的归结方法，基于归结的问题回答方法，基于规则的正向演绎基于归结的问题
3、回答方法，基于规则的正向演绎方法和基于规则的逆向演绎方法。方法和基于规则的逆向演绎方法。4.1一阶谓词逻辑基本理论一阶谓词逻辑基本理论一、命题与联结词一、命题与联结词定义定义4-1 4-1 具有确定真值的陈述句，称为命题。具有确定真值的陈述句，称为命题。 命题若是简单的陈述句，不能分解成更简单的句子，我们称这命题若是简单的陈述句，不能分解成更简单的句子，我们称这样的命题为样的命题为简单命题简单命题或或原子命题原子命题。可以用英文字母。可以用英文字母P P，Q Q，R R，或是或是带有下标的大写英文字母带有下标的大写英文字母P Pi i等表示简单命题，将命题用合适的符号表等表示简单命题，将命题用
4、合适的符号表示，称为示，称为命题符号化命题符号化。 对于简单命题来说，它的真值是确定的，因而又称为命题常项对于简单命题来说，它的真值是确定的，因而又称为命题常项或命题常元。或命题常元。 真值可以变化的简单陈述句称为命题变项或命题变元。真值可以变化的简单陈述句称为命题变项或命题变元。2 2、联结词、联结词（1 1）“否定否定”联结词，当命题联结词，当命题P P为真时，则为真时，则P P为假，反之为真。为假，反之为真。（2 2） ：“析取析取”联结词，它表示两个命题存在联结词，它表示两个命题存在“或或”的关系。的关系。（3 3）：“合取合取”联结词，它表示两个命题之间具有联结词，它表示两个命题之间
5、具有“与与”关系。关系。（4 4）：“蕴含蕴含”、“单条件单条件”，P PQ Q表示表示“如果如果P P，则，则Q Q”。其中。其中P P为前件，为前件，Q Q为后件。为后件。（5 5） ：“等价等价”、“双条件双条件”，P QP Q表示表示“P P当且仅当当且仅当Q Q”。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）二、个体词与谓词二、个体词与谓词1. 1. 个体词个体词定义定义4-2 4-2 个体个体 ( (个体词个体词) )是指所研究对象中可以独立存在的具体事是指所研究对象中可以独立存在的具体事物、状态或个体之间的关
6、系。物、状态或个体之间的关系。在谓词逻辑中，个体可以是常量也可以是变量在谓词逻辑中，个体可以是常量也可以是变量( (变元变元) )。个体常量个体常量：表示具体的或特定的个体，用：表示具体的或特定的个体，用a,b,c,da,b,c,d表示；表示；个体变量个体变量：表示抽象的或泛指的个体，用：表示抽象的或泛指的个体，用x,y,zx,y,z表示；表示；个体域个体域( (论域论域) )：个体变量的（取值范围）值域，常用：个体变量的（取值范围）值域，常用D D表示。个体域表示。个体域可以是有限的也可以是无限的可以是有限的也可以是无限的4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）2. 2.
7、谓词谓词定义定义4-3 4-3 用于刻画个体的性质、状态或个体之间的关系，用于刻画个体的性质、状态或个体之间的关系，称为谓词。称为谓词。谓词一般也用谓词一般也用P,Q,RP,Q,R等大写字母表示。等大写字母表示。3. 3. 函数符号函数符号函数符号，又称函词，是从若干个思维对象到某个思维函数符号，又称函词，是从若干个思维对象到某个思维对象的映射的符号。对象的映射的符号。n n元函数元函数f(x1,x2,f(x1,x2,xn),xn)规定为一个映射：规定为一个映射：f: Dn Df: Dn D4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）谓词与函数的区别：谓词与函数的区别：1 1、谓
8、词的真值是真和假，而函数无真值可言，其、谓词的真值是真和假，而函数无真值可言，其值是个体域中的某个个体。值是个体域中的某个个体。2 2、谓词实现的是从个体域中的个体到、谓词实现的是从个体域中的个体到T T或或F F的映射，的映射，而函数实现的是同一个个体域中从一个个体到另而函数实现的是同一个个体域中从一个个体到另一个个体的映射。一个个体的映射。3 3、在谓词逻辑中，函数本身不能单独使用，它必、在谓词逻辑中，函数本身不能单独使用，它必须嵌入到谓词中。须嵌入到谓词中。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）4. 4. 谓词谓词( (谓词填式谓词填式) )定义定义4-4 4-4 将
9、表示谓词的符号和表示个体的符号组合成一将表示谓词的符号和表示个体的符号组合成一个函词，就称谓词填式，简称谓词。如果没有特殊说明，个函词，就称谓词填式，简称谓词。如果没有特殊说明，以后我们提到的谓词均指谓词填式。与命题逻辑相似，以后我们提到的谓词均指谓词填式。与命题逻辑相似，谓词逻辑中也有谓词常项和谓词变项之分。含有个体变谓词逻辑中也有谓词常项和谓词变项之分。含有个体变元的谓词没有真值，但当谓词中的变元都用指定的个体元的谓词没有真值，但当谓词中的变元都用指定的个体取代时，谓词就有了特定的值取代时，谓词就有了特定的值T T或或F F。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）n n
10、元谓词：含有元谓词：含有n n个个体符号的谓词个个体符号的谓词P(x1,x2,P(x1,x2,xn),xn)，它表，它表示一个映射：示一个映射：P P：Dn TDn T，FF或是或是(D1(D1D2D2Dn)TDn)T，FF谓词的语义是由使用者根据需要人为定义的。谓词的语义是由使用者根据需要人为定义的。谓词中包含的个体数目称为谓词的元数，如：谓词中包含的个体数目称为谓词的元数，如：Q(x)Q(x)是一元是一元谓词，谓词，P(x, a)P(x, a)是二元谓词，是二元谓词，A(x1,x2,A(x1,x2,xn),xn)是是n n元谓词。元谓词。若若X X是个体常元、变元或函数，谓词称为一阶谓词；
11、如果是个体常元、变元或函数，谓词称为一阶谓词；如果某个某个X X本身又是一个一阶谓词，则谓词称为二阶谓词。依本身又是一个一阶谓词，则谓词称为二阶谓词。依次类推。次类推。与谓词联系着的与谓词联系着的n n个个体的出现顺序不是任意的。个个体的出现顺序不是任意的。同一谓词的个体变元取值于不同个体域时，所得命题真假同一谓词的个体变元取值于不同个体域时，所得命题真假值可以不同。值可以不同。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）三、量词三、量词设谓词设谓词P(x)P(x)表示表示x x是正数，是正数，F(x,y)F(x,y)表示表示x x与与y y是好朋是好朋友，则：友，则： (x)P
12、(x) (x)P(x)：表示个体域中所有个体：表示个体域中所有个体x x都是正数。都是正数。 (x) (y)F(x,y) (x) (y)F(x,y)：表示在个体域中所有个体：表示在个体域中所有个体x,x,都都存在个体存在个体y y，x x与与y y是好朋友。是好朋友。 4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）四、四、 谓词公式谓词公式项：项：单独一个个体符号（包括常量和变量）是项；单独一个个体符号（包括常量和变量）是项；若若t t1 1，t tn n是项，则是项，则f(tf(t1 1, ,t,tn n) )是项；是项；所有项由上述两规则生成。所有项由上述两规则生成。原子公式：
13、原子公式：若若t t1 1，t tn n是项，是项，P P是是n n元谓词符号，则单元谓词符号，则单独一个谓词独一个谓词P(tP(t1 1, ,t,tn n) )称为原子谓词公式；称为原子谓词公式；n=0n=0时退化为原子命题公式。简称原子时退化为原子命题公式。简称原子4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）定义定义4-5 4-5 下述规则得到谓词演算的合式公式：下述规则得到谓词演算的合式公式：(1) (1) 单个谓词是合式公式，称为原子谓词公式；单个谓词是合式公式，称为原子谓词公式；(2) (2) 若若A A是谓词公式，则是谓词公式，则 A A也是合式公式；也是合式公式；(
14、3) (3) 若若A A，B B都是合式公式，则都是合式公式，则ABAB，ABAB，ABAB，A BA B也都是合式公式；也都是合式公式；(4) (4) 若若A A是合式公式，是合式公式，x x是任一个体变元，则是任一个体变元，则 (x)A(x)A，(x)A(x)A也都是合式公式。也都是合式公式。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）2. 2. 公式的解释公式的解释在命题逻辑中，对命题公式中各个命题变元的一次真值在命题逻辑中，对命题公式中各个命题变元的一次真值指派称为命题公式的一个解释。一旦解释确定，根据各指派称为命题公式的一个解释。一旦解释确定，根据各联结词的定义就可求出
15、命题公式中真值联结词的定义就可求出命题公式中真值(T(T或或F)F)。定义定义4-6 4-6 解释解释I I有四个要素：有四个要素：(1) (1) 给出非空论域给出非空论域D D；(2) (2) 对公式对公式G G，对每个常量指派，对每个常量指派D D中的一个元素；中的一个元素；(3) (3) 对公式对公式G G，对每个，对每个n n元谓词指派一个元谓词指派一个Dn TDn T，FF的映的映射；射；(4) (4) 对公式对公式G G，对每个，对每个n n元函数指派一个元函数指派一个Dn DDn D的映射。的映射。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）5 5 谓词公式的永真性
16、与可满足性谓词公式的永真性与可满足性定义定义4-7 4-7 如果谓词公式如果谓词公式P P对于个体域上的任何一对于个体域上的任何一个解释都取得真值，则称个解释都取得真值，则称P P在在D D上是永真的，换上是永真的，换句话说，句话说，P P在每一个非空个体域上均永真，则称在每一个非空个体域上均永真，则称P P永真。永真。定义定义4-8 4-8 对于谓词公式对于谓词公式P P，在个体域，在个体域D D中，至少中，至少存在一个解释使得公式存在一个解释使得公式P P在此解释下真值为在此解释下真值为T T，则，则公式公式P P是可满足的或相容的。是可满足的或相容的。定义定义4-9 4-9 如果谓词公式
17、如果谓词公式P P对个体域对个体域D D上任何一个上任何一个解释都取得真值解释都取得真值F F，则称，则称P P在在D D上永假的，又称为上永假的，又称为不可满足性或不相容性的。不可满足性或不相容性的。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）定义定义4-10 4-10 若公式若公式G G在解释在解释I I下为下为T T，即取值为真，即取值为真，则称解释则称解释I I满足公式满足公式G G，或称解释，或称解释I I是是G G的一个模型。的一个模型。对于公式集对于公式集，可以看成是其中的每个公式，可以看成是其中的每个公式G G的的合取，即合取，即=G1G2=G1G2GnGn，若若
18、G1G1，G2G2，GnGn皆为真，则其合取亦为真，故皆为真，则其合取亦为真，故定义在公式定义在公式G G上的定义都可推广到公式集上的定义都可推广到公式集，也，也是适用的。是适用的。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）6 6 谓词公式的等价性与永真蕴含性谓词公式的等价性与永真蕴含性 推理规则推理规则(1) P(1) P规则：在推理的任何步骤上都可以引入前提。规则：在推理的任何步骤上都可以引入前提。(2) T(2) T规则：推理时，如果前面步骤中有一个或多个公式规则：推理时，如果前面步骤中有一个或多个公式永真蕴含公式永真蕴含公式S S，则可以把，则可以把S S引入推理过程中
19、。引入推理过程中。(3) CP(3) CP规则：如果能从规则：如果能从R R和前提集合中推出和前提集合中推出S S来，则可以来，则可以从前提集合推出从前提集合推出RSRS来。来。(4) (4) 反证法：反证法：P QP Q，当且仅当，当且仅当，P Q F P Q F ，即，即Q Q为为P P的逻的逻辑结论，当且仅当辑结论，当且仅当P QP Q是不可满足的。是不可满足的。定理定理4-1 4-1 为为P1,P2,P1,P2,Pn,Pn的逻辑结论，当且仅当的逻辑结论，当且仅当(P1P2P3(P1P2P3Pn)Pn)是不可满足的。是不可满足的。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）
20、定义定义1 1：谓词公式：谓词公式X X是谓词公式是谓词公式A A的一部分，则称的一部分，则称X X为为A A的子公式。若子公式为（的子公式。若子公式为（ X X）P(X)P(X)或或 （ X X）P(X)P(X)，则称，则称X X为指导变元，为指导变元，P(X)P(X)为相应量为相应量词的作用域或辖域。在辖域中词的作用域或辖域。在辖域中X X的所有出现称为的所有出现称为X X在公式在公式A A中的约束出现（即中的约束出现（即X X为相应量词的指导变为相应量词的指导变元所约束），元所约束），A A中不是约束出现的其它变元称为中不是约束出现的其它变元称为自由变元。自由变元。定义定义2 2：设：设
21、X X是谓词合式公式是谓词合式公式A A的一个个体变元，若的一个个体变元，若以以y y代替代替x x后不产生变元的新的约束出现，则称后不产生变元的新的约束出现，则称 A（X）关于）关于y是自由的。是自由的。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）定理定理1 1：设：设X X是谓词公式是谓词公式A A的一个个体变元，的一个个体变元，A A的论的论域为域为D D，A(x)A(x)关于关于y y是自由的，则是自由的，则 (x)P(x)=P(y) (x)P(x)=P(y) 特例：特例： (x)P(x)=P(X)(x)P(x)=P(X) 上述公式称为全称固化。上述公式称为全称固化。 定
22、理定理2 2：设：设X X是谓词公式是谓词公式A A的一个个体变元，的一个个体变元，A A的论的论域为域为D D，A(x)A(x)关于关于y y是自由的，则是自由的，则 (x)P(x)=P(y)(x)P(x)=P(y)，其中，其中y y是个体域中某是个体域中某一个可使一个可使P(y)P(y)为真的个体。为真的个体。 4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）6 6 谓词公式的等价性与永真蕴含性谓词公式的等价性与永真蕴含性定义定义4-11 4-11 设设P P与与Q Q是两个谓词公式，是两个谓词公式，D D是它们共同是它们共同的个体域，若对于的个体域，若对于D D上的任何解释，上
23、的任何解释，P P和和Q Q都有相都有相同的真值，则称同的真值，则称P P与与Q Q在个体域在个体域D D上是等价的，如上是等价的，如果果D D是任意个体域，则称是任意个体域，则称P P和和Q Q是等价的，记作是等价的，记作 P Q P Q。 定义定义4-12 4-12 对于谓词公式对于谓词公式P P和和Q Q，如果，如果PQPQ永真，则永真，则称称P P永真蕴含永真蕴含Q Q，且称，且称Q Q为为P P的逻辑结论，称的逻辑结论，称P P为为Q Q的的前提，记作前提，记作P QP Q。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）例：证明例：证明(P(PQ)Q)R)R)(R(RP)
24、P)(S(SP) TP) T4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）7 7 谓词公式的范式谓词公式的范式（1 1）. . 前束范式前束范式定义定义4-13 4-13 设设F F为一谓词公式，如果其中的所有为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，且它们的量词均非否定地出现在公式的最前面，且它们的辖域为整个公式，则称辖域为整个公式，则称F F为前述范式。一般地，为前述范式。一般地，前束范式可写成前束范式可写成(Q1x1)(Q1x1)(Qnxn)M(x1,(Qnxn)M(x1,xn),xn)其中，其中，Qi(iQi(i1,2,1,2,n),n)为前缀，它是一个
25、由全为前缀，它是一个由全称量词或存在量词组成的量词串，称量词或存在量词组成的量词串，M(x1,M(x1,xn),xn)为母式，它是一个不含任何量词的谓词公式。为母式，它是一个不含任何量词的谓词公式。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）(2). Skolem(2). Skolem范式范式定义定义4-14 4-14 如果前束范式中所有的存在量词都在如果前束范式中所有的存在量词都在全称量词之前，则称这种形式的谓词公式为全称量词之前，则称这种形式的谓词公式为SkolemSkolem范式。求该范式方法：范式。求该范式方法：把公式变换成等价的前束范式；把公式变换成等价的前束范式；把不
26、含量词的母式变换成等价的合取范式；把不含量词的母式变换成等价的合取范式；消去所有存在量词：消去所有存在量词：若不受全称量词约束，用母式中没有的常量若不受全称量词约束，用母式中没有的常量符号代换；符号代换；若受全称量词约束，用母式中没有的函数来若受全称量词约束，用母式中没有的函数来代换；代换；4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）3. 3. 范式的求解范式的求解对任一合式公式可通过以下步骤化成前束范式：对任一合式公式可通过以下步骤化成前束范式：(1) (1) 消去多余的前束消去多余的前束( (量词量词) )。这在化简过程都要随时注。这在化简过程都要随时注意到，因为可能出现母式
27、中没有其前束中相对应的约束意到，因为可能出现母式中没有其前束中相对应的约束变元，因而这个前束是多余的，应及时消去。变元，因而这个前束是多余的，应及时消去。(2) (2) 消去蕴涵符号消去蕴涵符号( (“”联结词联结词) )。反复使用具有。反复使用具有“”联结词的等值公式，把公式中所有的联结词的等值公式，把公式中所有的“”都消都消去。去。(3) (3) 内移否定词内移否定词“”“”的辖域范围。反复使用摩根定律和的辖域范围。反复使用摩根定律和量词互换式，把否定词标到只作用于原子公式为止。量词互换式，把否定词标到只作用于原子公式为止。(4) (4) 变量标准化。对变量作必要的换名，使每一量词只变量标
28、准化。对变量作必要的换名，使每一量词只约束一个唯一的变量名。由于变量名可任意设定，因而约束一个唯一的变量名。由于变量名可任意设定，因而该过程不影响合式公式的真值。该过程不影响合式公式的真值。(5) (5) 把所有量词都集中到公式左面，移动时不要改变其把所有量词都集中到公式左面，移动时不要改变其相对顺序。相对顺序。4.1一阶谓词逻辑基本理论（续）一阶谓词逻辑基本理论（续）置换（置换（substitution）：）：一个有序对的集合一个有序对的集合s=ts=ti i/v/vi i （i=1, 2,i=1, 2, n, n）称为）称为代代换换。其中其中v vi i（i=1, 2, . ni=1, 2
29、, . n）是互不相同的变量，）是互不相同的变量，t ti i（i=1, 2, . ni=1, 2, . n）是不同于）是不同于v vi i的项，可以是常量、的项，可以是常量、函数，或者其他的变量。函数，或者其他的变量。当当t ti i都是基项时，代换称为都是基项时，代换称为基代换基代换。不含任何元素。不含任何元素的代换称为的代换称为空代换空代换。它是一个空集，记作。它是一个空集，记作。置换置换s s表示将公式（表达式）中的所有变量表示将公式（表达式）中的所有变量v vi i用项用项t ti i代替。代替。对公式对公式E E施以置换施以置换s s，记作，记作E Es s。E Es s称作公式称
30、作公式E E的代换实例。的代换实例。一个公式的任何代换实例都是原公式的逻辑结论。一个公式的任何代换实例都是原公式的逻辑结论。例：例：设有置换设有置换s=z/x, a/ys=z/x, a/y，则：则：Px, f(y), bs=Pz, f(a), bPx, f(y), bs=Pz, f(a), b。这里这里x x被换成了被换成了z z，y y被换成了被换成了a a。定义：设定义：设=t=t1 1/x/x1 1,t,t2 2/x/x2 2, ,t,tn n/x/xn n ，=u=u1 1/y/y1 1,u,u2 2/y/y2 2u um m/y/ym m 是两个代换。是两个代换。与与的的复合代换，记
31、作复合代换，记作，是由下列集合，是由下列集合tt1 1/x/x1 1,t,t2 2/x/x2 2, ,t,tn n/x/xn n,u,u1 1/y/y1 1,u,u2 2/y/y2 2 u um m/y/ym m 删除所有满足删除所有满足t ti i=x=xi i的元素以及所有的元素以及所有yiyi出现在出现在xx1 1,x,x2 2, ,x xn n 中的元素得到的集合。中的元素得到的集合。例：例：设设=f(y)/x,z/y, =f(y)/x,z/y, =a/x,b/y,y/z=a/x,b/y,y/z复合代换一般不满足交换律。复合代换一般不满足交换律。合一（合一（Unify）：）：设有公式的
32、集合设有公式的集合EEi i(i=1, 2, ., m)(i=1, 2, ., m)，如果存在一个置，如果存在一个置换换s s，使得这，使得这m m个公式被施以个公式被施以s s以后，变得完全一样了，则以后，变得完全一样了，则称这称这m m个公式是可合一的，置换个公式是可合一的，置换s s是它们的合一者。是它们的合一者。例：例：设有公式集设有公式集P(x, f(y), b), P(z, f(b), b)P(x, f(y), b), P(z, f(b), b)和置换和置换s s1 1=a/x, b/y, a/z=a/x, b/y, a/z，由于：，由于：P(x, f(y), b)P(x, f(y
33、), b)s s=P(a, f(b), b)=P(a, f(b), b)P(z, f(b), b)P(z, f(b), b)s s=P(a, f(b), b)=P(a, f(b), b)所以公式集所以公式集P(x, f(y), b), P(z, f(b), b)P(x, f(y), b), P(z, f(b), b)是可合一是可合一的，置换的，置换s s1 1=a/x, b/y, a/z=a/x, b/y, a/z是它们的合一者。是它们的合一者。最一般合一者（最一般合一者（mgu）：）：一般来说，一个公式集的合一者不是唯一的。一般来说，一个公式集的合一者不是唯一的。如如s s2 2=z/x,
34、b/y=z/x, b/y和和s s3 3=x/z, b/y=x/z, b/y都是公式集都是公式集P(x, P(x, f(y), b), P(z, f(b), b)f(y), b), P(z, f(b), b)的合一者。的合一者。对于一个公式集来说，如果存在几个合一者，则其中置对于一个公式集来说，如果存在几个合一者，则其中置换数最少、限制最少、产生的例最具一般性的置换称为换数最少、限制最少、产生的例最具一般性的置换称为最一般合一者（最一般合一者（mgumgu）。如在上例中，置换如在上例中，置换s s1 1=a/x, b/y, a/z=a/x, b/y, a/z产生的例为产生的例为P(a, P(a
35、, f(b), b)f(b), b)，置换，置换s s2 2=z/x, b/y=z/x, b/y产生的例为产生的例为P(z, f(b), P(z, f(b), b)b)。对于置换。对于置换s s1 1，置换数为，置换数为3 3，而置换，而置换s s2 2的置换数为的置换数为2 2。相。相对于例对于例P(a, f(b), b)P(a, f(b), b)来说，例来说，例P(z, f(b), b)P(z, f(b), b)含有一个含有一个变量，因此更具一般性。实际上置换变量，因此更具一般性。实际上置换s s2 2就是上例公式集就是上例公式集的最一般合一者，即的最一般合一者，即mgumgu。置换。置换
36、s s3 3=x/z, b/y=x/z, b/y也是该公也是该公式集的式集的mgumgu。可见可见mgumgu也同样不是唯一的。也同样不是唯一的。一致化算法一致化算法定义：设定义：设E=EE=E1 1,E,E2 2, ,E,Ek k 是非空表达式的集合。是非空表达式的集合。从从E E中的各表达式的第一个符号起同时向右比较，中的各表达式的第一个符号起同时向右比较，直至发现第一个彼此不尽相同的符号止。再从各直至发现第一个彼此不尽相同的符号止。再从各表达式的这一符号开始，取出相应表达式的最大表达式的这一符号开始，取出相应表达式的最大子表达式，以这些不尽相同的最大子表达式为元子表达式，以这些不尽相同的
37、最大子表达式为元素组成的集合称为素组成的集合称为E E的分歧集。的分歧集。例：计算例：计算E=P(x,f(y,z),P(x,f(g(a),h(b)E=P(x,f(y,z),P(x,f(g(a),h(b)的分歧集。的分歧集。一致化算法：一致化算法： 设设E E是需要一致化的表达式集合，是需要一致化的表达式集合，W W是用来记录是用来记录E E或或E E的代的代换实例集，换实例集，D D用来记录用来记录W W的分歧集，的分歧集，用来记录代换。用来记录代换。1 1、置、置W W=E=E，= =。2 2、若、若W W中只有一个表达式，则算法终止，中只有一个表达式，则算法终止， 就是就是E E的最广通的
38、最广通代；否则求出代；否则求出W W的分歧集的分歧集D D。3 3、若、若D D中存在两个元素中存在两个元素v v和和t t，其中，其中v v是变量，是变量，t t是项且是项且t t中不中不出现出现v v，则转第，则转第4 4步；否则算法终止，步；否则算法终止，E E的通代不存在，即的通代不存在，即不可一致化。不可一致化。4 4、置、置= = t/v; t/v; 置置W=W t/vW=W t/v。转第。转第2 2步步4.2 确定性推理确定性推理 推理推理是指按照某种策略从已知事实出发去推出结是指按照某种策略从已知事实出发去推出结论的过程。论的过程。推理所用的事实可分为两种情况，一种是与求解推理
39、所用的事实可分为两种情况，一种是与求解问题有关的初始证据，另一种是推理过程中所得问题有关的初始证据，另一种是推理过程中所得到的中间结论。到的中间结论。通常，智能系统的推理过程是通过推理机来完成通常，智能系统的推理过程是通过推理机来完成的。所谓推理机就是智能系统中用来实现推理的的。所谓推理机就是智能系统中用来实现推理的那些程序。那些程序。 二二 推理方法及分类推理方法及分类1. 1. 按推理的逻辑基础分类按推理的逻辑基础分类 (1) (1) 演绎推理演绎推理 演绎推理演绎推理是从已知的一般性知识出发，去推出蕴是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结含在这些已知
40、知识中的适合于某种个别情况的结论。它是一种由一般到个别的推理方法，其核心论。它是一种由一般到个别的推理方法，其核心是三段论，即假言推理、拒取式和假言三段论。是三段论，即假言推理、拒取式和假言三段论。 4.2 确定性推理确定性推理 （续）（续）常用的三段论是由一个大前提、一个小前提和一常用的三段论是由一个大前提、一个小前提和一个结论三部分组成的。其中，大前提是已知的一个结论三部分组成的。其中，大前提是已知的一般性知识或推理过程得到的判断；小前提是关于般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合
41、于小前提的判断。大前提推出的，并且适合于小前提的判断。 4.2 确定性推理确定性推理 （续）（续）(2) (2) 归纳推理归纳推理 归纳推理归纳推理是从一类事物的大量特殊事例出发，去是从一类事物的大量特殊事例出发，去推出该类事物的一般性结论。它是一种由个别到推出该类事物的一般性结论。它是一种由个别到一般的推理方法。归纳推理的基本思想是：先从一般的推理方法。归纳推理的基本思想是：先从已知事实中猜测出一个结论，然后对这个结论的已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认，数学归纳法就是归纳推理正确性加以证明确认，数学归纳法就是归纳推理的一种典型例子。的一种典型例子。 对于归纳推理，
42、如果按照所选事例的广泛性可分对于归纳推理，如果按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理；如果按照推为完全归纳推理和不完全归纳推理；如果按照推理所使用的方法可分为枚举归纳推理、类比归纳理所使用的方法可分为枚举归纳推理、类比归纳推理、统计归纳推理和差异归纳推理等。推理、统计归纳推理和差异归纳推理等。 4.2 确定性推理确定性推理 （续）（续）所谓完全归纳推理是指在进行归纳时需要考察相应事物所谓完全归纳推理是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，来的全部对象，并根据这些对象是否都具有某种属性，来推出该类事物是否具有此属性。推出该类事物是否具有此属性
43、。 所谓不完全归纳推理是指在进行归纳时只考察了相应事所谓不完全归纳推理是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。物的部分对象，就得出了关于该事物的结论。 所谓枚举归纳推理是指在进行归纳时，如果已知某类事所谓枚举归纳推理是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。类事物都具有此种属性。所谓类比推理是指在两个或两类事物有许多属性都相同所谓类比推理是指在两个或两类事物有许多属性都相同或相似的基础上，其它属性上也相同或相似的一种归纳或相似的基础上，其它属性上也相同或相似
44、的一种归纳推理。推理。 4.2 确定性推理确定性推理 （续）（续）(3) (3) 默认推理默认推理 默认推理默认推理是在知识不完全的情况下假设某些条件是在知识不完全的情况下假设某些条件已经具备所进行的推理，因此也称为缺省推理。已经具备所进行的推理，因此也称为缺省推理。在推理过程中如果发现原先的假设不正确，就在推理过程中如果发现原先的假设不正确，就撤销原来的假设以及由此假设所推出的所有结论，撤销原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理。重新按新情况进行推理。 4.2 确定性推理确定性推理 （续）（续）(4) (4) 演绎推理与归纳推理的区别演绎推理与归纳推理的区别演绎推理与归
45、纳推理是两种完全不同的推理。演演绎推理与归纳推理是两种完全不同的推理。演绎推理是在已知领城内的一般性知识的前提下，绎推理是在已知领城内的一般性知识的前提下，通过演绎求解一个具体问题或来证明一个结论的通过演绎求解一个具体问题或来证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此它不能增殖新知识。在归纳推理揭示出来，因此它不能增殖新知识。在归纳推理中，所推出的结论是没有包含在前提内容中的。中，所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出
46、一般性知识的过程，这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。是增殖新知识的过程。 4.2 确定性推理确定性推理 （续）（续）2. 按所用知识的确定性分类按所用知识的确定性分类 按按所所用用知知识识的的确确定定性性，推推理理可可分分为为确确定定性性推推理理和和不不确确定性推理。定性推理。 所所谓谓确确定定性性推推理理是是指指推推理理所所使使用用的的知知识识和和推推出出的的结结论论都都是是可可以以精精确确表表示示的的，其其真真值值要要么么为为真真，要要么么为为假假，不不会有第三种情况出现。会有第三种情况出现。 所所谓谓不不确确定定性性推推理理是是指指推推理理时时所所用用的的知知
47、识识不不都都是是确确定定的的，推推出出的的结结论论也也不不完完全全是是确确定定的的，其其真真值值会会位位于于真真与与假之间。假之间。 4.2 确定性推理确定性推理 （续）（续）三、推理的控制策略及分类三、推理的控制策略及分类 推理的控制策略又可分为推理的控制策略又可分为推理策略推理策略和和搜索策搜索策略略。其中，推理策略主要解决推理方向、冲突消。其中，推理策略主要解决推理方向、冲突消解等问题，搜索策略主要解决推理线路、推理效解等问题，搜索策略主要解决推理线路、推理效果、推理效率等问题。果、推理效率等问题。 4.2 确定性推理确定性推理 （续）（续）四、推理的冲突消解策略四、推理的冲突消解策略在
48、推理的某一步，如果知识库中有多条知识可用，在推理的某一步，如果知识库中有多条知识可用，则称发生了则称发生了冲突冲突。 此时，需要按照某种策略从此时，需要按照某种策略从这多条知识中选择一条最佳知识用于推理，称这这多条知识中选择一条最佳知识用于推理，称这种解决冲突的过程为种解决冲突的过程为冲突消解冲突消解。冲突消解所用的。冲突消解所用的策略则称为策略则称为冲突消解策略冲突消解策略。 4.2 确定性推理确定性推理 （续）（续）常用的冲突消解策略有以下：常用的冲突消解策略有以下： 1. 1. 特殊知识优先特殊知识优先2. 2. 新鲜知识优先新鲜知识优先3. 3. 差异性大的知识优先差异性大的知识优先4
49、. 4. 领域特点优先领域特点优先5. 5. 上下文关系优先上下文关系优先6. 6. 前提条件少者优先前提条件少者优先4.2 确定性推理确定性推理 （续）（续）4.3 自然演绎推理自然演绎推理 从一组已知为真的事实出发，直接运用经典逻辑从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。中的推理规则推出结论的过程称为自然演绎推理。在这种推理中，最基本的推理规则是三段论推理，在这种推理中，最基本的推理规则是三段论推理，它包括假言推理、拒取式推理、假言三段论等。它包括假言推理、拒取式推理、假言三段论等。例：设已知下述事实和规则例：设已知下述事实和规则A BACB
50、CDDQ求证：求证：Q为真为真4.3 自然演绎推理自然演绎推理 例：设已知如下事实：例：设已知如下事实：1 1）凡是容易的课程小王（）凡是容易的课程小王（wangwang）都喜欢）都喜欢2 2）C C班的课程都是容易的班的课程都是容易的3 3）dsds是是C C班的一门课程班的一门课程证明：小王喜欢证明：小王喜欢dsds这门课程。这门课程。4.3 自然演绎推理（续）自然演绎推理（续） 4.4 归结演绎推理归结演绎推理 归结演绎推理是一种基于鲁宾逊归结演绎推理是一种基于鲁宾逊(Robinson)(Robinson)归结归结原理的机器推理技术。鲁宾逊归结原理亦称为消原理的机器推理技术。鲁宾逊归结原
51、理亦称为消解原理，是鲁宾逊于解原理，是鲁宾逊于19651965年在海伯伦年在海伯伦(Herbrand)(Herbrand)理论的基础上提出的一种基于逻辑的理论的基础上提出的一种基于逻辑的“反证法反证法”。 1. 1. 子句子句定义定义4-15 4-15 单个谓词公式或其否定式称为单个谓词公式或其否定式称为原子谓词公式原子谓词公式。如如A(x)A(x)，A(x)A(x)等。等。定义定义4-16 4-16 在谓词逻辑中把原子谓词公式及其否定式统称在谓词逻辑中把原子谓词公式及其否定式统称为为文字文字。原子称正文字，原子之非称负文字。原子称正文字，原子之非称负文字。定义定义4-17 4-17 任何文字
52、的析取式称为任何文字的析取式称为子句子句。如。如B(x)K(x)B(x)K(x)，P(x,f(x)Q(x,g(x)P(x,f(x)Q(x,g(x)等。一文字子句称为等。一文字子句称为单位子句单位子句。定义定义4-18 4-18 不包括任何文字的子句称为不包括任何文字的子句称为空子句空子句。因为空子。因为空子句不含有文字，它不能被任何解释满足，所以句不含有文字，它不能被任何解释满足，所以空子句永假空子句永假的，是不可满足的。空子句一般被记为的，是不可满足的。空子句一般被记为或或NILNIL。定义定义4-19 4-19 由子句或空子句所构成的集合称为由子句或空子句所构成的集合称为子句集子句集。它。
53、它表示由集合中的子句的合取构成的范式。表示由集合中的子句的合取构成的范式。空子句集永真空子句集永真。4.4 归结演绎推理归结演绎推理 （续）（续）化子句集的方法：化子句集的方法：、利用等价关系消去谓词公式中的、利用等价关系消去谓词公式中的 ， ；、利用等价关系把、利用等价关系把“ ”移到紧靠谓词的位置上移到紧靠谓词的位置上 ；、重新命名变元名，使不同量词约束的变元有不、重新命名变元名，使不同量词约束的变元有不 同的名字同的名字 ；、把量词全部移到公式的左边；、把量词全部移到公式的左边；、利用等价关系把公式化成斯格林标准形、利用等价关系把公式化成斯格林标准形 ；、消去存在量词、消去存在量词 ；、
54、隐去全称量词；、隐去全称量词；、对变元更名，使不同子句中的变元不同名、对变元更名，使不同子句中的变元不同名 ；、消去合取词、消去合取词 。判断子句集的不可满足性，需对个体域上的一切判断子句集的不可满足性，需对个体域上的一切解释逐个地进行判断，任何一个解释都是不可满解释逐个地进行判断，任何一个解释都是不可满足时，才能判定该子句是不可满足的，这在实际足时，才能判定该子句是不可满足的，这在实际中难以实现。如果实际中选取个体中域的某一有中难以实现。如果实际中选取个体中域的某一有限部分，在此个体域中处处不可满足，则认为子限部分，在此个体域中处处不可满足，则认为子句集处处不可满足成立，则就简单多了。句集处
55、处不可满足成立，则就简单多了。海伯伦构造了一个特殊的域，并证明只要对这个海伯伦构造了一个特殊的域，并证明只要对这个特殊的域上的一切解释进行判定，就可知子集是特殊的域上的一切解释进行判定，就可知子集是否不可满足，这个特殊的域就是海伯伦域。否不可满足，这个特殊的域就是海伯伦域。4.4 归结演绎推理归结演绎推理 （续）（续）海伯伦理论：海伯伦理论：海伯伦全域海伯伦全域基表达式基表达式基例基例H H基基H H解释解释海伯伦定理海伯伦定理语义树语义树海伯伦定理及其实现海伯伦定理及其实现海伯伦全域海伯伦全域H（S）海伯伦域是一个论域的子集，在此特殊域上讨论海伯伦域是一个论域的子集，在此特殊域上讨论子句集的
56、不可满足性与在所有论域上讨论具有相子句集的不可满足性与在所有论域上讨论具有相同的效果。同的效果。由以下方法构造而成：由以下方法构造而成：例：例：例例1 1 求子句集求子句集 的海伯伦域。的海伯伦域。例例2 2 求子句集求子句集 的海伯伦域。的海伯伦域。例例3 3 求子句集求子句集 的海伯伦域。的海伯伦域。定义定义4-22 4-22 如果用如果用H H域中的元素代换子句中的变域中的元素代换子句中的变元，则所得的子句称为基子句，其中的谓词称为元，则所得的子句称为基子句，其中的谓词称为基原子。由基子句构成的集合称为基子句集基原子。由基子句构成的集合称为基子句集S S 。另一种讲法：设另一种讲法：设S
57、 S是子句集，子句是子句集，子句CSCS，用，用H(S)H(S)中的元素代替中的元素代替C C中的变元而得到的基子句称为子中的变元而得到的基子句称为子句句C C的一个基例，也可以说成的一个基例，也可以说成S S的一个基例。的一个基例。定义定义4-23 4-23 子句集中所有基原子构成的集合称为子句集中所有基原子构成的集合称为基原子集。基原子集。基例：基例：用用H H（S S）中的元素代换子句中的变元而得到的）中的元素代换子句中的变元而得到的基子句称为原子句的一个基例。基子句称为原子句的一个基例。海伯伦基（海伯伦基（H H基）（记基）（记B(S)B(S)）：）：由由S S的谓词符号和的谓词符号和
58、H H域中的基项组成的全体基原域中的基项组成的全体基原子的集合。子的集合。B(S)=P(tB(S)=P(t1 1, ,t,tn n)|P)|P是中出现的谓词符号，是中出现的谓词符号， t t1 1, ,t,tn n属于（）属于（） 例：例：设设S=P(x),Q(y,f(y,a) ,S=P(x),Q(y,f(y,a) ,求求S S的海伯伦全域的海伯伦全域H(S),HH(S),H基基B(S)B(S)和第一个子句的基例。和第一个子句的基例。依定义有：依定义有：H H0 0=a=aH H1 1=a,f(a,a)=a,f(a,a) H(S)=a,f(a,a),f(a,f(a,a),f(f(a,a),a)
59、, H(S)=a,f(a,a),f(a,f(a,a),f(f(a,a),a), f(f(a,a),f(a,a) f(f(a,a),f(a,a) B(S)=P(a),Q(a,a),P(f(a,a),Q(a,f(a,a),B(S)=P(a),Q(a,a),P(f(a,a),Q(a,f(a,a), Q(f(a,a),a),Q(f(a,a),f(a,a), Q(f(a,a),a),Q(f(a,a),f(a,a), 第一个子句的基例有：第一个子句的基例有： P(a),P(f(a,a),P(f(a,f(a,a), P(a),P(f(a,a),P(f(a,f(a,a), P(f(f(a,a),a),P(f(
60、f(a,a),f(a,a) P(f(f(a,a),a),P(f(f(a,a),f(a,a)解释：解释：在海伯伦全域上，对子句集中出现的常量、在海伯伦全域上，对子句集中出现的常量、函数和谓词符号按下述方法进行赋值：函数和谓词符号按下述方法进行赋值：对每个常量指派常量本身；对每个常量指派常量本身；对每个对每个n n元函数指派一个从元函数指派一个从n n到的映射；到的映射；对每个对每个n n元谓词指派一个从元谓词指派一个从n n到真值，到真值，的映射；的映射；对谓词的所有指派等同于对对谓词的所有指派等同于对B(S)B(S)的每个基原子指派的每个基原子指派一个真值，则一个一个真值，则一个H-H-解释解
61、释I I* *可以表示成可以表示成I*=P(uI*=P(u1 1, ,u,um m), Q(v), Q(v1 1, ,v,vm m) ) P(u P(u1 1, ,u,um m) ) B(S), Q(vB(S), Q(v1 1, ,v,vm m) )B(S),B(S),且且P(uP(u1 1, ,u,um m) )在该在该 H-H-解释下取解释下取T T，Q(vQ(v1 1, ,v,vm m) )在该在该H-H-解释下取解释下取FF引理：若存在某一论域引理：若存在某一论域D D上的解释上的解释I I满足子句集满足子句集S S，则一定存在一个，则一定存在一个H-H-解释解释I I* *也满足也满
62、足S S。 证明：对证明：对S S在在D D上的任一解释上的任一解释I I，都可以找到与之对应的一个，都可以找到与之对应的一个H-H-解释解释I I* *：I I* *=P(u=P(u1 1, ,u,um m), Q(v), Q(v1 1, ,v,vm m) ) P(u P(u1 1, ,u,um m) ) B(S), QB(S), Q(v(v1 1, ,v,vm m) )B(S),B(S),且且P(uP(u1 1, ,u,um m) )在该在该 H-H-解释下取解释下取T T，Q(vQ(v1 1, ,v,vm m) )在该在该H-H-解释下取解释下取FF 因为在因为在D D上的解释上的解释I
63、 I满足满足S S，即，即S S取真值取真值T T，所以在，所以在H-H-解释解释I I* *下下S S也取也取T T，即，即I I* *满足满足S S，得证，得证定理：子句集定理：子句集S S是不可满足的，当且仅当是不可满足的，当且仅当S S在海伯伦在海伯伦全域全域H H的所有解释下都取真值的所有解释下都取真值F F。 证明：必要性。设证明：必要性。设子句集子句集S S是不可满足的，由定义，所有论是不可满足的，由定义，所有论域上的所有解释都不能满足域上的所有解释都不能满足S S。所以。所以S S在在H H域的所有解释下都取域的所有解释下都取值值F F。 充分性。若在某个论域充分性。若在某个论
64、域D D上的解释上的解释I I满足子句集满足子句集S S，则由引，则由引理，一定存在理，一定存在I I所对应所对应H-H-解释解释I I* *也满足也满足S S，即，即S S取值取值T T。得证。得证。语义树：语义树：定义：设定义：设B(s)B(s)是子句集是子句集S S的的H H基。基。S S的一棵语义树的一棵语义树是一棵向下倒长的二叉树，每一非终结点向下生是一棵向下倒长的二叉树，每一非终结点向下生长的两条边上分别附着长的两条边上分别附着B(s)B(s)中的某个基原子和该中的某个基原子和该基原子之非，但从根结点到任一结点的路径上不基原子之非，但从根结点到任一结点的路径上不存在这样的互补对。存
65、在这样的互补对。语义树是一棵完全语义树，当且仅当从根节点至语义树是一棵完全语义树，当且仅当从根节点至每一终结点的路径上出现每一终结点的路径上出现B(s)B(s)中每一个基原子所中每一个基原子所对应的正文字或负文字。对应的正文字或负文字。基原子代表基原子代表“真真”，基原子之非代表，基原子之非代表“假假”每一分支都代表了一个解释每一分支都代表了一个解释定义：子句集定义：子句集S S的语义树中，若节点的语义树中，若节点N N对应的部分对应的部分解释使解释使S S的某个子句的某个基例为假，而对的某个子句的某个基例为假，而对N N的前的前辈节点不能，则称辈节点不能，则称N N为为失败节点失败节点。若语
66、义树的每。若语义树的每一条分支的终点都是失败节点，则称该语义树为一条分支的终点都是失败节点，则称该语义树为封闭语义树封闭语义树。海伯伦定理：海伯伦定理： 型：一个子句集型：一个子句集S S是不可满足的，当且仅当从的完是不可满足的，当且仅当从的完全语义树中能导出一棵有限的封闭语义树。全语义树中能导出一棵有限的封闭语义树。 证明：必要性。若证明：必要性。若S S是不可满足的，则对任一是不可满足的，则对任一H-H-解释存解释存在在S S的某个字句的基例取假。因的某个字句的基例取假。因S S的完全语义树的每一条分支的完全语义树的每一条分支相当于相当于S S的一个的一个H-H-解释，且基例是由析取关系的
67、基文字组成解释，且基例是由析取关系的基文字组成的有限集合，所以每一分支比存在失败结点，也就是从的有限集合，所以每一分支比存在失败结点，也就是从S S的的完全语义树必能导出一棵有限的封闭语义树。完全语义树必能导出一棵有限的封闭语义树。 充分性：若能导出有限的封闭语义树，则每一条分支上充分性：若能导出有限的封闭语义树，则每一条分支上都有使都有使S S的某个子句基例取假的失败结点，也就是任一的某个子句基例取假的失败结点，也就是任一H-H-解释都不能满足解释都不能满足S S，所以，所以S S是不可满足的。得证。是不可满足的。得证。IIII型：型：一个子句集一个子句集S S是不可满足的，当且仅当存在的是
68、不可满足的，当且仅当存在的有限基例集是不可满足的有限基例集是不可满足的. . 证明证明 必要性：若子句集必要性：若子句集S S是不可满足的，由定理是不可满足的，由定理I I型，型，一定存在封闭语义树，由其所有失败结点所对应的一定存在封闭语义树，由其所有失败结点所对应的S S子句的子句的基例构成的集合是有限的，而且是不可满足的。基例构成的集合是有限的，而且是不可满足的。 充分性：设子句集充分性：设子句集S S有一个不可满足的基例集有一个不可满足的基例集S S 。因为。因为S S的每一个的每一个H-H-解释解释I I1 1总包含总包含S S 的某个的某个H-H-解释解释I I2 2，而，而I I2
69、 2不满足不满足S S ，所以，所以I I1 1也不满足也不满足S S 。 S S 是是S S的基例集，故的基例集，故I I1 1一定不满足一定不满足S S。即即S S不可满足。得证。不可满足。得证。海伯伦定理的实现方法：海伯伦定理的实现方法：1.1.重言式规则：重言式规则： 从从S S中删除所有含有互补文字的子句（称为重言式），中删除所有含有互补文字的子句（称为重言式），得到的子句集得到的子句集S S 不可满足，当且仅当不可满足，当且仅当S S不可满足。不可满足。2.2.单文字规则单文字规则 若若S S中含有单位基子句中含有单位基子句L L，则从，则从S S中删除包含中删除包含L L的所有基
70、子的所有基子句。若得到的子句集句。若得到的子句集S S 为空，则为空，则S S是是可满足可满足的；否则，再从的；否则，再从S S 的子句中删除的子句中删除 L L而得到基子句集而得到基子句集S S。若。若S S不可满足，不可满足，当且仅当当且仅当S S不可满足。不可满足。3.3.纯文字规则纯文字规则 基子句集基子句集S S中的一个文字中的一个文字L L称为纯文字，当且仅当文字称为纯文字，当且仅当文字 L L不出现在不出现在S S中。从中。从S S中删除所有包含纯文字的基子句而得中删除所有包含纯文字的基子句而得到子句集到子句集S S 。 S S 不可满足当且仅当不可满足当且仅当S S不可满足。不
71、可满足。 4 4、分裂规则、分裂规则例例:证明证明S=P(a),Q(a),P(f(a),Q(a)S=P(a),Q(a),P(f(a),Q(a)P(f(a)P(f(a)是不可满足的是不可满足的对对P(a)P(a)使用纯文字规则，得使用纯文字规则，得S S1 1=Q(a),P(f(a),Q(a)=Q(a),P(f(a),Q(a)P(f(a)P(f(a)对对Q(a)Q(a)使用单文字规则，得使用单文字规则，得S S2 2=P(f(a),P(f(a)=P(f(a),P(f(a)对对P(f(a)P(f(a)使用单文字规则，得使用单文字规则，得S S3 3=空空 这些理论是归结原理的理论依据，希望能理解这
72、些理论是归结原理的理论依据，希望能理解重点掌握重点掌握H(S),B(S),H(S),B(S),子句的基例的求法子句的基例的求法归结原理：归结原理：归结原理是一种定理证明方法，归结原理是一种定理证明方法，19651965年由年由RobinsonRobinson提出。由于该方法简单，容易在计算机提出。由于该方法简单，容易在计算机上程序实现，因此一经提出，就得到了人们的广上程序实现，因此一经提出，就得到了人们的广泛关注，对自动定理证明的研究起到了很大的推泛关注，对自动定理证明的研究起到了很大的推动作用。动作用。 用归结原理证明定理有些类似于用归结原理证明定理有些类似于 反证法反证法 的思想。的思想。
73、 在归结法中首先对结论求反，然后将已知条件和在归结法中首先对结论求反，然后将已知条件和结论的否定合在一起用子句集表达。如果该子句结论的否定合在一起用子句集表达。如果该子句集存在矛盾，则证明了结论的正确性。集存在矛盾，则证明了结论的正确性。如何证明子句集存在矛盾呢？如何证明子句集存在矛盾呢？其思路如下：其思路如下：设设S S是已知条件和结论的否定合并后所对应的子是已知条件和结论的否定合并后所对应的子句集。假定有一种变换方法，可以对句集。假定有一种变换方法，可以对S S实施一系实施一系列的变换。而且该变换能够保证变换前后的子句列的变换。而且该变换能够保证变换前后的子句集，在不可满足的意义下是等价的
74、。这样，如果集，在不可满足的意义下是等价的。这样，如果最终得到的子句集是不可满足的，就证明了子句最终得到的子句集是不可满足的，就证明了子句集集S S是不可满足的，从而证明结论成立。是不可满足的，从而证明结论成立。 命题逻辑的归结原理命题逻辑的归结原理例：设两个子句例：设两个子句C C1 1LCLC1 1，C C2 2（LL）C C2 2，则归结式则归结式C CC C1 1CC2 2。当当C C1 1C C2 2时，时，C C。 子句集子句集S SCC1 1，C C2 2，C Cn n 与子句集与子句集S S1 1CC，C C1 1，C C2 2，C Cn n 的不可满足性是等价的（的不可满足性
75、是等价的（S S1 1中中C C是是C C1 1和和C C2 2的归结式，即的归结式，即S S1 1是对是对S S应用归结法后导出应用归结法后导出的子句集）。的子句集）。 命题逻辑中，若给定公理集命题逻辑中，若给定公理集F F和命题和命题P P，则归结，则归结证明过程可归纳如下：证明过程可归纳如下：把把F F转化成子句集表示，得子句集转化成子句集表示，得子句集S S0 0；把命题把命题P P的否定式的否定式PP也转化成子句集表示，也转化成子句集表示，并将其加到并将其加到S S0 0中，得中，得S SS S0 0SSpp ；对子句集对子句集S S反复应用归结推理规则，直至反复应用归结推理规则，直
76、至导出含有空子句的扩大子句集为止。即出现导出含有空子句的扩大子句集为止。即出现归结式为空子句的情况时，表明已找到了矛归结式为空子句的情况时，表明已找到了矛盾，证明过程结束。盾，证明过程结束。例子：例子：设已知公理集为设已知公理集为P P （1 1） （PQPQ）R R （2 2） （STST）Q Q （3 3） T T （4 4）求证求证R R。化成子句集表示后得化成子句集表示后得S SPP，PQRPQR，SQSQ，TQTQ，T T，RR命题逻辑的归结演绎树命题逻辑的归结演绎树 谓词逻辑的归结原理谓词逻辑的归结原理 对于子句对于子句C C1 1LL1 1和和C C2 2LL2 2，如果，如果L
77、 L1 1与与L L2 2可合可合一，且一，且s s是其合一者，则是其合一者，则(C(C1 1CC2 2) )s s是其归结是其归结式。式。其中其中L L1 1、L L2 2是单文字。事实上是单文字。事实上L L1 1、L L2 2中有一个中有一个含有否定符，所以对另一个加上否定符后，才含有否定符，所以对另一个加上否定符后，才能判断它们是否可合一。能判断它们是否可合一。应用归结原理求取问题答案的步骤：应用归结原理求取问题答案的步骤：1 1）把已知前提用谓词公式表示出来，并化为子句集。）把已知前提用谓词公式表示出来，并化为子句集。2 2）把待求问题也用谓词公式表示出来，然后否定并与谓）把待求问题
78、也用谓词公式表示出来，然后否定并与谓词词ANSWERANSWER构成析取式。构成析取式。3 3）把此析取式化为子句集，并把该子句集并入到原子句）把此析取式化为子句集，并把该子句集并入到原子句集中。集中。4 4）对子句集应用归结原理进行归结。）对子句集应用归结原理进行归结。5 5）若得到）若得到ANSWERANSWER，则答案就在，则答案就在ANSWERANSWER中。中。例：已知例：已知1 1）王（）王（wangwang）先生是小李（）先生是小李（LiLi）的老师）的老师2 2）小张（）小张（zhangzhang）与小李是同班同学）与小李是同班同学3 3）如果）如果X X与与Y Y是同班同学，
79、则是同班同学，则X X的老师也是的老师也是Y Y的老的老师。师。求：小张的老师是谁？求：小张的老师是谁？例子：例子：已知：已知：会朗读的人是识字的；会朗读的人是识字的；海豚都不识字；海豚都不识字；有些海豚是很机灵的。有些海豚是很机灵的。证明：证明：有些很机灵的东西不会朗读。有些很机灵的东西不会朗读。 首先把问题用谓词逻辑描述如下：首先把问题用谓词逻辑描述如下：已知：已知：（ x x）（）（R R（x x）L L（x x）（ x x）（）（D D（x x）LL（x x）（ x x）（）（D D（x x）I I（x x）求证：（求证：（ x x）（）（I I（x x）RR（x x）化成子句集化成子
80、句集由已知条件（由已知条件（1 1）得到：）得到：（1 1）RR（x x）L L（x x）由已知条件（由已知条件（2 2）得到：）得到：（2 2）DD（y y）LL（y y）由已知条件（由已知条件（3 3）得到（两个子句）：）得到（两个子句）：（3a3a）D D（A A）（3b3b）I I（A A）由结论的否定得到：由结论的否定得到：（4 4）II（z z）R R（z z）归结反演树归结反演树 补充举例补充举例:试用归结原理作下述题：试用归结原理作下述题：(1)(1)王王(Wang)(Wang)喜欢喜欢(Like)(Like)所有种类的食物所有种类的食物(Food)(Food)；(2)(2)苹
81、果苹果(Apples)(Apples)是食物；是食物；(3)(3)任何一个东西，若任何人吃了任何一个东西，若任何人吃了(Eat)(Eat)它都不会被害死它都不会被害死(Killed)(Killed)，则该东西是食物；，则该东西是食物；(4)(4)李李(Li)(Li)吃花生且仍然活着吃花生且仍然活着(Alike)(Alike)；(5)(5)张张(Zhang)(Zhang)吃任何李吃的东西。吃任何李吃的东西。求证：王喜欢花生。求证：王喜欢花生。解：用谓表示知识：解：用谓表示知识：(1)( x)(Food(x)Like(Wang,x)(1)( x)(Food(x)Like(Wang,x)(2)Foo
82、d(Apples)(2)Food(Apples)(3) ( x)( (3) ( x)( y)(Eat(y,x)Alive(y)Food(x)y)(Eat(y,x)Alive(y)Food(x)(4)Eat(Li,Peanuts)Alive(Li)(4)Eat(Li,Peanuts)Alive(Li)(5) ( x)(Eat(Li,x)Eat(Zhang,x) (5) ( x)(Eat(Li,x)Eat(Zhang,x) 目标：目标：(6)Like(Wang,peanuts)(6)Like(Wang,peanuts) 上述知识化为子句集为：上述知识化为子句集为：(1)Food(x1)Like(W
83、ang,x)(1)Food(x1)Like(Wang,x)(2)Food(Apples)(2)Food(Apples)(3)Eat(y,x2)Alike(y)Food(x2)(3)Eat(y,x2)Alike(y)Food(x2)(4)Eat(Li,Peanuts)(4)Eat(Li,Peanuts)(5) Alive(Li)(5) Alive(Li)(6)Eat(Li,x3)Eat(Zhang,x3)(6)Eat(Li,x3)Eat(Zhang,x3)目标取非后得：目标取非后得：(7)Like(Wang,peanuts)(7)Like(Wang,peanuts)将上述子句进行归结：将上述子句
84、进行归结：(8)Food(Peanuts) (1)(8)Food(Peanuts) (1)和和(7)(7)归结归结(9)Eat(y,Peanuts)Alive(y) (3)(9)Eat(y,Peanuts)Alive(y) (3)和和(8)(8)归结归结(10)Alive(Li) (4)(10)Alive(Li) (4)和和(9)(9)归结归结(11)nil (5)(11)nil (5)和和(10)(10)归结归结 由上归结出空子句可知，命题成立由上归结出空子句可知，命题成立例例2用归结原理作下述题用归结原理作下述题某村农民张某被害，有四个嫌疑犯某村农民张某被害，有四个嫌疑犯A,B,C,DA,
85、B,C,D。公。公安局派出五个侦察员，他们的侦察结果安局派出五个侦察员，他们的侦察结果分别是：分别是：A A，B B之中至少有一人作案，之中至少有一人作案，B B，C C中至中至少有一人作案，少有一人作案，C C，D D中至少有一人作案，中至少有一人作案，A A，C C中至少有一人与此案无关，中至少有一人与此案无关，B B，D D中至少有一人中至少有一人与此案无关，所有侦察结果都是可靠的，求出与此案无关，所有侦察结果都是可靠的，求出谁是罪犯？谁是罪犯？解：设谓词解：设谓词C(D)C(D)表示表示D D为罪犯为罪犯对于第一个侦察员：对于第一个侦察员：C(A)C(B) (1)C(A)C(B) (1
86、)对于第一个侦察员对于第一个侦察员: C(B)C(C) (2): C(B)C(C) (2)对于第一个侦察员对于第一个侦察员: C(C)C(D) (3): C(C)C(D) (3)对于第一个侦察员对于第一个侦察员: : C(A)C(A)C(C) (4)C(C) (4)对于第一个侦察员对于第一个侦察员: : C(B)C(B)C(D) (5)C(D) (5)结论：结论：C(U) ANSWER(U) (6)C(U) ANSWER(U) (6)(1)(1)与（与（4 4）归结：）归结：C(B)C(B)C(C) (7)C(C) (7)(2)(2)与（与（7 7）归结：）归结：C(B) (8)C(B) (8
87、)(6)(6)与（与（8 8）归结：）归结：ANSWER(B). ANSWER(B). |B B是罪犯是罪犯(3)(3)与（与（5 5）归结：）归结：C(C)C(C)C(B) (7)C(B) (7)(2)(2)与（与（7 7）归结：）归结：C(C) (8)C(C) (8)(6)(6)与（与（8 8）归结：）归结：ANSWER(C).ANSWER(C).|C C是罪犯是罪犯 所以所以B,CB,C是罪犯是罪犯搜索策略：搜索策略： 归结方法很简单，但是即便是对于一个比较简单的问题，归结方法很简单，但是即便是对于一个比较简单的问题，往往可以进行归结的子句也比较多。如何从众多的可归结往往可以进行归结的子
88、句也比较多。如何从众多的可归结的子句中选择两个子句，即为搜索策略问题。不同的搜索的子句中选择两个子句，即为搜索策略问题。不同的搜索策略，会影响到系统的效率和开销，同时也会涉及到完备策略，会影响到系统的效率和开销，同时也会涉及到完备性问题。当给定的问题在已知条件下成立时，如果某种归性问题。当给定的问题在已知条件下成立时，如果某种归结策略一定可以在有限步内证明问题是成立的，则该策略结策略一定可以在有限步内证明问题是成立的，则该策略是完备的，否则则是不完备的。这里介绍的是几种在归结是完备的，否则则是不完备的。这里介绍的是几种在归结过程中常用的搜索策略。这些策略中有些是完备的，有些过程中常用的搜索策略
89、。这些策略中有些是完备的，有些是非完备的，应该注意每种策略的完备性。在系统实现时，是非完备的，应该注意每种策略的完备性。在系统实现时，我们当然希望选择完备的搜索策略，但一些非完备的搜索我们当然希望选择完备的搜索策略，但一些非完备的搜索策略往往具有较高的求解效率，因此也有使用的必要性。策略往往具有较高的求解效率，因此也有使用的必要性。搜索策略：搜索策略： （1 1）宽度优先策略）宽度优先策略 （2 2）支持集策略）支持集策略 （3 3）单元子句优先策略）单元子句优先策略（4 4）线性输入形策略）线性输入形策略（5 5）祖先过滤形策略）祖先过滤形策略 （1）宽度优先策略）宽度优先策略宽度优先策略首
90、先归结出基本集宽度优先策略首先归结出基本集S中可能生成的中可能生成的所有归结式，称第一级归结式，然后生成第二级所有归结式，称第一级归结式，然后生成第二级归结式等等，直到出现空子句。宽度优先策略是归结式等等，直到出现空子句。宽度优先策略是完备的，但效率低。完备的，但效率低。（2）支持集策略）支持集策略 支持集策略是指在每一次归结时，其母子句中，支持集策略是指在每一次归结时，其母子句中，至少有一个是与目标公式否定式有关的子句（即至少有一个是与目标公式否定式有关的子句（即目标公式否定式本身或与该否定式有关的后裔）。目标公式否定式本身或与该否定式有关的后裔）。可以证明支持集策略是完备的，即当矛盾存在时
91、，可以证明支持集策略是完备的，即当矛盾存在时，一定能找到由支持集策略产生的一棵反演树。也一定能找到由支持集策略产生的一棵反演树。也可以把支持集策略看成是在宽度优先策略中引进可以把支持集策略看成是在宽度优先策略中引进某种约束条件，它代表一种启发信息，因而有较某种约束条件，它代表一种启发信息，因而有较高的效率高的效率（3）单元子句优先策略）单元子句优先策略这种策略是支持集策略的进一步改进，每次归结这种策略是支持集策略的进一步改进，每次归结时优先选取单文字的子句（称单元子句）为母子时优先选取单文字的子句（称单元子句）为母子句进行归结，显然归结式的文字数会比其他情况句进行归结，显然归结式的文字数会比其
92、他情况归结的结果要少，这有利于向空子句的方向搜索，归结的结果要少，这有利于向空子句的方向搜索，实际上会提高效率。实际上会提高效率。（4）线性输入形策略）线性输入形策略 这种策略每次归结时，至少有一个母子句是从基这种策略每次归结时，至少有一个母子句是从基本集中挑选。该策略可限制生成归结式的数目，本集中挑选。该策略可限制生成归结式的数目，具有简单和效率高的优点。但它不是一个完备的具有简单和效率高的优点。但它不是一个完备的策略。策略。（5）祖先过滤形策略）祖先过滤形策略 祖先过滤形策略在每次归结时，有一个母子句或祖先过滤形策略在每次归结时，有一个母子句或者是从基本集中挑选，或者是从另一个母子句的者是
93、从基本集中挑选，或者是从另一个母子句的先辈子句中挑选，这和线性输入形策略有点相似，先辈子句中挑选，这和线性输入形策略有点相似，但比它降低了挑选的限制。可以证明这种策略也但比它降低了挑选的限制。可以证明这种策略也是完备的。是完备的。基于归结法的问答系统基于归结法的问答系统 通过前面的介绍，我们已经知道，当一个结论成立时，通过前面的介绍，我们已经知道，当一个结论成立时，归结法可以证明该结论成立。对于一个类似于这样的结归结法可以证明该结论成立。对于一个类似于这样的结论：论：(x)W(x)(x)W(x)，证明，证明(x)W(x)(x)W(x)成立固然重要，但有时我们成立固然重要，但有时我们可能更关心的
94、是使得可能更关心的是使得W(x)W(x)成立的那个成立的那个x x是什么，也就是说，是什么，也就是说，我们希望得到问题的答案。基于归结的问答就是利用归我们希望得到问题的答案。基于归结的问答就是利用归结方法获得问题答案的方法。结方法获得问题答案的方法。基本方法是先用归结法证明问题的正确性，给出归结树。基本方法是先用归结法证明问题的正确性，给出归结树。然后再根据该归结树构造一个修改证明树。然后再根据该归结树构造一个修改证明树。构造的方法是：将结论的否定对应的子句构造的方法是：将结论的否定对应的子句S1S1，再，再次求反得到一个新子句次求反得到一个新子句S2S2，用，用S1S1与与S2S2构造一个重
95、构造一个重言式言式S1S2S1S2，用该重言式代替归结树中的子句，用该重言式代替归结树中的子句S1S1，并参予有关的置换。最后在归结树得到空子句，并参予有关的置换。最后在归结树得到空子句的地方得到的子句就是问题的回答。的地方得到的子句就是问题的回答。基于归结法的问答系统基于归结法的问答系统 例：例：If Fido goes wherever John goes and if John is at school， where is Fido?这个问题给出两个已知事实和一个询问，这个询问的答这个问题给出两个已知事实和一个询问，这个询问的答案应从事实出发演绎得到。案应从事实出发演绎得到。先把问题用谓
96、词逻辑公式表示：先把问题用谓词逻辑公式表示：前提公式集：前提公式集：（ x）（）（AT（John，x）AT（Fido，x）AT（John，School）目标公式：（目标公式：（ x）AT（Fido，x）归结树：归结树：改为修改证明树：改为修改证明树：（1）用一个重言式来取代目标公式的否定式这）用一个重言式来取代目标公式的否定式这个子句，该重言式为个子句，该重言式为AT（Fido，x） AT（Fido，x）（2）按反演树的构造进行归结，给出重言式替）按反演树的构造进行归结，给出重言式替代目标否定式子句后的证明树，这时根子句不为代目标否定式子句后的证明树，这时根子句不为空，称这个证明树为修改证明树
97、。空，称这个证明树为修改证明树。（3）用根部的子句作为回答语句。）用根部的子句作为回答语句。修改证明树：修改证明树：提取回答的一般过程提取回答的一般过程 （1）使用某种搜索策略求出一个归结反演树，树中对合）使用某种搜索策略求出一个归结反演树，树中对合一集加一标记；一集加一标记；（2）目标公式否定式化简得到的子句中，对出现的任一）目标公式否定式化简得到的子句中，对出现的任一Skolem函数均以新变量置换；函数均以新变量置换；（3）根据目标公式否定式的子句，构造重言式；）根据目标公式否定式的子句，构造重言式；（4）按照已找到的归结反演树的结构，将目标否定式子）按照已找到的归结反演树的结构，将目标否
98、定式子句用永真式替代，且每次归结合一文字集不变，生成出句用永真式替代，且每次归结合一文字集不变，生成出修改证明树；修改证明树；（5）根部子句就作为所要提取的回答语句。）根部子句就作为所要提取的回答语句。猴子摘香蕉问题猴子摘香蕉问题 初始状态的公式集表示为：初始状态的公式集表示为： ONBOX（s0），），AT（box，b， s0），），AT（monkey，a，s0），），HB（s0） 公式组：公式组： （1）ONBOX（S0）（2）（）（ x）（）（ s）（）（ONBOX（s）AT（box， x， pushbox （x， s）（3）（）（ s）（）（ONBOX（climbbox（s）（4）（）
99、（ s）（）（ONBOX（s） AT（box， c， s）HB（grasp （s）（5）（）（ x）（）（ s）（）（AT（box， x， s）AT（box， x， climbbox（s）（6）（）（ s）HB（s）子句集：子句集： （1）ONBOX（S0）（2）ONBOX（s1） AT（box， x1， push（x1， s1）（3）ONBOX（climbbox（s2）（4）ONBOX（s3） AT（box， c， s3） HB（grasp（s3）（5）AT（box， x4， s4） AT（box， x4， climbbox（s4）（6）HB（S5）归结方法小结：归结方法小结：求子句集进行归
100、结，方法简单求子句集进行归结，方法简单通过修改证明树的方法，提取回答通过修改证明树的方法，提取回答方法通用方法通用求解效率低，不宜引入启发信息求解效率低，不宜引入启发信息不宜理解推理过程不宜理解推理过程基于规则的正向演绎系统基于规则的正向演绎系统 问题：问题：归结方法不自然归结方法不自然可能丢失包含在蕴涵形中有用的控制信息可能丢失包含在蕴涵形中有用的控制信息例如下面几个蕴涵式例如下面几个蕴涵式ABCABC， ACBACB，BCABCA， ABCABC，BACBAC， CABCAB都与子句（都与子句（ABCABC）等价）等价 但显然上面的蕴涵形所带有的信息更丰富但显然上面的蕴涵形所带有的信息更丰
101、富一般情况下，表述有关问题的知识分两类：一般情况下，表述有关问题的知识分两类：规则：规则：由蕴涵形给出的若干语句组成，是表示某一特由蕴涵形给出的若干语句组成，是表示某一特定领域中的一般知识，并可以当作产生式规则来使用。定领域中的一般知识，并可以当作产生式规则来使用。事实：事实：不以蕴涵形给出，是表示该问题领域的专门知不以蕴涵形给出，是表示该问题领域的专门知识。识。演绎系统就是根据这些演绎系统就是根据这些事实事实和和规则规则来证明一个来证明一个目标公式目标公式，这种定理证明系统是这种定理证明系统是直接直接法的证明系统而不是反演系统。法的证明系统而不是反演系统。一个直接系统不一定比反演系统更有效，
102、但其演绎过程一个直接系统不一定比反演系统更有效，但其演绎过程容易为人们所理解容易为人们所理解。这类系统主要强调使用规则进行演。这类系统主要强调使用规则进行演绎，故称为基于规则的演绎系统。绎，故称为基于规则的演绎系统。解题步骤：解题步骤：1事实表达式的与或形式及其表示事实表达式的与或形式及其表示 2应用规则对与或图作变换应用规则对与或图作变换 把事实表达式化与或形的步骤把事实表达式化与或形的步骤1 1、消去蕴含、等价符号；、消去蕴含、等价符号；2 2、把否定词移到紧跟谓词的位置上，直到每个否、把否定词移到紧跟谓词的位置上，直到每个否定符号的辖域最多只含一个谓词为止；定符号的辖域最多只含一个谓词为
103、止；3 3、对所有表达式进行前束化；、对所有表达式进行前束化；4 4、对全称量词辖域内的变元进行改名和标准化，、对全称量词辖域内的变元进行改名和标准化，使不同量词约束不同的名字；使不同量词约束不同的名字；5 5、消去存在量词；、消去存在量词；6 6、消去全称量词；、消去全称量词；7 7、对变元进行，使得各主合取式之间的变元名互、对变元进行，使得各主合取式之间的变元名互不相同。不相同。将规则转换成要求的形式：将规则转换成要求的形式：1、暂时消去蕴含符号；、暂时消去蕴含符号；2、把否定符号移到紧跟谓词的位置上，使其作、把否定符号移到紧跟谓词的位置上，使其作用域仅限于单个谓词；用域仅限于单个谓词；3
104、、消去存在量词；、消去存在量词；4、化成前束范式，消去全称量词；、化成前束范式，消去全称量词；5、恢复蕴含式表示。、恢复蕴含式表示。例例有事实表达式有事实表达式（ 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）事实的与或树表示：事实的与或树表示：其其“与与”和和“或或”的关系是刚的关系是刚好好相反相反的。的。在与或形中的在与或形中的 号在与或图号在与或图中表达为中表达为或或的关系，而与或的关系，而与或形中的形中的 号，在与或图中表号，
105、在与或图中表达为达为与与的关系。的关系。 2.应用应用F规则对与或图作变换规则对与或图作变换 F规则的表示形式：规则的表示形式： LW（1）其中）其中L是单文字，是单文字，W是任一化成与或形的是任一化成与或形的公式。公式。（2）这个蕴涵式中的所有变量都假定有全称）这个蕴涵式中的所有变量都假定有全称量词的约束量词的约束（3）变量已经换名，使之与事实公式或其他）变量已经换名，使之与事实公式或其他规则公式中的变量区别开来。规则公式中的变量区别开来。例：例：( x)( y)( z)P(x，y，z) ( u)Q(x，u) （1）暂时消去蕴涵符号）暂时消去蕴涵符号( x)( y)( z)P(x，y，z)
106、( 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）化成前束式并隐略去全部全称量词）化成前束式并隐略去全部全称量词P（x，y，f（x，y） Q（x，u）（5）恢复蕴涵式表示）恢复蕴涵式表示P（x，y，f（x，y）Q（x，u） 命题逻辑的情况：命题逻辑的情况：例：例：事实：事实：（P Q） R） （S （T U）规则：规则：S（X Y） Z规则化成子句为：规则化成子句为： S X Z；S
107、Y Z 原先子句集：原先子句集：S （P Q），），S R，（，（T U） （P Q），），（T U） R新子句集：新子句集： X Z P Q，X Z R，Y Z P Q，Y Z R，（T U） （P Q），（），（T U） R一个基于规则的正向演绎系统，其演绎过程就是一个基于规则的正向演绎系统，其演绎过程就是不断地调用匹配上的规则对与或图进行变换，直到生成的与或图含有目标表达式为止，也就是要也就是要用目标公式作为系统的结束条件。用目标公式作为系统的结束条件。正向系统的目标表达式要限制为文字析取形（子正向系统的目标表达式要限制为文字析取形（子句形）的一类公式，当目标公式中有一个文字同句形）的一
108、类公式，当目标公式中有一个文字同与或图中某一个端节点所标记的文字匹配上时，与或图中某一个端节点所标记的文字匹配上时，和规则匹配时做法一样，通过匹配弧把目标文字和规则匹配时做法一样，通过匹配弧把目标文字添加到图上，这个匹配弧的后裔节点称为目标节添加到图上，这个匹配弧的后裔节点称为目标节点。这样当产生式系统演绎得到的与或图包含有点。这样当产生式系统演绎得到的与或图包含有目标节点的解图时，系统结束演绎，这时便推出目标节点的解图时，系统结束演绎，这时便推出了一个与目标有关的子句。了一个与目标有关的子句。简例说明系统的推理过程简例说明系统的推理过程 事实表达式：事实表达式：A B规则集：规则集：AC D
109、BE G目标公式：目标公式：C G 谓词逻辑的情况谓词逻辑的情况 ：事实表达式化成与或形事实表达式化成与或形规则化成规则化成LW目标用对偶形式目标用对偶形式进行进行Skolem化化 ，即：，即：消去全称量词，对受全称量词约束的变量用消去全称量词，对受全称量词约束的变量用Skolem函数或者常量代替函数或者常量代替省略存在量词，所有变量默认为受存在量词约省略存在量词，所有变量默认为受存在量词约束束进行变量换名，使得目标公式的主析取元之间进行变量换名，使得目标公式的主析取元之间具有不同的变量名。具有不同的变量名。规则每使用一次，都要进行换名规则每使用一次，都要进行换名对偶形式进行对偶形式进行Sko
110、lem化举例化举例例如，设目标公式为例如，设目标公式为（ y）（）（ x）（）（P（x， y） Q（x， y）用用Skolem函数消去全称量词后有函数消去全称量词后有（ y）（）（P（f（y），）， y） Q（f（y），）， y）和命题逻辑的情况一样，目标公式也限制为文字的析和命题逻辑的情况一样，目标公式也限制为文字的析取式，这时要进行变量改名，使每个析取元具有不同取式，这时要进行变量改名，使每个析取元具有不同的变量符号，于是有的变量符号，于是有（ y）P（f（y），）， y） （ y1）Q（f（y1），）， y1）以后目标公式中的变量都假定受存在量词的束约。以后目标公式中的变量都假定受存在量
111、词的束约。例例事实与或形表示事实与或形表示 P（A，y） （Q（x，A） R（B，y）规则蕴涵式规则蕴涵式 P（z，B）（S（z） X（B）施以规则后的与或图施以规则后的与或图 前边用合一置换时的问题：前边用合一置换时的问题：会不会在合一置换过程中有矛盾会不会在合一置换过程中有矛盾的地方？的地方？可能有。怎么办？怎么办？求一致解图一致解图一致解图 只有当解图所涉及的置换集是一致的时，解图才只有当解图所涉及的置换集是一致的时，解图才是一致的。是一致的。置换集一致的充分必要条件是该置换集存在置换集一致的充分必要条件是该置换集存在合一合一复合复合。置换集的合一复合也是一个置换，表示的是置换置换集的合
112、一复合也是一个置换，表示的是置换集中所有置换集中所有置换综合综合以后的结果。以后的结果。 合一复合合一复合求一个置换集的合一复合，首先构造求一个置换集的合一复合，首先构造U1、U2两个表达式，其中两个表达式，其中U1由置换集中的所有由置换集中的所有被置被置换的变量换的变量组成，组成，U2由与由与U1中的变量所对应的中的变量所对应的置换项置换项组成。当组成。当U1、U2可以合一时，则所对可以合一时，则所对应的置换集是一致的（一致置换），它们的应的置换集是一致的（一致置换），它们的mgu就是该置换集的就是该置换集的合一复合合一复合。合一复合是可结合、可交换的。这是一个很好合一复合是可结合、可交换的
113、。这是一个很好的性质，说明在用基于规则的正向演绎方法求的性质，说明在用基于规则的正向演绎方法求解问题时，与使用规则的次序无关。解问题时，与使用规则的次序无关。一致置换举例：一致置换举例：例：猎犬问题例：猎犬问题 设事实和规则描述如下：设事实和规则描述如下：事实：事实：Fido barks and bites， or Fido is not a dog.F：DOG（FIDO） （BARKS（FIDO） BITES（FIDO）规则：规则：All terriers are dogs.R1：DOG（x）TERRIER（x）Anyone who barks is noisy.R2：BARKS（y）NOI
114、SY（y）要证明的目标是要证明的目标是There exists someone who is not a terriers or who is noisy.目标公式：目标公式： TERRIER（z） NOISY（z）NOISY(z)R1：DOG（x）TERRIER（x）R2：BARKS（y）NOISY（y）置换集置换集FIDO/x，FIDO/y，FIDO/z，它的合一复合它的合一复合u FIDO/x，FIDO/y，FIDO/z。根据这个一致解图，目标公式根据这个一致解图，目标公式 TERRIER（z） NOISY（z）是事实和规则的逻辑推）是事实和规则的逻辑推论，因而得到了证明。论，因而得到了
115、证明。如果用这个合一复合如果用这个合一复合u应用于这个目标公式，可得应用于这个目标公式，可得TERRIER（FIDO） NOISY（FIDO）它是已证目标公式的例，可作为一个回答语句。它是已证目标公式的例，可作为一个回答语句。正向演绎系统小结正向演绎系统小结事实表达式为与或形事实表达式为与或形规则化成规则化成LW目标公式为文字析取目标公式为文字析取对事实和规则进行对事实和规则进行Skolem化，消去存在量词，对化，消去存在量词，对主合取元进行变量换名主合取元进行变量换名 目标用对偶形式进行目标用对偶形式进行Skolem化化 ，消去全称量词，消去全称量词，对主析取元进行变量换名对主析取元进行变量
116、换名 事实表达成与或树，事实表达成与或树，“ ”对应对应“或或”的关系，的关系，而而“ ” 对应对应“与与”的关系。的关系。从事实出发，正向应用规则，直到得到目标结点从事实出发，正向应用规则，直到得到目标结点为结束的一致解图为止为结束的一致解图为止存在合一复合时，解图才有效存在合一复合时，解图才有效基于规则的逆向演绎系统基于规则的逆向演绎系统逆向演绎系统中，是从目标表达式出发，反方向逆向演绎系统中，是从目标表达式出发，反方向使用规则（使用规则（B规则）对目标表达式的与或图进行规则）对目标表达式的与或图进行变换，最后得到含有事实节点的一致解图。变换，最后得到含有事实节点的一致解图。 1目标表达式
117、的与或形表示目标表达式的与或形表示目标用对偶形式目标用对偶形式进行进行Skolem化化 ，即：，即：消去全称量词，对受全称量词约束的变量用消去全称量词，对受全称量词约束的变量用Skolem函数或者常量代替函数或者常量代替省略存在量词，所有变量默认为受存在量词约省略存在量词，所有变量默认为受存在量词约束束进行变量换名，使得目标公式的主析取元之间进行变量换名，使得目标公式的主析取元之间具有不同的变量名。具有不同的变量名。与或图表示与或图表示其其“与与”和和“或或”的关系是刚的关系是刚好好一致一致的。的。在与或形中的在与或形中的 号在与或图号在与或图中表达为中表达为与与的关系，而与或的关系，而与或形
118、中的形中的 号，在与或图中表号，在与或图中表达为达为或或的关系。的关系。例：例：目标公式：（目标公式：（ y）（）（ x）（）（P（x）（Q（x， y） （R（x） S（y）Skolem化后：化后：P（f（y） （Q（f（y），）， y） （R（f（y） S（y）变量标准化：变量标准化：P（f（z） （Q（f（y），）， y） （R（f（y） S（y） 目标公式的与或图表示目标公式的与或图表示 一致2规则的应用规则的应用 在一个逆向演绎系统中，规则具有形式：在一个逆向演绎系统中，规则具有形式：WL，其中，其中W是任意形式的与或形，是任意形式的与或形，L是单文字，它表示是单文字，它表示L可以由可
119、以由W推推导出。其中的变量受全称量词约束，如果有存在量词，导出。其中的变量受全称量词约束，如果有存在量词，则将其则将其Skolem化，消去存在量词。化，消去存在量词。如果在与或图中有一个叶节点刚好与如果在与或图中有一个叶节点刚好与L可以合一，则可以合一，则可以使用规则对与或图进行变换。其方法是，求出该叶可以使用规则对与或图进行变换。其方法是，求出该叶节点与节点与L的的mgu g，将该叶节点与，将该叶节点与L用一个匹配弧连接起来，用一个匹配弧连接起来，用用g对对W进行置换，然后将进行置换，然后将W添加到与或图中。添加到与或图中。例例:设事实有设事实有F1：DOG（FIDO）F2：BARKS（FI
120、DO）F3：WAGS-TAIL（FIDO）F4：MEOWS（MYRTLE）规则集：规则集：R1：（：（WAGS-TAIL（x1） DOG（x1）FRIENDLY（x1）R2：（FRIENDLY（x2） BARKS（x2）AFRAID（y2，x2）R3：DOG（x3）ANIMAL（x3）R4：CAT（x4）ANIMAL（x4）R5：MEOWS（x5）CAT（x5）询问：询问：If there are a cat and a dog such that the cat is unafraid of the dog.目标公式：目标公式：（ x）（）（ y）（）（CAT（x） DOG（y） AFRAI
121、D（x，y）其逆向一致解图如下其逆向一致解图如下:R1：（：（WAGS-TAIL（x1） DOG（x1）FRIENDLY（x1）R2：（：（FRIENDLY（x2） BARKS（x2）AFRAID（y2，x2）R5：MEOWS（x5）CAT（x5）F1：DOG（FIDO）F2：BARKS（FIDO）F3：WAGS-TAIL（FIDO）F4：MEOWS（MYRTLE）R1：（：（WAGS-TAIL（x1） DOG（x1）FRIENDLY（x1）R2：（：（FRIENDLY（x2） BARKS（x2）AFRAID（y2，x2）R3：DOG（x3）ANIMAL（x3）R4：CAT（x4）ANIMAL
122、（x4）R5：MEOWS（x5）CAT（x5）置换集是置换集是x/x5，MYRTLE/x，FIDO/y，x/y2，y/x2，FIDO/y，y/x1，FIDO/y，FIDO/y由此求得的合一复合是由此求得的合一复合是MYRTLE/x5，MYRTLE/x，FIDO/y，MYRTLE/y2，FIDO/x2，FIDO/x1解图是一个一致解图，目标公式得到证明。把这个合解图是一个一致解图，目标公式得到证明。把这个合一复合置换应用到目标公式得到的例，其回答语句为一复合置换应用到目标公式得到的例，其回答语句为（CAT（MYRTLE） DOG（FIDO） AFRAID（MYRTLE，FIDO）正向系统和逆向系
123、统特点对比正向系统和逆向系统特点对比正正 向向 系系 统统逆逆 向向 系系 统统使使用用条条件件（1）事实表达式是任意形式）事实表达式是任意形式（2）规则形式为）规则形式为LW或或L1L2W（L为单文字，为单文字，W为任意形式）为任意形式）（3）目标公式为文字析取形）目标公式为文字析取形（1）事实表达式是文字合取形式）事实表达式是文字合取形式（2）规则形式为）规则形式为WL或或WL1L2（L为单文字，为单文字，W为任意形式）为任意形式）（3）目标公式是任意形式）目标公式是任意形式正逆向系统特点对比正逆向系统特点对比(续续)化化简简过过程程（1）用）用Skolem函数消去事实表函数消去事实表达式
124、中的存在量词，化简的公式达式中的存在量词，化简的公式受全称量词的约束受全称量词的约束（2）对规则的处理同（）对规则的处理同（1）（3）用）用Skolem函数（对偶形）函数（对偶形）消去目标公式中的全称量词，化消去目标公式中的全称量词，化简的公式受存在量词约束简的公式受存在量词约束（1）用）用Skolem函数（对偶形）消函数（对偶形）消去目标公式中的全称量词，化简的去目标公式中的全称量词，化简的公式受存在量词的约束公式受存在量词的约束（2）对规则的处理同（）对规则的处理同（3）（3）用）用Skolem函数消去事实表达函数消去事实表达式中的存在量词，化简的公式受全式中的存在量词，化简的公式受全称量
125、词的约束称量词的约束正逆向系统特点对比正逆向系统特点对比(续续)初始综初始综合数据合数据库库事实表达式的与或树事实表达式的与或树（对应为与关系，对应为与关系，对对应为或关系）应为或关系）目标公式的与或树目标公式的与或树（对应为或关系，对应为或关系，对应为与关对应为与关系）系）推理过推理过程程从事实出发，正向应用规从事实出发，正向应用规则（变量改名，前项与事则（变量改名，前项与事实文字匹配，后项代替前实文字匹配，后项代替前项），直至得到目标节点项），直至得到目标节点为结束条件的一致解图为为结束条件的一致解图为止止从目标出发，逆向应用规则（变量从目标出发，逆向应用规则（变量改名，后项与子目标文字匹配，前改名，后项与子目标文字匹配，前项代替后项），直至得到事实节点项代替后项），直至得到事实节点为结束条件的一致解图为止为结束条件的一致解图为止子句形子句形式式文字的析取式文字的析取式文字的合取式文字的合取式子句集子句集形式形式子句的合取式（合取范式）子句的合取式（合取范式） 子句的析取式（析取范式）子句的析取式（析取范式）
