数学证明和数学/逻辑/间接证明原理

在上一节中，我们研究了与蕴涵相关的推理规则。大多数数学定理都采用蕴涵的形式，因此这些规则非常重要。（从某种意义上说，所有数学定理都采用蕴涵的形式，但我们稍后会讨论这一点。）

但逻辑不仅仅是蕴涵，所以我们需要一些额外的推理规则来处理其他逻辑连接词。其中最基本的是反证法。

矛盾

我们首先介绍矛盾的概念。你可以把它想象成一个已知为假的陈述。具有讽刺意味的是，这样的陈述在逻辑中起着重要的作用，逻辑的目的是证明某些陈述总是正确的。

有几个逻辑符号表示矛盾；其中一个是 $\bot$，在这种情况下，始终为真的陈述的符号是 $\top$。也许 $\top$ 是因为它与字母“T”（表示 True）相似，将其倒置意味着相反。另一个符号是 $\Box$，在这种情况下，符号 $\blacksquare$ 代表始终为真的陈述。由于我们大多数情况下避免使用这些符号，因此我们将简单地用文字拼写出 $False$ 来表示表格格式的证明。对于以散文形式给出的证明，通常会写类似“这是荒谬的”或“这是一个矛盾”之类的话。单词“矛盾”本身来自拉丁语短语，意思是“反对”，指的是彼此含义相反的语句。

否定

可以使用蕴涵和矛盾来“定义”所有剩余的逻辑连接词。首先，我们可以取语句

$P$ 蕴涵 $False$

作为

非 $P$ 的定义。

我们已经在逻辑连接词部分给出了“非 $P$”的定义，现在我们创建了一个新的、竞争的定义。只要我们可以确信这两个定义相互一致，这就没有问题。因此，我们需要确信语句

$P$ 蕴涵 $False$

当 $P$ 为真时，结果为假，当 $P$ 为假时，结果为真。但是语句 $P$ 蕴含 $Q$ 的定义是当 $P$ 为真时，结果为假，当 $P$ 为假且 $Q$ 为假时，结果为真。因此定义是吻合的。

给定这样的定义，我们可以创建两个新的推理规则。第一个用定义替换定义的表达式，第二个进行相反的替换。所以我们有

从非 $P$ 推导出 $P$ 蕴含 $False$

和

从 $P$ 蕴含 $False$ 推导出非 $P$.

通过将这些规则与上一页的规则结合起来，我们得到了更实用的形式

从 $P$，非 $P$ 推导出 $False$

和

如果通过假设 $P$ 可以推导出 $False$，那么推导出非 $P$.

示例证明 #1

让我们首先使用上述规则来证明

命题 1: $P$ 蕴含非非 $P$.

这是一个蕴含关系，因此我们从假设前提开始，推导出结论。所以证明的结构如下：

行	语句	理由
1	$P$	前提
(某个东西)
n	非非 $P$	?
n+1	$P$ 蕴含非非 $P$	由 1 和 n 推出

现在的目标是证明非非 $P$，但我们可以通过假设非 $P$ 并推导出矛盾来实现。证明的新形式是

行	语句	理由
1	$P$	前提
2	非 $P$	前提
(某个东西)
n−1	$False$	?
n	非非 $P$	由 2 和 n−1 推出
n+1	$P$ 蕴含非非 $P$	由 1 和 n 推出

现在我们需要证明 $False$，但语句 $P$ 和 非 $P$ 已经被假设，所以只需要进行最后的填充即可。

行	语句	理由
1	$P$	前提
2	非 $P$	前提
3	$P$	重复 1
4	$False$	2 和 3 之间的矛盾
5	非非 $P$	由 2 和 4 推出
6	$P$ 蕴含非非 $P$	由 1 和 5 推出

用散文形式表达

命题 1: $P$ 蕴含非非 $P$.

证明： 假设 $P$。现在假设不 $P$。根据原始假设，我们同时拥有不 $P$ 和 $P$，这是一个矛盾。所以假设不 $P$ 一定是假的，换句话说，不是不 $P$。从原始假设 $P$ 可以得出，不是不 $P$，因此我们可以得出结论 $P$ 蕴含不是不 $P$。

示例证明 #2

我们证明

