数学证明/逻辑

正如在引言中讨论的那样，逻辑语句不同于普通英语。 我们将讨论“或”、“与”、“如果”、“仅当”之类的概念。（在这里我想指出，在大多数数学论文中，在指代自己时使用“我们”是可以接受的。这被认为是礼貌的，既不会命令听众做某事，也不会将他们排除在讨论之外。）

真值和语句

我们在数学中经常遇到语句。

定义。 (语句) 一个语句 是一个陈述句，要么是真要么是假（但不能两者兼而有之），它的真值 是真（用$T$ 表示）或假（用$F$ 表示）。

例子。 考虑以下句子

1. 数字 9 是偶数。
2. $1<2$.
3. 数学很容易。
4. 如何解$x^{2}+2x-3=0$?
5. 请阅读这本书。

• 上面 1 和 2 句是语句（即使 1 句是假的）。
• 3、4 和 5 句不是语句，因为它们不是陈述句，我们无法确定它们是真是假。

• 特别是，3 句是观点，4 句是问题，5 句是命令。因此，它们都不是陈述句。

练习。

句子“$\pi$的小数展开式中第 123 位是 3”是一个语句吗？

	是。
	否。

对于那些不是语句的句子，其中有一种特殊的句子类型，即开放语句。

定义。 (开放语句) 一个开放语句 是一个句子的真值取决于某些变量的输入。

备注。

• 由于真值可能会随着输入的改变而改变，因此我们无法确定开放语句的真值（我们不能说它总是真或总是假）。

