数学证明和数学原理/逻辑/使用合取和析取的证明

我们已经了解了直接证明和间接证明，但到目前为止，我们还没有讨论合取和析取的推理规则。我们将在否定中定义这些，就像我们之前对否定的定义一样。

析取

我们把非 $P$ 蕴含 $Q$ 作为 $P$ 或 $Q$ 的定义。

首先我们必须确保这与我们之前对 $P$ 或 $Q$ 的定义一致。根据那个定义，$P$ 或 $Q$ 仅在 $P$ 为假且 $Q$ 为假时才为假。但非 $P$ 蕴含 $Q$ 仅在非 $P$ 为真时，换句话说，$P$ 为假，且 $Q$ 为假时才为假。

我们可以通过将此定义与蕴含的推理规则结合，将此定义转化为两个新的推理规则。

如果通过假设非 $P$ 可以推导出 $Q$，然后推导出 $P$ 或 $Q$.

从非 $P$，$P$ 或 $Q$ 推断 $Q$。

例证证明 #1

让我们应用这些来证明关于析取的一个基本事实。

命题 1： $P$ 或 $Q$ 蕴含 $Q$ 或 $P$。

和之前一样，我们先建立一个基本框架。

行	陈述	理由
1	$P$ 或 $Q$	假设
(某事)
n	$Q$ 或 $P$	?
n+1	$P$ 或 $Q$ 蕴含 $Q$ 或 $P$	从 1 和 n

从定义中引出的第一个推理规则来看，证明析取的方法是假设第一个陈述的否定并推导出第二个陈述。另外，第二个规则给了我们一种使用假设的方法。将此添加到证明中

行	陈述	理由
1	$P$ 或 $Q$	假设
2	非 $P$ 蕴含 $Q$	从 1
3	非 $Q$	假设
(某事)
n−1	$P$	?
n	$Q$ 或 $P$	从 2 和 n−1
n+1	$P$ 或 $Q$ 蕴含 $Q$ 或 $P$	从 1 和 n

现在我们需要将非 $P$ 蕴含 $Q$ 与非 $Q$ 组合起来，但前一页有几种组合蕴含和否定的方法。最有用的是命题 4，由此可以完成证明的其余部分。

行	陈述	理由
1	$P$ 或 $Q$	假设
2	非 $P$ 蕴含 $Q$	从 1
3	非 $Q$	假设
4	非 $Q$ 意味着非非 $P$	根据上一页的命题 4 应用于 2。
5	非非 $P$	根据 3 和 4
6	$P$	根据 5
7	$Q$ 或 $P$	根据 2 和 6
8	$P$ 或 $Q$ 蕴含 $Q$ 或 $P$	根据 1 和 7

用散文形式表达

命题 1: $P$ 或 $Q$ 意味着 $Q$ 或 $P$

证明：假设 $P$ 或 $Q$。这意味着非 $P$ 蕴含 $Q$。现在假设非 $Q$。从上一页的命题 4 我们有非 $Q$ 蕴含 非非 $P$，因此非非 $P$，所以 $P$。因此 $Q$ 或 $Q$。从原始假设 $P$ 或 $Q$ 可以得出 $Q$ 蕴含 $P$，因此我们可以得出结论，$P$ 或 $Q$ 蕴含 $Q$ 或 $P$。

将此命题与定义中的推理规则结合，我们得到另外两个

如果假设不成立$Q$，可以推导出$P$，然后推导出$P$ 或 $Q$。

从不成立$Q$，$P$ 或 $Q$ 推导出$P$。

留给读者（析取）

命题 2: $P$ 蕴含 $P$ 或 $Q$。

命题 3: $Q$ 蕴含 $P$ 或 $Q$。

命题 4: 不成立（$P$ 或 $Q$）蕴含不成立 $P$。

命题 5: 不成立（$P$ 或 $Q$）蕴含不成立 $Q$。

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

合取

我们对合取的定义比对析取的定义更复杂。具体来说，我们把语句非（非 $P$ 或 非 $Q$) 定义为 $P$ 与 $Q$ 的定义。

