数学证明与数学/逻辑/逻辑联结词原理

在上一节中，我们已经清楚地说明了什么叫数学命题。在本节中，我们将讨论如何将数学命题组合起来构成更复杂的命题。这可以通过使用所谓的“逻辑联结词”或“逻辑运算符”来完成。您可以将这些联结词看作是一个或多个变量的函数，其中变量可以是真或假，函数的值也可以是真或假。数学中常用的逻辑联结词有否定、合取、析取、蕴涵和等价，这些都是您在日常英语中会遇到的东西的复杂说法。

在本节中，符号 $P$ 和 $Q$ 表示数学命题。

否定

命题 $P$ 的否定是指命题 $P$ 不真。表达这一点的一些方法是

非 $P$.

它是假的 $P$.

例子

语句	否定
2005 年 9 月 1 日下雨了。	2005 年 9 月 1 日没有下雨。
所有老师都是女性。	并非所有老师都是女性。
迈克的狗有一条黑色的尾巴。	迈克的狗没有黑色的尾巴。
2 + 2 = 4	2 + 2 ≠ 4。
三角形 ABC 是等边的。	三角形 ABC 不是等边的。

否定将逻辑命题的真假值反转。换句话说，非 $P$ 为假，当 $P$ 为真，而非 $P$ 为真，当 $P$ 为假。以表格形式

$P$	非 $P$
真	假
假	真

否定的逻辑符号是“$\lnot$”，因此您可以将“非 $P$” 写成 $\lnot P$。

虽然“非”是最简单的逻辑运算符，但在试图证明某些对象是否具有某些属性时，命题的否定很重要。它使能够正确否定命题的能力成为一项重要的技能。

合取

两个语句 $P$ 和 $Q$ 的合取是表示 $P$ 和 $Q$ 都为真时的语句。有些表达方式如下：

$P$ 并且 $Q$.

$P$ 但是 $Q$.

$P$ 然而 $Q$.

注意，英语中的表达方式有时会包含“并且”一词无法表达的含义。例如，语句

虽然下雨了，但我们玩得很开心。

表达了这样一种意思：下雨的事实会让你觉得很难玩得开心。但在逻辑上，该语句等同于

我们玩得很开心，并且下雨了。

因为两者都结合了以下两个陈述：

我们玩得很开心。

并且

下雨了。

例子

第一个陈述	第二个陈述	合取
大厅很长。	大厅很暗。	大厅又长又暗。
所有老师都是女性。	所有的老师都是人类。	所有的老师都是女性人类。
迈克的狗有一条黑色的尾巴。	迈克的狗鼻子是湿的。	迈克的狗有黑色的尾巴，并且鼻子是湿的。
4 是偶数。	6 是奇数。	4 是偶数，并且 6 是奇数。
三角形 ABC 是等边的。	三角形 ABC 是等角三角形。	三角形 ABC 是等边等角三角形。

合取将两个陈述的断言合并成一个陈述。如果不循环，很难说得更具体，但你可以说 $P$ 并且 $Q$ 为真，当且仅当 $P$ 和 $Q$ 都为真，当且仅当 $P$ 或 $Q$ 为假。表格形式如下

$P$	$Q$	$P$ 并且 $Q$
真	真	真
真	假	假
假	真	假
假	假	假

合取的逻辑符号是“$\land$”，因此您可以将 $P\land Q$ 写成 $P$ 和 $Q$。

析取

两个语句 $P$ 和 $Q$ 的析取是指至少其中一个语句 $P$ 和 $Q$ 为真。一些表达方式如下：

$P$ 或 $Q$。

$P$ 除非 $Q$。

在数学中，异或从不使用，因此

$P$ 或 $Q$。

总是表示

$P$ 或 $Q$，或两者都为真。

这与英语形成对比，在英语中，异或通常由语境暗示，例如

你可以选择大盒子或幕帘 2 后面的东西。

在数学中，很少需要使用异或，如果需要，可以添加短语“但不能同时”，以明确表达意思。

例子

