2.3  谓词逻辑约束公式的等价与蕴涵

2.3.1  谓词逻辑的等价公式 

     定义2.7   设A、B是命题逻辑中的任意两个公式，设它们有共同的个体域E，若对任意的解释I都有TI（A）= TI（B），则称公式A、B在E上是等价的，记作AB。 

   定理1   设A（x）是谓词公式，有关量词否定的两个等价公式：

（1）﹁x A（x）x﹁A（x）

（2）﹁x A（x）x﹁A（x）

   证明  （1）设个体域是有限的为：D={ a1，a2，…，an}，则有

﹁x A（x）﹁（A（a1）∧A（a2）∧…∧A（an））

﹁A（a1）∨﹁A（a2）∨…∨﹁A（an））

     x﹁A（x）

（2）设个体域是有限的为：D={ a1，a2，…，an}，则有

    ﹁x A（x）﹁（A（a1）∨ A（a2）∨…∨A（an））

       ﹁A（a1）∧ ﹁A（a2）∧…∧﹁A（an）

x﹁A（x）

定理2   设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有

（1）x（A（x）∨B）x A（x）∨B

（2）x（A（x）∧B）x A（x）∧B

（3）x（A（x）→ B）x A（x）→ B

（4）x（B→A（x））B→ x A（x）

（5）x（A（x）∨B） x A（x）∨B

（6）x（A（x）∧B）x A（x）∧B

（7）x（A（x）→ B）x A（x）→ B

（8）x（B→A（x））B→x A（x）

证明  （1）设D是个体域，I为任意解释，即用确定的命题及确定的个体代替出现在x（A（x）∨B）和x A（x）∨B中的命题变元和个体变元，于是得到两个命题，若对x（A（x）∨B）代替之后所得命题的真值为真，此时必有A（x）∨B的真值为真；因而A（x）真值为真或B的真值为真，若B的真值为真，则x A（x）∨B的真值为真；若B的真值为假，则必有对D中任意x都使得A（x）的真值为真，所以x（A（x）∨B）为真，从而x A（x）∨B为真。若对x（A（x）∨B）代替之后所得命题的真值为假，则A（x）和B的真值必为假，因此x A（x）∨B的真值为假；所以x（A（x）∨B）为假，有x A（x）∨B为假。

（2）、（5）和（6）证明与（1）类似，证明过程略。

（3）x（A（x）→ B）x（A（x）∨B）

                      xA（x）∨ B

                      x A（x）∨B

                      x A（x）→ B

（4）、（7）、（8）证明与（3）类似，证明过程略。 

   定理3   设A（x）、B（x）是任意包含自由出现个体变元x的公式,则有：

（1）x（A（x）∧B（x））x A（x）∧x B（x）

（2）x（A（x）∨B（x））x A（x）∨x B（x）

  证明  （1）设D是任一个体域，若x（A（x）∧B（x））的真值为真，则对任意aD，有A（a）和B（a）同时为真，即x A（x）为真、x B（x）为真，从而x A（x）∧x B（x）为真。若x（A（x）∧B（x））的真值为假，则对任意aD，有A（a）和B（a）不能同时为真，即x A（x）和 x B（x）的真值不能同时为真，从而x A（x）∧x B（x）的真值为假。

综上所述 x（A（x）∧B（x））x A（x）∧x B（x）

       （2）设D是任一个体域，若x（A（x）∨B（x））的真值为真,则存在aD，使得A（a）∨B（a）为真，即A（a）为真或B（a）为真，即x A（x）为真或x B（x）为真，从而x A（x）∨x B（x）为真。若x（A（x）∨B（x））的真值为假，则存在aD，使得A（a）∨B（a）为假，此时，A（a）为假，B（a）为假，从而x A（x）∨x B（x）的真值为假。

综上所述 x（A（x）∨B（x））x A（x）∨x B（x）

  例2.11  证明下列各等价式

（1）﹁x（A（x）∧B（x））x（A（x）→﹁B（x））

（2）﹁x（A（x）→ B（x））x（A（x）∧﹁B（x））

证明  （1）﹁x（A（x）∧B（x））

        x ﹁（A（x）∧B（x））

        x（﹁A（x）∨﹁B（x））

         x（A（x）→﹁B（x））

     （2）﹁x（A（x）→ B（x））

        x ﹁（A（x）→ B（x））

        x ﹁（﹁A（x）∨B（x））

        x（A（x）∧﹁B（x））

   2.3.2   谓词逻辑的蕴涵公式

   定义2.8   设A、B是命题逻辑中的任意两个公式，若A→B是永真式，则称公式A蕴涵公式B，记作AB。

   定理4   下列蕴涵式成立

（1）x A（x）∨x B（x）x（A（x）∨B（x））

（2）x（A（x）∧B（x））x A（x）∧x B（x）

（3）x（A（x）→ B（x））x A（x）→ x B（x）

（4）x（A（x）→ B（x））x A（x）→ x B（x）

（5）x A（x）→ x B（x）x（A（x）→ B（x））

  证明：  

