离散数学：谓词演算的等价式与蕴涵式

如前所述，在谓词公式中，用客体名称取代客体变元，从而能够得到命题。对于谓词公式来说，如果客体域是有穷集合，则能够列举出对客体变元的所有可能的取代。反之，如果客体域是无穷的，则不可能列举出所有可能的取代。利用这种方法，能够证明一些含量词的等价式，对于有穷客体域来说，它们是有效的。

首先说明，用取代方法所求得的命题，能够表达含有量词的命题。为此，设客体域是个有穷集合S={a1，a2，…，an}。由前述的量词定义能够得出

(1)(∀x)A(x)⇔A(a1)∧A(a2)∧…∧A(an);

(2)(∃x)A(x)⇔A(a1)∨A(a2)∨…∨A(an)。

等价式（1）和（2）说明：如果客体域是有穷的，则可以略去量词。显然，如果客体域是无穷的，则不可能用有限个命题的合取或析取来表达含有量词的命题。

一个重要的问题是含有量词的命题的否定。首先举例说明，量化命题的否定与非量化命题的否定之间，存在着重大差别。为此，试考察下列命题：

（a）上海是一个小城镇。

（b）每一个自然数都是偶数。

命题（a）和（b）的否定如下：

（a′）上海不是一个小城镇。

（b′）一些自然数不是偶数。

应该注意，绝不可把命题（b）直接否定成：

（b′）每一个自然数都不是偶数。

显然，这样进行否定是不正确的。

设A（x）是一个谓词公式，试看」（（∀x）A（x））意味着什么。如果（∀x）A（x）的真值是真的，则应该把」（（∀x）A（x））理解成“命题（∃x）A（x）是假的”。后者等价于“对一些x，A（x）不是真的”，或者“（∃x）」A（x）”。这就是说，应有

(3)」((∀x)A(x))⇔(∃x)」A(x)。

与此类似，如果（∃x）A（x）的真值为真，则」（（∃x）A（x））说明“存在一个x，能使A（x）的真值为真”这个命题是假的。它等价于“不存在任何一个x，能使A（x）为真”，或者“对于所有的x，A（x）是假的”。这就是说，应有

