数学证明与数学/逻辑原理/存在量词

如果全称量词是合取的扩展版本，那么关于析取的扩展版本呢？这是唯一一个这种扩展有意义的连接词，你应该能够说服自己。

存在量词

我们通过以下方式定义存在量词，它基于全称量词：

对于一些 $x$，$P(x)$

意味着

非（对于所有 $x$，非 $P(x)$）。

第二个语句有点复杂，让我们分解它看看这个定义是否有意义。对于语句

对于所有 $x$，$Q(x)$

要为假，需要一个 $x$ 的值，使得 $Q(x)$ 为假。当 $Q(x)$ 是非 $P(x)$ 时，这意味着对于语句

对于所有 $x$，非 $P(x)$

要为假，需要一个 $x$ 的值，使得 $P(x)$ 为真。换句话说

非（对于所有 $x$，非 $P(x)$)

等同于说存在一个 $x$ 的值，使得 $P(x)$ 为真，或者更简洁地说

对于一些 $x$，$P(x).$

还有关于语句

非（对于所有 $x$，非 $P(x)$)

需要注意的一点是，它取决于量词和两个否定符号的顺序。更具体地说，

并非不是（对于所有$x$，$P(x)$)

以及

对于所有$x$，并非不是$P(x)$

都等价于

对于所有$x$，$P(x)$

这不是我们想要的。

从逻辑上解释存在量词的一种方式是说，对于所有 x，P(x) 等同于所有语句 P(a) 的析取，其中 a 取遍论域中的所有值。如果论域是有限的，则可以明确地写出来。因此，如果论域包含两个对象'a' 和 'b'，则

对于一些 $x$，$P(x)$

等同于

$P(a)$ 或 $P(b).$

这在我们的定义中是有意义的，因为

$P(a)$ 或 $P(b)$

等价于

并非（并非$P(a)$ 且 并非$P(b)$)

如果我们的论域没有对象，那么定义说

对于一些 $x$，$P(x)$

无论$P(x)$ 是什么都是 False。这可能看起来有点奇怪，但它确实有意义，因为如果你把这个语句改成

存在某个$x$ 使得$P(x)$

那么，如果

存在某个$x$

部分是 False，则它必须是 False。

如果我们的论域包含一个对象，$a,$ 那么定义说

对于一些 $x$，$P(x)$

等同于

非（对于所有 $x$，非 $P(x)$)

或者

并非不是$P(a)$

或者

$P(a)$

巧合的是，事实证明

对于一些 $x$，$P(x)$

等价于

对于所有$x$，$P(x)$

在一个包含一个对象的宇宙中。

证明存在量词

与这种类型的定义一样，我们得到两个推理规则

从

非（对于所有 $x$，非 $P(x)$)

推断

对于一些 $x$，$P(x)$)

以及

从

对于一些 $x$，$P(x)$

推断

非（对于所有 $x$，非 $P(x)$)

这些对于进行证明非常实用，所以我们将根据这些添加一些其他内容。首先，我们将证明，作为一个例子

命题 1：$P(a)$ 意味着对于一些 $x$，$P(x).$

以通常的方式设置蕴含的证明，得到

行	语句	证明
1	$P(a)$	假设
(某事物)
n	对于一些 $x$，$P(x)$	?
n+1	$P(a)$ 意味着对于一些 $x$，$P(x)$	从 1 和 n

此时，我们除了定义之外别无他物可以证明

对于一些 $x$，$P(x)$

所以对上一行使用它。

行	语句	证明
1	$P(a)$	假设
(某事物)
n−1	非（对于所有 $x$，非 $P(x)$)	?
n	对于一些 $x$，$P(x)$	从 n−1
n+1	$P(a)$ 意味着对于一些 $x$，$P(x)$	从 1 和 n

现在我们需要证明否定，所以假设该语句为真并推导出矛盾。

行	语句	证明
1	$P(a)$	假设
2	对于所有 $x$，非 $P(x)$	假设
(某事物)
n−2	$False$	?
n−1	非（对于所有 $x$，非 $P(x)$)	从 2 和 n−2
n	对于一些 $x$，$P(x)$	从 n−1
n+1	$P(a)$ 意味着对于一些 $x$，$P(x)$	从 1 和 n

但是从 2 我们可推断出非 $P(a)$，这会导致必要的矛盾，证明可以完成。

行	语句	证明
1	$P(a)$	假设
2	对于所有 $x$，非 $P(x)$	假设
3	非 $P(a)$	从 2
4	$False$	从 1 和 3
5	非（对于所有 $x$，非 $P(x)$)	从 2 和 4
6	对于一些 $x$，$P(x)$	从 5
7	$P(a)$ 意味着对于一些 $x$，$P(x)$	从 1 和 6