（1）设x A（x）∨x B（x）在任意解释下的真值为真，即对个体域中的每一个x。都能使A（x）的真值为真或者对个体域中的每一个x都能使B（x）的真值为真，无论哪种情况，对于个体域中的每一个x都能使A（x）∨B（x）的真值为真。因此，蕴涵式x A（x）∨x B（x）x（A（x）∨B（x））成立。 

（2）设个体域为D，在解释I下x（A（x）∧B（x））的真值为真，即存在aD使得A（a）∧B（a）为真，从而A（a）为真，B（a）为真，故有x A（x）、x B（x）均为真，所以，蕴涵式x（A（x）∧B（x））x A（x）∧x B（x）成立。

（3）设个体域为D，在解释I下x A（x）→ x B（x）的真值为假,即存在aD使得A（a）→ B（a）为假，所以蕴涵式x（A（x）→ B（x））x A（x）→ x B（x）成立。

（4）x（A（x）→ B（x））→（x A（x）→ x B（x））

     ﹁x（A（x）→ B（x））∨（x A（x）→ x B（x））

     ﹁x（A（x）→ B（x））∨（﹁x A（x）∨x B（x））

     ﹁x（A（x）→ B（x））∨﹁x A（x）∨x B（x）

     ﹁（x（A（x）→ B（x））∧x A（x））∨x B（x）

     （x（A（x）→ B（x））∧x A（x））→x B（x）

（5）x A（x）→ x B（x）x A（x）∨x B（x）

                           x A（x）∨x B（x）

                           x（A（x）∨B（x））

                           x（A（x）→ B（x））

   2.3.3   多个量词的使用 

  定义2.9   设谓词公式G，不包含联结词→，↔。把G中出现的联结词，互换；命题常量T，F互换；量词，互换之后得到的公式称为G的对偶公式，记作G*。 

   定理5（对偶定理）   设A、B是任意两个公式并且不包含联结词→，↔。若AB，则A*B*。

2.4   前束范式

   定义2.10   一个谓词公式，如果量词均在全式的开头，且辖域延伸到公式的末尾，则该公式称为前束范式。

   定理6   对任意一个谓词公式都可以化为与它等价的前束范式。

证明  首先利用等价公式将谓词公式中的联结词→，↔去掉。其次利用量词的转化律将量词前面的否定深入到谓词前面，在利用改名和代入规则以及量词辖域扩张的公式将量词移到全式的最前面，这样便得到前束范式。

   例2.12  求下列谓词公式的前束范式。

（1）x y（z A（x，z）∧A（x，z））→t B（x，y，t）

解  （1）x y（z A（x，z）∧A（x，z））→ t B（x，y，t）

     ﹁x y（z A（x，z）∧A（x，z））∨t B（x，y，t）

     x y（z﹁A（x，z）∨﹁A（x，z））∨t B（x，y，t）                                                                        （量词转化）

     x y（w﹁A（x，w）∨﹁A（x，z））∨t B（u，v，t）                                                                              （改名及代入规则）

     x y w t（﹁A（x，w）∨﹁A（x，z）∨B（u，v，t））

（量词辖域扩张）

（2）﹁x（y P（x，y）→ x y（Q（x，y）∧y（P（y，x）→Q（x，y）））） 

解  （2）﹁x（y P（x，y）→ x y（Q（x，y）∧y（P（y，x）→Q（x，y））））

  ﹁x（﹁y P（x，y）∨x y（Q（x，y）∧y（P（y，x）→Q（x，y））））

  x（y P（x，y）∧xy（﹁Q（x，y）∨y（P（y，x）∧﹁ Q（x，y））））

                                               （量词转化、德·摩根定律）

  x（y P（x，y）∧x y（﹁Q（x，y）∨z（P（z，x）∧﹁Q（x，z））））                                       （改名原则）

x（y P（x，y）∧x y z（﹁Q（x，y）∨（P（z，x）∧﹁Q（x，z））））                                （量词辖域扩张）

 x（y P（x，y）∧u v z（﹁Q（u，v）∨（P（z，u）∧﹁Q（u，z））））                                        （改名原则）

x y u v z （P（x，y）∧（ Q（u，v）∨（P（z，u）∧﹁Q（u，z））））                                                 （量词辖域扩张） 

   定义2.11   若一个谓词公式，具有如下形式，则称该公式为前束析取范式。 

   定义2.12   若一个谓词公式，具有如下形式，则称该公式为前束合取范式。 

   定理7   任意谓词公式都可以化为与其等价的前束析取范式和前束合取范式。

2.5   谓词演算的推理理论

   1．全称指定规则（简称US规则） 

这条规则有下面两种形式：

(1)x P（x）P（y）

(2)x P（x）P（c）

其中，P是谓词，（1）中y为任意不在P（x）中约束出现的个体变元；（2）中c为个体域中的任意一个个体常元。

   2．存在指定规则（简称ES规则）

                  x P（x）P（c）

其中，c为个体域中使P成立的特定个体常元。必须注意，应用存在指定规则，其指定的个体c不是任意的。

   3．全称推广规则（简称UG规则）

                   P（y）x P（x） 

   4．存在推广规则（简称EG规则）

