下载掌阅APP，畅读海量书库
立即打开
从命题逻辑和谓词逻辑的归结方法中可以看出，当使用归结法时，若从子句集S出发做所有可能的归结，并将归结式加入子句集S中，再做第二层这样的归结，直到产生空子句为止。这种无控制的、盲目全面归结导致大量不必要的归结式的产生，无疑会产生组合爆炸问题。更为严重的是，它们又将产生下一层的更大量的不必要的归结式。于是，如何给出控制策略，以使系统仅选择合适的子句对其做归结来避免多余不必要的归结式的出现，或者说，少做一些归结但仍然导出空子句，进而提高归结效率已成为一个重要问题。
归纳起来，归结过程控制策略的要点有：
①要解决的问题是归结方法的知识爆炸；
②控制策略的目的是归结点尽量少；
③控制策略的原则是删除不必要的子句，或对参加归结的子句加以限制；
④给出控制策略，以仅选择合适的子句对其做归结，避免多余的、不必要的归结式出现。
归类：设有两个子句C和D，若有置换σ，使得Cσ⊂D成立，则称子句C把子句D归类。
例如，C =P（x），D=P（a）∨Q（y）归类。
取σ= {a /x}，便有Cσ=P（a）⊂{P（a），Q（y）}，而{P（a），Q（y）}的逻辑表达式是D =P（a）∨Q（y），C与D是两个子句，它们的关系是“与”的关系，即C，D中有一个为假，则整个谓词公式为假。当P（a）为真时，C与D都为真，C可以代表D；当P（a）为假时，虽然D的真值由Q（y）决定，但是，因为整个谓词公式的真值已经被确定了，所以讨论Q（y）的真假已无意义。可以认为，由于C经过置换可以成为D的一部分，因此可以代表D。也可以简单地理解为，由于小的可以代表大的，因此小的吃掉了大的。
删除策略在归结过程中可以随时删除以下子句：
①含有永真式的子句；
②被子句集中其他子句归类的子句。
对S使用归结推理过程，当归结式C j 是重言式，且C j 被S中子句和子句集的归结式C i （i<j）所归类时，便将C j 删除。这样的推理过程称作使用了删除策略的归结过程。
删除策略的主要想法是在归结过程中寻找可归结子句时，子句集中的子句越多，需要付出的代价就越大。如果在归结时能把子句集中无用的子句删除，则会缩小搜索范围，减少比较次数从而提高归结效率。删除策略有效地阻止了不必要的归结式的产生，从而缩短归结过程，然而要在归结式C j 产生后方能判别它是否可被删除，这部分计算量是要花费的，只是节省了被删除的子句又生成的归结式。尽管使用删除策略的归结，但不影响产生空子句，也就是说，删除策略的归结推理是完备的，即采用归结策略进行的归结过程没有破坏归结法的完备性。
由于删除策略的完备性，可以放心大胆地使用该方法提高归结的效率。然而并不是所有可以归结的谓词公式都能采用删除策略来处理，达到加快归结速度的目的。例如，当一个谓词公式中没有可删除的子句，那么在该公式中就无法使用删除策略。因此，完备的归结推理采用删除策略不一定都有效。
支撑集的定义是：设有不可满足子句集S的子集T，如果S-T是可满足的，则称T是S的支撑集。
采用支撑集策略时，从开始到得到空子句的整个归结过程中，只选取不同时属于S-T的子句对，在其间进行归结。也就是说，至少有一个子句来自支撑集T或由T导出的归结式。
例如，A 1 ∧A 2 ∧A 3 ∧¬B中的¬B可以作为支撑集使用。要求每一次参加归结的亲本子句中，应该有一个是由目标公式的否定所得到的子句或者它们的后裔。
这种策略的思想就是尽量避免在可满足的子句集中进行归结，由于从中推导不出空子句。而求证公式的前提通常是已知的，因此支撑集策略一般是以目标公式的否定的子句作为支撑集，由此出发进行归结，也可以将支撑集策略理解为目标指导的反向推力。
例如，S = {P∨Q，¬P∨R，¬Q∨R，¬R}
取T = {¬R}
支撑集归结过程通常为：
这是采用支撑集策略的全面归结过程。可以证明支撑集策略的归结是完备的，即采用归结策略进行归结过程没有破坏归结法的完备性。同时，任意的完备谓词归结过程都可以采用支撑集策略达到加快归结速度的目的。
对任意的归结可以放心大胆地运用支撑集策略，问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非。
语义归结策略是将子句S按照一定的语义分成两个部分，约定每部分内的子句间不允许进行归结。还引入了文字次序，约定归结时，其中一个子句的被归结文字只能是该子句中“最大”的文字。
例如，S = {¬P∨¬Q∨R，P∨R，Q∨R，¬R}，它首先规定S中出现的文字次序，如依次为P，Q，R，或记作P>Q>R。再选出S的一个解释I，令
用这个解释将S分为两个部分。规定在I下为假的子句放在S 1 中，在I下为真的子句放在S 2 中，于是有
规定S i 内部的子句间不允许进行归结，同时S 1 与S 2 子句间的归结必须是S 1 中的最大文字才可进行。这样所得的归结式，仍按照I放入S 1 或S 2 。
归结过程为：
上例采用了语义归结策略下的盲目归结过程，明显减少了归结的次数，阻止了①和④的归结，也阻止了②和④的归结。
可以证明与支撑集策略一样，语义归结策略的归结也是完备的。同样，所有可归结的谓词公式都可以使用语义归结策略达到加快归结速度的目的。问题是如何寻找合适的语义分类方法，并根据其含义将子句集两个部分中的子句进行适当的排序。
线性归结策略首先从子句集中选取一个称为顶子句的子句C 0 开始进行归结。归结过程中所得的归结式C 1 立即同另一个子句B i 进行归结，得归结式C i+1 ，而B i 属于S或已出现的归结式C j （j<i）。通过归结得到的新子句。简言之，每次归结得到的新子句立即参加归结，而后再加入子句集等待再次参加归结，如图 3.8 所示。
图 3.8 线性归结策略示意图
如同支撑集策略和语义归结策略一样，可以证明，线性归结策略没有破坏归结原理的基本完备性，同时，任意可归结的谓词公式集都可以采用线性归结策略提高归结效率，从而达到加快归结速度的目的。
最重要的是，如果能找到一个较好的顶子句，那么就可以使归结顺利进行；否则，归结还可能走很长的弯路。
单元归结策略要求在归结过程中，每次归结都有一个子句是单元子句，即只含一个文字的子句或单元因子。显而易见，此种方法可以简单地削去另一个非单元子句中的一个因子，使其长度减少，趋向简单化，因此归结效率较高。同样，单元归结策略保持了归结原理的基本完备性，但并不是所有可以归结的谓词公式集合都可以采用单元归结策略进行归结。显然当初始子句集中没有单元子句时，单元归结策略无效。
与单元归结策略相似，输入归结策略要求在归结过程中，每一次归结的两个子句中必须有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结而造成的恶性循环，可以减少不必要的归结次数。同样，输入归结策略保持了归结原理的基本完备性，但并不是所有可归结的谓词公式集合都可以采用输入归结策略进行归结。
如同单元归结策略一样，不是所有的可归结谓词公式的最后结论都是可以从原始子句集中得到的。简单的例子是归结结束时，最后一个归结式为空子句的条件是参加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式集合一定不能采用输入归结策略。
1.什么是推理、正向推理、逆向推理、混合推理？试列出常用的几种推理方式并列出每种推理方式的特点。
2.什么是冲突？在产生式系统中解决冲突的策略有哪些？
3.什么是子句，什么是子句集？请写出求谓词公式子句集的步骤。
4.为什么要引入Herbrand理论？什么是H域？如何求子句集的H域？
5.什么是归结策略，归结策略的目的是什么？
6.将下列谓词公式化成子句集
（1）（（（P∨¬Q）→R）→（P∧R））；
（2）（∀x）{P（x）→（∀y）[P（y）→P（f（x，y））]∧¬（∀y）[Q（x，y）→P（y）]}。
7.假设：所有不贫穷且聪明的人都快乐。那些看书的人是聪明的。李明能看书且不贫穷。快乐的人过着激动人心的生活。
求证：李明过着激动人心的生活。
8.已知：能够阅读的都是有文化的。海豚是没有文化的。某些海豚是有智能的。
求证：某些有智能的并不能阅读。
9.已知：如果x与y是同班同学，则x的老师也是y的老师。王先生是小李的老师。小李和小张是同班同学。
问：小张的老师是谁？
10.设A，B，C 3 人中有人从不说真话，也有人从不说假话，某人向这 3 人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”;B答：“A和C都是说谎者”;C答：“A和B至少有一个是说谎者。”求谁是老实人，谁是说谎者？
习题答案