知识一阶谓词逻辑表示法.pptx

《知识一阶谓词逻辑表示法.pptx》由会员分享，可在线阅读，更多相关《知识一阶谓词逻辑表示法.pptx（161页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能中的谓词演算及应用1 学习目标：了解一阶谓词演算的基本体系，掌握命题逻辑和谓词逻辑的归结方法，以及基于归结的提取问题回答的方法，掌握基于规则的正向演绎方法和逆向演绎方法。2 学习指南：本章内容是在一阶谓词逻辑的基础上介绍有关的方法，假定读者已经学习过一阶谓词逻辑的有关内容。在学习的同时，自己尝试重新做一遍例题，将有助于你的学习。在有条件的情况下，可以尝试用程序实现本章介绍的一些主要方法，不过有一定的难度。第1页/共161页人工智能中的谓词演算及应用3 难重点：命题逻辑的归结方法，谓词逻辑的归结方法，基于归结的问题回答方法，基于规则的正向演绎方法和基于规则的逆向演绎方法。第2页/共161

2、页第3页/共161页4.1一阶谓词逻辑基本理论一、命题与联结词定义4-1 具有确定真值的陈述句，称为命题。命题若是简单的陈述句，不能分解成更简单的句子，我们称这样的命题为简单命题或原子命题。可以用英文字母P，Q，R，或是带有下标的大写英文字母Pi等表示简单命题，将命题用合适的符号表示，称为命题符号化。对于简单命题来说，它的真值是确定的，因而又称为命题常项或命题常元。真值可以变化的简单陈述句称为命题变项或命题变元。第4页/共161页2、联结词（1）“否定”联结词，当命题P为真时，则P为假，反之为真。（2）：“析取”联结词，它表示两个命题存在“或”的关系。（3）：“合取”联结词，它表示两个命题之间

3、具有“与”关系。（4）：“蕴含”、“单条件”，PQ表示“如果P，则Q”。其中P为前件，Q为后件。（5）：“等价”、“双条件”，P Q表示“P当且仅当Q”。4.1一阶谓词逻辑基本理论（续）第5页/共161页4.1一阶谓词逻辑基本理论（续）第6页/共161页二、个体词与谓词1.个体词定义4-2 个体(个体词)是指所研究对象中可以独立存在的具体事物、状态或个体之间的关系。在谓词逻辑中，个体可以是常量也可以是变量(变元)。个体常量：表示具体的或特定的个体，用a,b,c,d表示；个体变量：表示抽象的或泛指的个体，用x,y,z表示；个体域(论域)：个体变量的（取值范围）值域，常用D表示。个体域可以是有限的

4、也可以是无限的4.1一阶谓词逻辑基本理论（续）第7页/共161页2.谓词定义4-3 用于刻画个体的性质、状态或个体之间的关系，称为谓词。谓词一般也用P,Q,R等大写字母表示。3.函数符号函数符号，又称函词，是从若干个思维对象到某个思维对象的映射的符号。n元函数f(x1,x2,xn)规定为一个映射：f:Dn D4.1一阶谓词逻辑基本理论（续）第8页/共161页谓词与函数的区别：1、谓词的真值是真和假，而函数无真值可言，其值是个体域中的某个个体。2、谓词实现的是从个体域中的个体到T或F的映射，而函数实现的是同一个个体域中从一个个体到另一个个体的映射。3、在谓词逻辑中，函数本身不能单独使用，它必须嵌

5、入到谓词中。4.1一阶谓词逻辑基本理论（续）第9页/共161页4.谓词(谓词填式)定义4-4 将表示谓词的符号和表示个体的符号组合成一个函词，就称谓词填式，简称谓词。如果没有特殊说明，以后我们提到的谓词均指谓词填式。与命题逻辑相似，谓词逻辑中也有谓词常项和谓词变项之分。含有个体变元的谓词没有真值，但当谓词中的变元都用指定的个体取代时，谓词就有了特定的值T或F。4.1一阶谓词逻辑基本理论（续）第10页/共161页n元谓词：含有n个个体符号的谓词P(x1,x2,xn)，它表示一个映射：P：Dn T，F或是(D1D2Dn)T，F谓词的语义是由使用者根据需要人为定义的。谓词中包含的个体数目称为谓词的元

