数学证明和数学/逻辑/逻辑等价原理

我们将介绍最后一个逻辑连接词。

等价

再次，我们用其他连接词来“定义”它，并验证它与之前给出的定义相匹配。在这种情况下，我们取

($P$ 蕴含 $Q$) 并且 ($Q$ 蕴含 $P$)

作为

$P$ 当且仅当 $Q$ 的定义。

这个定义就是“当且仅当”表达式的由来，因为

$Q$ 蕴含 $P$

可以表述为 $P$ 如果 $Q$，并且

$P$ 蕴含 $Q$

可以表述为 $P$ 仅当 $Q$。

为了确认这与先前的定义相符，请注意 $P$ 蕴含 $Q$ 为假时，$P$ 为真，而 $Q$ 为假，同时 $Q$ 蕴含 $P$ 为假时，$Q$ 为真，而 $P$ 为假，因此表达式 ($P$ 蕴含 $Q$) 和 ($Q$ 蕴含 $P$) 只有当 $P$ 和 $Q$ 同时为真或同时为假时才为真。

将此定义与其他推理规则结合，我们可以得到以下结论

从 $P$ 蕴含 $Q$，$Q$ 蕴含 $P$ 推导出 $P$ 当且仅当 $Q$.

如果假设不为 $P$，可以推导出 $Q$，并且如果假设不为 $Q$，可以推导出 $P$，那么推导出 $P$ 当且仅当 $Q$。

从 $P$，$P$ 当且仅当 $Q$ 推导出 $Q$。

从 $Q$，$P$ 当且仅当 $Q$ 推导出 $P$。

因此，您可以像使用蕴涵一样使用等价关系，只是它双向有效，而证明等价关系与证明蕴涵相同，只是您需要双向进行。

示例证明#1

命题 1：$P$ 或 $Q$ 当且仅当 $Q$ 或 $P$

在这种情况下，我们已经有了 $P$ 或 $Q$ 意味着 $Q$ 或 $P$，如上一页的命题 1。通过交换字母 $Q$ 和 $P$ 在命题中，我们得到 $Q$ 或 $P$ 意味着 $P$ 或 $Q$。因此，证明只是将这两个先前结果组合在一起的问题。

行	陈述	证明
1	$P$ 或 $Q$ 意味着 $Q$ 或 $P$	上一页的命题 1。
2	$Q$ 或 $P$ 意味着 $P$ 或 $Q$	同样是上一页的命题 1。
3	$Q$ 或 $P$ 当且仅当 $P$ 或 $Q$	来自 1 和 2

示例证明 #2

对于更复杂的示例，我们需要使用子证明。

命题 2： $P$ 或 $Q$ 当且仅当 ($P$ 蕴含 $Q$) 蕴含 $Q$

我们要证明两个方向的蕴含，所以证明的结构看起来像这样

行	陈述	证明
1	$P$ 或 $Q$	假设
(某些东西)
n	($P$ 蕴含 $Q$) 蕴含 $Q$	?
n+1	($P$ 蕴含 $Q$) 蕴含 $Q$	假设
(某些东西)
n+p	$P$ 或 $Q$	?
n+p+1	$P$ 或 $Q$ 当且仅当 ($P$ 蕴含 $Q$) 蕴含 $Q$	从 1 和 n，n+1 和 n+p

在这一点上，我们已经将证明分解成可以单独处理的部分。在第一种情况下，我们需要证明一个蕴含，但这似乎比通常的做法更容易。在第二种情况下，我们需要证明一个析取，有两种方法可以做到。看起来更容易的方法是假设不是 $P$ 并证明 $Q$。现在，我们已经有了几种证明方法，可能有些方法比其他方法更简单，但没有足够的经验来体会这一点，你可能需要使用试错法来找到最简单的方法。不过请记住，当你看到书本或文章中的证明时，作者可能在找到有效的证明之前尝试了很多失败的尝试，但你无法看到这些失败。

填充更多结构，我们有