将命题 1 与其他推理规则结合起来，我们得到

从 $P(a)$ 推断

对于一些 $x$，$P(x).$

使用存在量词

使用存在量词的规则相对复杂。它是基于以下命题，这将是我们第二个例子证明。

命题 2：（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$)) 蕴含 $Q.$

首先以正常方式建立蕴含证明，并将假设分解成单独的陈述。

以通常的方式设置蕴含的证明，得到

行	语句	证明
1	（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$))	假设
2	对于一些 $x$，$P(x)$	从 1
3	对于所有 $x$，($P(x)$ 蕴含 $Q$)	从 1
(某事物)
n	$Q$	?
n+1	（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$)) 蕴含 $Q.$	从 1 和 n

使用定义展开第 2 行，因为这是目前为止使用存在量词的唯一方法。

行	语句	证明
1	（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$))	假设
2	对于一些 $x$，$P(x)$	从 1
3	对于所有 $x$，($P(x)$ 蕴含 $Q$)	从 1
4	非（对于所有 $x$，非 $P(x)$)	从 1
(某事物)
n	$Q$	?
n+1	（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$)) 蕴含 $Q.$	从 1 和 n

现在我们需要证明 $Q$，由于似乎没有直接证明，因此建立一个间接证明。

行	语句	证明
1	（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$))	假设
2	对于一些 $x$，$P(x)$	从 1
3	对于所有 $x$，($P(x)$ 蕴含 $Q$)	从 1
4	非（对于所有 $x$，非 $P(x)$)	从 1
5	非 $Q$	假设
(某事物)
n−1	$False$	?
n	$Q$	从 5 和 n−1
n+1	（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$)) 蕴含 $Q.$	从 1 和 n

为了得出矛盾，我们证明第 4 行是假的，换句话说

对于所有 $x$，非 $P(x)$

是真的。这是一个普遍的命题，因此引入一个任意的常数 $a$ 并推导出非 $P(a)$

行	语句	证明
1	（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$))	假设
2	对于一些 $x$，$P(x)$	从 1
3	对于所有 $x$，($P(x)$ 蕴含 $Q$)	从 1
4	非（对于所有 $x$，非 $P(x)$)	从 1
5	非 $Q$	假设
6	选择 $a$	任意常数
(某事物)
n−3	非 $P(a)$	?
n−2	对于所有 $x$，非 $P(x)$	从 6 和 n−3
n−1	$False$	从 4 和 n−2
n	$Q$	从 5 和 n−1
n+1	（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$)) 蕴含 $Q.$	从 1 和 n

此时 $a$ 可以代入第 3 行，并使用语句的推理规则来完成证明。

行	语句	证明
1	（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$))	假设
2	对于一些 $x$，$P(x)$	从 1
3	对于所有 $x$，($P(x)$ 蕴含 $Q$)	从 1
4	非（对于所有 $x$，非 $P(x)$)	从 1
5	非 $Q$	假设
6	选择 $a$	任意常数
7	$P(a)$ 蕴涵 $Q$	从 3
8	非 $P(a)$	从 5 和 7
9	对于所有 $x$，非 $P(x)$	从 6 和 8
10	$False$	从 4 和 9
11	$Q$	从 5 和 10
12	（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$)) 蕴含 $Q.$	从 1 和 11

散文格式

命题 2：（对于某些 $x$，$P(x)$) 并且（对于所有 $x$，($P(x)$ 蕴含 $Q$)) 蕴含 $Q.$