6、数，如：Q(x)是一元谓词，P(x,a)是二元谓词，A(x1,x2,xn)是n元谓词。若X是个体常元、变元或函数，谓词称为一阶谓词；如果某个X本身又是一个一阶谓词，则谓词称为二阶谓词。依次类推。与谓词联系着的n个个体的出现顺序不是任意的。同一谓词的个体变元取值于不同个体域时，所得命题真假值可以不同。4.1一阶谓词逻辑基本理论（续）第11页/共161页三、量词设谓词P(x)表示x是正数，F(x,y)表示x与y是好朋友，则：(x)P(x)：表示个体域中所有个体x都是正数。(x)(y)F(x,y)：表示在个体域中所有个体x,都存在个体y，x与y是好朋友。4.1一阶谓词逻辑基本理论（续）第12页/共1

7、61页四、谓词公式项：单独一个个体符号（包括常量和变量）是项；若t1，tn是项，则f(t1,tn)是项；所有项由上述两规则生成。原子公式：若t1，tn是项，P是n元谓词符号，则单独一个谓词P(t1,tn)称为原子谓词公式；n=0时退化为原子命题公式。简称原子4.1一阶谓词逻辑基本理论（续）第13页/共161页定义4-5 下述规则得到谓词演算的合式公式：(1)单个谓词是合式公式，称为原子谓词公式；(2)若A是谓词公式，则 A也是合式公式；(3)若A，B都是合式公式，则AB，AB，AB，A B也都是合式公式；(4)若A是合式公式，x是任一个体变元，则(x)A，(x)A也都是合式公式。4.1一阶谓词

8、逻辑基本理论（续）第14页/共161页2.公式的解释在命题逻辑中，对命题公式中各个命题变元的一次真值指派称为命题公式的一个解释。一旦解释确定，根据各联结词的定义就可求出命题公式中真值(T或F)。定义4-6 解释I有四个要素：(1)给出非空论域D；(2)对公式G，对每个常量指派D中的一个元素；(3)对公式G，对每个n元谓词指派一个Dn T，F的映射；(4)对公式G，对每个n元函数指派一个Dn D的映射。4.1一阶谓词逻辑基本理论（续）第15页/共161页5 谓词公式的永真性与可满足性定义4-7 如果谓词公式P对于个体域上的任何一个解释都取得真值，则称P在D上是永真的，换句话说，P在每一个非空个体

9、域上均永真，则称P永真。定义4-8 对于谓词公式P，在个体域D中，至少存在一个解释使得公式P在此解释下真值为T，则公式P是可满足的或相容的。定义4-9 如果谓词公式P对个体域D上任何一个解释都取得真值F，则称P在D上永假的，又称为不可满足性或不相容性的。4.1一阶谓词逻辑基本理论（续）第16页/共161页定义4-10 若公式G在解释I下为T，即取值为真，则称解释I满足公式G，或称解释I是G的一个模型。对于公式集，可以看成是其中的每个公式G的合取，即=G1G2Gn，若G1，G2，Gn皆为真，则其合取亦为真，故定义在公式G上的定义都可推广到公式集，也是适用的。4.1一阶谓词逻辑基本理论（续）第17

10、页/共161页6 谓词公式的等价性与永真蕴含性 推理规则(1)P规则：在推理的任何步骤上都可以引入前提。(2)T规则：推理时，如果前面步骤中有一个或多个公式永真蕴含公式S，则可以把S引入推理过程中。(3)CP规则：如果能从R和前提集合中推出S来，则可以从前提集合推出RS来。(4)反证法：P Q，当且仅当，P Q F，即Q为P的逻辑结论，当且仅当P Q是不可满足的。定理4-1 为P1,P2,Pn的逻辑结论，当且仅当(P1P2P3Pn)是不可满足的。4.1一阶谓词逻辑基本理论（续）第18页/共161页定义1：谓词公式X是谓词公式A的一部分，则称X为A的子公式。若子公式为（X）P(X)或 （X）P(

11、X)，则称X为指导变元，P(X)为相应量词的作用域或辖域。在辖域中X的所有出现称为X在公式A中的约束出现（即X为相应量词的指导变元所约束），A中不是约束出现的其它变元称为自由变元。定义2：设X是谓词合式公式A的一个个体变元，若以y代替x后不产生变元的新的约束出现，则称 A（X）关于y是自由的。4.1一阶谓词逻辑基本理论（续）第19页/共161页定理1：设X是谓词公式A的一个个体变元，A的论域为D，A(x)关于y是自由的，则 (x)P(x)=P(y)特例：(x)P(x)=P(X)上述公式称为全称固化。定理2：设X是谓词公式A的一个个体变元，A的论域为D，A(x)关于y是自由的，则 (x)P(x)

