数学证明与数学/逻辑原理/全称量词

我们已经介绍了量词的一般概念，尤其是全称量词。在继续下一个量词之前，我们将给出第一个量词的推理规则。

证明一个全称量词

要证明以下形式的语句：

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

首先要求读者选择一个任意的常数 $a$，然后证明语句 $P(a)$。想法是，由于常数 $a$ 是随机选择的，除了它是在论域中的对象之外没有其他假设，因此 $P(a)$ 的证明是有效的，无论 $a$ 的选择是什么。因此，对于所有 $x.$，$P(x)$ 为真。

请注意，对于一个蕴含的证明，读者被要求做一个假设，然后你作为证明者必须推导出一个结论。类似地，在全称量词的证明中，读者被要求做一些事情，即选择一个常数，然后你作为证明者必须推导出一个结论。所以我们将以类似于第一个蕴含推理规则陈述的方式陈述推理规则。

如果通过选择 $a$ 作为任意常数可以推导出 $P(a)$，那么推断

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

考虑到这一点，我们将使全称量词证明的结构为

行	语句	证明
1	选择 $a$	任意常数
(某些内容)
n	$P(a)$	?
n+1	对于所有 $x$，$P(x)$	来自 1 和 n

缩进用于显示字母 a 在第 1 行中引入，在第 1 行到第 n 行之外没有意义。

(需要注意的是，大多数逻辑书籍遵循不同的约定。这条规则通常被陈述为

从 $P(x)$ 推断

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

其中$x$ 是$P(x)$ 中的自由变量，并且受到$x$ 在证明中其他地方出现的限制。这可能是一种有效的推理形式，但这不是数学环境中通常编写证明的方式。一方面，表达式$P(x)$，由于它具有一个自由变量，实际上是一个谓词，而不是一个语句。但在数学中，除了偶尔的命令（例如“假设...”）之外，证明只包含语句。该规则还要求区分绑定变量和自由变量。但我们正在避免这种区别，而是关注语句和谓词之间的差异。）

示例证明 #1

我们使用上面的推理规则来证明

命题 1：对于所有$x$，（$P(x)$ 蕴含 $P(x)$）。

首先，像上面一样列出证明的结构。

行	语句	证明
1	选择 $a$	任意常数
(某些内容)
n	$P(a)$ 蕴含 $P(a)$	?
n+1	对于所有$x$，（$P(x)$ 蕴含 $P(x)$)	来自 1 和 n

现在的任务是证明$P(a)$ 蕴含 $P(a)$，但$P(a)$ 是一个语句，所以我们可以应用之前证明的命题

$P$ 蕴含 $P$。

因此，证明可以完成为

行	语句	证明
1	选择 $a$	任意常数
2	$P(a)$ 蕴含 $P(a)$	命题 1 关于 蕴含的直接证明.
3	对于所有$x$，（$P(x)$ 蕴含 $P(x)$)	由 1 和 2

用散文形式，这变成

命题 1：对于所有$x$，（$P(x)$ 蕴含 $P(x)$）。

证明： 设 $a$ 为任意值。然后 $P(a)$ 蕴含 $P(a)$ 由命题 1 关于 蕴含的直接证明 推出。因此 $P(x)$ 蕴含 $P(x)$ 对所有 $x$ 成立。

使用一个全称量词

使用全称量词的规则相对简单。

如果 $a$ 是一个常数，那么由

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

推导出

$P(a)$.

基本上，这意味着如果 $P(x)$ 对所有 $x$ 成立，那么它对 $x$ 的特定值 $a$ 成立。请注意，只有当 $a$ 在当前范围内定义时，此规则才有效。

示例证明 #2

我们现在拥有了证明涉及全称量词的语句所需的所有推理规则，所以让我们通过另一个例子来运用它们。经典的三段论

所有人都是凡人。

苏格拉底是一个人。

因此苏格拉底是凡人。

可以用我们的符号表示为

对所有 $x$， ($P(x)$ 蕴含 $M(x)$).

$P(s)$

因此 $M(s)$

其中 $P(x)$ 是谓词 $x$ 是一个人，$M(x)$ 是谓词 $x$，而 $s$ 是常量苏格拉底。这应该是一个三段论，换句话说，结论应该对任何 $P$、$M$ 和 $s$ 有效，只要前两个陈述有效。这相当于