例子。 考虑句子$P(x):x=2$ ($:$ 读作“使得”）。

• 当$x=2$时，该句子为真，否则为假。
• 该句子是一个开放语句。

为了表示一些语句真值的所有可能组合，我们通常将它们列在一个表中，称为真值表。

示例.（两个命题的真值表）对于两个命题 $P$ 和 $Q$，它们的真值表如下：$${\begin{array}{|c|c|}P&Q\\\hline T&T\\T&F\\F&T\\F&F\\\end{array}}$$，$P$ 和 $Q$ 的真值共有四种可能的组合。

示例.（三个命题的真值表）对于三个命题 $P$，$Q$ 和 $R$，它们的真值表如下：$${\begin{array}{|c|c|c|}P&Q&R\\\hline T&T&T\\T&T&F\\T&F&T\\T&F&F\\F&T&T\\F&T&F\\F&F&T\\F&F&F\\\end{array}}$$，$P$，$Q$ 和 $R$ 的真值共有八种可能的组合。

备注。

• 一般来说，$\underbrace {2\times \dotsb \times 2} _{n{\text{ times}}}=2^{n}$ 种可能的 $n$ 个命题的真值组合，因为每个命题都有两种可能的真值。
• 三个命题的真值表看起来可能很复杂，如果你不够小心，可能会遗漏（或重复）真值表中的一些组合。因此，这里有一些构建这种真值表的建议：

• 对于 $P$，从上到下写四个 $T$，然后是四个 $F$；
• 对于 $Q$，从上到下写以下模式：$TTFFTTFF$；
• 对于 $R$，从上到下以这种模式书写：$TFTFTFTF$.

合取、析取和否定

在本节中，我们将讨论一些将两个语句合并成一个语句的方法（合取和析取），类似于 数学证明/集合论导论#集合运算，其中两个集合被合并成一个集合。此外，我们还将讨论一种将语句更改为另一个语句的方法（否定）。

合取

定义。 （合取）语句 $P$ 和 $Q$ 的 合取，记为 $P\land Q$，是一个当 两个 $P$ 和 $Q$ 都为真时为真，否则为假。

备注。

• $P\land Q$ 读作 "P 且 Q"，语句 $P$ 和 $Q$ 的合取也可以直接用 "$P$ 且 $Q$" 来表达。

示例。 （$P\land Q$ 的真值表）$P\land Q$ 的真值表（根据 $P$ 和 $Q$ 的真值可能组合表示）为 $${\begin{array}{|c|c|c|}P&Q&P\land Q\\\hline T&T&T\\T&F&F\\F&T&F\\F&F&F\\\end{array}}$$

• 我们可以看到，$P\land Q$ 只有当 同时 $P$ 和 $Q$ 都为真时才为真，否则为假。

析取

定义. (析取) 语句 $P$ 和 $Q$ 的 析取，记作 $P\lor Q$，是一个语句，只有当 同时 $P$ 和 $Q$ 都为假时才为假，否则为真。

备注。

• 也就是说，$P\lor Q$ 当 至少 $P$ 和 $Q$ 之一为真时才为真，否则为假。
• $P\lor Q$ 读作 "P 或 Q"，语句 $P$ 和 $Q$ 的析取也可以直接用 "$P$ 或 $Q$" 来表达。
• "或" 在数学中的含义可能与 "或" 作为英语单词的含义不同。在数学中，"或" 是 包含性 的，即 $P$ 或 $Q$ 表示 $P$ 或 $Q$ 或两者都成立。然而，作为英语单词，"或" 可能是 排斥性 的，即 $P$ 或 $Q$ 表示 $P$ 或 $Q$ 但不能两者都成立。例如，当有人说 "我今天下午要去图书馆或去公园" 时，我们理解为 "我要么去图书馆，要么去公园，但不能两者都去"。

示例。 ($P\lor Q$ 的真值表) $P\lor Q$ 的真值表是 $${\begin{array}{|c|c|c|}P&Q&P\lor Q\\\hline T&T&T\\T&F&T\\F&T&T\\F&F&F\\\end{array}}$$

• 我们可以看到，$P\lor Q$ 只有当 两者 $P$ 和 $Q$ 都为假时才为假，其他情况都为真。

否定

定义。 语句 $P$ 的 否定，记为 $\sim P$，是一个真值与 $P$ 相反的语句。

备注。

• $~P$ 读作 "非 P"，语句 $P$ 的否定也可以直接用 "非 $P$" 或 "不是 $P$" 来表达。
• 语句 $P$ 否定的另一种常用记法是 $\lnot P$。
• 我们将表达语句否定的过程称为 否定 语句。

示例。 ($\sim P$ 的真值表) $\sim P$ 的真值表是 $${\begin{array}{|c|c|}P&\sim P\\\hline T&F\\F&T\\\end{array}}$$

• 我们可以看到，$\sim P$ 的真值总是与 $P$ 相反。

要否定一个陈述，我们通常会在陈述中添加“不”字，或从陈述中删除“不”字。例如，陈述“数字 4 是偶数。”的否定是“数字 4 不是 偶数。”，而陈述“数字 1 不是质数。”的否定是“数字 1 不是 质数。”

练习。 完成以下真值表：$${\begin{array}{|c|c|c|c|c|c|}P&Q&\sim P&\sim Q&P\lor Q&(\sim P)\lor (\sim Q)&\sim (P\lor Q)\\\hline T&T\\T&F\\F&T\\F&F\\\end{array}}$$

答案

$${\begin{array}{|c|c|c|c|c|c|}P&Q&\sim P&\sim Q&P\lor Q&(\sim P)\lor (\sim Q)&\sim (P\lor Q)\\\hline T&T&{\color {red}F}&{\color {red}F}&{\color {red}T}&{\color {red}F}&{\color {red}F}\\T&F&{\color {red}F}&{\color {red}T}&{\color {red}T}&{\color {red}T}&{\color {red}F}\\F&T&{\color {red}T}&{\color {red}F}&{\color {red}T}&{\color {red}T}&{\color {red}F}\\F&F&{\color {red}T}&{\color {red}T}&{\color {red}F}&{\color {red}T}&{\color {red}T}\\\end{array}}$$

• 我们可以观察到，在一些$P$和$Q$的真值组合中，$(\sim P)\lor (\sim Q)$和$\sim (P\lor Q)$的真值是不同的。

练习。 令$P$为陈述“数字 3 是偶数”，而$Q$为陈述“数字${\sqrt {2}}$是无理数。”

写下（用文字）$P$和$Q$的每个否定的形式 不要使用“不”字。

答案

• 对 $P$ 的否定可以是“数字 3 是奇数”。
• 对 $Q$ 的否定可以是“数字 ${\sqrt {2}}$ 是有理数”。

练习。 令 $P$ 为语句 $3>5.$，$Q$ 为语句 $3<2.$。

(a) 语句 $\sim (P\land Q)$ 为真还是假？

(b) 语句 $\sim (P\lor Q)$ 为真还是假？

(c) 语句 $(\sim P)\land (\sim Q)$ 为真还是假？

(d) 语句 $(\sim P)\lor (\sim Q)$ 为真还是假？

答案

• 首先，我们可以看到 $P$ 和 $Q$ 都是假命题。

(a) 由于 $P\land Q$ 是假命题，答案为 真。

(b) 由于 $P\lor Q$ 是假命题，答案为 真。

(c),(d) 由于 $\sim P$ 和 $\sim Q$ 都是真命题，(c) 和 (d) 的答案都是 真。

条件句

除了以上几种构成新语句的方式之外，我们还有一种非常常见的构成方式，即“如果-那么组合”。使用“如果-那么组合”构成的语句被称为条件句。

定义。 (条件语句) 两个语句 $P$ 和 $Q$ 的 条件语句 是指“如果 $P$ 那么 $Q$”，记作 $P\to Q$。 $P$ 和 $Q$ 分别被称为条件语句的 假设 和 结论。 条件语句 $P\to Q$ 当 $P$ 为真而 $Q$ 为假时为 假，其他情况下为 真。

示例。 ($P\to Q$ 的真值表) $P\to Q$ 的真值表为 $${\begin{array}{|c|c|c|}P&Q&P\to Q\\\hline T&T&T\\T&F&F\\F&T&T\\F&F&T\\\end{array}}$$

• 我们可以观察到，特别地，即使假设 $P$ 为假，根据定义 ，条件语句 $P\to Q$ 为真。
• 另一个观察是，当结论为真时，无论假设是真还是假，条件语句都必须为真（参见第 1 行和第 3 行）。

为了更直观地理解为什么当假设为假时，条件语句始终为真，请考虑以下示例。

示例。 假设鲍勃正在修一门名为 MATH1001 的数学课程。MATH1001 的课程讲师警告鲍勃，如果他在这门课程的期末考试中不及格，那么他将在这门课程中不及格。令 $P$ 表示“鲍勃在 MATH1001 的期末考试中不及格”，而 $Q$ 表示“鲍勃在 MATH1001 中不及格”。那么，课程讲师所说的话是“$P\to Q$”。

为了使课程讲师所说的话为真，要么 鲍勃确实在 MATH1001 的期末考试中不及格，并且他确实在这门课程中不及格，要么 鲍勃通过了 MATH1001 的期末考试。在后一种情况下，鲍勃是否在 MATH1001 中不及格并不重要，因为课程讲师并没有承诺如果鲍勃通过了 MATH1001 的期末考试会发生什么 。

为了使课程讲师所说的话为假，唯一的情况是鲍勃在 MATH1001 的期末考试中不及格，但他仍然通过了 MATH1001 ($P$ 为真，而 $Q$ 为假)（这表明讲师在撒谎！）。

逆否命题和双条件语句

在讨论了 条件句 $P$ 和 $Q$ 之后，我们将讨论 双条件句 $P$ 和 $Q$。顾名思义，双条件句包含 两个 条件句。除了 $P\to Q$ 之外，另一个条件句是 $Q\to P$，称为条件句 $P\to Q$ 的 逆命题。

在数学中，给定条件句 $P\to Q$ 为真，我们通常想知道它的 逆命题 $Q\to P$ 是否也为真 。

示例. 上一个例子中课程讲师所做陈述的逆命题是“如果 Bob 在 MATH1001 中不及格，那么他在 MATH1001 的期末考试中不及格。”

定义. (双条件句) 两个语句 $P$ 和 $Q$ 的 双条件句，记为 $P\leftrightarrow Q$，是指 $(P\to Q)\land (Q\to P)$，也就是说，“如果 $P$ 那么 $Q$” 和“如果 $Q$ 那么 $P$”。

备注。

• 我们也可以写成 $P$ 当且仅当 $Q$。

• 为了更清楚地理解“当且仅当”这个短语，请考虑以下内容
• $P$ 当且仅当 $Q$ 可以解释为 "$P$ 如果 $Q$ 并且 $P$ 仅当 $Q$”。
• 对于 "$P$ 如果 $Q$"，应该很容易接受它意味着“如果 $Q$ 那么 $P$”。
• 对于 "$P$ 仅当 $Q$"，这意味着 $P$ 只能在 $Q$ 为真时为真。也就是说，$Q$ 是 $P$ 的 必要条件。因此，我们可以推断，当 $P$ 为真时，$Q$ 必须为真（否则 $P$ 不可能为真）。因此，"$P$ 仅当 $Q$" 意味着“如果 $P$ 那么 $Q$”。

示例。 ($P\leftrightarrow Q$ 的真值表）$P\leftrightarrow Q$ 的真值表为 $${\begin{array}{|c|c|c|}P&Q&P\to Q&Q\to P&P\leftrightarrow Q\\\hline T&T&T&T&T\\T&F&F&T&F\\F&T&T&F&F\\F&F&T&T&T\\\end{array}}$$

• 我们可以看到，当 $P$ 和 $Q$ 具有 相同 的真值（即 $P$ 和 $Q$ 均为真，或者 $P$ 和 $Q$ 均为假），否则为假。

蕴涵和逻辑等价

当条件语句 $P\to Q$ 为 真 时，我们可以说“$P$ 蕴涵 $Q$”，记作 $P\Rightarrow Q$。另一方面，当 $P$ 不 蕴涵 $Q$，即 $P\to Q$ 为 假 时，我们记作 $P\nRightarrow Q$.

我们有其他几种等价的说法来表达“$P$ 蕴涵 $Q$”，即

• $P$ 是 充分条件 $Q$ (或简而言之，$P$ 对于 $Q$ 是充分的)

• 我们称 $P$ 对于 $Q$ 是充分的，因为当 $P$ 蕴涵 $Q$ 时，“$P$ 为真”就充分 足以推断出“$Q$ 为真”。

• $Q$ 是 $P$ 的 必要条件 (或简而言之，$Q$ 对于 $P$ 是必要的)

• 我们将 $Q$ 称为 必要 条件，对于 $P$，因为当 $P$ 蕴含 $Q$ 时，当结果 $Q$ 为假时，假设不可能为真（否则条件 $P\to Q$ 将为假）。这解释了 必要 性，“$Q$ 为真”。

当 $P\Rightarrow Q$ 时，我们经常想知道 $P\to Q$ 的 逆命题 是否为真，即我们是否拥有 $Q\Rightarrow P$ 。

在 $P\Rightarrow Q$ 但 $Q\nRightarrow P$ 的情况下，我们有多种等效的方法来表达这一点

• $P$ 是 充分但非必要 条件，对于 $Q$。

• 从之前的解释中，当我们说 $P$ 对 $Q$ 是必要的，我们的意思是 $Q\Rightarrow P$。因此，当 $P$ 对 $Q$ 是 充分的 但 非必要的，我们的意思是 ${\color {blue}P\Rightarrow Q}$ 以及 ${\color {red}Q\nRightarrow P}$。

• $P$ 是一个 更强的条件 比 $Q$ （或者 $P$ 比 $Q$ 更强）。

在 $P\Rightarrow Q$ 和 $Q\Rightarrow P$ 都为真的情况下，双条件语句 $P\leftrightarrow Q$ 也为真，我们用 $P\Leftrightarrow Q$ 表示。还有多种等价的方式来表达这一点。

• $P$ 与 $Q$ 逻辑等价。

• 我们说它们是 逻辑 等价的，因为它们始终具有相同的真值（因为 $P\leftrightarrow Q$ 为真），这与 逻辑 相关。

• "$P$ 当且仅当 $Q$"（为真）。

• 回想一下，我们也使用 "$P$ 当且仅当 $Q$" 来表示 双条件 $P\leftrightarrow Q$。因此，从技术上讲，我们应该写 "$P$ 当且仅当 $Q$" 在 $P\Leftrightarrow Q$ 为真的情况下是真的。然而，我们很少在实践中这样写，通常会省略“是真的”这句话，因为它使表达式更复杂。因此，当我们在这种情况下写 "$P$ 当且仅当 $Q$" 时，我们的意思是双条件为真，而没有明确地说出来。
• 通常，当我们只写 "$P$ 当且仅当 $Q$" 时，我们有逻辑等价的含义 $P\Leftrightarrow Q$，而不是语句 $P\leftrightarrow Q$。如果我们真的想要后者的含义，我们应该说明 "$P$ 当且仅当 $Q$" 指的是一个 语句。

• $P$ 是 必要且充分 的 $Q$。

• 按照之前的解释，$P$ 是 必要 且 充分 的 $Q$ 意味着 ${\color {blue}Q\Rightarrow P}$ 和 ${\color {red}P\Rightarrow Q}$。

定理. (关于合取、析取和否定的某些规律) 在以下内容中，$P$，$Q$ 和 $R$ 是任意命题。

• ${\big (}\sim (\sim P){\big )}\Leftrightarrow P$ (双重否定)
• $P\land Q\Leftrightarrow Q\land P$ (合取的交换律)
• $P\lor Q\Leftrightarrow Q\lor P$ (析取的交换律)
• $P\land (Q\land R)\Leftrightarrow (P\land Q)\land R$ (合取的结合律)
• $P\lor (Q\lor R)\Leftrightarrow (P\lor Q)\lor R$ (析取的结合律)
• $P\lor (Q\land R)\Leftrightarrow (P\lor Q)\land (P\lor R)$ (分配律)
• $P\land (Q\lor R)\Leftrightarrow (P\land Q)\lor (P\land R)$ (分配律)
• ${\big (}\sim (P\land Q){\big )}\Leftrightarrow (\sim P)\lor (\sim Q)$ (德摩根定律)
• ${\big (}\sim (P\lor Q){\big )}\Leftrightarrow (\sim P)\land (\sim Q)$ (德摩根定律)

证明. 它们可以使用真值表来证明。

$\Box$

备注。

• 你可以观察到，集合论中也有一些类似的结果（甚至有些名字相同！），在关于集合论的章节中讨论。这是因为关于集合论的章节中讨论的结果实际上是从上面相应的结论几乎直接证明出来的。

定理. （条件语句与析取语句的桥梁）语句 $P\to Q$ 和 $(\sim P)\lor Q$ 在逻辑上是等价的。

证明. 可以使用以下真值表来证明：$${\begin{array}{|c|c|c|c|c|}P&Q&\sim P&P\to Q&(\sim P)\lor Q\\\hline T&T&F&T&T\\T&F&F&F&F\\F&T&T&T&T\\F&F&T&T&T\\\end{array}}$$

$\Box$

定理. （条件语句与其逆否命题的逻辑等价）条件语句 $P\to Q$ 的逆否命题被定义为另一个条件语句 $(\sim Q)\to (\sim P)$，它们在逻辑上是等价的。

证明. 利用条件语句与析取语句的桥梁和一些其他定律，可以证明如下：$$P\to Q\Leftrightarrow (\sim P)\lor Q\Leftrightarrow Q\lor (\sim P)\Leftrightarrow {\big (}\sim (\sim Q){\big )}\lor (\sim P)\Leftrightarrow (\sim Q)\to (\sim P).$$

$\Box$

备注。

• 当我们“突然”两次否定 $Q$ 时，似乎有些“令人惊讶”。实际上，当我们思考如何证明逻辑等价时，我们不会直接从无中生有地进行这样的操作。相反，在观察到 $P\to Q\Leftrightarrow (\sim P)\lor Q$ 和 $(\sim Q)\to (\sim P)\Leftrightarrow {\big (}\sim (\sim Q){\big )}\lor (\sim P)$ 之后，我们才“被激发”这样做。因此，我们从某种程度上来说，是以“三明治”的方式（从左到右和从右到左同时进行）完成了上述一系列等价关系。这可能对其他类似的证明很有用。
• 这个结果对于后面将要讨论的逆否命题证明法非常重要。

重言式和矛盾式

在定义重言式和矛盾式之前，我们首先需要介绍一些术语。在前面的章节中，我们已经讨论了符号 $\sim ,\lor ,\land ,\to$ 和 $\leftrightarrow$ 的含义。这些符号有时被称为 逻辑联结词，我们可以用 逻辑联结词 来构建一些复杂的语句。这些语句由至少一个给定的（或组成）语句（通常用 $P,Q,R$ 等表示）和至少一个逻辑联结词组成，被称为 复合语句。

定义。 （重言式和矛盾式） 一个 复合语句 $S$ 称为 重言式 （矛盾式），如果对于构成 $S$ 的组成语句的每个可能的真值组合，它都 为真 （为假）。

备注。

• 我们用 $\mathbf {T}$ 表示重言式，用 $\mathbf {F}$ 表示矛盾式。
• 当一个语句 $S$ 是重言式时，我们也可以写成 $S\Leftrightarrow \mathbf {T}$，因为这意味着 $S$ 和 $\mathbf {T}$ 始终具有相同的真值，并且因为 $\mathbf {T}$ 的真值始终为真，因此 $S$ 的真值也始终为真，即 $S$ 是重言式。

• 因此，当我们想要证明一个语句 $S$ 始终为真 时，一种方法是证明 $S\Leftrightarrow \mathbf {T}$。例如，如果我们想要证明 $P\to Q$ 和 $(\sim Q)\to (\sim P)$ 在逻辑上是等价的，我们可以证明 $\left[{\big (}P\to Q{\big )}\leftrightarrow {\big (}(\sim Q)\to (\sim P){\big )}\right]\Leftrightarrow \mathbf {T}$。

例子。 令 $P$ 为任意语句。那么，

• $P\lor (\sim P)$ 是重言式。
• $P\land (\sim P)$ 是矛盾式。

这是因为 $P\lor (\sim P)$ 的真值表是 $${\begin{array}{|c|c|c|}P&\sim P&P\lor (\sim P)\\\hline T&F&T\\F&T&T\\\end{array}}$$，而 $P\land (\sim P)$ 的真值表是 $${\begin{array}{|c|c|c|}P&\sim P&P\land (\sim P)\\\hline T&F&F\\F&T&F\\\end{array}}.$$

示例。 设 $P$ 和 $Q$ 是任意命题。那么，$(P\land Q)\to (P\lor Q)$ 是一个永真式，因为它的真值表是 $${\begin{array}{|c|c|c|c|c|}P&Q&P\land Q&P\lor Q&(P\land Q)\to (P\lor Q)\\\hline T&T&T&T&T\\T&F&F&T&T\\F&T&F&T&T\\F&F&F&F&T\\\end{array}}.$$

练习。 以下是关于此示例的一些进一步问题。

1 示例中命题的逆命题，$(P\lor Q)\to (P\land Q)$，是永真式，矛盾式，还是既非永真式也非矛盾式？

	永真式。
	矛盾式。
	既非永真式也非矛盾式。

2 示例中命题的否定，$\sim {\big (}(P\land Q)\to (P\lor Q){\big )}$，是永真式，矛盾式，还是既非永真式也非矛盾式？

	永真式。
	矛盾式。
	既非永真式也非矛盾式。

3 示例中命题的逆否命题，${\big (}\sim (P\lor Q){\big )}\to {\big (}\sim (P\land Q){\big )}$，是永真式，矛盾式，还是既非永真式也非矛盾式？

	永真式。
	矛盾式。
	既非永真式也非矛盾式。

证明 $(P\land Q)\to (P\lor Q)$ 是一个永真式，无需使用真值表。

答案

由于 $$(P\land Q)\to (P\lor Q)\Leftrightarrow {\big (}\sim (P\land Q){\big )}\lor (P\lor Q)\Leftrightarrow {\big (}(\sim P)\lor (\sim Q){\big )}\lor (P\lor Q)\Leftrightarrow {\big (}(\sim P)\lor P{\big )}\lor {\big (}(\sim Q)\lor Q{\big )}\Leftrightarrow \mathbf {T} \lor \mathbf {T} \Leftrightarrow \mathbf {T} ,$$ 给定的条件句是一个永真式。

一位学生声称 $(P\lor Q)\to (P\land Q)$ 是一个矛盾句，并用以下论证来支持他的观点：

由于 $(P\lor Q)\to (P\land Q)\Leftrightarrow {\big (}\sim (P\lor Q){\big )}\lor (P\land Q)\Leftrightarrow {\big (}(\sim P)\land (\sim Q)){\big )}\lor (P\land Q)\Leftrightarrow {\big (}(\sim P)\land P){\big )}\lor {\big (}(\sim Q)\land Q{\big )}\Leftrightarrow \mathbf {F} \lor \mathbf {F} \Leftrightarrow \mathbf {F}$，这个条件句是矛盾句。