12、=P(y)，其中y是个体域中某一个可使P(y)为真的个体。4.1一阶谓词逻辑基本理论（续）第20页/共161页6 谓词公式的等价性与永真蕴含性定义4-11 设P与Q是两个谓词公式，D是它们共同的个体域，若对于D上的任何解释，P和Q都有相同的真值，则称P与Q在个体域D上是等价的，如果D是任意个体域，则称P和Q是等价的，记作 P Q。定义4-12 对于谓词公式P和Q，如果PQ永真，则称P永真蕴含Q，且称Q为P的逻辑结论，称P为Q的前提，记作P Q。4.1一阶谓词逻辑基本理论（续）第21页/共161页例：证明(PQ)R)(RP)(SP)T4.1一阶谓词逻辑基本理论（续）第22页/共161页7 谓词公

13、式的范式（1）.前束范式定义4-13 设F为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，且它们的辖域为整个公式，则称F为前述范式。一般地，前束范式可写成(Q1x1)(Qnxn)M(x1,xn)其中，Qi(i1,2,n)为前缀，它是一个由全称量词或存在量词组成的量词串，M(x1,xn)为母式，它是一个不含任何量词的谓词公式。4.1一阶谓词逻辑基本理论（续）第23页/共161页(2).Skolem范式定义4-14 如果前束范式中所有的存在量词都在全称量词之前，则称这种形式的谓词公式为Skolem范式。求该范式方法：把公式变换成等价的前束范式；把不含量词的母式变换成等价的合取范式；消

14、去所有存在量词：若不受全称量词约束，用母式中没有的常量符号代换；若受全称量词约束，用母式中没有的函数来代换；4.1一阶谓词逻辑基本理论（续）第24页/共161页3.范式的求解对任一合式公式可通过以下步骤化成前束范式：(1)消去多余的前束(量词)。这在化简过程都要随时注意到，因为可能出现母式中没有其前束中相对应的约束变元，因而这个前束是多余的，应及时消去。(2)消去蕴涵符号(“”联结词)。反复使用具有“”联结词的等值公式，把公式中所有的“”都消去。(3)内移否定词“”的辖域范围。反复使用摩根定律和量词互换式，把否定词标到只作用于原子公式为止。(4)变量标准化。对变量作必要的换名，使每一量词只约束

15、一个唯一的变量名。由于变量名可任意设定，因而该过程不影响合式公式的真值。(5)把所有量词都集中到公式左面，移动时不要改变其相对顺序。4.1一阶谓词逻辑基本理论（续）第25页/共161页置换（substitution）：一个有序对的集合s=ti/vi（i=1,2,n）称为代换。其中vi（i=1,2,.n）是互不相同的变量，ti（i=1,2,.n）是不同于vi的项，可以是常量、函数，或者其他的变量。当ti都是基项时，代换称为基代换。不含任何元素的代换称为空代换。它是一个空集，记作。第26页/共161页置换s表示将公式（表达式）中的所有变量vi用项ti代替。对公式E施以置换s，记作Es。Es称作公式

16、E的代换实例。一个公式的任何代换实例都是原公式的逻辑结论。例：设有置换s=z/x,a/y，则：Px,f(y),bs=Pz,f(a),b。这里x被换成了z，y被换成了a。第27页/共161页定义：设=t1/x1,t2/x2,tn/xn，=u1/y1,u2/y2um/ym是两个代换。与的复合代换，记作，是由下列集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2 um/ym 删除所有满足ti=xi的元素以及所有yi出现在x1,x2,xn中的元素得到的集合。例：设=f(y)/x,z/y,=a/x,b/y,y/z复合代换一般不满足交换律。第28页/共161页合一（Unify）：设有公式的集合

17、Ei(i=1,2,.,m)，如果存在一个置换s，使得这m个公式被施以s以后，变得完全一样了，则称这m个公式是可合一的，置换s是它们的合一者。例：设有公式集P(x,f(y),b),P(z,f(b),b)和置换s1=a/x,b/y,a/z，由于：P(x,f(y),b)s=P(a,f(b),b)P(z,f(b),b)s=P(a,f(b),b)所以公式集P(x,f(y),b),P(z,f(b),b)是可合一的，置换s1=a/x,b/y,a/z是它们的合一者。第29页/共161页最一般合一者（mgu）：一般来说，一个公式集的合一者不是唯一的。如s2=z/x,b/y和s3=x/z,b/y都是公式集P(x,

18、f(y),b),P(z,f(b),b)的合一者。对于一个公式集来说，如果存在几个合一者，则其中置换数最少、限制最少、产生的例最具一般性的置换称为最一般合一者（mgu）。如在上例中，置换s1=a/x,b/y,a/z产生的例为P(a,f(b),b)，置换s2=z/x,b/y产生的例为P(z,f(b),b)。对于置换s1，置换数为3，而置换s2的置换数为2。相对于例P(a,f(b),b)来说，例P(z,f(b),b)含有一个变量，因此更具一般性。实际上置换s2就是上例公式集的最一般合一者，即mgu。置换s3=x/z,b/y也是该公式集的mgu。可见mgu也同样不是唯一的。第30页/共161页一致化算

