证明的方法

用来证明形如$\forall x(P(x)\to Q(x))$的定理

直接证明法

也就是条件语句$p\to q$

反证法

条件语句$p\to q$等价于它的逆否命题$\neg q \to \neg p$

空证明和平凡证明

空证明

如果知道$p$为假，那么就能证明条件语句$p \to q$为真

平凡证明

如果知道$q$为真，那么就能证明条件语句$p \to q$为真

归谬证明法

假如要证明命题$p$是真的。假定我们能找到一个矛盾式$q$使得$\neg p \to q$为真。那么这就意味着$p$为真

因为$r \land \neg r$一定是一个矛盾式，所以如果我们能够证明对某个命题$r$，$\neg p \to (r \land \neg r)$为真，就能证明$p$是真的。

举例

证明$\sqrt{2}$是无理数

证明

设$p$是命题“$\sqrt{2}$是无理数“。假定$\neg p$为真，即“$\sqrt{2}$为有理数，则存在整数$a$和$b$满足$\sqrt{2}=\frac{a}{b}$其中$b \neq 0$并且$a$和$b$没有公因子

等式两端取平方，则

$$2=\frac{a^2}{b^2}$$

因此

$$2b^2=a^2$$

可得$a^2$是偶数，通过反证法可得出$a$也是偶数，那么$\exists c$有$a=2c$。那么

$$2b^2=4c^2$$

等式两端除以$2$得

$$b^2=2c^2$$

同理可得$b$是偶数。

我们证明了假设$\neg p$导致等式$\sqrt{2}=\frac{a}{b}$并且$a$和$b$没有公因子，又推出$a$和$b$有公因子$2$，推出了矛盾，因此证明了$p$为真

等价证明法

为了证明一个双条件命题的定理，即形如$p \leftrightarrow q$的语句，那么只需证明$p \to q$和$q \to p$都是真的。

因为

$$(p \leftrightarrow q) \leftrightarrow(p \to q) \land (q \to p)$$

反例证明法

如果要证明形如$\forall x P(x)$的语句为假，只要能找到一个反例$x$使$P(x)$为假

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

为了证明如下的条件语句

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

可以用永真式

$$[(p_1 \lor p_2 \lor \cdots \lor p_n) \to q] \leftrightarrow [(p_1 \to q) \land (p_2 \to q) \land \cdots \land (p_n \to q)]$$

这种论证称为分情形证明法

穷举证明法

如果一些证明只需通过检验相对少量的例子来证明，那么这样的证明叫做穷举证明法，一个穷举证明法是分情形证明的特例

分情形证明法

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

存在性证明

$\exists xP(x)$这类命题的证明称为存在性证明。

有时可以通过找出一个使得$P(a)$为真的元素$a$来给出$\exists xP(x)$的存在性证明。这样的存在性证明称为是构造性的，也可以给出一种非构造性的存在性证明，即不是找出使$P(a)$为真的元素$a$，而是以某种其他方式来证明$\exists xP(x)$为真。给出非构造性证明的一种常用方法是使用归谬证明，证明该存在量化式的否定式蕴含一个矛盾。

一个非构造性的存在性证明

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

证明

由之前的例子可得$\sqrt{2}$是无理数，考虑数$\sqrt{2}^{\sqrt{2}}$，如果它是有理数，那就存在两个无理数$x$和$y$是有理数，即$x=\sqrt{2}, y=\sqrt{2}$，另一方面如果$\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$

唯一性证明

唯一性证明的两个部分如下

存在性：证明存在某个元素$x$具有期望的性质

唯一性：证明如果$y \neq x$，则$y$不具有期望的性质

我们也可以等价地证明如果$x$和$y$都具有期望的性质，则$x=y$