数学证明和数学/逻辑原理/蕴涵的直接证明

我们已经讨论了数学中使用哪些类型的语句，所以现在我们可以讨论如何将这些语句组合在一起以证明定理。在这一点上，我们只能证明重言式，所以如果这是一个视频游戏，那么这将是训练级别。我们在这里证明的语句不能真正被称为定理，所以我们将称它们为命题。

如前所述，$P$，$Q$，... 将在本节中代表数学语句。

推理规则

在数学中，证明必须基于逻辑推论，换句话说，每一步都必须是前一步的逻辑结果。逻辑结果究竟是什么，是逻辑学的问题，逻辑学为我们提供了“推理规则”。每个推理规则都是一个将真命题组合在一起的规则，保证会产生另一个真命题。最简单的例子是

从 $P$ 推导出 $P$。

这条规则被称为“迭代”；许多推理规则都有名称，但在数学证明中，应该从上下文中清楚地知道使用了哪条规则。

还有其他一些规则以简单的方式组合先前的语句，但事实证明，仅凭它们无法走得太远。一种方法是添加逻辑公理，例如

$P$ 或 $P$ 蕴涵 $P$。

但这虽然是一种有效的方法，但如果直接使用逻辑公理，数学中的证明将长得多，也更难理解。因此，数学中使用的方法是允许使用“辅助假设”。

这种类型规则最常用的例子是

如果通过做出假设 $P$ 可以推导出 $Q$，则推导出 $P$ 蕴涵 $Q$。

这需要一段时间才能理解，所以我们将给出一些使用这条推理规则的证明示例。

证明示例 #1

我们第一个证明示例是针对语句

命题 1 $P$ 蕴涵 $P$。

证明的第一个版本将采用表格格式，以便清楚地说明推理规则的使用方式。

行	语句	理由
1	$P$	假设
2	$P$	迭代第 1 行
3	$P$ 蕴涵 $P$	由 1 和 2

在表格中，第一行缩进表示我们正在引入假设或假设，下一行缩进表示我们在第一行的假设下进行操作。最后一行没有缩进，这意味着该语句在没有假设的情况下仍然有效。

所以让我们来研究一下在这种情况下推理规则是如何应用的。首先，我们做出了假设$P$. 然后我们推导出$P$，在这种情况下只是简单地重复$P$。由于通过假设$P$，我们能够推导出$P$，推理规则指出你可以得出结论$P$ 意味着 $P$.

证明的表格格式很少在数学中使用。如果你像我们现在这样非常详细和谨慎，或者如果你刚开始接触证明，就像我们现在一样，你可以使用它。在数学文献中，你会使用更像散文的形式。我们的第二个版本展示了证明在这种格式下可能是什么样的。

命题 1: $P$ 意味着 $P$.

证明: 假设$P$。那么根据假设$P$。因此$P$ 意味着 $P$.

在这个版本的证明中，有语言来介绍假设。这通常是“假设…”或“设…”。第二行得出结论并给出理由。用于此的语言通常类似于“那么…因为…”，“因此…通过…”，“所以…既然…”。最后一行实际上不是必需的，因为我们已经知道我们试图证明哪个语句。但由于它包含在内，因此使用了“因此”一词来指出这是证明中的一个重要点。在这种情况下，是因为我们将假设与我们能够从中推导出来的内容结合起来，从而消除了假设。

经验丰富的数学家通常能够毫不费力地完成像这样的陈述的证明。因此，另一个可接受的证明可能是

命题 1: $P$ 意味着 $P$.

证明: 平凡的。

但是，将一个陈述称为“平凡的”、“显然的”或“清晰的”是一种特权，你必须通过做足够多的证明才能自动填补逻辑证明才能获得这种特权。它不能用于根据你的直觉似乎为真的陈述。还要记住，对某些人来说是平凡的，对另一些人来说可能不是平凡的，因此在写证明时，你必须牢记你的读者，就像所有的写作一样。

Q.E.D. 和墓碑

