《谓词逻辑基础》PPT课件.ppt

《《谓词逻辑基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《谓词逻辑基础》PPT课件.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.2谓词逻辑基础谓词逻辑基础一阶逻辑一阶逻辑l基本概念基本概念l个体词：表示主语的词个体词：表示主语的词l谓词：刻画个体性质或个体之间关系的词谓词：刻画个体性质或个体之间关系的词l量词：表示数量的词量词：表示数量的词l小王是个工程师。小王是个工程师。l8是个自然数。是个自然数。l我去买花。我去买花。l小丽和小华是朋友。小丽和小华是朋友。其其中中，“小小王王”、“工工程程师师”、“我我”、“花花”、“8”、“小小丽丽”、“小小华华”都都是是个个体体词词，而而“是是个个工工程程师师”、“是是个个自自然然数数”、“去去买买”、“是是朋朋友友”都都是是谓谓词词。显显然然前前两两个个谓谓词词表表示示的

2、的是是事事物物的的性性质质，第第三三个个谓谓词词“去去买买”表表示示的的一一个个动动作作也也表表示示了了主主、宾宾两两个个个个体体词词的的关关系系，最最后后一一个个谓谓词词“是是朋朋友友”表表示示两两个个个个体体词词之之间间的的关系。关系。3.2谓词逻辑基础谓词逻辑基础3.2谓词逻辑基础谓词逻辑基础l例如：（例如：（1）所有的人都是要死的。）所有的人都是要死的。l（2）有的人活到一百岁以上。有的人活到一百岁以上。在个体域在个体域D为人类集合时，可符号化为：为人类集合时，可符号化为：（1）xPxP(x x)，其中，其中P P(x x)表示表示x x是要死的。是要死的。（2）x Qx Q(x x)

3、,),其中其中Q Q(x x)表示表示x x活到一百岁以上。活到一百岁以上。在个体域在个体域D是全总个体域时，是全总个体域时，引入特殊谓词引入特殊谓词R R(x x)表示表示x x是人，可符号化为：是人，可符号化为：（1 1）x x（R R(x x)P P(x x)）,其中，其中，R R(x x)表示表示x x是人；是人；P P(x x)表示表示x x是要死的。是要死的。（2 2）x x（R R(x x)Q Q(x x)），），其中，其中，R R(x x)表示表示x x是人；是人；Q Q(x x)表示表示x x活到一百岁以上。活到一百岁以上。一阶逻辑一阶逻辑l公式及其解释公式及其解释l个体常量