行	陈述	证明
1	$P$ 或 $Q$	假设
2	$P$ 蕴含 $Q$	假设
(某些东西)
n−1	$Q$	?
n	($P$ 蕴含 $Q$) 蕴含 $Q$	从 2 和 n−1
n+1	($P$ 蕴含 $Q$) 蕴含 $Q$	假设
n+2	不是 $P$	假设
(某些东西)
n+p−1	$Q$	?
n+p	$P$ 或 $Q$	从 n+2 和 n+p−1
n+p+1	$P$ 或 $Q$ 当且仅当 ($P$ 蕴含 $Q$) 蕴含 $Q$	从 1 和 n，n+1 和 n+p

(为了节省空间，我们同时构造证明的两半；通常你一次只做一半。)

在前半部分，我们需要证明 $Q$，看起来最好的方法是使用反证法。在后半部分，我们已经从前面的页面获得了足够的结果来填补其余内容。像往常一样，我们鼓励你在查看最终结果之前尝试自己填补其余内容。通过不同的方法，你甚至可能找到比给出的证明更简单的证明。

行	陈述	证明
1	$P$ 或 $Q$	假设
2	$P$ 蕴含 $Q$	假设
3	非 $Q$	假设
4	$P$	从 1 和 3
5	不是 $P$	从 2 和 3
6	$False$	从 4 和 5
7	$Q$	从 3 和 6
8	($P$ 蕴含 $Q$) 蕴含 $Q$	从 2 和 7
9	($P$ 蕴含 $Q$) 蕴含 $Q$	假设
10	不是 $P$	假设
11	$P$ 蕴含 $Q$	关于间接证明页面的命题 8。
12	$Q$	从 9 和 11
13	$P$ 或 $Q$	从 10 和 12
14	$P$ 或 $Q$ 当且仅当 ($P$ 蕴含 $Q$) 蕴含 $Q$	从 1 和 8，9 和 13

以散文形式，最好对语句进行标记，并清楚地标记正在证明哪个蕴含，以便读者可以轻松地理解证明。

命题 2： $P$ 或 $Q$ 当且仅当 ($P$ 蕴含 $Q$) 蕴含 $Q$

Proof: We first prove that $P$ or $Q$ implies (($P$ implies $Q$) implies $Q$). Assume $P$ or $Q$. Now assume $P$ implies $Q$. We need to proof $Q$, so suppose not $Q$. Then $P$ by the first assumption and not $P$ by the second assumption. This is a contradiction so we have $Q$. Therefore ($P$ implies $Q$) implies $Q$. From the original assumption $P$ or $Q$ it follows that ($P$ implies $Q$) implies $Q$, so we can conclude that $P$ or $Q$ implies (($P$ implies $Q$) implies $Q$).

现在我们证明 (($P$ 蕴含 $Q$) 蕴含 $Q$) 蕴含 $P$ 或 $Q$。假设 ($P$ 蕴含 $Q$) 蕴含 $Q$。现在假设非 $P$。那么 $P$ 蕴含 $Q$，因此 $Q$，所以 $P$ 或 $Q$。

留给读者

我们现在已经涵盖了几乎所有常用的推理规则，所以现在可以证明的语句并不缺乏。以下是一些之前结果的相对简单的扩展，一些需要一个或多个子证明，但由你来判断哪个是哪个。

命题 3: ($P$ 或 $Q$) 或 $R$ 当且仅当 $P$ 或 ($Q$ 或 $R$)

命题 4: $P$ 且 $Q$ 当且仅当 $Q$ 且 $R$

命题 5: ($P$ 且 $Q$) 且 $R$ 当且仅当 $P$ 且 ($Q$ 且 $R$)

命题 6: ($P$ 且 $Q$) 或 $R$ 当且仅当 ($P$ 或 $R$) 且 ($Q$ 或 $R$)

命题 7: ($P$ 或 $Q$) 且 $R$ 当且仅当 ($P$ 且 $R$) 或 ($Q$ 且 $R$).

命题 8: ($P$ 当且仅当 $Q$) 蕴涵 ($Q$ 当且仅当 $P$)

命题 9: ($P$ 当且仅当 $Q$) 且 ($Q$ 当且仅当 $R$) 蕴涵 ($P$ 当且仅当 $R$)