评价他的说法。

答案

• 他的说法是错误的。
• 步骤 ${\big (}(\sim P)\land (\sim Q)){\big )}\lor (P\land Q)\Leftrightarrow {\big (}(\sim P)\land P){\big )}\lor {\big (}(\sim Q)\land Q{\big )}$ 是不正确的，因为我们应该在这里使用分配律而不是结合律，并且我们不能在这里对两种类型的逻辑连接符应用结合律。
• 事实上，如上述问题所示，条件句 $(P\lor Q)\to (P\land Q)$ 既不是永真式也不是矛盾句。

定理。（关于永真式和矛盾句的定律）设 $P$ 是一个任意的命题。那么，

• $P\lor \mathbf {T} \Leftrightarrow \mathbf {T}$.
• $P\land \mathbf {T} \Leftrightarrow P$.
• $P\lor \mathbf {F} \Leftrightarrow P$.
• $P\land \mathbf {F} \Leftrightarrow F$.
• $(\sim \mathbf {T} )\Leftrightarrow \mathbf {F}$.
• $(\sim \mathbf {F} )\Leftrightarrow \mathbf {T}$.

证明. 它们可以使用真值表来证明。

$\Box$

量词

回顾一下，一个 开放语句 是一个语句，其真值取决于某些变量的输入。在本节中，我们将讨论一种使用量词来将开放语句转换为语句的方法，而这种转换得到的语句被称为量化语句。例如，考虑语句“每个实数的平方是非负的”。它可以被改写为“对于每个实数 $x$，$x^{2}\geq 0$”。我们可以让 $P(x)$ 为 开放语句 “$x^{2}\geq 0$”。然后，它可以进一步改写为“对于每个实数 $x$，$P(x)$”。在这种情况下，我们可以观察到一个开放语句 ($P(x)$) 如何被转换为一个语句（对于每个实数 $x$，$P(x)$），而短语“对于每个”是一种 全称量词。其他也是全称量词的短语包括“对于每一个”，“对于所有”和“无论何时”。全称量词通常用 $\forall$（一个倒置的“A”）来表示。在引入这个符号后，我们提到的语句可以进一步改写为“$\forall x\in \mathbb {R} ,x^{2}\geq 0$”（我们在这里也使用了一些集合符号）。