同样，我们需要确保这个定义与之前给出的定义一致。语句 $P$ 与 $Q$ 为真，当且仅当 $P$ 为真且 $Q$ 为真。另一方面，语句非（非 $P$ 或 非 $Q$) 为真，当且仅当 非 $P$ 或 非 $Q$ 为假。这等同于说非 $P$ 为假且非 $Q$ 为假，这等同于说 $P$ 为真且 $Q$ 为真，这与之前的定义相符。

这个定义在生成推理规则方面相当繁琐，但它意味着一些可以替代使用的其他语句。我们只给出证明的提示，并将细节留给读者补充。

命题 7: $P$ 和 $Q$ 蕴含 $P$.

(应用定义和命题 4.)

这产生推理规则

从 $P$ 和 $Q$ 推导出 $P$.

命题 8: $P$ 和 $Q$ 蕴含 $Q$.

(应用定义和命题 5.)

这产生推理规则

从 $P$ 和 $Q$ 推导出 $Q$.

命题 9: $P$ 蕴含 ($Q$ 蕴含 $P$ 和 $Q$.

(为了证明 $P$ 和 $Q$, 假设非 $P$ 或者 非 $Q$, 然后推导出矛盾.)

这产生推理规则

从 $P$, $Q$ 推导出 $P$ 和 $Q$.

连接词在列出陈述所需的多项假设时非常有用，例如 $P$ 和 $Q$ 意味着 $R$。到目前为止，我们一直使用 $P$ 意味着 ($Q$ 意味着 $R$) 来做到这一点。我们留给读者证明 

命题 10：($P$ 意味着 ($Q$ 意味着 $R$)) 意味着 ($P$ 和 $Q$ 意味着 $R$).

和

命题 11：($P$ 和 $Q$ 意味着 $R$) 意味着 ($P$ 意味着 ($Q$ 意味着 $R$)).

留给读者（连接词）

命题 12：$P$ 和 $Q$ 意味着 $Q$ 和 $P$.

命题 13： ($P$ 和 $Q$) 并且 $R$ 蕴含 $P$ 并且 ($Q$ 并且 $R$).

命题 14： ($P$ 和 $Q$) 或 $R$ 蕴含 ($P$ 或 $R$) 并且 ($Q$ 或 $R$).

命题 15： ($P$ 或 $R$) 并且 ($Q$ 或 $R$) 蕴含 ($P$ 并且 $Q$) 或 $R$.

命题 16: ($P$ 或 $Q$) 且 $R$ 蕴涵 ($P$ 且 $R$) 或 ($Q$ 且 $R$).

命题 17: ($P$ 且 $R$) 或 ($Q$ 且 $R$) 蕴涵 ($P$ 或 $Q$) 且 $R$.

情况证明

这是一种重要的证明方法，虽然它只是我们已经见过的证明方法的应用。其思想是，当你试图证明一个陈述 $R$ 时，有时如果有假设可以利用，就会更容易。换句话说，证明 $P$ 蕴涵 $R$ 比直接证明 $R$ 更容易。假设你已经证明了 $P$ 或 $Q$。如果你能证明 $P$ 蕴涵 $R$，然后证明 $Q$ 蕴涵 $R$，那么 $R$ 似乎就随之得证了。

在证明中，这可能类似这样表达:

我们有 $P$ 或 $Q$

情况一: $P$

(某事)

$R$

情况二: $Q$

(某事)

$R$

所以 $R$.

将这个想法写成一个命题，得到

命题 18: ($P$ 或 $Q$) 且 (($P$ 蕴涵 $R$) 且 ($Q$ 蕴涵 $R$)) 蕴涵 $R$

我们可以使用其他推理规则来证明这一点。这留作间接证明的练习。

将此作为推理规则来表述

如果通过假设$P$可以推导出$R$，并且通过假设$Q$可以推导出$R$，并且$P$或$Q$，$R$.

作为一个练习，应用这条推理规则来构造命题 14 到 17 的更简单的证明。