19、法定义：设E=E1,E2,Ek是非空表达式的集合。从E中的各表达式的第一个符号起同时向右比较，直至发现第一个彼此不尽相同的符号止。再从各表达式的这一符号开始，取出相应表达式的最大子表达式，以这些不尽相同的最大子表达式为元素组成的集合称为E的分歧集。例：计算E=P(x,f(y,z),P(x,f(g(a),h(b)的分歧集。第31页/共161页一致化算法：设E是需要一致化的表达式集合，W是用来记录E或E的代换实例集，D用来记录W的分歧集，用来记录代换。1、置W=E，=。2、若W中只有一个表达式，则算法终止，就是E的最广通代；否则求出W的分歧集D。3、若D中存在两个元素v和t，其中v是变量，t是项且

20、t中不出现v，则转第4步；否则算法终止，E的通代不存在，即不可一致化。4、置=t/v;置W=W t/v。转第2步第32页/共161页4.2 确定性推理 推理是指按照某种策略从已知事实出发去推出结论的过程。推理所用的事实可分为两种情况，一种是与求解问题有关的初始证据，另一种是推理过程中所得到的中间结论。通常，智能系统的推理过程是通过推理机来完成的。所谓推理机就是智能系统中用来实现推理的那些程序。第33页/共161页二 推理方法及分类1.按推理的逻辑基础分类(1)演绎推理 演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。它是一种由一般到个别的推理方法，其核心

21、是三段论，即假言推理、拒取式和假言三段论。4.2 确定性推理（续）第34页/共161页常用的三段论是由一个大前提、一个小前提和一个结论三部分组成的。其中，大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。4.2 确定性推理（续）第35页/共161页(2)归纳推理 归纳推理是从一类事物的大量特殊事例出发，去推出该类事物的一般性结论。它是一种由个别到一般的推理方法。归纳推理的基本思想是：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认，数学归纳法就是归纳推理的一种典型例子。对于归纳推理，如果按照

22、所选事例的广泛性可分为完全归纳推理和不完全归纳推理；如果按照推理所使用的方法可分为枚举归纳推理、类比归纳推理、统计归纳推理和差异归纳推理等。4.2 确定性推理（续）第36页/共161页所谓完全归纳推理是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，来推出该类事物是否具有此属性。所谓不完全归纳推理是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。所谓枚举归纳推理是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。所谓类比推理是指在两个或两类事物有许多属性都相同或相似的基础上，其它属性上也相同或相似

23、的一种归纳推理。4.2 确定性推理（续）第37页/共161页(3)默认推理 默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理，因此也称为缺省推理。在推理过程中如果发现原先的假设不正确，就撤销原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理。4.2 确定性推理（续）第38页/共161页(4)演绎推理与归纳推理的区别演绎推理与归纳推理是两种完全不同的推理。演绎推理是在已知领城内的一般性知识的前提下，通过演绎求解一个具体问题或来证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此它不能增殖新知识。在归纳推理中，所推

24、出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。4.2 确定性推理（续）第39页/共161页2.按所用知识的确定性分类 按所用知识的确定性，推理可分为确定性推理和不确定性推理。所谓确定性推理是指推理所使用的知识和推出的结论都是可以精确表示的，其真值要么为真，要么为假，不会有第三种情况出现。所谓不确定性推理是指推理时所用的知识不都是确定的，推出的结论也不完全是确定的，其真值会位于真与假之间。4.2 确定性推理（续）第40页/共161页三、推理的控制策略及分类 推理的控制策略又可分为推理策略和搜索策略。其中，推理策略主要解决推理方向、冲突消解等问题，

25、搜索策略主要解决推理线路、推理效果、推理效率等问题。4.2 确定性推理（续）第41页/共161页四、推理的冲突消解策略在推理的某一步，如果知识库中有多条知识可用，则称发生了冲突。此时，需要按照某种策略从这多条知识中选择一条最佳知识用于推理，称这种解决冲突的过程为冲突消解。冲突消解所用的策略则称为冲突消解策略。4.2 确定性推理（续）第42页/共161页常用的冲突消解策略有以下：1.特殊知识优先2.新鲜知识优先3.差异性大的知识优先4.领域特点优先5.上下文关系优先6.前提条件少者优先4.2 确定性推理（续）第43页/共161页4.3 自然演绎推理 从一组已知为真的事实出发，直接运用经典逻辑中的

26、推理规则推出结论的过程称为自然演绎推理。在这种推理中，最基本的推理规则是三段论推理，它包括假言推理、拒取式推理、假言三段论等。第44页/共161页例：设已知下述事实和规则A BACBCDDQ求证：Q为真4.3 自然演绎推理 第45页/共161页例：设已知如下事实：1）凡是容易的课程小王（wang）都喜欢2）C班的课程都是容易的3）ds是C班的一门课程证明：小王喜欢ds这门课程。4.3 自然演绎推理（续）第46页/共161页4.4 归结演绎推理 归结演绎推理是一种基于鲁宾逊(Robinson)归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理，是鲁宾逊于1965年在海伯伦(Herbrand)理

27、论的基础上提出的一种基于逻辑的“反证法”。第47页/共161页1.子句定义4-15 单个谓词公式或其否定式称为原子谓词公式。如A(x)，A(x)等。定义4-16 在谓词逻辑中把原子谓词公式及其否定式统称为文字。原子称正文字，原子之非称负文字。定义4-17 任何文字的析取式称为子句。如B(x)K(x)，P(x,f(x)Q(x,g(x)等。一文字子句称为单位子句。定义4-18 不包括任何文字的子句称为空子句。因为空子句不含有文字，它不能被任何解释满足，所以空子句永假的，是不可满足的。空子句一般被记为或NIL。定义4-19 由子句或空子句所构成的集合称为子句集。它表示由集合中的子句的合取构成的范式。

28、空子句集永真。4.4 归结演绎推理（续）第48页/共161页化子句集的方法：、利用等价关系消去谓词公式中的，；、利用等价关系把“”移到紧靠谓词的位置上；、重新命名变元名，使不同量词约束的变元有不 同的名字；、把量词全部移到公式的左边；、利用等价关系把公式化成斯格林标准形；、消去存在量词；、隐去全称量词；、对变元更名，使不同子句中的变元不同名；、消去合取词。第49页/共161页判断子句集的不可满足性，需对个体域上的一切解释逐个地进行判断，任何一个解释都是不可满足时，才能判定该子句是不可满足的，这在实际中难以实现。如果实际中选取个体中域的某一有限部分，在此个体域中处处不可满足，则认为子句集处处不可

29、满足成立，则就简单多了。海伯伦构造了一个特殊的域，并证明只要对这个特殊的域上的一切解释进行判定，就可知子集是否不可满足，这个特殊的域就是海伯伦域。4.4 归结演绎推理（续）第50页/共161页海伯伦理论：海伯伦全域基表达式基例H基H解释海伯伦定理语义树海伯伦定理及其实现第51页/共161页海伯伦全域H（S）海伯伦域是一个论域的子集，在此特殊域上讨论子句集的不可满足性与在所有论域上讨论具有相同的效果。由以下方法构造而成：第52页/共161页例：第53页/共161页例1 求子句集 的海伯伦域。例2 求子句集 的海伯伦域。例3 求子句集 的海伯伦域。第54页/共161页定义4-22 如果用H域中的元

30、素代换子句中的变元，则所得的子句称为基子句，其中的谓词称为基原子。由基子句构成的集合称为基子句集S。另一种讲法：设S是子句集，子句CS，用H(S)中的元素代替C中的变元而得到的基子句称为子句C的一个基例，也可以说成S的一个基例。定义4-23 子句集中所有基原子构成的集合称为基原子集。第55页/共161页基例：用H（S）中的元素代换子句中的变元而得到的基子句称为原子句的一个基例。海伯伦基（H基）（记B(S)）：由S的谓词符号和H域中的基项组成的全体基原子的集合。B(S)=P(t1,tn)|P是中出现的谓词符号，t1,tn属于（）第56页/共161页例：设S=P(x),Q(y,f(y,a),求S的

31、海伯伦全域H(S),H基B(S)和第一个子句的基例。依定义有：H0=aH1=a,f(a,a)H(S)=a,f(a,a),f(a,f(a,a),f(f(a,a),a),f(f(a,a),f(a,a)第57页/共161页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),第一个子句的基例有：P(a),P(f(a,a),P(f(a,f(a,a),P(f(f(a,a),a),P(f(f(a,a),f(a,a)第58页/共161页解释：在海伯伦全域上，对子句集中出现的常量、函数和谓词符号按下述方法进行赋值：对每个常量指派常量本

32、身；对每个n元函数指派一个从n到的映射；对每个n元谓词指派一个从n到真值，的映射；第59页/共161页对谓词的所有指派等同于对B(S)的每个基原子指派一个真值，则一个H-解释I*可以表示成I*=P(u1,um),Q(v1,vm)P(u1,um)B(S),Q(v1,vm)B(S),且P(u1,um)在该 H-解释下取T，Q(v1,vm)在该H-解释下取F第60页/共161页引理：若存在某一论域D上的解释I满足子句集S，则一定存在一个H-解释I*也满足S。证明：对S在D上的任一解释I，都可以找到与之对应的一个H-解释I*：I*=P(u1,um),Q(v1,vm)P(u1,um)B(S),Q(v1,

33、vm)B(S),且P(u1,um)在该 H-解释下取T，Q(v1,vm)在该H-解释下取F 因为在D上的解释I满足S，即S取真值T，所以在H-解释I*下S也取T，即I*满足S，得证第61页/共161页定理：子句集S是不可满足的，当且仅当S在海伯伦全域H的所有解释下都取真值F。证明：必要性。设子句集S是不可满足的，由定义，所有论域上的所有解释都不能满足S。所以S在H域的所有解释下都取值F。充分性。若在某个论域D上的解释I满足子句集S，则由引理，一定存在I所对应H-解释I*也满足S，即S取值T。得证。第62页/共161页语义树：定义：设B(s)是子句集S的H基。S的一棵语义树是一棵向下倒长的二叉树

34、，每一非终结点向下生长的两条边上分别附着B(s)中的某个基原子和该基原子之非，但从根结点到任一结点的路径上不存在这样的互补对。语义树是一棵完全语义树，当且仅当从根节点至每一终结点的路径上出现B(s)中每一个基原子所对应的正文字或负文字。基原子代表“真”，基原子之非代表“假”每一分支都代表了一个解释第63页/共161页定义：子句集S的语义树中，若节点N对应的部分解释使S的某个子句的某个基例为假，而对N的前辈节点不能，则称N为失败节点。若语义树的每一条分支的终点都是失败节点，则称该语义树为封闭语义树。第64页/共161页海伯伦定理：型：一个子句集S是不可满足的，当且仅当从的完全语义树中能导出一棵有

35、限的封闭语义树。证明：必要性。若S是不可满足的，则对任一H-解释存在S的某个字句的基例取假。因S的完全语义树的每一条分支相当于S的一个H-解释，且基例是由析取关系的基文字组成的有限集合，所以每一分支比存在失败结点，也就是从S的完全语义树必能导出一棵有限的封闭语义树。充分性：若能导出有限的封闭语义树，则每一条分支上都有使S的某个子句基例取假的失败结点，也就是任一H-解释都不能满足S，所以S是不可满足的。得证。第65页/共161页IIII型：型：一个子句集一个子句集S S是不可满足的，当且仅当存在的是不可满足的，当且仅当存在的有限基例集是不可满足的有限基例集是不可满足的.证明证明 必要性：若子句集

36、必要性：若子句集S S是不可满足的，由定理是不可满足的，由定理I I型，型，一定存在封闭语义树，由其所有失败结点所对应的一定存在封闭语义树，由其所有失败结点所对应的S S子句的子句的基例构成的集合是有限的，而且是不可满足的。基例构成的集合是有限的，而且是不可满足的。充分性：设子句集充分性：设子句集S S有一个不可满足的基例集有一个不可满足的基例集SS。因为。因为S S的每一个的每一个H-H-解释解释I I1 1总包含总包含SS的某个的某个H-H-解释解释I I2 2，而，而I I2 2不满足不满足SS，所以，所以I I1 1也不满足也不满足SS。S S是是S S的基例集，故的基例集，故I I1

37、 1一定不满足一定不满足S S。即即S S不可满足。得证。不可满足。得证。第66页/共161页海伯伦定理的实现方法：1.重言式规则：从S中删除所有含有互补文字的子句（称为重言式），得到的子句集S不可满足，当且仅当S不可满足。2.单文字规则 若S中含有单位基子句L，则从S中删除包含L的所有基子句。若得到的子句集S为空，则S是可满足的；否则，再从S的子句中删除 L而得到基子句集S。若S不可满足，当且仅当S不可满足。3.纯文字规则 基子句集S中的一个文字L称为纯文字，当且仅当文字 L不出现在S中。从S中删除所有包含纯文字的基子句而得到子句集S。S 不可满足当且仅当S不可满足。4、分裂规则第67页/共

38、161页例:证明S=P(a),Q(a),P(f(a),Q(a)P(f(a)是不可满足的对P(a)使用纯文字规则，得S1=Q(a),P(f(a),Q(a)P(f(a)对Q(a)使用单文字规则，得S2=P(f(a),P(f(a)对P(f(a)使用单文字规则，得S3=空第68页/共161页这些理论是归结原理的理论依据，希望能理解重点掌握H(S),B(S),子句的基例的求法第69页/共161页归结原理：归结原理是一种定理证明方法，1965年由Robinson提出。由于该方法简单，容易在计算机上程序实现，因此一经提出，就得到了人们的广泛关注，对自动定理证明的研究起到了很大的推动作用。用归结原理证明定理有

39、些类似于反证法的思想。第70页/共161页在归结法中首先对结论求反，然后将已知条件和结论的否定合在一起用子句集表达。如果该子句集存在矛盾，则证明了结论的正确性。如何证明子句集存在矛盾呢？其思路如下：第71页/共161页设S是已知条件和结论的否定合并后所对应的子句集。假定有一种变换方法，可以对S实施一系列的变换。而且该变换能够保证变换前后的子句集，在不可满足的意义下是等价的。这样，如果最终得到的子句集是不可满足的，就证明了子句集S是不可满足的，从而证明结论成立。第72页/共161页命题逻辑的归结原理例：设两个子句C1LC1，C2（L）C2，则归结式CC1C2。当C1C2时，C。子句集SC1，C2

40、，Cn与子句集S1C，C1，C2，Cn的不可满足性是等价的（S1中C是C1和C2的归结式，即S1是对S应用归结法后导出的子句集）。第73页/共161页命题逻辑中，若给定公理集F和命题P，则归结证明过程可归纳如下：把F转化成子句集表示，得子句集S0；把命题P的否定式P也转化成子句集表示，并将其加到S0中，得SS0Sp；对子句集S反复应用归结推理规则，直至导出含有空子句的扩大子句集为止。即出现归结式为空子句的情况时，表明已找到了矛盾，证明过程结束。第74页/共161页例子：设已知公理集为P（1）（PQ）R（2）（ST）Q（3）T（4）求证R。化成子句集表示后得SP，PQR，SQ，TQ，T，R第75

41、页/共161页命题逻辑的归结演绎树 第76页/共161页谓词逻辑的归结原理 对于子句C1L1和C2L2，如果L1与L2可合一，且s是其合一者，则(C1C2)s是其归结式。其中L1、L2是单文字。事实上L1、L2中有一个含有否定符，所以对另一个加上否定符后，才能判断它们是否可合一。第77页/共161页应用归结原理求取问题答案的步骤：1）把已知前提用谓词公式表示出来，并化为子句集。2）把待求问题也用谓词公式表示出来，然后否定并与谓词ANSWER构成析取式。3）把此析取式化为子句集，并把该子句集并入到原子句集中。4）对子句集应用归结原理进行归结。5）若得到ANSWER，则答案就在ANSWER中。第7

42、8页/共161页例：已知1）王（wang）先生是小李（Li）的老师2）小张（zhang）与小李是同班同学3）如果X与Y是同班同学，则X的老师也是Y的老师。求：小张的老师是谁？第79页/共161页例子：已知：会朗读的人是识字的；海豚都不识字；有些海豚是很机灵的。证明：有些很机灵的东西不会朗读。第80页/共161页首先把问题用谓词逻辑描述如下：已知：（x）（R（x）L（x）（x）（D（x）L（x）（x）（D（x）I（x）求证：（x）（I（x）R（x）第81页/共161页化成子句集由已知条件（1）得到：（1）R（x）L（x）由已知条件（2）得到：（2）D（y）L（y）由已知条件（3）得到（两个子句）

43、：（3a）D（A）（3b）I（A）由结论的否定得到：（4）I（z）R（z）第82页/共161页归结反演树 第83页/共161页补充举例:试用归结原理作下述题：(1)王(Wang)喜欢(Like)所有种类的食物(Food)；(2)苹果(Apples)是食物；(3)任何一个东西，若任何人吃了(Eat)它都不会被害死(Killed)，则该东西是食物；(4)李(Li)吃花生且仍然活着(Alike)；(5)张(Zhang)吃任何李吃的东西。求证：王喜欢花生。第84页/共161页解：用谓表示知识：(1)(x)(Food(x)Like(Wang,x)(2)Food(Apples)(3)(x)(y)(Eat(

44、y,x)Alive(y)Food(x)(4)Eat(Li,Peanuts)Alive(Li)(5)(x)(Eat(Li,x)Eat(Zhang,x)目标：(6)Like(Wang,peanuts)第85页/共161页上述知识化为子句集为：(1)Food(x1)Like(Wang,x)(2)Food(Apples)(3)Eat(y,x2)Alike(y)Food(x2)(4)Eat(Li,Peanuts)(5)Alive(Li)(6)Eat(Li,x3)Eat(Zhang,x3)目标取非后得：(7)Like(Wang,peanuts)第86页/共161页将上述子句进行归结：(8)Food(Pea

45、nuts)(1)和(7)归结(9)Eat(y,Peanuts)Alive(y)(3)和(8)归结(10)Alive(Li)(4)和(9)归结(11)nil (5)和(10)归结 由上归结出空子句可知，命题成立第87页/共161页例2用归结原理作下述题某村农民张某被害，有四个嫌疑犯A,B,C,D。公安局派出五个侦察员，他们的侦察结果分别是：A，B之中至少有一人作案，B，C中至少有一人作案，C，D中至少有一人作案，A，C中至少有一人与此案无关，B，D中至少有一人与此案无关，所有侦察结果都是可靠的，求出谁是罪犯？第88页/共161页解：设谓词C(D)表示D为罪犯对于第一个侦察员：C(A)C(B)(1

46、)对于第一个侦察员:C(B)C(C)(2)对于第一个侦察员:C(C)C(D)(3)对于第一个侦察员:C(A)C(C)(4)对于第一个侦察员:C(B)C(D)(5)结论：C(U)ANSWER(U)(6)第89页/共161页(1)与（4）归结：C(B)C(C)(7)(2)与（7）归结：C(B)(8)(6)与（8）归结：ANSWER(B).B是罪犯(3)与（5）归结：C(C)C(B)(7)(2)与（7）归结：C(C)(8)(6)与（8）归结：ANSWER(C).C是罪犯 所以B,C是罪犯第90页/共161页搜索策略：归结方法很简单，但是即便是对于一个比较简单的问题，往往可以进行归结的子句也比较多。如

47、何从众多的可归结的子句中选择两个子句，即为搜索策略问题。不同的搜索策略，会影响到系统的效率和开销，同时也会涉及到完备性问题。当给定的问题在已知条件下成立时，如果某种归结策略一定可以在有限步内证明问题是成立的，则该策略是完备的，否则则是不完备的。这里介绍的是几种在归结过程中常用的搜索策略。这些策略中有些是完备的，有些是非完备的，应该注意每种策略的完备性。在系统实现时，我们当然希望选择完备的搜索策略，但一些非完备的搜索策略往往具有较高的求解效率，因此也有使用的必要性。第91页/共161页搜索策略：（1）宽度优先策略（2）支持集策略（3）单元子句优先策略（4）线性输入形策略（5）祖先过滤形策略 第9

48、2页/共161页（1）宽度优先策略第93页/共161页宽度优先策略首先归结出基本集S中可能生成的所有归结式，称第一级归结式，然后生成第二级归结式等等，直到出现空子句。宽度优先策略是完备的，但效率低。第94页/共161页（2）支持集策略 第95页/共161页支持集策略是指在每一次归结时，其母子句中，至少有一个是与目标公式否定式有关的子句（即目标公式否定式本身或与该否定式有关的后裔）。可以证明支持集策略是完备的，即当矛盾存在时，一定能找到由支持集策略产生的一棵反演树。也可以把支持集策略看成是在宽度优先策略中引进某种约束条件，它代表一种启发信息，因而有较高的效率第96页/共161页（3）单元子句优先

49、策略第97页/共161页这种策略是支持集策略的进一步改进，每次归结时优先选取单文字的子句（称单元子句）为母子句进行归结，显然归结式的文字数会比其他情况归结的结果要少，这有利于向空子句的方向搜索，实际上会提高效率。第98页/共161页（4）线性输入形策略 第99页/共161页这种策略每次归结时，至少有一个母子句是从基本集中挑选。该策略可限制生成归结式的数目，具有简单和效率高的优点。但它不是一个完备的策略。第100页/共161页（5）祖先过滤形策略 第101页/共161页祖先过滤形策略在每次归结时，有一个母子句或者是从基本集中挑选，或者是从另一个母子句的先辈子句中挑选，这和线性输入形策略有点相似，

50、但比它降低了挑选的限制。可以证明这种策略也是完备的。第102页/共161页基于归结法的问答系统 通过前面的介绍，我们已经知道，当一个结论成立时，归结法可以证明该结论成立。对于一个类似于这样的结论：(x)W(x)，证明(x)W(x)成立固然重要，但有时我们可能更关心的是使得W(x)成立的那个x是什么，也就是说，我们希望得到问题的答案。基于归结的问答就是利用归结方法获得问题答案的方法。基本方法是先用归结法证明问题的正确性，给出归结树。然后再根据该归结树构造一个修改证明树。第103页/共161页构造的方法是：将结论的否定对应的子句S1，再次求反得到一个新子句S2，用S1与S2构造一个重言式S1S2，