一般来说，我们可以使用全称量词将一个开语句 $P(x)$ 转换为一个语句，即 "$\forall x\in S,P(x)$"，其中 $S$ 是一个（全集）集合（或域），它限制了输入 $x$。

除了全称量词之外，将开语句转换为语句的另一种方法是使用 存在量词。每个短语 "存在"、"有"、"至少有一个"、"对于某些" 、"对于至少一个" 都被称为 存在量词，并用 $\exists$（反转的 "E"）表示。例如，我们可以将语句 "某个实数的平方为负数" 改写为 "$\exists x\in \mathbb {R} ,x^{2}<0.$"（这是错误的）。

一般来说，我们可以使用存在量词将一个开语句 $P(x)$ 转换为一个语句，即 "$\exists x\in S,P(x)$"，其中 $S$ 是一个（全集）集合（或域），它限制了输入 $x$。

另一个与 存在 量词相关的量词是 唯一存在量词。每个短语 "存在唯一的"、"正好有一个"、"对于唯一的"、"对于正好一个" 都被称为 唯一存在量词，并用 $\exists !$ 表示。例如，我们可以将语句 "存在唯一的实数 $x$ 使得 $2x=0$。" 改写为 "$\exists !x\in \mathbb {R} ,2x=0$"。我们可以用存在量词和全称量词来表示唯一存在量词，通过 定义 "$\exists !x\in S,P(x)$" 为 $$\left(\exists x\in S,P(x)\right)\land \left(\forall x_{1},x_{2}\in S,P(x_{1})\land P(x_{2})\to x_{1}=x_{2}\right)$$，其中左括号是存在部分，右括号是唯一部分。换句话说，这个表达式意味着