4、：个体常量：a,b,cl个体变量：个体变量：x,y,zl谓词符号：谓词符号：P,Q,Rl量词符号：量词符号：,3.2谓词逻辑基础谓词逻辑基础量词否定等值式：量词否定等值式：l(x x ）P P（x x）（y y ）P P（y y）l(x x ）P P（x x）（y y ）P P（y y）量词分配等值式：量词分配等值式：l(x x ）(P P（x x）Q Q（x x）)()(x x ）P P（x x）(x x ）Q Q（x x）l(x x ）(P P（x x）Q Q（x x）)()(x x ）P P（x x）(x x ）Q Q（x x）消去量词等值式：消去量词等值式：设个体域为有穷集合（设个体域

5、为有穷集合（a a1 1,a,a2 2,a,an n）l(x x ）P P（x x）P P（a a1 1 ）P P（a a2 2 ）P P（a an n ）l(x x ）P P（x x）P P（a a1 1 ）P P（a a2 2 ）P P（a an n ）3.2谓词逻辑基础谓词逻辑基础量词辖域收缩与扩张等值式：量词辖域收缩与扩张等值式：l(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Ql(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q l(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q l(x x ）(Q Q

6、 P P（x x）)Q Q (x x ）P P（x x）l(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Ql(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q l(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q l(x x ）(Q Q P P（x x）)Q Q (x x ）P P（x x）3.2谓词逻辑基础谓词逻辑基础3.2谓词逻辑基础谓词逻辑基础SKOLEMSKOLEM标准形标准形l前束范式前束范式定义定义：说公式：说公式A A是一个前束范式，如果是一个前束范式，如果A A中中的一切量词都位于该公式的最左边（不

7、含否的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的定词），且这些量词的辖域都延伸到公式的末端。末端。3.3谓词逻辑归结原理谓词逻辑归结原理即：即：把所有的量词都提到前面去，然后消把所有的量词都提到前面去，然后消掉所有量词掉所有量词(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2)(Q)(Qn nx xn n)M(x)M(x1 1,x,x2 2,x,xn n)约束变项换名规则：约束变项换名规则：l(Qx(Qx ）MM（x x）（QyQy ）MM（y y）l(Qx(Qx ）MM（x,zx,z）（QyQy ）MM（y,zy,z）3.3谓词逻辑归结原理谓词逻辑归结

8、原理 l量词消去原则：量词消去原则：消去存在量词消去存在量词“”，略去全程量词，略去全程量词“”。注意：注意：左边有全程量词的存在量词，消去左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，时该变量改写成为全程量词的函数；如没有，改写成为常量。改写成为常量。3.3谓词逻辑归结原理谓词逻辑归结原理 lSkolemSkolem定理定理：谓词逻辑的任意公式都可以化为与之等价谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。的前束范式，但其前束范式不唯一。lSKOLEMSKOLEM标准形定义：标准形定义：消去量词后的谓词公式。消去量词后的谓词公式。注意注意：谓词公

9、式：谓词公式G G的的SKOLEMSKOLEM标准形同标准形同G G并并不等值不等值。3.3谓词逻辑归结原理谓词逻辑归结原理例：例：将下式化为将下式化为Skolem标准形：标准形：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)l解：第一步，消去解：第一步，消去号，得：号，得：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)l第二步，深入到量词内部，得：第二步，深入到量词内部，得：(x)(y)P(a,x,y)(x)x)(y)Q(y,b)R(x)l第三步，变元易名，得第三步，变元易名，得(x)(y)P(a,x,y)(u)(v)(Q(v,b)R(u)l第第四四步步，存存在在

10、量量词词左左移移，直直至至所所有有的的量量词词移移到到前前面面，(x)(y)(u)(v)(P(a,x,y)(Q(v,b)R(u)由此得到前述范式由此得到前述范式l第第五五步步，消消去去“”（存存在在量量词词），略略去去“”全全称称量词量词l消消去去(y)，因因为为它它左左边边只只有有(x)，所所以以使使用用x的的函函数数f(x)代替之，这样得到：代替之，这样得到：(x)(u)(v)(P(a,x,f(x)Q(v,b)R(u)l消去消去(u)，同理使用，同理使用g(x)代替之，这样得到：代替之，这样得到：(x)(v)(P(a,x,f(x)Q(v,b)R(g(x)l则，略去全称变量，原式的则，略去全

11、称变量，原式的Skolem标准形为：标准形为：P(a,x,f(x)Q(v,b)R(g(x)l子句与子句集子句与子句集l文字：不含任何连接词的谓词公式。文字：不含任何连接词的谓词公式。l子句：一些文字的析取（谓词的和）。子句：一些文字的析取（谓词的和）。l子句集子句集S S的求取：的求取：G G SKOLEM SKOLEM标准形标准形 消去存在变量消去存在变量 以以“，”取代取代“”，并表示为集合形式，并表示为集合形式 。3.3谓词逻辑归结原理谓词逻辑归结原理l G是不可满足的是不可满足的S是不可满足的是不可满足的lG与与S不等价，但在不可满足得意义下是一致的。不等价，但在不可满足得意义下是一致

12、的。l定理：定理：若若G是给定的公式，而是给定的公式，而S是相应的子句集，则是相应的子句集，则G是不是不可满足的可满足的S是不可满足的。是不可满足的。注意注意：G真不一定真不一定S真，而真，而S真必有真必有G真。真。即：即：S=G3.3谓词逻辑归结原理谓词逻辑归结原理lG=GG=G1 1 G G2 2 G G3 3 G Gn n的子句形的子句形lG G的字句集可以分解成几个单独处理。的字句集可以分解成几个单独处理。l有有 S SG G=S=S1 1 U SU S2 2 U S U S3 3 U U S U U Sn n则则S SG G 与与 S S1 1 U U S S2 2 U U S S3

13、 3 U U U U S Sn n在在不不可可满满足足得得意意义义上上是一致的。是一致的。即即S SG G 不可满足不可满足 S S1 1 U SU S2 2 U S U S3 3 U U S U U Sn n不可满足不可满足3.3谓词逻辑归结原理谓词逻辑归结原理例例：对对所所有有的的x,y,z来来说说，如如果果y是是x的的父父亲亲，z又又是是y的的父父亲亲，则则z是是x的的祖祖父父。又又知知每每个个人人都都有有父父亲亲，试试问问对对某某个人来说谁是它的祖父？个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：解：

14、这里我们首先引入谓词：lP(x,y)表示表示x是是y的父亲的父亲lQ(x,y)表示表示x是是y的祖父的祖父lANS(x)表示问题的解答表示问题的解答3.3谓词逻辑归结原理谓词逻辑归结原理对对于于第第一一个个条条件件，“如如果果x是是y的的父父亲亲，y又又是是z的的父父亲亲，则则x是是z的祖父的祖父”，一阶逻辑表达式如下：，一阶逻辑表达式如下：A1：(x)(y)(z)(P(x,y)P(y,z)Q(x,z)SA1：P(x,y)P(y,z)Q(x,z)对于第二个条件：对于第二个条件：“每个人都有父亲每个人都有父亲”，一阶逻辑表达式：，一阶逻辑表达式：A2：(y)(x)P(x,y)SA2：P(f(y)

15、,y)对于结论：某个人是它的祖父对于结论：某个人是它的祖父B：(x)(y)Q(x,y)否定后得到子句：否定后得到子句：（(x)(y)Q(x,y)）ANS(x)SB：Q(x,y)ANS(x)则得到的相应的子句集为：则得到的相应的子句集为：SA1，SA2，SB3.3谓词逻辑归结原理谓词逻辑归结原理l归结原理正确性的根本在于，找到矛盾归结原理正确性的根本在于，找到矛盾可以肯定不真。可以肯定不真。l方法：方法：l和命题逻辑一样。和命题逻辑一样。l但由于有函数，所以要考虑但由于有函数，所以要考虑合一合一和和置换置换。3.3谓词逻辑归结原理谓词逻辑归结原理l置置换换：可可以以简简单单的的理理解解为为是是在

16、在一一个个谓谓词词公公式式中中用用置置换换项项去去置置换换变变量。量。l定义：定义：置置换换是是形形如如t1/x1,t2/x2,tn/xn的的有有限限集集合合。其其中中，x1,x2,xn是是互互不不相相同同的的变变量量，t1,t2,tn是是不不同同于于xi的的项项（常常量量、变变量量、函函数数）；ti/xi表表示示用用ti置置换换xi，并并且且要要求求ti与与xi不不能能相相同同，而而且且xi不能循环地出现在另一个不能循环地出现在另一个ti中。中。例如例如a/x，c/y，f(b)/z是一个置换。是一个置换。g(y)/x，f(x)/y不是一个置换，不是一个置换，3.3谓词逻辑归结原理谓词逻辑归结

17、原理置换置换置换的合成置换的合成l设设 t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,un/yn，是两个置换。，是两个置换。则则 与与 的合成也是一个置换，记作的合成也是一个置换，记作 。它是从集合。它是从集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn中删去以下两种元素：中删去以下两种元素：li.当当ti=xi时，删去时，删去ti/xi(i=1,2,n);lIi.当当yi x1,x2,xn时时，删删去去uj/yj(j=1,2,m)最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。合成即是对合成即是对ti先做先做 置换然后再做置换然后再做 置换，置

18、换置换，置换xi3.3谓词逻辑归结原理谓词逻辑归结原理l例：例：设：设：f(y)/x,z/y，a/x,b/y,y/z，求，求 与与 的合成。的合成。解：先求出集合解：先求出集合f(b/y)/x,(y/z)/y,a/x,b/y,y/zf(b)/x,y/y,a/x,b/y,y/z其其中中，f(b)/x中中的的f(b)是是置置换换 作作用用于于f(y)的的结结果果；y/y中中的的y是是置置换换 作作用用于于z的的结结果果。在在该该集集合合中中，y/y满满足足定定义义中中的的条条件件i，需需要要删删除除；a/x，b/y满满足足定定义义中中的的条条件件ii，也也需需要要删删除除。最后得最后得 f(b)/

19、x，y/z3.3谓词逻辑归结原理谓词逻辑归结原理合一合一l合合一一可可以以简简单单地地理理解解为为“寻寻找找相相对对变变量量的的置置换换，使使两两个个谓谓词词公式一致公式一致”。l定定义义：设设有有公公式式集集FF1，F2，Fn，若若存存在在一一个个置置换换，可可使使F1 F2=Fn，则则称称 是是F的的一一个个合合一一。同同时时称称F1，F2，.，Fn是可合一的。是可合一的。l例：例：设设有有公公式式集集FP(x,y,f(y),P(a,g(x),z)，则则 a/x,g(a)/y,f(g(a)/z是它的一个合一。是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。注意：一般说来，一个公

20、式集的合一不是唯一的。3.3谓词逻辑归结原理谓词逻辑归结原理3.3谓词逻辑归结原理谓词逻辑归结原理3.3谓词逻辑归结原理谓词逻辑归结原理3.3谓词逻辑归结原理谓词逻辑归结原理归结原理归结原理l归结的注意事项：归结的注意事项：1.1.谓词的一致谓词的一致性性，P()P()与与Q()Q()，不可以不可以2.2.常量的一致性常量的一致性，P(a,)P(a,)与与P(b,.)P(b,.)，不可以不可以 变量变量，P(a,.)P(a,.)与与P(x,)P(x,)，可以可以3.3.变量与函数变量与函数，P(a,x,.)P(a,x,.)与与P(x,f(x),)P(x,f(x),)，不可不可以；以；1.1.是

21、不能同时消去两个互补对是不能同时消去两个互补对，PQPQ与与PPQ Q的空，的空，不可以不可以2.2.先进行内部简化（置换、合并）先进行内部简化（置换、合并）3.3谓词逻辑归结原理谓词逻辑归结原理l归结的过程归结的过程写出谓词关系公式写出谓词关系公式 用反演法写出谓词表达式用反演法写出谓词表达式 SKOLEMSKOLEM标准形标准形 子句集子句集S S 对对S S中可归结的子句做归结中可归结的子句做归结 归结式仍放入归结式仍放入S S中，反复归结过程中，反复归结过程 得到空子句得到空子句 得证得证3.3谓词逻辑归结原理谓词逻辑归结原理例题例题“快乐学生快乐学生”问题问题l假假设设任任何何通通过

22、过计计算算机机考考试试并并获获奖奖的的人人都都是是快快乐乐的的，任任何何肯肯学学习习或或幸幸运运的的人人都都可可以以通通过过所所有有的的考考试试，张张不不肯肯学学习习但但他他是是幸幸运运的的，任任何何幸幸运运的的人人都都能能获获奖奖。求求证证：张是快乐的。张是快乐的。l解：先将问题用谓词表示如下：解：先将问题用谓词表示如下：lR1:“任何通过计算机考试并获奖的人都是快乐的任何通过计算机考试并获奖的人都是快乐的”(x)(Pass(x,computer)Win(x,prize)Happy(x)lR2:“任何肯学习或幸运的人都可以通过所有考试任何肯学习或幸运的人都可以通过所有考试”(x)(y)(St

23、udy(x)Lucky(x)Pass(x,y)lR3:“张不肯学习但他是幸运的张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)lR4:“任何幸运的人都能获奖任何幸运的人都能获奖”(x)(Luck(x)Win(x,prize)l结论：结论：“张是快乐的张是快乐的”的否定的否定Happy(zhang)例题例题“快乐学生快乐学生”问题问题l由由R1及逻辑转换公式及逻辑转换公式:PWH=（PW）H，可得，可得l(1)Pass(x,computer)Win(x,prize)Happy(x)l由由R2：(2)Study(y)Pass(y,z)l(3)Lucky(u)Pass(u,v

24、)l由由R3：(4)Study(zhang)l(5)Lucky(zhang)l由由R4：(6)Lucky(w)Win(w，prize)l由结论：由结论：(7)Happy(zhang)（结论的否定）（结论的否定）l(8)Pass(w,computer)Happy(w)Luck(w)(1)(6)，w/xl(9)Pass(zhang,computer)Lucky(zhang)(8)(7)，zhang/wl(10)Pass(zhang,computer)(9)(5)l(11)Lucky(zhang)(10)(3)，zhang/u,computer/vl(12)(11)(5)l归结法的实质：归结法的实质

25、：l归结法是仅有一条推理规则的推理方法。归结法是仅有一条推理规则的推理方法。l归结的过程是一个语义树倒塌的过程。归结的过程是一个语义树倒塌的过程。l归结法的问题归结法的问题l子句中有等号或不等号时，完备性不成立。子句中有等号或不等号时，完备性不成立。Herbrand Herbrand定理的不实用性引出了可实用的定理的不实用性引出了可实用的归结法。归结法。3.3谓词逻辑归结原理谓词逻辑归结原理归结过程的控制策略归结过程的控制策略l要解决的问题：要解决的问题：l归结方法的知识爆炸。归结方法的知识爆炸。l控制策略的目的控制策略的目的l归结点尽量少归结点尽量少l控制策略的原则控制策略的原则l给给出出控

26、控制制策策略略，以以使使仅仅对对选选择择合合适适的的子子句句间间方方可可做做归归结结。避避免免多多余余的的、不不必必要要的的归归结结式式出出现现。或或者者说说，少少做做些些归归结结仍仍能能导导出出空子句。空子句。3.3谓词逻辑归结原理谓词逻辑归结原理删除策略删除策略=完备完备l名名词词解解释释：归归类类：设设有有两两个个子子句句C C和和D D，若若有有置置换换 使使得得C C D D成立，则称子句成立，则称子句C C把子句把子句D D归类。归类。由于小的可以代表大的，所以小的吃掉大的了。由于小的可以代表大的，所以小的吃掉大的了。l若若对对S S使使用用归归结结推推理理过过程程中中，当当归归结

27、结式式C Cj j是是重重言言式式（永永真真式式）和和C Cj j被被S S中中子子句句和和子子句句集集的的归归结结式式C Ci i(ij)(ij)所所归归类类时时，便便将将C Cj j删删除除。这这样样的的推推理理过过程程便便称做使用了删除策略的归结过程。称做使用了删除策略的归结过程。3.3谓词逻辑归结原理谓词逻辑归结原理l主主要要思思想想：归归结结过过程程在在寻寻找找可可归归结结子子句句时时，子子句句集集中中的的子子句句越越多多，需需要要付付出出的的代代价价就就会会越越大大。如如果果在在归归结结时时能能把把子子句句集集中中无无用用的的子子句句删删除除掉掉，就就会会缩缩小小搜搜索索范范围围，

28、减减少少比比较较次次数数，从从而而提提高高归归结结效效率率。删删除除策策略略对对阻阻止止不不必必要要的的归归结结式式的的产产生生来来缩缩短短归归结结过过程程是是有有效效的的。然然而而要要在在归归结结式式C Cj j产产生生后后方方能能判判别别它它是是否否可可被被删删除除，这这部部分分计计算算量量是是要要花花费费的的，只只是是节节省省了了被被删删除除的的子子句句又又生生成成的的归归结结式式。尽尽管管使使用用删删除除策策略略的的归归结结，少少做做了了归归结结但但不不影影响响产产生生空空子子句句，就就是是说说删删除除策略的归结推理是完备的。策略的归结推理是完备的。3.3谓词逻辑归结原理谓词逻辑归结原

29、理采用支撑集采用支撑集 完备完备 支支撑撑集集：设设有有不不可可满满足足子子句句集集S S的的子子集集T T，如如果果S-TS-T是可满足的，则是可满足的，则T T是支持集。是支持集。采采用用支支撑撑集集策策略略时时，从从开开始始到到得得到到 的的整整个个归归结结过过程程中中，只只选选取取不不同同时时属属于于S-TS-T的的子子句句，在在其其间间进进行行归归结结。就就是是说说，至至少少有有一一个个子子句句来自于支撑集来自于支撑集T T或由或由T T导出的归结式。导出的归结式。3.3谓词逻辑归结原理谓词逻辑归结原理例例如如：A A1 1AA2 2AA3 3B B中中的的B B可可以以作作为为支支

30、撑撑集集使使用用。要要求求每每一一次次参参加加归归结结的的亲亲本本子子句句中中，只只要要应应该该有有一一个个是是有有目标公式的否定（目标公式的否定（B B）所得到的子句或者它们的后裔。）所得到的子句或者它们的后裔。l支撑集策略的归结是完备的，同样，所有可归结的谓词支撑集策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用支撑集策略达到加快归结速度的目的。公式都可以用采用支撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最容易找到的支撑问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非，即集是目标子句的非，即S SB B。3.3谓词逻辑归结原理谓词逻辑归结原理

31、ST可满足支撑集示意图3.3谓词逻辑归结原理谓词逻辑归结原理 语义归结语义归结 完备完备 语语义义归归结结策策略略是是将将子子句句S S按按照照一一定定的的语语义义分分成成两两部部分分，约约定定每每部部分分内内的的子子句句间间不不允允许许作作归归结结。同同时时还还引引入入了了文文字字次次序序，约约定定归归结结时时其其中中的的一一个个子子句句的的被被归归结结文文字字只只能能是是该该子子句中句中“最大最大”的文字。的文字。语义归结策略的归结是完备的，同样，语义归结策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用语义归所有可归结的谓词公式都可以用采用语义归结策略达到加快归结速度的目的。问题

32、是如结策略达到加快归结速度的目的。问题是如何寻找合适的语义分类方法，并根据其含义何寻找合适的语义分类方法，并根据其含义将子句集两个部分中的子句进行排序。将子句集两个部分中的子句进行排序。3.3谓词逻辑归结原理谓词逻辑归结原理线性归结线性归结 完备完备 线性归结策略首先从子句集中选取一个称作顶子线性归结策略首先从子句集中选取一个称作顶子句的子句句的子句C C0 0开始作归结。归结过程中所得到的归结开始作归结。归结过程中所得到的归结式式C Ci i立即同另一子句立即同另一子句B Bi i进行归结得归结式进行归结得归结式C Ci+1i+1。而。而B Bi i属于属于S S或是已出现的归结式或是已出现

33、的归结式C Cj j(ji)(j=完备完备 单单元元归归结结策策略略要要求求在在归归结结过过程程中中，每每次次归归结结都都有有一一个个子子句句是是单单元元子子句句（只只含含一一个个文文字字的的子子句句）或或单单元元因因子子。显显而而易易见见，词词中中方方法法可可以以简简单单地地削削去去另另一一个个非非单单子子句句中中的的一一个个因因子子，使使其其长长度度减减少少，构成简单化，归结效率较高。构成简单化，归结效率较高。初始子句集中没有单元子句时，单元归结策略初始子句集中没有单元子句时，单元归结策略无效。所以说无效。所以说“反之不成立反之不成立”，即此问题不能采，即此问题不能采用单元归结策略用单元归

34、结策略。3.3谓词逻辑归结原理谓词逻辑归结原理输入归结输入归结 =完备完备 与与单单元元归归结结策策略略相相似似，输输入入归归结结策策略略要要求求在在归归结结过过程程中中，每每一一次次归归结结的的两两个个子子句句中中必必须须有有一一个个是是S S的的原原始始子子句句。这这样样可可以以避避免免归归结结出出的的不不必必要要的的新新子子句句加加入入归归结结，造造成成恶恶性性循循环环。可可以以减减少少不不必必要要的的归归结结次数。次数。3.3谓词逻辑归结原理谓词逻辑归结原理如同单元归结策略，不是所有的可归结谓如同单元归结策略，不是所有的可归结谓词公式的最后结论都是可以从原始子句集词公式的最后结论都是可以从原始子句集中的得到的。简单的例子，归结结束时，中的得到的。简单的例子，归结结束时，即最后一个归结式为空子句的条件是，参即最后一个归结式为空子句的条件是，参加归结的双方必须是两个单元子句。原始加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式一定不子句集中没有单元子句的谓词公式一定不能采用输入归结策略。能采用输入归结策略。3.3谓词逻辑归结原理谓词逻辑归结原理