子   句

 1、子句的定义：

    由文字的析取组成的公式称为子句。

 2、重要概念

  变量标准化：即使每个量词采用不同的变量。根据量词的性质 "(x)P(x)º"(y)P(y)和         "(x)P(x)º"(y)P(y),公式中的约束变量可以用其它变量符号代替，而不影响公式的真值。

      Skolem化：考虑一个合式公式　，即对所有的y，总存在一个x使P(x)为真。显然， 这里的变量x的取值依赖于变量y的取值。因此可以把x记为g(y)，这个函数称 为   Skolem函数，用Skolem函数代替每个存在量词量化的变量的过程称为Skolem化。注意，这里的函数g应是原合式公式中没有的符号。因此有

            ("y)[($x)P(x,y)®("y)P(g(y),y)

       常量化：如果该存在量词不在任何一个全称量词的辖域中，则该存在量词就不    依赖于任何其它的变量，因此可以用一个常量代替，该常量应是原合式公式中没有   的符号，这称为常量化。因此有($x)P(x)®P(A)

       前束形：就是把所有的全称量词都移到公式的前部，由于公式中已无存在量词，   且所有的全称量词的约束变量完全不同，因此可  以把所有的全称量词放在公式前  面，是每个量词的辖域都包括公式后面的整个部分。前束形的公式就由全称量词串   组成的前缀和称为母式的无量词公式组成。

    合取范式：就是子句的合取式，可以反复应用合式公式的分配律实现从任一母式向合取范式的转换：

      X1∨(X2∧X3)≡(X1∨X2)∧(X1∨X3)

      (X1∧X2)∨(X1∧X3)≡X1∧(X2∨X3)

   3、由于归结方法必须应用于子句形式，因此我们首先介绍任一个谓词演算公式

如何化为一个子句集。

    设有一个谓词演算公式

      ("x){[ØP(x)ÚØQ(x)®($y)[S(x,y)ÙQ(x)]}Ù("x)[P(x)Úb(x)]

转化成子句的过程如下：

　（１）消去蕴含符号，办法是应用性质X1ÞX2ºØX1ÚX2。上例变成

　　("x){Ø[ØP(x)ÚØQ(x)Ú($y)[S(x,y)ÙQ(x)]}Ù("x)[P(x)Úb(x)]

　（２）把否定符号Ø移到每个谓词符号的前面，办法是应用第三章知识表示叙

述的摩根定律及其他等价关系。上例公式可写成

        ("x){[P(x)ÙQ(x)Ú($y)[S(x,y)ÙQ(x)]}Ù("x)[P(x)Úb(x)]

  （３）变量标准化，得到

     ("x){[P(x)ÙQ(x)Ú($y)[S(x,y)ÙQ(x)]}Ù("w)[P(w)Úb(w)]

   （４）消去存在量词。采取两种方法：Skolem化和常量化方法。根据以上所述，   将上例Skolem化的结果为

   ("x){[P(x)ÙQ(x)Ú[S(x,f(x))ÙQ(x)]}Ù("w)[P(w)Úb(w)]

              下接