缩写“Q.E.D.”有时出现在证明的末尾，但在现代数学中很少使用。它是拉丁语短语 quod erat demonstrandum 的缩写，大致意思是“这是要被证明的”。拉丁语不像以前那样广泛为人所知，而且这种缩写是在作者可以放心地假设他们的读者具有基本知识的时候使用的。有一些变体，包括 quod erat faciendum 的“Q.E.F.”，意思是“这是要做的”。如果证明的结尾在现代文本中被标记，那么就会使用墓碑或一个小矩形或正方形。但是，如果你是一位喜欢在日常生活中使用 mutatis mutandis 这样短语的传统人士，那么如果你愿意，使用 Q.E.D. 并没有什么错误。

示例证明 #2

下一个证明示例将针对以下陈述

命题 2: $P$ 意味着 ($Q$ 意味着 $P$).

这有点复杂，但我们鼓励你在阅读更多内容之前尝试一下，记住它可以使用到目前为止我们给出的两个推理规则来证明。

更复杂的证明不是那么多的编写，而是构建的。换句话说，你并不是从头到尾地写它们。就像看到一栋已建成的房子并不能告诉你如何建造它一样，看到一个已完成的证明并不能告诉你如何写它。因此，我们将尝试展示用于创建示例证明的过程，而不仅仅是最终结果。

我们首先假设有一个证明，然后试图找出它的样子。该陈述是一个蕴涵，所以为了使推理规则起作用，我们需要假设“蕴涵”一词之前的部分并推导出“蕴涵”一词之后的。因此，以表格形式，证明的结构是

行	语句	理由
1	$P$	假设
(something)
n	$Q$ 蕴涵 $P$	?
n+1	$P$ 蕴涵 ($Q$ 蕴涵 $P$)	从 1 和 n

现在我们需要一个关于

$Q$ 蕴涵 $P$

的证明来填补中间。这又是一个蕴涵，所以我们需要假设第一部分，$Q$，并证明第二部分，$P$。这意味着在第一个假设中做出第二个假设，我们当前版本的证明是

行	语句	理由
1	$P$	假设
2	$Q$	假设
(something)
n−1	$P$	?
n	$Q$ 蕴涵 $P$	从 2 和 n−1
n+1	$P$ 蕴涵 ($Q$ 蕴涵 $P$)	从 1 和 n

此时我们需要证明 $P$，但它已经是假设之一，所以只需要重新陈述它。这给了我们证明的最终版本

行	语句	理由
1	$P$	假设
2	$Q$	假设
3	$P$	迭代第 1 行
4	$Q$ 蕴涵 $P$	从 2 和 3
5	$P$ 蕴涵 ($Q$ 蕴涵 $P$)	从 1 和 4

让我们翻译成散文格式。

命题 2：$P$ 蕴涵 ($Q$ 蕴涵 $P$)

证明：假设 $P$。现在假设 $Q$。根据原始假设，我们有 $P$。因此，$Q$ 蕴涵 $P$。从原始假设 $P$ 可以得出 $Q$ 蕴涵 $P$，所以我们可以得出结论，$P$ 蕴涵 ($Q$ 蕴涵 $P$).

示例证明 #3

在这个例子中，我们需要一个新的推理规则。

从 $P$，$P$ 蕴含 $Q$ 推导出 $Q$。

换句话说，如果语句 $P$ 和语句 $P$ 蕴含 $Q$ 都已被证明，那么你可以添加语句 $Q$。

你可能会认为这是之前推理规则的逆，因为它使用了一个蕴含，而之前的规则证明了一个蕴含。