命题 10: $P$ 蕴涵 $Q$ 当且仅当 非 $P$ 或 $Q$

命题 11: 非 ($P$ 蕴涵 $Q$) 当且仅当 $P$ 且 非 $Q$

命题 11: 非 ($P$ 或 $Q$) 当且仅当 非 $P$ 且 非 $Q$

命题 12: 非 ($P$ 且 $Q$) 当且仅当 非 $P$ 或 非 $Q$

命题 13: ($P$ 当且仅当 $Q$) 蕴涵 ($P$ 蕴涵 $R$) 当且仅当 ($Q$ 蕴涵 $R$)

命题 14: ($P$ 当且仅当 $Q$) 蕴含 ($R$ 蕴含 $P$ 当且仅当 $R$ 蕴含 $Q$)

命题 15: $P$ 当且仅当 非非 $P$

等价陈述组

在某些情况下，一个定理可能表明几个陈述的组彼此等价。例如，定理的陈述可能以以下形式：

定理： 以下是等价的

1. 陈述 1

2. 陈述 2

3. 陈述 3

4. 陈述 4

这意味着陈述 1 当且仅当陈述 2，陈述 1 当且仅当陈述 3，... 陈述 3 当且仅当陈述 4，共 6 种可能的变体。证明这种定理的通常方法是证明一个循环中的蕴含关系。在这种情况下，您将证明：

P1: 陈述 1 蕴含陈述 2

P2: 陈述 2 蕴含陈述 3

P3: 陈述 3 蕴含陈述 4

P4: 陈述 4 蕴含陈述 1

这是非常有效的，因为通过证明仅仅四个蕴含关系，您实际上证明了四个陈述中的任意两个之间的所有 12 种可能的蕴含关系。之所以能这样做，是因为反复应用了以下公式：

命题 13: ($P$ 蕴含 $Q$) 并且 ($Q$ 蕴含 $R$) 蕴含 ($P$ 蕴含 $R$)

证明：（这是对先前结果的简单应用，留作练习。）

作为进一步的练习，证明以下结论：

P1 并且 P2 并且 P3 并且 P4 蕴含（陈述 1 当且仅当陈述 3）

替换

当两个陈述在逻辑上等价时，它们具有相同的真值。因此，声称如果 $P$ 等价于 $Q$ 并且 $E(P)$ 是包含 $P$ 的表达式，则 $E(P)$ 等价于 $E(Q)$，其中 $E(Q)$ 是通过用 $Q$ 替换 $P$ 从 $E(P)$ 中获得的。

作为此应用方式的示例，我们从上面第 15 条推论得知 $P$ 等价于非非 $P$。然后，我们希望得出结论：

非非 $P$ 蕴涵 $R$ 或 ($Q$ 当且仅当 $S$)

等价于

$P$ 蕴涵 $R$ 或 ($Q$ 当且仅当 $S$)

无需进行单独的证明。

这是一个有效的结论，但证明它的工具属于数学逻辑的范畴，超出了本书的范围。然而，我们可以针对具体情况进行证明，一些示例表明了如何构建这些证明。如果表达式 $E(P)$ 仅涉及蕴涵和逻辑常数 $False$，那么我们可以重复应用上面第 13 和 14 条推论。

例如，如果 $E(P)$ 是

$Q$ 蕴涵 ($P$ 蕴涵 $R$)

那么我们可以证明

$Q$ 蕴涵 ($P$ 蕴涵 $R$)

等价于

$Q$ 蕴涵 (非非 $P$ 蕴涵 $R$)

如下所示

非非 $P$ 等价于 $P$ (根据命题 15)

非非 $P$ 蕴涵 $R$ 等价于 $P$ 蕴涵 $R$ (根据命题 13)

$Q$ 蕴涵 (非非 $P$ 蕴涵 $R$) 等价于 $Q$ 蕴涵 ($P$ 蕴涵 $R$) (根据命题 14)

对于涉及其他逻辑连接词的表达式，我们可以使用我们根据蕴涵给出的定义，将表达式转换为之前类型中的一个表达式。