命题 2: 对于所有 $x$，($P(x)$ 蕴含 $M(x)$) 并且 $P(s)$ 蕴含 $M(s)$

这是一个蕴含，所以从直接证明的标准概要开始。

行	语句	证明
1	对于所有 $x$，($P(x)$ 蕴含 $M(x)$) 并且 $P(s)$	假设
(某些内容)
n	$M(s)$	?
n+1	对于所有$x$，($P(x)$ 意味着 $M(x)$) 以及 $P(s)$ 意味着 $M(s)$	来自 1 和 n

最好将“以及”分开成独立的语句。

行	语句	证明
1	对于所有 $x$，($P(x)$ 蕴含 $M(x)$) 并且 $P(s)$	假设
2	对于所有$x$，($P(x)$ 意味着 $M(x)$)	从 1
3	$P(s)$	从 1
(某些内容)
n	$M(s)$	?
n+1	对于所有$x$，($P(x)$ 意味着 $M(x)$) 以及 $P(s)$ 意味着 $M(s)$	来自 1 和 n

我们有 $P(s)$ 并需要推导出 $M(s)$，因此类似 $P(s)$ 意味着 $M(s)$ 的东西会起作用。但我们可以通过将 s 应用于全称量词来得到它。填充细节给出

行	语句	证明
1	对于所有 $x$，($P(x)$ 蕴含 $M(x)$) 并且 $P(s)$	假设
2	对于所有$x$，($P(x)$ 意味着 $M(x)$)	从 1
3	$P(s)$	从 1
4	$P(s)$ 意味着 $M(s)$	从 2
5	$M(s)$	从 2 和 4
6	对于所有$x$，($P(x)$ 意味着 $M(x)$) 以及 $P(s)$ 意味着 $M(s)$	从 1 和 5

翻译范畴命题

历史上，逻辑处理的是范畴命题；这些命题以特定方式将两个谓词联系起来。有四种类型

所有 P 都是 Q。

没有 P 是 Q。

有些 P 是 Q。

有些 P 不是 Q。

第一种类型，我们在上一节中已经见过，变成

对于所有$x$，($P(x)$ 意味着 $Q(x)$）。

在我们的符号中。第二种类型可以改写为

所有 P 都不是 Q。

所以在我们的符号中它变成了

对于所有 $x$，($P(x)$ 意味着不 $Q(x)$）。

注意，我们从命题逻辑中得到

$P(a)$ 意味着不 $Q(a)$ 当且仅当 $Q(a)$ 意味着不 $P(a)$。

我们留作练习来证明

没有 P 是 Q 当且仅当没有 Q 是 P。

现在想想第一种类型

所有 P 都是 Q。

是假的意味着什么。需要有一个既是 P 又不是 Q 的对象。换句话说，第四种类型的语句

有些 P 不是 Q。

必须为真。另一方面，如果

有些 P 不是 Q。

是假的，那么没有 P 不是 Q，换句话说，

所有 P 都是 Q。

所以第四个语句

有些 P 不是 Q。

可以翻译为

不（所有 P 都是 Q）。

或者

不（对于所有 $x$，($P(x)$ 意味着 $Q(x)$))。

同样，第三个语句

有些 P 是 Q。

可以翻译为

不（没有 P 是 Q）。

或者

不（对于所有 $x$，($P(x)$ 意味着不 $Q(x)$))。

我们将在下一页介绍另一个量词，这将使这些表达式更容易处理。同时，我们留作练习将两个范畴三段论

所有 P 都是 Q。

所有 Q 都是 R。

因此所有 P 都是 R。

和

所有 P 都是 Q。

没有 R 是 Q。

因此没有 P 是 R。

翻译成我们的符号，并使用我们迄今为止给出的推理规则来证明它们。

您可能已经注意到，我们试图将范畴命题翻译成我们的符号的结果，既比原来的命题冗长，也不像自然语言那么自然。因此您可能会想知道，我们的符号有什么优势。一个优势是，我们的符号足以表达所有数学语句，而范畴命题本身过于限制。其次，范畴三段论并没有涵盖证明定理所需的所有有效推理形式。考虑

所有三角形和矩形都是直线图形。

所有正方形都是所有边相等的矩形。

因此所有正方形都是直线图形。

这似乎是一个有效的三段论，但由于前提都包含三个谓词而不是两个，所以它不是范畴三段论之一。此外，范畴命题只处理谓词，而不处理关系，而只用谓词进行数学运算是不可能的。