存在一个 $x\in S$ 使得 $P(x)$ 成立，并且对于所有 $x_{1},x_{2}\in S$，如果 $P(x_{1})$ 且 $P(x_{2})$ 成立，那么 $x_{1}=x_{2}$ （即 $x_{1}$ 和 $x_{2}$ 实际上指的是同一个东西，因此存在 唯一一个 $x$ 使得 $P(x)$ 成立）。

一般来说，我们需要像上面一样分别证明存在性和唯一性来证明涉及唯一存在量词的命题。

量化命题的否定

例： 命题 "$\exists A\subseteq U,A=U$" 可以用文字 (部分) 表达为“存在一个集合 $A\subseteq U$ 使得 $A=U$。”

练习： 用文字 (部分) 写下这个命题的 否定。（提示："$n\geq 1$” （$n$ 是一个非负整数）的否定是什么？因此，“存在至少一个 $x\in S$ 使得 $P(x)$” 的否定是什么？

答案

• 提示中，“$n\geq 1$ ($n$ 是一个非负整数)”的否定是 “$n=0$”，而“至少存在一个 $x\in S$ 使得 $P(x)$”的否定因此是 “不存在 $x\in S$ 使得 $P(x)$”。它也可以等价地表示为“对于每个 $x\in S$，$P(x)$ 均不满足”，或 $\forall x\in S,\sim P(x)$。
• 受提示启发，该陈述的否定可以写成“对于每个集合 $A\subseteq U$，$A\neq U$”。

