数学证明/逻辑

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

真值和陈述

我们在数学中经常遇到陈述。

定义。 (陈述) 一个陈述是一个可以判断为真或假（但不能同时为真假）的陈述句，其真值为真（用$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$”。
• 数学中的“或”的含义可能与英语单词“or”的含义不同。在数学中，“或”是 包含性的，即 $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$ 和 $Q$ 为假时，$P\lor Q$ 为假，否则为真。

否定

定义： 一个命题 $P$ 的 否定，记作 $\sim P$，是一个真值与 $P$ 相反的命题。

备注。

• $~P$ 读作“非 P”，命题 $P$ 的否定也可以直接用“非 $P$”或“并非 $P$”来表达。
• 另一个常见的符号是 $\lnot P$ 来表示命题 $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$ 为真且 $Q$ 为假时，条件语句 $P\to 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 行）。

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

示例。 假设 Bob 正在上一个叫做 MATH1001 的数学课程。MATH1001 的课程老师警告 Bob，如果他在这门课程的期末考试中不及格，那么他将无法通过这门课程。令 $P$ 表示语句“Bob 在 MATH1001 的期末考试中不及格”，而 $Q$ 表示语句“Bob 无法通过 MATH1001”。那么，课程老师的陈述是“$P\to Q$”。

为了使课程老师的陈述为真，要么 Bob 确实在 MATH1001 的期末考试中不及格，并且他确实无法通过这门课程，要么 Bob 通过了 MATH1001 的期末考试。在后一种情况下，无论 Bob 是否通过 MATH1001 都无关紧要，因为如果 Bob 通过了 MATH1001 的期末考试，课程老师不会承诺任何事情 。

为了使课程老师的陈述为假，唯一的情况是 Bob 在 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\leftrightarrow Q$ 为真时，$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$ 为 充分条件，因为当 $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)$