P（c）x P（x）

其中，c为个体域中的个体常元，这个规则比较明显，对于某些个体c，若P（c）成立，则个体域中必有x P（x）。

   例2.13  证明 x（M（x）→ D（x））∧M（s）D（s）这是著名的苏格拉底三段论的论证。

其中     M（x）：x是一个人。

         D（x）：x是要死的。

         s：苏格拉底。

证明  （1）x（M（x）→ D（x））                P

      （2）M（s）→ D（s）                    US（1）

      （3）M（s）                             P

      （4）D（s）                            T（2）（3）I

   例 2.14  判断下列的推理过程是否正确。

      （1）x y G（x，y）                     P

      （2）y G（z，y）                        US（1）

      （3）G（z，c）                           ES（2）

      （4）x G（x，c）                        UG（3）

      （5）y x G（x，y）                     EG（4）

   解  这个推理过程是错误的，因为从它可以得出结论：

                x y G（x，y）y x G（x，y）

从前面的学习中我们知道这个式子不成立。它的推导错误出现在第（3）步。x y G（x，y）的含义是：对于任意的一个x，存在着与它对应的y，使得G（x，y）成立。但是，对y G（z，y）利用ES规则消去存在变量后得到G（z，c）的含义却是：对于任意个体z，有同一个体c，使得G（z，c）成立。显然，G（z，c）不是y G（z，y）的有效结论。因此，使用ES规则x P（x）P（c）消去存在量词的条件是:P（x）中除x外没有其他自由出现的个体变元。

   例2.15  证明：x（C（x）→（W（x）∧R（x）））∧x C（x）∧Q（x）

x Q（x）∧x Q（x）

证明  （1）x C（x）                             P

      （2）C（y）                                ES（1）

      （3）x（C（x）→（W（x）∧R（x）））      P

      （4）C（y）→（W（y）∧R（y））            US（3）

      （5）W（y）∧R（y）                       T（2）（4）I

      （6）R（y）                                T（5）I

      （7）x R（x）                             EG（6）

      （8）Q（x）                                P

      （9）x Q（x）                             EG（8）

      （10）x Q（x）∧x Q（x）                T（7）（9）I

   例2.16  证明：x（A（x）∨B（x））x A（x）∨x B（x）

证明   （1）x（A（x）∨B（x））                    P

      （2）A（y）∨B（y）                        US（1）

      （3）x（A（x）∨B（x））                  EG（2）

      （4）x A（x）∨x B（x）                 T（3）E

   例2.17  给定前提： 

x（P（x）∧y（Q（y）→ R（x，y）））

x（P（x）→y（S（y）→﹁R（x，y）））

证明下列结论： 

x（Q（x）→﹁S（x））

   证明： 

  （1）x（P（x）∧y（Q（y）→ R（x，y）））      P

  （2）P（a）∧y（Q（y）→ R（a，y））           ES（1）

  （3）P（a）                                     T（2）

  （4）x（P（x）→ y（S（y）→﹁R（x，y）））   P

  （5）P（a）→ y（S（y）→﹁R（a，y））         US（4）

  （6）y（S（y）→﹁R（a，y））                  T（3）（5）I

  （7）y（Q（y）→ R（a，y））                    T（2）I

（8）S（z）→﹁R（a，z）                      US（6）

（9）Q（z）→R（a，z）                       US（7）

（10）R（a，z）→﹁S（z）                     T（8）E

（11）Q（z）→S（z）                      T（9）（10）I

（12）x（Q（x）→﹁S（x））                  UG（11）

   例2.18  符号化下面的命题“所有的有理数都是实数，所有的无理数也是实数，任何虚数都不是实数，所以任何虚数既不是有理数也不是无理数”，并推证其结论。

证明  设：P（x）：x是有理数。

          Q（x）：x是无理数。

          R（x）：x是实数。

          S（x）：x是虚数。

本题符号化为：x（P（x）→ R（x）），x（Q（x）→ R（x）），

x（S（x）→﹁R（x））x（S（x）→﹁P（x）﹁R（x））

解（1）x（S（x）→﹁R（x））                      P

（2）S（y）→﹁R（y）                            US（1）

（3）x（P（x）→ R（x））                       P

（4）P（y）→ R（y）                             US（3）

（5）﹁R（y）→﹁P（y）                          T（4）E

（6）x（Q（x）→ R（x））                       P

（7）Q（y）→ R（y）                             US（6）

（8）﹁R（y）→﹁Q（y）                          T（7）E

  （9）S（y）→﹁P（y）                            T（2）（5）I

（10）S（y）→﹁Q（y）                             T（2）（8）I

（11）（S（y）→﹁P（y））∧（S（y）→﹁Q（y）       T（9）（10）I

（12）（﹁S（y）∨﹁P（y））∧（S（y）∨﹁Q（y））  T（11）E

（13）﹁S（y）∨（﹁P（y）∧﹁Q（y））              T（12）E

（14）S（y）→（﹁P（y）∧﹁Q（y））                T（13）E

（15）x（S（x）→﹁P（x）∧﹁R（x））               UG（14）