命题 2： ($P$ 蕴含 $Q$) 蕴含 (不 $Q$ 蕴含不 $P$）。

对于任何蕴含 $P$ 蕴含 $Q$，蕴含不 $Q$ 蕴含不 $P$ 被称为其“逆否命题”。正如我们将看到的，逆否命题在逻辑上等价于原始蕴含，这与逆命题不同。命题 2 是证明该等价性的第一步。

你可以从头开始证明，这留作练习，但另一种方法是使用上一页的命题 5 作为捷径。改写为推理规则，该命题指出

从 $P$ 蕴含 $Q$ 推导出 ($Q$ 蕴含 $R$) 蕴含 ($P$ 蕴含 $R$）。

这产生了一个更简单的证明

行	语句	理由
1	$P$ 意味着 $Q$	前提
2	非 $Q$	前提
3	$Q$ 意味着 $False$	“非”的定义
4	$P$ 意味着 $Q$	重复 1
5	($Q$ 意味着 $False$) 意味着 ($P$ 意味着 $False$).	上一页命题5
6	$P$ 蕴涵 $False$	从3和5得出
7	非 $P$	“非”的定义
8	非 $Q$ 意味着 非 $P$	从2和7得出
9	($P$ 意味着 $Q$) 意味着 (非 $Q$ 意味着 非 $P$).	从1和8得出

间接证明方法

我们几乎得到了一种非常有用和重要的证明方法，称为反证法，或者对于喜欢拉丁语的人来说，称为Reductio ad absurdum，大致翻译成归谬法。使用这种方法的证明被称为间接证明，因为它不像所谓的直接证明那么直接，直接证明依赖于目前为止使用的方法。

为了使用这种方法来证明一个命题 $P$，假设它是假的，然后推导出矛盾。如果假设一个命题是假的会导致不可能的结果，那么这个命题就必须是非假的，即为真的。换句话说，如果假设非 $P$ 你可以推导出矛盾，也就是说，如果非非 $P$，那么你可以推导出 $P$.

我们将以新的推论规则的形式重新说明这一点

从非非 $P$ 推导出 $P$.

另一种说法是

如果假设不为 $P$，可以推导出 $False$，那么可以推导出 $P$.

这是最后一个推论规则，无法从定义或其他推论规则中推导出。我们将像对否定一样定义析取、合取和等价，这些定义会产生两个推论规则，但可以通过像上一页中的命题 2 一样证明蕴涵来推导出。

示例证明 #3 和 #4

为了使这个推论规则发挥作用，让我们从命题 1 的逆命题开始

命题 3: 不不 $P$ 蕴涵 $P$.

这很容易推导出，证明留作练习。

命题 4: (不 $Q$ 蕴涵 不 $P$) 蕴涵 ($P$ 蕴涵 $Q$)

从构建一个轮廓开始，就像之前一样。

行	语句	理由
1	非 $Q$ 意味着 非 $P$	前提
2	$P$	前提
(某个东西)
n−1	$Q$	?
n	$P$ 意味着 $Q$	由 2 和 n−1 推出
n+1	(不 $Q$ 蕴涵 不 $P$) 蕴涵 ($P$ 蕴涵 $Q$)	由 1 和 n 推出

此时我们需要证明 $Q$，但直接证明似乎行不通，所以假设不为 $Q$ 并尝试推导出矛盾。

行	语句	理由
1	非 $Q$ 意味着 非 $P$	前提
2	$P$	前提
3	非 $Q$	前提
(某个东西)
n−2	$False$	?
n−1	$Q$	从 3 和 n−2
n	$P$ 意味着 $Q$	由 2 和 n−1 推出
n+1	(不 $Q$ 蕴涵 不 $P$) 蕴涵 ($P$ 蕴涵 $Q$)	由 1 和 n 推出

我们现在有足够的假设来开始填充一些推理并完成证明。

行	语句	理由
1	非 $Q$ 意味着 非 $P$	前提
2	$P$	前提
3	非 $Q$	前提
4	非 $Q$ 意味着 非 $P$	重复 1
5	非 $P$	从 3 和 4
6	$P$	迭代 2
7	$False$	从 5 和 6
8	$Q$	从 3 和 7
9	$P$ 意味着 $Q$	从 2 和 8
10	(不 $Q$ 蕴涵 不 $P$) 蕴涵 ($P$ 蕴涵 $Q$)	从 1 和 9

用散文形式表达

命题 4: (不 $Q$ 蕴涵 不 $P$) 蕴涵 ($P$ 蕴涵 $Q$)

证明： 假设并非 $Q$ 蕴涵并非 $P$。现在假设 $P$。我们需要证明 $Q$，所以假设并非如此，换句话说，并非 $Q$。那么根据第一个假设，并非 $P$。但这与第二个假设相矛盾。假设并非 $Q$ 导致了矛盾，所以 $Q$。因此，$P$ 蕴涵 $Q$。从最初的假设并非 $Q$ 蕴涵并非 $P$，可以得出结论： (并非 $Q$ 蕴涵并非 $P$) 蕴涵 ($P$ 蕴涵 $Q$)。

注意，虽然这不是严格必要的，但我们陈述了接下来要证明的内容，并以“假设并非如此”的形式插入了一个小小的路标，以表明接下来将使用间接论证。其他具有相同目的的短语可能包括“假设并非”和“如果错误，那么”。

留给读者

命题 5：并非 ($P$ 蕴涵 $Q$) 蕴涵并非 $Q$

命题 6：并非 ($P$ 蕴涵 $Q$) 蕴涵 $P$

命题 7: (($P$ 蕴含 $Q$) 蕴含 $P$) 蕴含 $P$

命题 8: 非 $P$ 蕴含 ($P$ 蕴含 $Q$)

命题 9: $False$ 蕴含 $Q$

命题 10: 非 $False$