第一个陈述	第二个陈述	析取
大厅很长。	大厅很暗。	大厅要么很长要么很暗。
迈克的狗有一条黑色的尾巴。	戴夫的狗有一条黑色的尾巴。	迈克的狗或戴夫的狗有一条黑色的尾巴。
4 是偶数。	6 是奇数。	4 是偶数或 6 是奇数。
三角形 ABC 是等腰三角形。	三角形 ABC 是不等边三角形。	三角形 ABC 或是等腰三角形或是不等边三角形。

析取提供两种可能性，由两个语句给出。同样，在不循环的情况下，很难更具体，但你可以说 $P$ 或 $Q$ 为真，当 $P$ 或 $Q$ （或两者）为真时，当 $P$ 和 $Q$ 均为假时，则为假。以表格形式

$P$	$Q$	$P$ 或 $Q$
真	真	真
真	假	真
假	真	真
假	假	假

析取的逻辑符号是“$\lor$”，所以你可以写 $P\lor Q$ 来表示 $P$ 和 $Q$。

蕴涵

蕴涵可能是最重要的，但也是最令人困惑的逻辑连接词。事实上，它甚至有一个以它命名的悖论。

两个语句 $P$ 和 $Q$ 的蕴涵是指语句 $Q$ 为真，只要 $P$ 为真。一些表达方式是

$P$ 蕴涵 $Q$。

如果 $P$ 则 $Q$。

$P$ 只有在 $Q$ 的情况下才成立。

$Q$ 如果 $P$ 成立。

$Q$ 是 $P$ 的必要条件。

$P$ 是 $Q$ 的充分条件。

当我们在英语中使用 "If ... then ..." 这个短语时，通常意味着存在某种因果关系。例如，这句话

如果下雨，交通就会很糟糕。

在某种程度上包含了下雨会导致交通状况糟糕的想法。但从逻辑的角度来看，这两个语句之间并不一定存在这种联系。这就是悖论，即“实质蕴涵的悖论”之一，出现的地方。也就是说，如果 $P$ 是一个错误的陈述，那么蕴涵 $P$ 蕴涵 $Q$ 是真的，即使 $P$ 和 $Q$ 之间没有任何联系。例如

如果 0=1，那么月球是由奶酪做的。

在逻辑上是正确的，即使月球是否是由奶酪制成的与 0 是否等于 1 无关。

这种情况可能看起来很奇怪，这就是为什么它被称为悖论。所以也许询问你什么时候可以说语句 $P$ 蕴涵 $Q$ 是假的，而不是你什么时候可以说它是真的，会更有帮助。想象你的牙医对你说

如果你吃很多糖，你就会有更多的蛀牙。

这是两个陈述之间的蕴涵

你吃很多糖。

并且

你会有更多的蛀牙。

现在假设你想要证明你的牙医错了，并说：“哈！你不知道你在说什么。我要去别的地方看牙医。” 如果你远离糖并且没有蛀牙，那么你的牙医是对的。 如果你远离糖，但仍然有蛀牙，那么你的牙医可以问“你吃饭后刷牙了吗？” 你会说“没有”，你的牙医会说“你看吧！” 并且仍然是对的。 你唯一能证明你的牙医错了的方式是吃很多糖，但没有蛀牙。

这个事实实际上在某些情况下很有用，因为它在逻辑上是有效的，所以在证明中使用它没有什么错。

例子

第一个陈述	第二个陈述	蕴涵
大厅很长。	大厅里有许多门。	如果大厅很长，那么它就有很多门。
迈克的狗鼻子是湿的。	迈克的狗很健康。	如果迈克的狗的鼻子湿润，那么它就健康。
4 是偶数。	6 是奇数。	如果 4 是偶数，那么 6 是奇数。
三角形 ABC 是等边的。	三角形 ABC 是等腰三角形。	如果三角形 ABC 是等边三角形，那么它是等腰三角形。

正如我们所见，蕴涵 $P$ 蕴涵 $Q$ 当 $P$ 为假时为真。当 $Q$ 为真时也为真，只有当 $P$ 为真且 $Q$ 为假时才为假。表格形式如下

