证明的配方

证明所需的要素包括：被假设为简单的事实（公理）、我们所处理对象（及运算）的定义、假设条件、推理规则，以及一点洞察力。一个证明是一系列数学陈述的序列，从一个假设或已知事实开始，第 $i$ 个陈述在前 $i-1$ 个陈述都为真时也必须为真。通常，最后一个陈述是结论。公理、假设和定义被视为证明中的真命题；其他命题只有在其能根据推理规则从前述命题推导出时才被认为是真。

我们可以在任何现有的证明中看到这些组成部分。一个著名的问题是：如何构造新的证明？一个臭名昭著但正确的答案是：不存在一种通用的“配方”来构建新证明。那么我们该如何做呢？这是一门艺术，如同创作一幅从未有人尝过的画作或菜肴一样。然而，我们可以讨论一些著名的做法和现有证明的主要类型。让我们从直接证明开始探索这些类别。

直接证明

直接证明通常用于确立如下类型的量化条件命题的真实性：

$$\forall x \left(P(x)\Rightarrow Q(x)\right).$$

当然，这个命题是在某个特定论域内进行分析的。我们假设该论域中的所有元素都具有性质 $P$，并由此推导出每个元素也都具有性质 $Q$。这里 $P(x)$ 是假设，$Q(x)$ 是结论。通常会有多个假设和已知事实作为起点；在这种情况下，$P$ 是所有前提的合取。也就是说，如果 $P_1, P_2, P_3, \ldots, P_n$ 都是被假设为真的命题，那么我们可以将 $P(x)$ 写作：

$$P(x) \equiv \left(P_1(x) \land P_2(x) \land P_3(x) \land \ldots \land P_n(x)\right).$$

除了假设之外，我们还使用定义和推理规则来推进到结论。下面我们通过几个例子来探讨直接证明的典型结构。

例子

我们以整数集作为论域。一个整数是偶数，如果它可以写成 $2k$ 的形式，其中 $k$ 是某个整数。一个奇数整数可以写成 $2k+1$，其中 $k$ 是某个整数。每个整数要么是偶数，要么是奇数。我们利用已有信息来证明以下命题。

定理 1

如果 $x$ 是一个偶数整数，那么 $x^2$ 也是偶数。

证明

我们需要证明 $\forall x \left(E(x)\Rightarrow E(x^2)\right)$，其中 $E(x)$ 表示 $x$ 是偶数。我们知道，当蕴含命题的前件为假时，整个蕴含命题为真。因此，对于所有非偶数的整数，该命题显然成立。我们现在只关注偶数整数。任取一个偶数整数 $y$。根据定义，存在某个整数 $k$，使得 $y = 2k$。两边平方得 $y^2 = (2k)^2$。可改写为 $y^2 = 2(2k^2)$。由于 $k$ 是整数，故 $z = 2k^2$ 也是整数。因为 $y^2$ 可表示为 $2z$，所以它是偶数。我们选取的 $y$ 是任意一个偶数整数，因此通过全称推广，得出：对每一个偶数整数，其平方也是偶数。我们已证明该命题对所有整数都成立，无论它们是否为偶数。因此，$\forall x \left(E(x)\Rightarrow E(x^2)\right)$ 为真。

---

定理 2

如果 $x$ 是一个奇数整数，那么 $x^2$ 也是奇数。

证明

我们需要证明 $\forall x \left(O(x)\Rightarrow O(x^2)\right)$，其中 $O(x)$ 表示 $x$ 是奇数。任取一个奇数整数 $y$。根据定义，存在某个整数 $k$，使得 $y = 2k + 1$。两边平方得 $y^2 = (2k + 1)^2$。展开右边得 $y^2 = 4k^2 + 4k + 1$。由于 $k$ 是整数，故 $z = 2k^2 + 2k$ 也是整数。因为 $y^2$ 可表示为 $2z + 1$，所以它是奇数。我们选取的 $y$ 是任意一个奇数整数，因此通过全称推广，得出：对每一个奇数整数，其平方也是奇数。若 $x$ 不是奇数，则蕴含命题的前件为假，命题自然为真。我们已证明该命题对所有整数都成立，无论它们是否为奇数。因此，$\forall x\left(O(x)\Rightarrow O(x^2)\right)$ 为真。

---

定理 3

如果 $m$ 是一个奇数整数，$n$ 是一个偶数整数，那么 $mn$ 是偶数。

证明

我们需要证明 $\forall m \forall n\left(O(m)\land E(n)\Rightarrow E(mn)\right)$。任取一个奇数整数 $y$ 和一个偶数整数 $z$。根据定义，存在整数 $j$ 和 $k$，使得 $y = 2j + 1$，$z = 2k$。相乘得 $yz = (2j + 1)(2k)$。化简右边得 $yz = 4jk + 2k$。由于 $j$ 和 $k$ 是整数，故 $p = 2jk + k$ 也是整数。因为 $yz$ 可表示为 $2p$，所以它是偶数。我们选取的 $y$ 是任意奇数整数，$z$ 是任意偶数整数，因此通过全称推广，得出：任意奇数与任意偶数的乘积都是偶数。因此，$\forall m \forall n\left(O(m)\land E(n)\Rightarrow E(mn)\right)$ 为真。