从这个例子中，我们可以看到，语句 "$\exists x\in S,P(x)$" 的否定在逻辑上等价于 "$\forall x\in S,\sim P(x)$"。现在，我们自然想知道语句 "$\forall x\in S,P(x)$" 的否定。考虑这种情况：当 $P(x)$ 不是对每个 $x\in S$ 都为真时，这意味着 $P(x)$ 对 至少一个 $x\in S$ 是假的。换句话说，$\exists x\in S,\sim P(x)$。因此，我们知道语句 "$\forall x\in S,P(x)$" 的否定在逻辑上等价于 $\exists x\in S,\sim P(x)$.

包含多个量词的量化语句

一个量化语句可以包含多个量词。当这种量化语句中只使用一种类型的量词时，情况会更简单。例如，考虑语句“对于每个实数 $x$ 以及对于每个实数 $y$，$xy$ 都是实数”。它可以写成“$\forall x\in \mathbb {R} ,\forall y\in \mathbb {R} ,xy\in \mathbb {R}$”。当我们互换“$\forall x\in \mathbb {R}$”和“$\forall y\in \mathbb {R}$”时，语句的含义不受影响（语句仍然意味着“两个任意实数的乘积是一个实数”。） 因此，我们可以简单地将语句写成“$\forall x,y\in \mathbb {R} ,xy\in \mathbb {R}$” 没有任何歧义。