命题 3： $P$ 蕴含 (($P$ 蕴含 $Q$) 蕴含 $Q$。

同样，我们鼓励你在继续阅读之前尝试一下，记住它可以用我们迄今为止给出的三个推理规则来证明。

我们将使用上一个例子中讨论的构造方法来达到这一点，留作练习。

行	语句	理由
1	$P$	假设
2	$P$ 蕴含 $Q$	假设
(something)
n−1	$Q$	?
n	($P$ 蕴含 $Q$) 蕴含 $Q$	从 2 和 n−1
n+1	$P$ 蕴含 (($P$ 蕴含 $Q$) 蕴含 $Q$)	从 1 和 n

我们需要证明

$Q$

在这一点上，但我们有

$P$

和

$P$ 蕴含 $Q$

作为假设。因此，只需应用我们新的推理规则即可。证明的最终形式如下：

行	语句	理由
1	$P$	假设
2	$P$ 蕴含 $Q$	假设
3	$P$	迭代第 1 行
4	$Q$	3,2
5	($P$ 蕴含 $Q$) 蕴含 $Q$	从 2 和 5
6	$P$ 蕴含 (($P$ 蕴含 $Q$) 蕴含 $Q$)	从 1 和 6

以散文格式

命题 3： $P$ 蕴涵 (($P$ 蕴涵 $Q$) 蕴涵 $Q$)

证明： 假设 $P$。现在假设 $P$ 蕴涵 $Q$。根据最初的假设，我们有 $P$，所以 $Q$。因此，$Q$ 蕴涵 ($P$ 蕴涵 $Q$)。从最初的假设 $P$ 可以得出 ($Q$ 蕴涵 $P$) 蕴涵 $Q$)，因此我们可以得出结论 $P$ 蕴涵 (($Q$ 蕴涵 $P$) 蕴涵 $Q$)).

引用之前的结果

如果所有东西都必须从头开始证明，数学将不会取得很大进展。幸运的是，每次证明一个新的结果时，它都可以作为其他证明的捷径。通常可以清楚地知道使用了哪个结果，否则，如果它是同一文档中之前证明的结果，则在证明中指向它。使用某种标签或编号系统来简化此操作非常方便。如果您引用其他来源，请使用您喜欢的引用风格，以清楚地表明您从哪里引用，并清楚地说明在该来源中哪里可以找到该结果。请注意，任何形式为$P$ 蕴含 $Q$ 的结果可以与前面的推理规则结合起来，创建一个新的推理规则“从 $P$ 推断 $Q$”。例如，命题 2 创建了一个新的推理规则

从 $P$ 推断 $Q$ 蕴含 $P$.

命题 4： $P$ 蕴含 ($Q$ 蕴含 ($R$ 蕴含 $P$))).

证明：假设$P$。那么$R$ 蕴含 $P$，根据命题 2。同样，$Q$ 蕴含 ($R$ 蕴含 $P$)，根据命题 2。因此$P$ 蕴含 ($Q$ 蕴含 ($R$ 蕴含 $P$))。

注意，在命题 2 的第一次应用中，语句 $R$ 替换了命题中使用的 $Q$。在第二次应用中，语句 $R$ 蕴含 $P$ 替换了命题中使用的 $P$。

留给读者完成

以下证明留给读者完成

命题 5: ($P$ 蕴含 $Q$) 蕴含 (($Q$ 蕴含 $R$) 蕴含 ($P$ 蕴含 $R$))。

命题 6: ($P$ 蕴涵 ($Q$ 蕴涵 $R$)) 蕴涵 ($Q$ 蕴涵 ($P$ 蕴涵 $R$)).

命题 7: ($P$ 蕴涵 ($P$ 蕴涵 $Q$)) 蕴涵 ($P$ 蕴涵 $Q$).

命题 8: ($P$ 蕴涵 ($Q$ 蕴涵 $R$)) 蕴涵 (($P$ 蕴涵 $Q$) 蕴涵 ($P$ 蕴涵 $R$)).

命题 9: (($R$ 蕴含 $Q$) 蕴含 $P$) 蕴含 ($Q$ 蕴含 $P$)

命题 10: (($R$ 蕴含 $Q$) 蕴含 ($Q$ 蕴含 $P$)) 蕴含 ($Q$ 蕴含 $P$)

到目前为止，我们只讨论了蕴含，但这并不意味着我们已经完成了它。有一些陈述，虽然为真，但无法用我们目前给出的推理规则证明。其中之一是

命题 ??： (($P$ 蕴含 $Q$) 蕴含 $P$) 蕴含 $P$.

你可能想尝试一下，记住只使用本页的推理规则，看看你能走多远。如果你真的找到了一个证明，那么这意味着你（可能）做错了什么。