(4)」((∃x)A(x)⇔(∀x)」A(x)。

这里约定，出现在量词之前的否定，不是仅否定该量词，而是否定被量化的整个命题，亦即

(5)」(∀x)A(x)⇔」((∀x)A(x))。

(6)」(∃x)A(x)⇔」((∃x)A(x))。

在有穷客体域的情况下，根据等价式（1）、（2）和德·摩根定律，能够证明等价式（3）和（4）。于是有：

」(∀x)A(x)⇔」(A(a1)∧A(a2)∧…∧A(an))

⇔」A(a1)∨」A(a2)∨…∨」A(an)

⇔(∃x)」A(x),

」(∃x)A(x)⇔」(A(a1)∨A(a2)∨…∨A(an))

⇔

」A(a1)∧」A(a2)∧…∧」A(an)

⇔(∀x)」A(x)。

假定全称量词和存在量词是互为对偶的，于是可以把上述等价式表达成：量化谓词公式的否定，等价于这样的一个公式，其中用量词的对偶取代该量词，用量词的辖域的否定取代该量词的辖域。

上面使用了查遍有穷客体域的方法，证明了等价式（3）和（4），这种证明方法比较简明而且有用。不过，用这种方法证明的结果，也适用于无穷客体域的情况。事实上，对于任意的客体域来说，等价式（3）和（4）也都成立。如果不要求作形式方法的证明，那么在任意客体域内可证明（3）如下：设S为给定的任意客体域，谓词公式」∀（x）A（x）为T。由否定律知（∀x）A（x）为F。根据全称量词的定义，在S中至少有一个客体名称c，使得A（c）为F，换句话说，S中至少有一个c使得」A（c）为T，可以直接写成（∃x）」A（x）为T。同理，」（∀x）A（x）为F，使得（∃x）」A（x）也为F。所以

」(∀x)A(x)⇔(∃x」)A(x)

（4）式也可作同样的证明。

这样，就能够得到以下两个等价式：

(3a)」(∀x)A(x)⇔(∃x」)A(x)。

(4a)」(∃x)A(x)⇔(∀x」)A(x)。

这两个等价式通常称为量词转换律。

还有许多其他的等价式，不但对于有穷客体域的情况成立，而且对于任意客体域的情况也成立。首先考察一组等价式：

(7)(∀x)A(x)∨P⇔(∀x)(A(x)∨P)。

(8)(∀x)A(x)∧P⇔(∀x)(A(x)∧P)。

(9)(∃x)A(x)∨P⇔(∃x)(A(x)∨P)。

(10)(∃x)A(x)∧P⇔(∃x)(A(x)∧P)。

根据前述的原理，也能够证明等价式（7）。同样也能够证明等价式（8）、（9）和（10）。这一组等价式，通常称为量词辖域的扩张及收缩律。

还有一组等价式，通常称为量词分配律，可表达如下：(www.xing528.com)

(11)(∀x)(A(x)∧B(x))⇔(∀x)A(x)∧(∀x)B(x)。

(12)(∃x)(A(x)∨B(x))⇔(∃x)A(x)∨(∃x)B(x)。

在等价式（11）和（12）中，x的出现全都是约束出现。对于等价式（11）来说，可以把命题（∀x）（A（x）∧B（x））读成：“对于所有的x，A（x）是真的和B（x）是真的”，或者是“对于所有的x，A（x）和B（x）都是真的”；可把命题（∀x）A（x）∧（∀x）B（x）表述成：“对所有的x，A（x）是真的，同时对于所有的x，B（x）也是真的”。不难看出，上述两个命题互为等价。

对于等价式（12）来说，能够把命题（∃x）（A（x）∨B（x））表述成：“存在一个x，能使A（x）为真或能使B（x）为真”；同时，可以把命题（∃x）A（x）∨（∃x）B（x）表述成：“存在一个x，能使A（x）为真，或者存在一个x，能使B（x）为真”。不难看出，上述两个命题为等价。在等价式（11）中，对谓词公式A（x）和B（x）并未施加任何限制，亦即它们可以是任意的，因此它容许用」C（x）取代A（x），用」D（x）取代B（x）。另外，对一个等价式的两侧同时进行否定，其结果的两侧仍然等价。

应该注意，全称量词（∀x）对于析取∨不服从分配律，亦即（∀x）（A（x）∨B（x））不等价于（∀x）A（x）∨（∀x）B（x）；存在量词（∃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）为真或B（x）为真”；另外，又可以把（∀x）A（x）∨（∀x）B（x）表述成：“对于每一个x，有A（x）为真，或者对于每一个x，有B（x）为真”。用客体域中的每一个客体名称取代x之后，若能使A（x）∨B（x）为真，但在同样取代的情况下，却不一定都能使A（x）为真，或者都使B（x）为真。下面将举例说明这种情况。

例1 设客体域是整数集合，令A（x）：x是偶整数，B（x）：x是奇整数。试考察（∃x）（A（x）∧B（x））和（∃x）A（x）∧（∃x）B（x）是否等价。

解 在这种情况下，（∃x）A（x）∧（∃x）B（x）是个真命题；而（∃x）（A（x）∧B（x））却是个假命题，因此二者不等价。

虽然如此，但是能够证明下列蕴涵式成立：

(13)(∀x)A(x)∨(∀x)B(x)⇒(∀x)(A(x)∨B(x))。

(14)(∃x)(A(x)∧B(x)⇒(∃x)A(x)∧(∃x)B(x)。

如果命题（∃x）（A（x）∧B（x））的真值为真，则在客体域中存在一些客体名称c，能使命题A（c）∧B（c）为真。于是，能够得出命题A（c）为真和B（c）为真。由此能够得出结论：由A（c）的真值为真，可以导致命题（∃x）A（x）为真；由B（c）的真值为真，可以得出命题（∃x）B（x）为真。从而，命题（∃x）A（x）∧（∃x）B（x）的真值也是真的，故蕴涵式（14）成立。在蕴涵式（14）中，用」A（x）取代A（x），用」B（x）取代B（x），并使用前述的方法，就能得到：

(∃x)(」A(x)∧」B(x))⇔(∃x)」(A(x)∨B(x))⇔」(∀x)(A(x)∨B(x)),

(∃x)」A(x)∧(∃x)」B(x)⇔」(∀x)A(x)∧」(∀x)B(x)⇔」((∀x)A(x)∨(∀x)B(x))。

已知P→Q⇔」Q→」P，于是应有

」((∃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))⇔(∀x)(A(x)∨B(x))

(∀x)A(x)∨(∀x)B(x)⇒(∀x)(A(x)∨B(x))

由此可见，蕴涵式（13）成立。

为了引用时方便起见，下面把一些重要的等价式和蕴涵式加以编号，并列举如下：

量词分配律：

E23(∃x)(A(x)∨B(x)⇔(∃x)A(x)∨(∃x)B(x)

E24(∀x)(A(x)∧B(x)⇔(∀x)A(x)∧(∀x)B(x)

量词转换律：

E25 」(∃x)A(x)⇔(∀x)」A(x)

E26 」(∀x)A(x)⇔(∃x)」A(x)

E27(∀x)A(x)∨P⇔(∀x)(A(x)∨P)

E28(∀x)A(x)∧P⇔(∀x)(A(x)∧P)

E29(∃x)A(x)∨P⇔(∃x)(A(x)∨P)

E30(∃x)A(x)∧P⇔(∃x)(A(x)∧P)

其他等价式和蕴涵式：

E31(∀x)A(x)→B⇔(∃x)(A(x)→B)

E32(∃x)A(x)→B⇔(∀x)(A(x)→B)

E33 A→(∀x)B(x)⇔(∀x)(A→B(x))

E34 A→(∃x)B(x)⇔(∃x)(A→B(x))

E35(∃x)(A(x)→B(x))⇔(∀x)A(x)→(∃x)B(x)

I15(∃x)A(x)→(∀x)B(x)⇒(∀x)(A(x)→B(x))

I16(∀x)A(x)∨(∀x)B(x)⇒(∀x)(A(x)∨B(x))

I17(∃x)(A(x)∧B(x))⇒(∃x)A(x)∧(∃x)B(x)

如果谓词公式A不依赖于变元x，则应有：

(∀x)A⇔A

(∃x)A⇔A

于是，蕴涵式I16和I17就能分别转化成等价式E27和E30。