证明：假设对于某些$x$，$P(x).$ 也假设对于所有$x$，($P(x)$ 意味着 $Q.$ 我们通过反证法证明 $Q$，所以假设不是$Q.$ 为了得到矛盾，足以证明对于所有 $x$，不是$P(x)$，因为它与第一个假设相矛盾。 选择$a.$ 从第二个假设，$P(a)$ 意味着 $Q.$ 但这和不是$Q$ 意味着不是$P(a).$ 对于任何$a$，所以对于所有 $x$，不是$P(x)$，这与第一个假设相矛盾。

通过将此命题与其他推理规则（包括证明普遍性的规则）结合起来，我们可以将其改写为推理规则

如果有

对于某些$x$，P(x)

并且如果通过选择$a$ 作为任意常数，可以推导出

$P(a)$ 蕴涵 $Q$

然后推断$Q$.

为了证明蕴含，需要假设 $P(a)$ 并推导出 $Q$。将

选择 $a$

与

假设 $P(a)$

步骤合并为一个，得到

选择 $a:P(a).$

可以理解为

选择 $a$ 使得 $P(a).$

通过这种简化，推理规则变为

如果有

对于一些 $x$，$P(x)$

如果通过选择 $a:P(a)$ 可以推导出 $Q$，那么可以推断出 $Q$。

对于每个和所有

这两个量词可以以两种方式组合

对于某些 $x$，对于所有 $y$，$P(x,y).$

对于所有 $y$，对于某些 $x$，$P(x,y)$

以及

为了清楚起见，最好将第一个重新表述为

存在一些 $x$，使得对于每个 $y$，$P(x,y).$

对于每个 $y$，存在一些 $x$ 使得 $P(x,y)$

第二个表述为

尽管只是量词顺序的变化，这两个陈述却不同。为了说明这一点，假设论域包含魔法戒指，并设 $P(x,y)$ 代表 "$x$ 统治 $y$"。第二个陈述仅仅说明每个戒指都被某个戒指统治。人们可以很容易地想象每个戒指都统治着自己，所以这并没有太多意义。但第一个陈述说存在一个戒指，我们可以称之为至尊魔戒，它统治着所有其他戒指；这可是一个相当厉害的戒指。请注意，我们使用第一个陈述中的“每个”来强调 $x$ 对每个 $y$ 都适用，而在第二个陈述中，我们使用“每个”来强调 $x$ 的值取决于 $y.$

所以第二个陈述并不意味着第一个，但我们可以证明，作为我们的第三个例子，第一个陈述意味着第二个。

命题 3: 存在某个 $x$ 使得对于每个 $y$，$P(x,y)$ 蕴涵着对于每个 $y$，存在某个 $x$ 使得 $P(x,y).$

按照常规方法设置直接证明，然后根据新规则使用存在量词。

行	语句	证明
1	存在一些 $x$，使得对于每个 $y$，$P(x,y).$	假设
2	选择 $a$：对于所有 $y$，$P(a,y).$	满足条件的常数
(某事物)
n−1	对于每个 $y$，存在某个 $x$ 使得 $P(x,y).$	?
n	对于每个 $y$，存在某个 $x$ 使得 $P(x,y).$	从 1、2 和 n−1
n+1	存在一些 $x$ 使得对于每个 $y$，$P(x,y)$ 意味着对于每个 $y$，存在一些 $x$ 使得 $P(x,y).$	从 1 和 n

现在我们需要证明

对于每个 $y$，存在一些 $x$ 使得 $P(x,y)$

这是一个全称量词，因此我们对于任意 $b$ 来证明它

行	语句	证明
1	存在一些 $x$，使得对于每个 $y$，$P(x,y).$	假设
2	选择 $a$：对于所有 $y$，$P(a,y).$	满足条件的常数
3	选择 $b$	任意常数
(某事物)
n−2	存在一些 $x$ 使得 $P(x,b).$	?
n−1	对于每个 $y$，存在某个 $x$ 使得 $P(x,y).$	根据3和n−2
n	对于每个 $y$，存在某个 $x$ 使得 $P(x,y).$	从 1、2 和 n−1
n+1	存在一些 $x$ 使得对于每个 $y$，$P(x,y)$ 意味着对于每个 $y$，存在一些 $x$ 使得 $P(x,y).$	从 1 和 n

现在我们可以将 $b$ 代入第2行，证明完成。

行	语句	证明
1	存在一些 $x$，使得对于每个 $y$，$P(x,y).$	假设
2	选择 $a$：对于所有 $y$，$P(a,y).$	满足条件的常数
3	选择 $b$	任意常数
4	$P(a,b)$	从 2
5	存在一些 $x$ 使得 $P(x,b).$	根据4
6	对于每个 $y$，存在某个 $x$ 使得 $P(x,y).$	根据3和5
7	对于每个 $y$，存在某个 $x$ 使得 $P(x,y).$	根据1，2和6
8	存在一些 $x$ 使得对于每个 $y$，$P(x,y)$ 意味着对于每个 $y$，存在一些 $x$ 使得 $P(x,y).$	根据1和7

在散文版本中，不需要重复第6行和第7行，因此它变成了

命题 3: 存在某个 $x$ 使得对于每个 $y$，$P(x,y)$ 蕴涵着对于每个 $y$，存在某个 $x$ 使得 $P(x,y).$

证明： 假设存在一个 $x$，使得对于任意 $y$，$P(x,y).$ 选择 $a$，使得对于任意 $y$，$P(a,y)$，并令 $b$ 为任意值。则 $P(a,b)$，因此存在一个 $x$，使得 $P(x,b).$ 由于 $b$ 为任意值，因此对于每个 $y$，存在一个 $x$，使得 $P(x,y).$