对于包含两个存在量词的示例，考虑语句“存在一个实数 $x$ 和一个实数 $y$ 使得 $xy$ 是实数”。它可以写成“$\exists x\in \mathbb {R} ,\exists y\in \mathbb {R} ,xy\in \mathbb {R}$”。类似地，互换“$\exists x\in \mathbb {R}$”和“$\exists y\in \mathbb {R}$” 不会影响语句的含义（语句仍然意味着“对于至少一对实数 $x$ 和 $y$，$xy$ 是实数”。） 因此，我们可以简单地将语句写成“$\exists x,y\in \mathbb {R} ,xy\in \mathbb {R}$” 没有任何歧义。

然而，当这两种类型的量词都用于这样的量化语句时，事情就会变得更加复杂。例如，考虑语句“对于每个整数 $x$，存在一个整数 $y$ 使得 $y<x$。” 这也可以写成“$\forall x\in \mathbb {Z} ,\exists y\in \mathbb {Z} ,y<x$”。这意味着对于每个整数，我们都可以找到一个（严格）更小的整数，我们可以看到这是一个真命题。例如，如果你选择 $x=13$，我可以选择 $y=-99,0$ 或者 $12$。事实上，对于你选择的整数 $x$，我总是可以将我的 $y$ 选择为 $x-1$，使得 $y<x$。

