1.8. 证明的方法和策略

本章将研究关于证明的艺术和科学方面的一些问题。我们将提供如何寻找一个定理的证明的一些忠告。我们还将描述一些窍门，包括如何通过反向思维和通过改编现有证明来发现证明。

穷举证明法和分情形证明法

为了证明如下的条件语句

$$(p_1 \lor p_2 \lor \dots \lor p_n) \to q$$

可以使用永真式

$$[(p_1 \lor p_2 \lor \dots \lor p_n) \to q] \harr [(p_1 \to q) \land (p_2 \to q) \land \dots \land (p_n \to q) ]$$

如果$p_n$为假，则$(p_n \to q)$为真。

来证明由命题$p_1, \: p_2 , \: \dots , p_n$ 的析取式组成前提的原条件语句。这种论证称为分情形证明法（proof by cases）。

穷举证明法

有些定理可以通过校验相对少量的例子来证明。这样的证明叫做穷举证明法（exhaustive proof, proof by exhaustion）。因为这些证明是要穷尽所有可能性的。

证明如果$n$是一个满足$n \le 4$的正整数时，则有$(n+1)^3 \ge 3^n$。
采用穷举证明法。我们只需检验当$n = 1,2,3,4$时，不等式$(n+1)^3 \ge 3^n$成立。

分情形证明法 分情形证明一定要覆盖定理中出现的所有可能情况。

存在性证明

存在性证明

许多定理是断言特定类型对象的存在性。这种类型的定理是形如$\exist x P(x)$的命题，其中$P$是谓词。$\exist x P(x)$这类命题的证明称为存在性证明（existence proof）。

有时可以通过找出一个使得$P(a)$为真的元素$a$（称为一个物证）来给出$\exist x P(x)$的存在性证明。这样的存在性证明是构造性的（constructive）。也可以给出一种非构造性的（nonconstractive）存在性证明，即不是找出使$P(a)$为真的元素$a$，而是以某种其他方式来证明$\exist x P(x)$为真。

证明存在无理数$x$和$y$使得$x^y$是有理数。

$\sqrt{2}$是无理数。考虑数$\sqrt{2}^{\sqrt{2}}$。如果它是有理数，那就存在两个无理数$x$和$y$且$x^y$是有理数。
如果$\sqrt{2}^{\sqrt{2}}$是无理数，那么令$x = \sqrt{2}^{\sqrt{2}}$且$y=\sqrt{2}$，
因此$x^y=(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}}=\sqrt{2}^{\sqrt{2} \cdot \sqrt{2}}=\sqrt{2}^2 = 2$

唯一性证明

某些定理断言具有特定性质的元素唯一存在。换句话说，这些定理断言恰好只有一个元素具有这个性质。

唯一性证明（uniqueness proof）的两个部分如下：

• 存在性：证明存在某个元素$x$具有期望的性质。
• 唯一性：证明如果$y \neq x$，则$y$不具有期望的性质。

评注

证明存在唯一元素$x$使得$P(x)$为真等同于证明语句

$$\exist x (P(x) \land \forall y(y \neq x \to \lnot P(y)) )$$

证明策略

正向推理（forward reasoning）

无论选择什么证明方法，都需要为证明找一个起点。条件语句的直接证明就从前提开始。利用这些前提以及公理和已知定理，用导向结论的一系列步骤来构造证明。这类推理称为正向推理。

反向推理（backward reasoning）

要反向推理证明命题$q$，我们就寻找一个命题$p$并可证明其具有性质$p \to q$。（注意，寻找一个命题$r$并能证明其具有$q \to r$不会有所帮助，因为从$q \to r$和$r$得出$q$为真是一种窃取论题的错误推理）