$P$	$Q$	$P$ 或 $Q$
真	真	真
真	假	假
假	真	真
假	假	真

蕴涵的逻辑符号是 “$\implies$”，尽管 “$\supset$” 有时也会出现。因此你可以写成 $P\implies Q$ 表示 $P$ 蕴涵 $Q$。

不像 $P$ 和 $Q$ 以及 $P$ 或 $Q$，$P$ 蕴涵 $Q$ 的值可能在你交换 $P$ 与 $Q$ 时发生改变。换句话说

$P$ 蕴涵 $Q$

并不总是与

$Q$ 意味着 $P$.

这两个语句是相关的，我们称语句

$Q$ 意味着 $P$

为 “逆命题”。

$P$ 蕴涵 $Q$

蕴含在数学中扮演着重要的角色，因为大多数定理都采用蕴含的形式。

等价

我们接下来要讨论的最后一个连接词是等价。它在英语中并不常见，所以表达等价关系的一些方式可能不熟悉。但它在数学中足够重要，因此拥有自己的术语。

两个语句 $P$ 和 $Q$ 的等价关系是，$P$ 和 $Q$ 具有相同的真值。另一种说法是 $P$ 意味着 $Q$，并且 $Q$ 意味着 $P$.

表达等价关系的一些方式是

$P$ 等价于 $Q$.

$P$ 当且仅当 $Q$.

$P$ 正好当 $Q$.

$P$ 当且仅当 $Q$。 (iff 是 “当且仅当” 的缩写)。

$P$ 是 $Q$ 的充分必要条件。

例子

第一个陈述	第二个陈述	等价
4 是偶数。	6 是奇数。	4 是偶数当且仅当 6 是奇数。
三角形 ABC 是等边的。	三角形 ABC 是等角三角形。	三角形 ABC 是等边三角形当且仅当它是等角三角形。

当 $P$ 和 $Q$ 的真值相同，$P$ 当且仅当 $Q$ 为真，当它们具有不同的真值时为假。换句话说，$P$ 当且仅当 $Q$ 为真，当 $P$ 和 $Q$ 同时为真或同时为假，而 $P$ 当且仅当 $Q$ 为假，是 $P$ 和 $Q$ 中一个为真而另一个为假。表格形式如下

$P$	$Q$	$P$ 或 $Q$
真	真	真
真	假	假
假	真	假
假	假	真

蕴涵的逻辑符号是 "$\iff$"，所以你可以写 $P\iff Q$ 来表示 $P$ 当且仅当 $Q$。

语句

$P$ 当且仅当 $Q$

说明以下蕴涵

$P$ 蕴涵 $Q$

及其逆命题都是真的。

复杂表达式

利用以上给出的连接词，我们可以构建更复杂的表达式。例如

(非 $P$) 或 $Q$

($P$ 或 $Q$) 并且 $R$

为了避免写过多的括号，存在优先级规则来决定不明确表达式中运算的顺序。最高优先级是“非”，因此你永远不需要在“非 $P$”周围添加括号。接下来是“与”和“或”，它们具有相同的优先级。然后是“蕴含”和最后是“当且仅当”。

例如，上面第一个例子可以更简单地写成

非 $P$ 或 $Q$

但第二个例子不能简化。

可以证明，任何逻辑连接词在任意数量的变量中都可以表示为上面给出的连接词的某种组合。事实上，你实际上只需要“非”、“与”和“或”。我们在这里不会证明这一点，因为它实际上是逻辑而不是数学中的一个定理，但我们可以通过构造异或的表达式来给你基本思路。首先，列出连接词为真的条件；在本例中，$P$ 异或 $Q$ 为真时，$P$ 为真，而 $Q$ 为假，或者 $P$ 为假，而 $Q$ 为真，否则为假。现在将每个条件列出为一个合取，因此在本例中我们得到

$P$ 并且 非 $Q$

并且

非 $P$ 并且 $Q$

最后，形成前面步骤中形成的所有语句的析取，因此最终结果，我们可以将其作为 $P$ 异或 $Q$ 的定义是

($P$ 且不为 $Q$) 或 (不为 $P$ 且为 $Q$)