让我们看看如果我们交换“$\forall x\in \mathbb {Z}$” 和 “$\exists y\in \mathbb {Z}$” 会发生什么。这个语句就变成了 $\exists y\in \mathbb {Z} ,\forall x\in \mathbb {Z} ,y<x$，这意味着存在一个整数 $y$，使得它（严格地）小于所有整数 $x$！这是错误的，因为例如，没有一个整数（严格地）小于它自身（它本身就是一个整数）。在这个例子中，我们可以看到，交换全称量词和存在量词的位置会改变语句的含义。因此，清楚地理解包含全称量词和存在量词的量化语句的含义非常重要。为了便于理解，这里有一些阅读此类语句的技巧。

对于与量词 $\exists$ 关联的变量，它可能取决于语句中前面介绍的变量，但必须独立于语句中后面介绍的变量。

What does it mean? For example, consider the above example. In the first case, we have $\forall x\in \mathbb {Z} ,\exists y\in \mathbb {Z} ,y<x.$. Then, since the variable $x$ appears earlier than the variable $y$ which associated to $\exists$, $y$ may depend on $x$ (This is similar to the case in English. In a sentence, a thing may depend on other things mentioned earlier.). For instance, when you choose $x=13$, and I choose $y=12$. Then, $y<x$. However, if you change your choice to $x=9$, then my $y=12$ does not work, and I need to change my $y$ to, say, 8 so that $y<x$. Then, we can see that $y$ depends on $x$ in this case. In the second case, we have $\exists y\in \mathbb {Z} ,\forall x\in Z,y<x$. In this case, the variable $x$ appears later than the variable $y$. Hence, the variable $y$ must be independent from from $x$. That is, when such $y$ is determined, it needs to satisfy $y<x$ for each $x$ chosen, and the $y$ cannot change depend on what $x$ is. Indeed, $y$ cannot possibly depend on $x$, since $y$ is supposed to be determined when $x$ is not even introduced!

练习

在以下问题中，$P,Q,R,S$ 是命题。

A. 为以下每个命题构造真值表，并给出它的逆命题和否命题

1. $\sim P\to Q$
2. $P\to (\sim Q)$
3. $(P\lor Q)\to R$
4. $(P\land Q)\to (R\lor S)$
5. $(R\to S)\to (P\to Q)$

B. 对以下语句进行否定

1. $P\land Q$
2. $(P\lor Q)\land (R\land S)$
3. $(P\land \sim Q)\lor (\sim R\lor S)$