COMS W3261 : 离散数学复习

这部分是文档的作者和来源信息。

• Anum Ahmad, William Pires：这两位是这份复习笔记的作者。在学术材料中，通常会在开头注明作者，以明确责任和出处。
• 这些笔记基于 Cyrus Illick 和 Walt McKelvie (2022) 的内容。：这句话说明了当前笔记的知识来源。它表明 Ahmad 和 Pires 的工作不是完全原创的，而是在 Cyrus Illick 和 Walt McKelvie 于 2022 年创建的笔记基础上进行改编、补充或修订的。这在学术上是一种常见的做法，叫做引用或致谢，体现了对前人工作的尊重。

这部分是文档的引言，明确了文档的目的、范围、目标读者以及寻求帮助的途径。

• 本文档是离散数学的复习。：开门见山，直接点明了这份文档的性质——它是一份复习资料，而不是一本完整的教科书。
• 以下定义、定理和示例列表并未涵盖离散数学的所有内容。：这句话设定了文档的范围和局限性。它提醒读者，这份笔记是有选择性的，不是包罗万象的。离散数学是一个广泛的领域，这份笔记只摘取了其中的一部分。
• 这些只是我们认为对我们的计算机科学理论课程有帮助的一些方面...：这解释了内容筛选的标准。作者们只挑选了那些与“计算机科学理论 (Computer Science Theory)”这门特定课程紧密相关的主题。这使得复习更有针对性、更高效。
• （课程网页上也有指向其他一些资源的链接）：这是一个非常有用的提示，告诉学生如果需要更全面的信息，可以去哪里寻找。课程网页是获取官方信息和补充材料的主要渠道。
• 离散数学是本课程的先修课程：这句话强调了一个重要的前提条件。先修课程 (prerequisite) 意味着学生在学习“计算机科学理论”之前，应该已经具备了离散数学的知识基础。
• 如果你觉得对内容掌握得不牢固，我们建议你回顾并复习笔记...：这是给基础不扎实的学生提出的具体建议。它鼓励学生自我评估，并主动弥补知识上的不足。
• ...欢迎参加办公时间（office hours）。我们在这里为你提供帮助！：这提供了寻求帮助的具体方式。办公时间是学生与教师或助教进行一对一交流、解决个性化问题的宝贵机会。最后一句“我们在这里为你提供帮助！”传达了一种积极和支持的态度，鼓励学生不要害怕求助。

这一段引入了布尔逻辑 (Boolean Logic) 的最基本元素。布尔逻辑是计算机科学的基石，因为它处理的是最简单的信息单位：真与假。

• 我们用 1 表示“真”（TRUE），0 表示“假”（FALSE）。：这是一个核心约定。在数字电路和计算机内部，所有的信息最终都被编码为高低电平，这两种状态正好对应了“真”和“假”。用数字 1 和 0 来表示，使得逻辑运算可以转化为数学运算。
• 我们使用字母（如 $P, Q$）来表示变量...：这些字母被称为布尔变量或命题变量。它们就像代数中的 $x$ 和 $y$，但区别在于，$x$ 和 $y$ 可以取任何数值，而布尔变量 $P$ 和 $Q$ 只能取两个值：0 (假) 或 1 (真)。
• 三种基本的布尔逻辑规则是 $(\neg)=$ 非（NOT），$(\wedge)=$ 与（AND），$(\vee)=$ 或（OR）：这里列出了三种最基础的逻辑运算符。它们是构建所有复杂逻辑电路和逻辑表达式的“原子”。
• 非 (NOT)，符号 $\neg$：这是一个一元运算符，它只作用于一个变量。它的作用是“取反”。如果一个变量是真的，NOT 运算后就变成假的；反之亦然。
• 与 (AND)，符号 $\wedge$：这是一个二元运算符，连接两个变量。它的规则是“两者都为真，结果才为真”。只要有一个是假的，结果就是假的。
• 或 (OR)，符号 $\vee$：这也是一个二元运算符。它的规则是“只要有一个为真，结果就为真”。只有当两者都为假时，结果才是假的。

这部分通过列举所有可能的情况，具体展示了三种基本布尔运算的结果。这通常被称为真值表 (Truth Table) 的内容。

• AND 运算 ($\wedge$) (第1-4项):

1. 假 AND 假 = 假 ($0 \wedge 0=0$): 如果“天是绿的” (假) 并且“猪会飞” (假)，那么“天是绿的并且猪会飞”整个陈述是假的。
2. 假 AND 真 = 假 ($0 \wedge 1=0$): 如果“天是绿的” (假) 并且“草是绿的” (真)，那么“天是绿的并且草是绿的”是假的，因为它没有全部为真。
3. 真 AND 假 = 假 ($1 \wedge 0=0$): 如果“草是绿的” (真) 并且“猪会飞” (假)，那么“草是绿的并且猪会飞”是假的。
4. 真 AND 真 = 真 ($1 \wedge 1=1$): 如果“草是绿的” (真) 并且“天是蓝的” (真)，那么“草是绿的并且天是蓝的”整个陈述是真的。这是 AND 运算唯一为真的情况。
   • OR 运算 ($\vee$) (第5-8项):
5. 假 OR 假 = 假 ($0 \vee 0=0$): 如果“你想吃苹果” (假) 并且“你想吃香蕉” (假)，那么“你想吃苹果或香蕉”是假的。这是 OR 运算唯一为假的情况。
6. 假 OR 真 = 真 ($0 \vee 1=1$): 如果“你想吃苹果” (假) 但“你想吃香蕉” (真)，那么“你想吃苹果或香蕉”是真的，因为你至少想吃一种。
7. 真 OR 假 = 真 ($1 \vee 0=1$): 如果“你想吃苹果” (真) 但“你想吃香蕉” (假)，那么“你想吃苹果或香蕉”是真的。
8. 真 OR 真 = 真 ($1 \vee 1=1$): 如果“你想吃苹果” (真) 并且“你想吃香蕉” (真)，那么“你想吃苹果或香蕉”也是真的。这体现了逻辑“或”的包容性。
   • NOT 运算 ($\neg$) (第9-10项):
9. NOT 真 = 假 ($\neg 1=0$): 如果“地球是圆的”是真的，那么“地球不是圆的”就是假的。
10. NOT 假 = 真 ($\neg 0=1$): 如果“2+2=5”是假的，那么“2+2不等于5”就是真的。

这一段引入了另外两个重要的逻辑概念：命题和两种新的逻辑运算符——蕴含和等价。

• 命题 (Proposition)：定义非常关键——它必须是一个陈述性语句 (declarative sentence)，并且这个语句的真假值必须是确定的、唯一的。它不能是问题、命令或模糊不清的描述。
• “$1+1=2$” 是一个命题，因为它是陈述句，并且它的真假是确定的（为真）。
• “$4<3$” 是一个命题，因为它是陈述句，并且它的真假是确定的（为假）。
• “今天天气很好” 不是一个严格的命题，因为“好”的标准因人而异，真假不确定。
• “你吃了吗？” 不是一个命题，因为它是问句。
• “关上门！” 不是一个命题，因为它是命令。
• $(\rightarrow)=$ 蕴含 (Implies)：这是布尔逻辑中非常核心且容易混淆的一个运算符。它连接两个命题，通常写成 $A \rightarrow B$。
• $(\leftrightarrow)=$ 等价 (Equivalent)：也称为“当且仅当”(if and only if, iff)。它也连接两个命题，写成 $A \leftrightarrow B$。

这一段详细解释了蕴含 $(\rightarrow)$ 的定义和行为，这是布尔逻辑中最反直觉但又极其重要的部分。

• $A \rightarrow B$ 读作“如果 $A$，那么 $B$”：$A$ 被称为前提 (premise) 或假设 (hypothesis)，$B$ 被称为结论 (conclusion)。这个结构表达了一种条件关系。
• $A \rightarrow B$ 等同于 $\neg A \vee B$：这是蕴含的形式化定义，是理解其行为的关键！让我们用真值表来拆解这个定义：

• 所以，只要 $B$ 为真或 $A$ 为假，$A \rightarrow B$ 就是真的。：
• $A$ 为假 (0)：对应真值表的前两行。如果前提 $A$ 是假的，那么整个蕴含式 $A \rightarrow B$ 自动为真，无论结论 $B$ 是真是假。这被称为善意推定 (vacuously true)。逻辑上可以理解为：从一个错误的前提出发，可以推导出任何结论，这个推导过程本身没有逻辑错误。
• $B$ 为真 (1)：对应真值表的第二和第四行。如果结论 $B$ 本身就是真的，那么无论前提 $A$ 是什么，"如果 $A$ 那么 $B$" 这个陈述也不会是错的。
• 特别地，如果 $A$ 为真，$B$ 必须为真。：这对应真值表的后两行。当前提 $A$ 为真时，结论 $B$ 必须也为真，整个蕴含式才能为真。如果 $A$ 为真而 $B$ 为假（第三行），这是唯一导致 $A \rightarrow B$ 为假的情况。这符合我们的直觉：一个真的前提不能推导出假的结论。
• 例子分析：
• “如果 $1+1=3$ (A, 假)，那么 $1+1=2$ (B, 真)”：这里 $A=0, B=1$。根据真值表第二行，$0 \rightarrow 1$ 结果为真。
• “如果 $\sqrt{1}=2$ (A, 假)，那么 $1+1=3$ (B, 假)”：这里 $A=0, B=0$。根据真值表第一行，$0 \rightarrow 0$ 结果为真。

这一段解释了等价运算符 $(\leftrightarrow)$，也叫双向蕴含或“当且仅当”。

• $A \leftrightarrow B$ 读作“$A$ 当且仅当 $B$”：这里的“当且仅当”(if and only if, 缩写为 iff) 是关键词。它表示 $A$ 是 $B$ 的充分必要条件。
• 当 $A$ 和 $B$ 同时为真，或者它们同时为假时，$A \leftrightarrow B$ 为真。：这直接给出了等价的真值表定义。它要求 $A$ 和 $B$ 的真值必须相同。

可以看到，只有在第一行 ($A,B$ 都为假) 和第四行 ($A,B$ 都为真) 时，结果才为真。

• $A \leftrightarrow B$ 与：$(A \rightarrow B) \wedge (B \rightarrow A)$ 相同。：这是等价的另一个核心定义。它把等价拆解成了两个方向的蕴含。
• $A \rightarrow B$：“如果 A，那么 B” ($A$ 是 $B$ 的充分条件)。
• $B \rightarrow A$：“如果 B，那么 A” ($A$ 是 $B$ 的必要条件)。
• 将两者用“与”($\wedge$)连接起来，意味着这两个方向的蕴含必须同时成立。
• 让我们用真值表验证这个等价性：

最后一列的结果与上面 $A \leftrightarrow B$ 的真值表完全一样，证明了两者是逻辑等价的。

这一段引入了与蕴含相关的两个重要概念：逆命题和逆否命题中的第一个。

• 逆命题 (Converse)：定义非常直接，就是把原命题 $A \rightarrow B$ 的前提和结论交换位置，得到 $B \rightarrow A$。
• 注意它们不是一回事！：这是本段的核心警告。一个命题为真，不代表它的逆命题也为真。它们是两个独立的命题。
• 例子分析：
• 原命题: “如果一个四边形是正方形 ($A$)，那么它的所有角都是 $90^{\circ}$ ($B$)”。 这是一个真命题。($A \rightarrow B$ is True)。
• 逆命题: “如果一个四边形的所有角都是 $90^{\circ}$ ($B$)，那么它就是正方形 ($A$)”。 这是一个假命题。($B \rightarrow A$ is False)。为什么假？因为长方形也满足所有角都是 $90^{\circ}$，但长方形不一定是正方形。长方形是一个反例 (counterexample)。
• 在本课程中...请确保你不要使用...：这是一个非常重要的实践建议。在应用一个定理时，比如 “如果语言 L 是正则的，那么它有一个 DFA”，你只能从左向右推导。你不能想当然地认为“如果一个语言有一个 DFA，那么它就是正则的”（尽管在这个特定的例子里，逆命题恰好也为真，但这需要额外证明，不能直接使用）。混淆原命题和逆命题是逻辑推理中最常见的错误之一。

这一段引入了与蕴含相关的第二个重要概念：逆否命题。

• 逆否命题 (Contrapositive)：它的构造分两步：1. 交换原命题 $A \rightarrow B$ 的前提和结论（得到 $B \rightarrow A$）；2. 然后将两者都取反。最终得到 $\neg B \rightarrow \neg A$。
• 特别地，这两个陈述具有相同的真值。：这是逆否命题最至关重要的特性！一个命题和它的逆否命题是逻辑等价的。一个为真，另一个必然为真；一个为假，另一个必然为假。
• 公式 $(A \rightarrow B) \leftrightarrow(\neg B \rightarrow \neg A)$：这就是上述特性的形式化表达。
• 例子分析：
• 原命题: “如果一个语言 $L$ 是正则的 ($A$)，那么存在一个针对 $L$ 的 DFA ($B$)”。
• 逆否命题: “如果没有针对 $L$ 的 DFA ($\neg B$)，那么 $L$ 就不是正则的 ($\neg A$)”。

这两个陈述表达的是完全相同的事实，只是角度不同。

• 如果在课堂上你学到了...你总是可以使用...：这为我们提供了一个强大的证明工具。有时，直接证明 $A \rightarrow B$ 可能很困难，但证明它的逆否命题 $\neg B \rightarrow \neg A$ 可能会容易得多。因为它们是等价的，所以证明了逆否命题，就等于证明了原命题。这被称为逆否命题证明法 (Proof by Contraposition)。

这段话是一个非常重要的提醒，关于学术写作（尤其是定义）中的一个常见“潜规则”。

• 一个小注解。有时在一个定义中...：这里指出，在数学和计算机科学的“定义”性陈述中，作者有时为了语言简洁，会用“如果...那么...”来表达一个实际上是“当且仅当”的关系。
• 例子分析：
• 书面陈述: “如果 $L$ 是一个正则语言，那么存在一个识别 $L$ 的 DFA”。
• 形式: $A \rightarrow B$。
• 实际含义: 因为这是一个定义，它的意思是，“正则语言”这个术语就是用来指代那些可以被 DFA 识别的语言的。这两个概念是等同的。所以，真实的、完整的逻辑关系是等价关系。
• 完整陈述: “$L$ 是一个正则语言 当且仅当 存在一个识别 $L$ 的 DFA”。
• 形式: $A \leftrightarrow B$。
• 在这种情况下，...逆命题是真的...：在上面这个例子中，原定义写作 $A \rightarrow B$。它的逆命题是 $B \rightarrow A$（“如果存在一个识别 $L$ 的 DFA，那么 $L$ 是正则的”）。通常我们说逆命题不一定为真，但因为这里是一个定义，其背后隐藏的逻辑是 $A \leftrightarrow B$，而 $A \leftrightarrow B$ 本身就包含了 $A \rightarrow B$ 和 $B \rightarrow A$ 两个方向。所以，这个逆命题 $B \rightarrow A$ 在这种特定语境下是真的。
• 如果你不确定...请询问我们！：这是一个非常善意和负责任的建议。因为区分一个陈述是普通的定理（$A \rightarrow B$）还是一个定义（$A \leftrightarrow B$ 的简写）需要经验和对上下文的理解。对于初学者来说，感到困惑是正常的，最好的办法就是向老师或助教确认。

这一段引入了数学中的另一个基本概念：集合 (Set)。

• 集合非正式地说，是元素的汇集。：“非正式地说”表明这是一种直觉性的描述，而不是严格的数学定义（严格定义需要公理化集合论）。“元素的汇集” (collection of elements) 是核心思想，就像一个袋子里装了很多东西。
• 它们通过所包含的元素来表征：这是集合的外延性原则 (Principle of Extensionality)。一个集合的全部信息就由它的成员决定。两个集合如果成员完全相同，那么它们就是同一个集合，无论它们看起来多么不同或者如何被描述。
• 对于一个集合 $A$ 和任何 $x$，我们可以说 $x \in A$（$x$ 在 $A$ 中），或 $x \notin A$（$x$ 不在 $A$ 中）。：这里引入了最重要的集合关系符号：$\in$ (属于) 和 $\notin$ (不属于)。这是一个二元关系，判断一个“元素”和一个“集合”之间是否存在成员关系。这个判断必须是明确的、无歧义的。
• 集合既可以显式定义（通过列出所有元素），也可以隐式定义（如下文所示）。：这指出了描述或定义一个集合的两种主要方法。
• 显式定义 (Explicit Definition)：也叫枚举法或列举法 (roster method)。就是把集合里的所有成员一个一个地列出来，用花括号 {} 括起来。例如 {1, 2, 3}。
• 隐式定义 (Implicit Definition)：也叫描述法或构造法 (set-builder notation)。就是不列出成员，而是描述成员需要满足的共同属性。例如 {所有大于5的整数}。

这一段通过六个具体的例子来展示集合的多样性和普遍性。

1. $\{1,5,6\}$：这是一个简单的、有限的数字集合，通过显式列举法定义。
2. {猫, 狗, 狼}：这个例子说明集合的元素不一定是数字，可以是任何事物，比如字符串或现实世界中的对象。
3. $\{1,2,\{ \},\{1,2\}\}$：这是一个非常关键的例子，揭示了集合的两个重要特性：
   • 元素可以是集合: 集合的成员本身也可以是集合。这里，第三个元素是空集 $\{ \}$, 第四个元素是集合 $\{1,2\}$。
   • 元素类型可以混合: 一个集合里可以同时包含整数、集合、字符串等不同类型的东西。
4. $\mathbb{N}$ 是所有自然数的集合 $\{0,1,2,3,4, \ldots\}$：
   • $\mathbb{N}$ 是一个标准数学符号，代表自然数集 (Natural Numbers)。
   • 这是一个无限集合，我们无法用列举法写出所有成员，所以用 ... 表示无限延续。
   • 注意: 自然数是否包含 0 在不同的数学分支或国家有不同的约定。在这门课程的上下文中，明确了是从 0 开始的。
5. $\mathbb{Z}$ 是整数的集合 $\{\ldots,-2,-1,0,1,2, \ldots\}$：
   • $\mathbb{Z}$ 是标准符号，代表整数集 (Integers)，源于德语单词 "Zahlen" (数字)。
   • 它也是一个无限集合，向正负两个方向无限延伸。
6. $\mathbb{R}$ 是实数的集合：
   • $\mathbb{R}$ 是标准符号，代表实数集 (Real Numbers)。
   • 这是一个更“大”的无限集合。它不仅包括整数，还包括分数、小数、无理数（如 $\pi, \sqrt{2}$）。我们甚至不能像 $\mathbb{N}$ 和 $\mathbb{Z}$ 那样试图去“列举”它们，因为在任意两个实数之间都还有无穷多个实数。

这一段强调了集合的三个决定性特征：基数（有限/无限）、无序性和互异性。

• 有限 vs 无限：
• 有限集 (Finite Set)：元素的数量是有限的，理论上可以一个一个数完。例如 $\{1, 2, 3\}$。
• 无限集 (Infinite Set)：元素的数量是无限的，无法数完。例如自然数集 $\mathbb{N}$。
• 可数无限集 (Countably Infinite Set)：这是一个更精细的分类，后面会讲。直观上，它是指虽然无限，但可以像自然数一样“排队”并编号的无限集（如 $\mathbb{N}, \mathbb{Z}$）。实数集 $\mathbb{R}$ 就是“不可数”的。
• 无序性 (Unordered)：
• 集合中的顺序并不重要：这是集合与序列（或列表、数组）最根本的区别之一。在集合中，元素没有“第一”、“第二”之分，它们是平等地存在于集合中。
• 例子: $\{猫, 狗, 狼\}$ 和 $\{狗, 猫, 狼\}$ 是完全相同的集合。
• 对比序列 (Sequence)：序列（用圆括号 () 表示）是讲究顺序的。序列 (猫, 狗, 狼) 和 (狗, 猫, 狼) 是两个不同的序列。
• 互异性 (Distinct)：
• 一个集合仅由不同的元素组成：集合中不能有重复的成员。
• 每个元素要么在集合中，要么不在：不存在一个元素“在集合中两次”这样的概念。
• 例子: 如果你试图写一个集合 $\{a, b, b, c, d\}$，它会被自动理解为（或等同于）$\{a, b, c, d\}$。重复的 b 会被忽略掉。

这一段定义了一个非常基础但极其重要的特殊集合——空集。

• 没有元素的集合：这是空集的定义。它是一个集合，但里面是空的，什么成员都没有。
• 称为空集 (Empty Set)：这是它的正式名称。
• 写作 $\emptyset$ 或 $\{ \text{ } \}$：这里给出了表示空集的两种标准符号。
• $\emptyset$：这是一个专门的数学符号，读作 "phi" (fai)。它看起来像一个被斜线划掉的字母O。
• $\{ \text{ } \}$：这更直观地体现了空集的本质——一个花括号，里面什么都不写。

这一段详细介绍了隐式定义集合的标准化写法，即集合构造式符号 (Set-Builder Notation)。

• $\{x \mid \text{某些条件适用于 } \mathrm{x}\}$：这是集合构造式的基本结构。它由三部分组成：

1. 花括号 {...}：表示这是一个集合。
2. 变量 x：在竖线 | 的左边，代表集合中元素的“模板”或“形式”。
3. 竖线 |：读作“满足”(such that)。它是一个分隔符。
4. 条件/谓词 某些条件适用于 x：在竖线的右边，是一个逻辑陈述，用来筛选元素。只有使这个陈述为真的 x 才会被包含在集合中。
   • 读法: “所有满足某些条件的 $x$ 的集合”。
   • $: $ vs $|$: 这里明确指出，用冒号 : 代替竖线 | 是完全可以的，两者是等价的符号，纯粹是个人或领域的书写习惯不同。

这一段给出了两个使用集合构造式的具体例子，一个简单，一个复杂，以展示其用法。

• 示例1:
• 目标: 定义大于5的整数集合。
• 写法: $\{x \in \mathbb{Z} \mid x>5\}$
• 拆解:
• x \in \mathbb{Z}: 这部分放在了竖线的左边，是一种常见的简写。它同时完成了两件事：声明变量 x 和限定它的论域是整数集 $\mathbb{Z}$。这比在右边写 x \in \mathbb{Z} 更紧凑。
• |: 满足...
• x > 5: ...$x$ 大于 5 这个条件。
• 读法: “所有属于整数集 $\mathbb{Z}$ 且大于5的元素 $x$ 的集合”。
• 这个集合就是 $\{6, 7, 8, \ldots\}$。
• 示例2:
• 目标: 严格定义质数集合。
• 写法: $\{x \in \mathbb{N}: \text{不存在 } y \in \mathbb{N} \text{ 使得 } 1<y<x \text{ 且 } y \text{ 整除 } x\}$
• 拆解:
• x \in \mathbb{N}: 候选者 $x$ 是自然数。
• :: 满足...
• \text{不存在 } y \in \mathbb{N} \text{ 使得 } ...: 这里描述的条件是一个存在性命题的否定。
• 1 < y < x: 存在一个自然数 $y$ 在 1 和 $x$ 之间（不包括1和x）。
• y \text{ 整除 } x: 并且这个 $y$ 是 $x$ 的一个因子。
• 条件解读: 整个条件是“找不到一个在1和x之间的数y能整除x”。这正是质数的定义：除了1和它本身，没有别的正因子。（这里定义排除了1，因为如果 $x=1$，找不到满足 $1<y<1$ 的 $y$，按此定义1会是质数，通常质数定义为大于1。更严谨的定义应为 $\{x \in \mathbb{N}: x > 1 \text{ 且 } \ldots\}$）。
• 这个集合就是 $\{2, 3, 5, 7, 11, 13, \ldots\}$。

这一段通过三个例子，回顾和巩固了成员关系运算符 $\in$ (属于) 和 $\notin$ (不属于) 的用法。

1. $0 \in\{0,1,2,3,4\}$
   • 陈述: 0 是集合 $\{0,1,2,3,4\}$ 的一个元素。
   • 分析: 我们查看集合 $\{0,1,2,3,4\}$ 的成员列表，发现 0 确实是其中的第一个成员。
   • 结论: 该陈述为真。
2. $dog \notin \{\text{cat, bird, tiger}\}$
   • 陈述: "dog" 不是集合 $\{\text{cat, bird, tiger}\}$ 的一个元素。
   • 分析: 我们查看集合的成员列表，里面有 "cat", "bird", "tiger"，但没有 "dog"。
   • 结论: 该陈述为真。
3. $3 \in\{x \mid x<5\}$
   • 陈述: 3 是集合 $\{x \mid x<5\}$ 的一个元素。
   • 分析: 这是一个隐式定义的集合。我们要判断 3 是否是其成员，就需要用 3 去测试它是否满足成员条件 $x<5$。
   • 测试: 将 $x=3$ 代入条件，我们得到 $3<5$。这是一个真命题。
   • 结论: 因为 3 满足条件，所以 3 是该集合的一个成员。该陈述为真。
   • 注意: 这里的论域是模糊的。如果论域是整数，那么这个集合是 $\{\ldots, 2, 3, 4\}$。如果论域是实数，它是一个区间 $(-\infty, 5)$。但无论如何，3 都满足条件。

这一段引入了集合的一个重要属性：基数。

• 基数 (Cardinality) 或 势 (Power): 这是用来衡量集合大小的专业术语。
• 写作 $|A|$: 这是表示集合 $A$ 的基数的标准符号。两边的竖线让人联想到求绝对值或长度的符号，它们在概念上都是衡量“大小”。
• 对于有限集，这仅仅是集合中元素的数量。: 这个定义非常直观。对于一个有限集，你只需数一数里面有多少个互不相同的元素。
• 例子分析:
• $A=\{1,2,3\}$: 这个集合有3个元素（1, 2, 3）。所以 $|A|=3$。
• $B=\{1,3,1,2,\{\text{ }\}\}\}$: 在计算基数前，我们首先要应用互异性原则，去掉重复的元素。这个集合实际上是 $\{1, 3, 2, \{\text{ }\}\}$。现在我们来数一下：元素1，元素3，元素2，元素 $\{\text{ }\}$ (空集)。总共有 4 个不同的元素。所以 $|B|=4$。
• $C=\emptyset$: 空集里没有任何元素。所以 $|C|=0$。
• 我们稍后将在课堂上讨论无限集的基数。: 这是一个预告。对于无限集，基数的概念会变得更复杂和有趣。例如，我们会发现自然数集 $\mathbb{N}$ 和整数集 $\mathbb{Z}$ 的“大小”是相同的，但它们都比实数集 $\mathbb{R}$ 要“小”。

这一段定义了第一个基本的集合运算：并集。

• 并集 (Union)：这是将两个集合合并成一个新集合的操作。
• 写作 $A \cup B$: 这是并集的标准符号。符号 $\cup$ 看起来像一个大碗，要把所有东西都装进去。
• 是所有在 $A$ 或 $B$ 中的 $x$ 的集合：这是并集的自然语言定义。一个元素，只要它至少在两个集合中的一个里面出现，它就会被包含在并集中。
• 使用集合构造式符号，$A \cup B=\{x \mid x \in A \vee x \in B\}$：这是并集的形式化定义。它精确地表达了上述思想：新集合的成员 $x$ 满足的条件是 "$x$ 属于 $A$ 或 $x$ 属于 $B$"。这里的逻辑或 ($\vee$) 是关键。
• 例子分析:
• $A = \{1,2,3\}$, $B = \{2,3,4\}$
• $A \cup B$: 我们把 $A$ 的所有元素 (1, 2, 3) 和 $B$ 的所有元素 (2, 3, 4) 都放进一个大集合里，得到 $\{1, 2, 3, 2, 3, 4\}$。
• 然后，根据集合的互异性，我们去掉重复的元素。2 和 3 都出现了两次，我们只保留一个。
• 最终结果是 $\{1, 2, 3, 4\}$。

这一段定义了第二个基本的集合运算：交集。

• 交集 (Intersection)：这是从两个集合中筛选出共同元素的操作。
• 写作 $A \cap B$: 这是交集的标准符号。符号 $\cap$ 看起来像并集符号 $\cup$ 倒了过来。
• 是所有既在 $A$ 中又在 $B$ 中的 $x$ 的集合：这是交集的自然语言定义。一个元素，必须同时在两个集合中都出现，才能被包含在交集里。
• 使用集合构造式符号，$A \cap B=\{x \mid x \in A \wedge x \in B\}$：这是交集的形式化定义。新集合的成员 $x$ 满足的条件是 "$x$ 属于 $A$ 与 $x$ 属于 $B$"。这里的逻辑与 ($\wedge$) 是关键。
• 例子分析:
• $A = \{1,2,3\}$, $B = \{2,3,4\}$
• $A \cap B$: 我们要寻找同时在 $A$ 和 $B$ 里的元素。
• 1 在 $A$ 中，但不在 $B$ 中。排除。
• 2 在 $A$ 中，也在 $B$ 中。保留。
• 3 在 $A$ 中，也在 $B$ 中。保留。
• 4 在 $B$ 中，但不在 $A$ 中。排除。
• 最终结果是 $\{2, 3\}$。

这一段定义了第三个重要的集合运算：笛卡尔积。

• 笛卡尔积 (Cartesian Product)：它不是像并集/交集那样处理单个元素，而是创造一种新的元素——有序对 (ordered pair)。
• 写作 $A \times B$: 这是笛卡尔积的标准符号，使用了乘法符号 ×。这个符号是有意为之的，因为笛卡尔积的基数等于原集合基数的乘积。
• 是所有...对 $(p, q)$ 的集合：笛卡尔积的结果是一个集合，但这个集合的成员不再是单个元素，而是一个个形如 (p, q) 的有序对。
• 满足 $p \in A$ 且 $q \in B$: 这规定了有序对的构成规则：对中的第一个元素 p 必须来自第一个集合 A，第二个元素 q 必须来自第二个集合 B。
• 有序对: (p, q) 和 (q, p) 是不同的，除非 p=q。顺序很重要！这与集合 {p, q} 不同。
• 集合构造式符号: $A \times B=\{(p, q) : p \in A \text{ 且 } q \in B\}$。这个定义非常清晰：
• {(p, q) | ...}: 集合的元素是 (p,q) 这种形式的。
• p \in A \text{ 且 } q \in B: 构造规则。
• 例子分析:
• $A = \{1,2,3\}$, $B = \{4,5\}$
• $A \times B$: 我们要从 $A$ 中取一个元素作第一部分，从 $B$ 中取一个元素作第二部分，组成所有可能的有序对。
• 取 1 from A: 可以组成 (1, 4) 和 (1, 5)。
• 取 2 from A: 可以组成 (2, 4) 和 (2, 5)。
• 取 3 from A: 可以组成 (3, 4) 和 (3, 5)。
• 把所有这些有序对收集起来，就得到了最终的集合。

这一段定义了第四个集合运算：集合差。

• 集合差 (Set Difference)：可以理解为从一个集合中“减去”另一个集合的元素。
• 记作 $A \backslash B$: 这是集合差的标准符号，使用反斜杠 \。有时也写作 $A - B$。
• 是在 $A$ 中但不在 $B$ 中的元素集合：这是自然语言定义。它的操作对象是集合 $A$，从 $A$ 中剔除掉那些同时也存在于 $B$ 中的元素。
• 即 $A \backslash B=\{x: x \in A \wedge x \notin B\}$: 这是形式化定义。新集合的成员 $x$ 必须同时满足两个条件：1. $x$ 必须是 $A$ 的成员；2. $x$ 不能是 $B$ 的成员。
• 例子分析:
• $A = \{1,2,3\}$, $B = \{2,4,5,6\}$。求 $A \backslash B$。
• 我们从 $A$ 的元素开始检查：
• 1: 在 $A$ 中。在 $B$ 中吗？不在。保留。
• 2: 在 $A$ 中。在 $B$ 中吗？在。剔除。
• 3: 在 $A$ 中。在 $B$ 中吗？不在。保留。
• 结果是 $\{1, 3\}$。
• 求 $B \backslash A$。
• 我们从 $B$ 的元素开始检查：
• 2: 在 $B$ 中。在 $A$ 中吗？在。剔除。
• 4: 在 $B$ 中。在 $A$ 中吗？不在。保留。
• 5: 在 $B$ 中。在 $A$ 中吗？不在。保留。
• 6: 在 $B$ 中。在 $A$ 中吗？不在。保留。
• 结果是 $\{4, 5, 6\}$。
• $A \backslash B \neq B \backslash A$: 这个例子清晰地表明，集合差不满足交换律。

这一段定义了集合之间的一种基本关系：子集关系。

• 定义6: 这是对子集 (Subset) 关系的正式定义。
• 条件: 对于所有 $x \in A$，我们都有 $x \in B$: 这是判断子集关系的核心规则。它要求集合 A 中的每一个元素都必须同时是集合 B 的元素。只要能在 A 中找到哪怕一个元素不在 B 中，那么 A 就不是 B 的子集。
• $A \subseteq B$: 这是子集关系的符号。读作 "A is a subset of B" (A是B的子集)。符号 ⊆ 像一个拉长的 ⊂ 下面加了一横，可以类比小于等于号 ≤，表示 A “小于或等于” B。
• $B \supseteq A$: 这是同一个关系从 B 的角度看的写法。读作 "B is a superset of A" (B是A的超集)。

这一段通过三个例子来巩固对子集定义的理解。

1. $\{0\} \subseteq\{0,1\}$
   • 左边集合 A: $\{0\}$。
   • 右边集合 B: $\{0,1\}$。
   • 判断: 我们需要检查 A 的所有元素是否都在 B 中。A 只有一个元素，就是 0。
   • 元素 0 在 B 中吗？是的。
   • 结论: 因为 A 的所有元素都在 B 中，所以该陈述为真。
2. $\mathbb{N} \subseteq \mathbb{Z}$
   • 左边集合 A: $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ (自然数)。
   • 右边集合 B: $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$ (整数)。
   • 判断: 我们需要检查是否每一个自然数都是一个整数。根据定义，是的。每一个自然数（0, 1, 2, ...）都包含在整数的集合中。
   • 结论: 该陈述为真。
3. 对于任何集合 $S$，我们都有 $\emptyset \subseteq S$
   • 左边集合 A: $\emptyset$ (空集)。
   • 右边集合 B: 任何一个集合 $S$。
   • 判断: 我们需要检查空集的所有元素是否都在 $S$ 中。但空集里没有任何元素。
   • 逻辑论证 (反证法): 假设 $\emptyset \not\subseteq S$。根据子集的定义，这意味着存在一个元素 $x$ 使得 $x \in \emptyset$ 并且 $x \notin S$。但是 $x \in \emptyset$ 这个前提本身就是假的，因为空集没有任何元素。从一个假的前提出发，无法推导出任何结论，所以我们的假设不成立。因此，$\emptyset \subseteq S$ 必须为真。
   • 结论: 这是一条普遍成立的定理。空集是宇宙中所有集合的子集。

这一段引入了子集关系的一个更严格的版本：真子集。

• 对于任何集合 $A$，$A \subseteq A$: 重申了任何集合都是其自身的子集。这是因为子集的定义 $A \subseteq B$ 允许 $A$ 和 $B$ 是相等的。
• 如果我们想表达 $A \subseteq B$ 且 $A \neq B$...: 这里提出了一个新的需求：如何表达 A 被 B 包含，但又不等于 B？
• 我们可以写 $A \subsetneq B$（“$A$ 是 $B$ 的真子集”）: 这就是答案。
• 真子集 (Proper Subset)：如果 A 是 B 的子集，并且 B 中至少有一个元素不在 A 中，那么 A 就是 B 的真子集。
• 符号 $A \subsetneq B$: ⊂ 下面没有了横线，这与小于号 < 类似，表示“严格小于”。
• 定义: $A \subsetneq B \iff (A \subseteq B) \wedge (A \neq B)$。

这一段从集合论转向了组合数学，介绍了一个非常重要的计数工具：二项式系数。

• 查看某个集合中所有大小为 $k$ 的子集: 这是一个非常经典的组合问题。例如，从一个包含5个人的集合中，选出所有可能的3人小组。
• 如果你有一个包含 $n$ 个元素的集合...: 这里设定了问题的参数：
• $n$: 原集合的基数，即 $|S| = n$。
• $k$: 我们感兴趣的子集的基数。
• 大小为 $k$ 的子集数量记为 $\binom{n}{k}$: 这是二项式系数的符号，读作 "n choose k" (n选k)。它代表了从 $n$ 个不同元素中无序地选取 $k$ 个元素组成一个子集的方法数。
• 我们有 $\binom{n}{k}=\frac{n!}{k!(n-k)!}$: 这是计算二项式系数的公式。

这一段定义了一个非常重要的集合构造：幂集。

• 幂集 (Power Set)：它的定义听起来有点绕口，需要仔细理解。
• 写作 $\mathcal{P}(A)$: 这是幂集的标准符号，使用一个花体的P。
• 是 $A$ 的所有子集的集合: 这是关键定义。幂集本身是一个集合，它的元素不是普通的值，而是 $A$ 的所有可能的子集。
• 例子分析:
• $A = \{1, 2, 3\}$。我们来找出 $A$ 的所有子集。
• 大小为 0 的子集: $\emptyset$ (1个)
• 大小为 1 的子集: $\{1\}, \{2\}, \{3\}$ (3个)
• 大小为 2 的子集: $\{1,2\}, \{1,3\}, \{2,3\}$ (3个)
• 大小为 3 的子集: $\{1,2,3\}$ (1个)
• $\mathcal{P}(A)$ 就是把上面找到的所有子集都作为元素，放入一个大集合中。
• $\mathcal{P}(\{1,2,3\})=\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$。
• 基数公式: 如果 $|A|=k$，那么 $|\mathcal{P}(A)|=2^{k}$: 这是一个计算幂集大小的重要公式。
• 在例子中，$|A|=3$。
• $|\mathcal{P}(A)| = 2^3 = 8$。
• 我们数一下上面列出的幂集元素个数，确实是8个。

这一段引入了谓词逻辑 (Predicate Logic) 的基本概念，它是对命题逻辑的扩展。

• 谓词 (Predicate)：一个谓词就像一个“带洞的命题”。它是一个陈述，但包含一个或多个变量，因此它的真假取决于这些变量的取值。
• $\mathrm{P}(\mathrm{x})=$ “$x$ 是偶数”: 这是一个典型的谓词例子。
• 它本身不是命题，因为我们不知道 $x$ 是什么，所以无法判断真假。
• 当变量被赋值时，它就变成了一个命题。
• 如果 $x=4$，$\mathrm{P}(4)$ 就是“4是偶数”，这是一个真命题。
• 如果 $x=5$，$\mathrm{P}(5)$ 就是“5是偶数”，这是一个假命题。
• 量化 (Quantification)：除了给变量赋具体的值，我们还有另一种方法让谓词变成命题，那就是量化。量化就是对变量的取值范围进行断言。
• 两种类型的量化:
• 全称量化 (Universal Quantification)：断言谓词对于指定范围内的所有值都为真。
• 存在量化 (Existential Quantification)：断言谓词对于指定范围内至少存在一个值为真。

这一段详细定义了全称量化。

• 全称量化 (Universal Quantification)：这是一种非常强的断言，它声称某个属性对一个范围内的所有个体都成立。
• 符号 $\forall$: 这是全称量词的符号，是一个倒过来的字母 'A'，代表 "All" (所有)。它读作“对于所有”或“对于任意”。
• 如果对于所有值 $x \in S$，谓词 $P(x)$ 都为真，则命题 $(\forall x \in S, P(x))$ 为真: 这给出了全称量化陈述为真的条件。你必须检查集合 $S$（称为论域）中的每一个元素 $x$，把它们代入谓词 $P(x)$，并且每一次的结果都必须是真。只要你能找到哪怕一个反例（一个在 $S$ 中但使 $P(x)$ 为假的 $x$），整个全称量化陈述就为假。
• $(\forall x \in S, P(x))$: 这是一个完整的命题。它不再有自由变量，它的真假是确定的。

这一段详细定义了存在量化。

• 存在量化 (Existential Quantification)：这是一种比全称量化“宽松”得多的断言，它只声称某个属性在一个范围内的至少一个个体上成立。
• 符号 $\exists$: 这是存在量词的符号，是一个反过来的字母 'E'，代表 "Exists" (存在)。它读作“存在”或“对于某个”。
• 如果存在至少一个值 $x \in S$ 使得谓词 $P(x)$ 为真，则命题 $(\exists x \in S P(x))$ 为真: 这给出了存在量化陈述为真的条件。你只需要在集合 $S$ 中找到至少一个例子（一个满足 $P(x)$ 的 $x$），整个存在量化陈述就为真。只有当你检查了 $S$ 中的所有元素，发现没有一个能使 $P(x)$ 为真时，这个陈述才为假。
• $(\exists x \in S P(x))$: 这是一个完整的命题，其真假是确定的。

这一段给出了四个从简单到复杂的量化陈述实例。

1. $(\forall x \in \mathbb{R})(x+0=x)$
   • 类型: 全称量化。
   • 论域: $\mathbb{R}$ (实数集)。
   • 谓词: $P(x) = "x+0=x"$。
   • 分析: 这是加法单位元的性质，对于所有实数都成立。
   • 结论: 真命题。
2. $(\exists x \in \mathbb{N})(x+5=20)$
   • 类型: 存在量化。
   • 论域: $\mathbb{N}$ (自然数集)。
   • 谓词: $P(x) = "x+5=20"$。
   • 分析: 我们需要解方程 $x+5=20$，得到 $x=15$。我们需要检查这个解是否在论域 $\mathbb{N}$ 中。15 是一个自然数。
   • 结论: 因为我们找到了一个例子 ($x=15$)，所以这是真命题。
3. $(\forall x \in \{1,2\} \quad \exists y \in \{1,2,-1,-2\})(x+y=0)$
   • 类型: 嵌套量化 (全称在外，存在在内)。
   • 分析: 这种嵌套量词的解读顺序是从左到右。它像一个“挑战-回应”游戏。
   • 挑战者 (外层 $\forall$): 依次拿出 $x$ 的所有可能值。
   • 回应者 (内层 $\exists$): 对于挑战者给出的每一个 $x$，回应者必须能从自己的集合中找到一个 $y$ 来满足条件。
   • 游戏过程:
   • 挑战者拿出 $x=1$。回应者需要找一个 $y \in \{1,2,-1,-2\}$ 使得 $1+y=0$。回应者找到了 $y=-1$。挑战成功。
   • 挑战者拿出 $x=2$。回应者需要找一个 $y \in \{1,2,-1,-2\}$ 使得 $2+y=0$。回应者找到了 $y=-2$。挑战成功。
   • 结论: 因为对于所有挑战，回应者都能成功回应，所以整个命题为真。
4. $(\exists x \in\{-1,0,1,2\} \forall y \in \mathbb{R})(x+y>y)$
   • 类型: 嵌套量化 (存在在外，全称在内)。
   • 分析: 再次使用“挑战-回应”模型，但角色反过来了。
   • 挑战者 (外层 $\exists$): 尝试从自己的集合 $\{-1,0,1,2\}$ 中选出一个“万能的” $x$。
   • 回应者 (内层 $\forall$): 拿到挑战者选的 $x$ 后，回应者会尝试从实数集 $\mathbb{R}$ 中找出一个 $y$ 来让条件 $x+y > y$ 失败。
   • 游戏过程: 我们可以简化条件 $x+y > y$ 为 $x > 0$。所以原命题等价于 “$\exists x \in\{-1,0,1,2\} (x>0)$”。
   • 挑战者可以选 $x=1$ 或 $x=2$。
   • 我们选 $x=1$。那么命题变为 "对于所有实数 $y$， $1+y > y$ 是否成立？"。是的，化简后为 $1>0$，这永远成立。
   • 结论: 因为挑战者可以找到一个 $x$ (比如 $x=1$) 使得对于所有 $y$ 条件都成立，所以整个命题为真。

这一段是前一段的补充说明，极其重要，它强调了嵌套量词的两个核心特点：依赖关系和顺序的重要性。

• $y$ 被允许依赖于 $x$: 这是对 $\forall x \exists y$ 结构的解释。因为 $\exists y$ 在 $\forall x$ 的“内部”，所以对于外部 $\forall x$ 选择的每一个不同的 $x$，内部的 $\exists y$ 都可以灵活地选择一个不同的 $y$ 来应对。
• 在例子 $(\forall x \in\{1,2\} \exists y \in\{...\} )(x+y=0)$ 中：
• 当 $x=1$ 时，我们选择 $y=-1$。
• 当 $x=2$ 时，我们选择 $y=-2$。
• 这里的 $y$ 明显是依赖于 $x$ 的一个函数，即 $y = -x$。
• 量词的顺序很重要！: 这是本段的中心论点。
• 例子分析:
• 真命题: $(\forall x \in \mathbb{R} \exists y \in \mathbb{R})(x+y=0)$。
• 解读: “对于任何一个实数 $x$，都存在一个实数 $y$ 使得它们的和为0”。
• 证明: 是真的。因为对于任何给定的 $x$，我们总可以选择 $y = -x$。这个 $y$ 也是一个实数。因为对每个 $x$ 我们都能找到对应的 $y$，所以陈述为真。
• 假命题: $(\exists y \in \mathbb{R} \forall x \in \mathbb{R})(x+y=0)$。
• 解读: “存在一个实数 $y$，它能让所有的实数 $x$ 在与它相加后都等于0”。
• 证明: 是假的。假设我们找到了这样一个“万能的” $y$。
• 让 $x=1$，我们需要 $1+y=0$，所以 $y$ 必须是 $-1$。
• 让 $x=2$，我们需要 $2+y=0$，所以 $y$ 必须是 $-2$。
• 一个 $y$ 不可能同时等于 $-1$ 和 $-2$。所以不存在这样一个能满足所有 $x$ 的 $y$。陈述为假。

这一段介绍了量词的德·摩根定律，这是对命题逻辑中德·摩根定律 ($\neg(A \wedge B) \equiv \neg A \vee \neg B$ 和 $\neg(A \vee B) \equiv \neg A \wedge \neg B$) 的推广。这个定律告诉我们如何正确地否定一个量化陈述。

• 第一条定律: $\neg(\forall x \in S: P(x)) \leftrightarrow(\exists x \in S: \neg P(x))$
• 左边: “并非所有S中的x都满足P(x)” / “说‘所有x都满足P(x)’是假的”。
• 右边: “存在一个S中的x，它不满足P(x)”。
• 直观理解: 如何证明“并非所有天鹅都是白色的”？你只需要找到一只黑天鹅即可。这正是这条定律的含义。否定一个“全部”的断言，等价于找到一个“存在的”反例。
• 第二条定律: $\neg(\exists x \in S: P(x)) \leftrightarrow(\forall x \in S: \neg P(x))$
• 左边: “不存在S中的x满足P(x)” / “说‘存在x满足P(x)’是假的”。
• 右边: “对于所有S中的x，它都不满足P(x)”。
• 直观理解: 如何证明“这个房间里不存在一个会说法语的人”？你必须问遍房间里的每一个人，并确认他们都“不会说法语”。这正是这条定律的含义。否定一个“存在”的断言，等价于证明一个“全部都不”的断言。
• 总结规则: 当你把否定符号 $\neg$ “推”进一个量词时：

1. 量词翻转：$\forall$ 变成 $\exists$，$\exists$ 变成 $\forall$。
2. 谓词否定：$P(x)$ 变成 $\neg P(x)$。

这一段通过两个例子，具体演示了如何应用量词的德·摩根定律。

• 第一个例子:
• 原命题: $(\forall x \in \mathbb{N})(x+0=x)$。
• 否定: $\neg [ (\forall x \in \mathbb{N})(x+0=x) ]$。
• 应用规则:

1. 把 $\neg$ 推过 $\forall$。
2. $\forall$ 翻转为 $\exists$。
3. 谓词 $(x+0=x)$ 被否定，变成 $(x+0 \neq x)$。
   • 结果: $(\exists x \in \mathbb{N})(x+0 \neq x)$。“存在一个自然数x，使得x+0不等于x”。（原命题为真，所以其否定为假）。
   • 第二个例子 (嵌套量词):
   • 原命题: $(\exists x \in\{-1,0,1,2\} \forall y \in \mathbb{R})(x+y>y)$。
   • 否定: $\neg [ (\exists x \in S_x \forall y \in S_y)(P(x,y)) ]$。
   • 应用规则 (分步):
4. 把 $\neg$ 推过第一个量词 $\exists x$。
5. $\exists x$ 翻转为 $\forall x$。
6. $\neg$ 现在位于第二个量词之前: $(\forall x \in S_x) [ \neg (\forall y \in S_y, P(x,y)) ]$。
7. 再把 $\neg$ 推过第二个量词 $\forall y$。
8. $\forall y$ 翻转为 $\exists y$。
9. $\neg$ 现在位于谓词之前: $(\forall x \in S_x \exists y \in S_y) [ \neg P(x,y) ]$。
10. 否定谓词 $(x+y>y)$，变成 $(x+y \leq y)$。
    • 结果: $(\forall x \in\{-1,0,1,2\} \quad \exists y \in \mathbb{R})(x+y \leq y)$。
    • 规则总结: 像剥洋葱一样，从外到内，每遇到一个量词就翻转它，最后否定最里面的谓词。

这一段引入了形式语言理论 (Formal Language Theory) 的第一个基本概念：字母表。

• 字母表 (Alphabet)：在形式语言的上下文中，“字母表”是一个专业术语，它不一定指我们日常使用的字母。
• $\Sigma$ (Sigma)：这是在形式语言理论中，约定俗成地用来表示字母表的符号，即大写的希腊字母 Sigma。
• 是符号的有限集合: 这是字母表的严格定义。它有两个关键属性：

1. 它是一个集合: 这意味着字母表中的符号是无序的且互不相同的。$\{0,1\}$ 和 $\{1,0\}$ 是同一个字母表。
2. 它是有限的: 字母表中的符号数量必须是有限的。你不能有一个包含无限个基本符号的字母表。这些符号被称为字母 (letters) 或字符 (symbols)。
   • 例子:
   • $\Sigma_1 = \{0,1\}$: 这是最著名的二元字母表 (binary alphabet)，是计算机科学的基础。
   • $\Sigma_2 = \{a, b, c\}$: 这是一个包含三个拉丁字母的字母表。
   • $\Sigma_3 = \{\text{名词}, \text{动词}, \text{形容词}\}$: 这是一个更抽象的字母表，它的符号是词性类别。

这一段定义了字符串，这是形式语言理论的第二个基本概念。

• 一个在 $\Sigma$ 上的字符串 (String): 表明字符串是与某个特定的字母表 $\Sigma$ 相关联的。
• 是来自 $\Sigma$ 的符号的有限序列: 这是字符串的严格定义，包含两个关键点：

1. 序列 (Sequence): 这意味着字符串中的符号是有顺序的。ab 和 ba 是两个不同的字符串。这也意味着字符串中可以有重复的符号，比如 aa。这与集合的无序性和互异性形成鲜明对比。
2. 有限 (Finite): 字符串的长度必须是有限的。它可以很长，但不能是无限的。
   • 长度记作 $|s|$: 这是表示字符串长度的符号，与集合基数的符号相同，但上下文清晰。它表示字符串中符号的个数（包括重复的）。
   • 例子分析:
   • $\Sigma=\{0,1\}$
   • 00: 这是一个有限序列，由 $\Sigma$ 中的符号组成。它的长度是2，所以 $|00|=2$。
   • 111001: 这是一个长度为6的字符串。
   • 000...: 这是一个无限长的0序列，根据定义，它不是一个字符串。在计算理论中，这种无限序列被称为“流”(stream)或“无限字符串”，是一种不同的研究对象。

这一段引入了两个关于字符串的重要概念和记法。

• 空字符串 (Empty String)：这是一个特殊的字符串。
• 符号 $\epsilon$: 这是在形式语言理论中，约定俗成地用来表示空字符串的符号，是小写的希腊字母 epsilon。
• 唯一的长度为 0 的字符串: 这是它的定义。它不包含任何符号。
• 脚注解释: $\epsilon$ 对应于 Python 中的字符串 ""。这个类比非常有助于理解。在几乎所有的编程语言中，都存在一个表示空的字符串，例如 "" (在C++, Java, Python, JavaScript等中) 或 '' (在Python, JavaScript中)。$\epsilon$ 就是这个概念在理论上的符号。
• 字符串的下标记法:
• $s=s_{1} s_{2} \ldots s_{n}$: 这是一种表示字符串结构的标准数学记法。
• $s$: 代表整个字符串。
• $n$: 字符串的长度，即 $|s|=n$。
• $s_i$: 代表字符串中第 $i$ 个位置的符号 (从1开始计数)。
• $s_i \in \Sigma$: 强调了每个位置上的符号都必须来自指定的字母表 $\Sigma$。

这一段定义了字符串的两种基本运算：反转和拼接。

• 反转 (Reversal):
• 记法 $s^R$: 这是表示字符串 $s$ 反转的标准记法。上标 'R' 代表 Reversal。
• 顺序反转的 s: 定义非常直观，就是把字符串的符号顺序完全颠倒。
• $s^{R}=s_{n} \ldots s_{2} s_{1}$: 这是基于下标记法的形式化定义。原来在第 $n$ 位的符号现在是第1位，原来第 $n-1$ 位的现在是第2位，依此类推。
• 拼接 (Concatenation):
• 记法 $s \circ t$ 或 $st$: ∘ 是形式化的运算符号，但在上下文中如果不会引起混淆，通常会省略，直接把两个字符串变量写在一起，就像代数中的乘法一样。
• 定义: 就是把字符串 $t$ 的内容紧跟在字符串 $s$ 的内容后面，形成一个更长的字符串。
• 例子分析:
• 拼接: $s = 11$, $t = 010$。$st = 11010$。
• 空字符串的拼接: $s = \epsilon$, $t = 00$。$\epsilon t = 00$。把一个空的字符串放在 00 前面，00 没有任何变化。同理，$t \epsilon = 00$。空字符串 $\epsilon$ 是字符串拼接运算的单位元 (identity element)，就像数字1是乘法的单位元 ($a \times 1 = 1 \times a = a$)。

这一段引入了从字母表生成所有可能字符串的集合的强大记法。

• $\Sigma^k$:
• 读法: "Sigma to the k" 或 "Sigma k"。
• 定义: 由字母表 $\Sigma$ 中的符号构成的、所有长度正好为 $k$ 的字符串的集合。
• 与笛卡尔积的关系: $\Sigma^k$ 本质上是字母表 $\Sigma$ 与自身进行 $k$ 次笛卡尔积的结果，只是我们不写成元组 (a,b) 的形式，而是写成字符串 ab 的形式。$\Sigma^2 \approx \Sigma \times \Sigma$。
• $\Sigma^*$ (Sigma Star):
• 读法: "Sigma star"，中文常称为“Sigma的克林闭包” (Kleene Closure)。
• 定义: $\Sigma$ 上所有可能的、任意长度的（包括长度为0）字符串的集合。
• $\Sigma^{*}=\cup_{i=0}^{\infty} \Sigma^{i}$: 这是 $\Sigma^*$ 的形式化定义。它等于所有长度为0的字符串的集合 ($\Sigma^0$)，与所有长度为1的字符串的集合 ($\Sigma^1$)，与所有长度为2的字符串的集合 ($\Sigma^2$)，...，取并集，一直到无穷。
• 例子分析:
• $\Sigma = \{0, 1\}$
• $\Sigma^0$: 所有长度为0的字符串的集合。只有一个成员，就是空字符串 $\epsilon$。所以 $\Sigma^0 = \{\epsilon\}$。
• $\Sigma^1$: 所有长度为1的字符串的集合。即 $\{0, 1\}$。这恰好等于字母表本身。
• $\Sigma^2$: 所有长度为2的字符串的集合。即 $\{00, 01, 10, 11\}$。
• $\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \ldots = \{\epsilon\} \cup \{0,1\} \cup \{00,01,10,11\} \cup \ldots$。这是一个包含所有可能的二进制字符串的无限集。

这一段给出了形式语言理论最核心的定义：语言。

• 一个语言 L (Language)：在形式语言理论中，“语言”这个词有非常精确的数学含义。
• 是字符串的集合: 这是语言定义的本质。一个语言不是别的，它就是一个集合，只不过这个集合里的元素比较特殊，都是字符串。
• $L \subseteq \Sigma^{*}$: 这是最关键的形式化定义。
• $\Sigma^*$: 我们刚刚定义过，它是在字母表 $\Sigma$ 上所有可能字符串的“宇宙”。
• $L \subseteq \Sigma^*$: 一个语言 $L$ 是这个宇宙的一个子集。这意味着，一个语言就是从所有可能的字符串中，根据某种规则，挑选出来的一部分字符串所组成的集合。
• 特别地，一个语言就是一个集合: 这句话再次强调了语言的本质。这意味着所有我们学过的集合运算（并集、交集、差集等）和关系（子集）都直接适用于语言。
• 它可以是有限的或无限的:
• 有限语言: 集合中包含有限个字符串。
• 无限语言: 集合中包含无限个字符串。
• 我们可以取两个语言的并集...: 因为语言是集合，所以可以对它们进行集合运算，得到新的语言。
• $L \cup L'$: 包含所有在 $L$ 中或者在 $L'$ 中的字符串。
• $L \cap L'$: 包含所有同时在 $L$ 和 $L'$ 中的字符串。

这一段定义了语言的一个重要运算：补集。

• 补集 (Complement)：给定一个语言 $L$，它的补集包含所有那些“可能存在但没有被 $L$ 包含”的字符串。
• 记法 $L^c$ 或 $\bar{L}$: 都是表示补集的标准符号。
• 是 $\Sigma$ 上所有不在 $L$ 中的字符串的集合: 这是自然语言定义。这里的关键是，我们讨论的范围被限制在“$\Sigma$ 上的所有字符串”之内，即 $\Sigma^*$。
• $L^{c}=\Sigma^{*} \backslash L$: 这是基于集合差运算的形式化定义。语言 $L$ 的补集，就是全集 $\Sigma^*$ 减去 $L$ 本身。
• $\{s \in \Sigma^{*}: s \notin L\}$: 这是用集合构造式给出的等价定义。补集的成员 $s$ 必须满足两个条件：1. 它必须是一个在 $\Sigma$ 上的合法字符串 ($s \in \Sigma^*$)；2. 它不能是 $L$ 的成员 ($s \notin L$)。

这一段通过三个例子，进一步澄清了语言的性质，特别是有限/无限，以及空语言的概念。

1. $L=\{0,1,000111\}$
   • 这是一个有限语言，因为它只包含3个字符串。
   • $0 \in L$: 字符串 0 是它的成员。
   • $\epsilon \notin L$: 空字符串 $\epsilon$ 不是它的成员。
2. $L=\{0,00,000, \ldots\}$
   • 这是一个无限语言，因为它包含了无限多个由 0 组成的字符串。
   • 关键点: 语言可以是无限的（包含无限多个字符串），但语言中的每一个字符串本身必须是有限长度的。
   • 对于任何 s in L，对于某个整数 k，我们有 |s|=k：这句话精确地表达了上述思想。例如，000 在 $L$ 中，它的长度是3，是有限的。你永远不会在 $L$ 中找到一个无限长的字符串。
3. $\{ \text{ } \}$ 是空语言
   • 空语言 (Empty Language): 这是一个不包含任何字符串的语言。
   • 记作 $\emptyset$: 这再次强调了语言就是集合，所以空语言就是空集。
   • 对于任何字符串 s，我们有 s not in O: 空语言里什么都没有。
   • 特别地 e not in O: 即使是空字符串 $\epsilon$，也不在空语言 $\emptyset$ 中。这是区分空语言 $\emptyset$ 和只包含空字符串的语言 $\{\epsilon\}$ 的关键点。

这是一个引言，告诉读者接下来将要介绍的是一系列可复用的“证明模板”或“证明策略”。这部分内容非常实用，它将前面介绍的逻辑规则转化为了解决问题的具体方法。

• 不确定如何开始证明: 这是学生在面对理论性问题时普遍的困境。不知道第一步该怎么写。
• 参考这些模板来寻找灵感: 作者表明，证明并不是漫无目的的，而是有一些常见的模式和套路。熟悉这些模板，可以为解决证明题提供一个清晰的起点和思路。

这个模板讲解了如何证明一个全称量化陈述 $(\forall x \in S, P(x))$。

• 证明“对于所有...”: 这种证明的目标是展示一个属性对一个集合中的所有元素都成立。
• 步骤 1: 设 $x$ 是 $S$ 的一个任意元素。: 这是证明的“起手式”。这句话非常关键。
• “设 $x$ ...”：引入一个变量。
• “是 $S$ 的一个元素”：明确变量的来源和范围。
• “任意 (arbitrary)”：这是最重要的词。它意味着你对这个 $x$ 不能做任何额外的、特殊的假设，除了它是 $S$ 的成员这个事实之外。它代表了 $S$ 中的任何一个元素。
• 步骤 2: 证明对于 $x$，该陈述为真。: 在引入这个“任意的” $x$ 之后，你的任务就是运用公理、定义和其他已知定理，通过逻辑推导，证明谓词 $P(x)$ 对这个 $x$ 成立。
• 确保你没有选择一个特定的 $x$ 来处理。: 这是一个重要的警告。因为你的证明必须对所有 $x$ 有效，所以如果你在证明中用了一个具体的值（比如“设 $x=2$”），那么你的证明就只对这一个值有效，而不能推广到所有情况。

这个例子完整地演示了证明模板1的应用。

• 命题: $\forall x \in \mathbb{Z}, (\text{IsOdd}(x) \rightarrow \text{IsOdd}(x^2))$。
• 证明步骤分析:

1. 设 $x$ 是一个奇整数。: 这一步完全符合模板。它引入了一个任意的元素 $x$，并假设了蕴含式的前提（$x$ 是奇数）。
2. 那么对于某个整数 $k$，$x=2 k+1$。: 这是使用了“奇数”的定义。任何奇数都可以表示为 $2 \times (\text{某个整数}) + 1$。这是我们能对这个“任意的” $x$ 使用的唯一信息。
3. 所以 $x^{2}=4 k^{2}+4 k+1$。: 对方程两边进行平方运算，这是一个代数操作。$(2k+1)^2 = (2k)^2 + 2(2k)(1) + 1^2 = 4k^2 + 4k + 1$。
4. 特别地，$x^{2}=2\left(2 k^{2}+2 k\right)+1$。: 这是证明的关键一步。我们想要证明 $x^2$ 是奇数，所以我们需要把它也凑成 $2 \times (\text{某个整数}) + 1$ 的形式。通过从前两项中提取公因数2，我们做到了这一点。
5. 所以 $x^{2}$ 是奇数。: 因为 $k$ 是整数，所以 $2k^2+2k$ 也必然是一个整数。我们成功地把 $x^2$ 表示成了 $2 \times (\text{一个新整数}) + 1$ 的形式。根据奇数的定义，$x^2$ 是奇数。
   • 对错误做法的批评:
   • “设 $x=5$...”: 这再次强调了使用具体例子来证明全称命题是无效的。这只能叫“验证”，不能叫“证明”。

这一段提出了与证明模板1相辅相成的另一个重要警告：当使用一个包含存在量词的定理时，你不能想当然地指定存在的是哪一个。

• “如果 A，那么存在 x 使得...”: 这是一种非常常见的定理形式，其结论是一个存在量化陈述。它告诉你“有”，但没告诉你“是哪个”。
• 确保你没有选择一个特定的 x: 当你应用这个定理时，你只能知道“存在这样一个x”，但你不能假设这个x是你想要的任何特定值。你必须把它当作一个未知的、但确实存在的实体来处理。
• 例子分析:
• 定理2: “如果 $L$ 是正则的 ($A$)，那么存在一个整数 $k \geq 1$，使得 $L$ 有一个 $k$ 状态的 DFA ($\exists k, P(k)$)”。
• 这个定理被称为“泵引理”的一个推论或正则语言定义的一部分。它保证了任何正则语言都有一个有限状态的自动机。
• 错误的应用:
• 已知: $L=\{0,00,000, \ldots\}$ 是一个正则语言。（这是真的，它可以被一个2状态的DFA识别）。
• 错误推论: “...所以它拥有一个具有 $k=2$ 个状态的 DFA”。
• 为什么错: 定理只承诺了存在一个 $k$，但没有告诉你 $k$ 的具体值。它可能是一个2状态的DFA，也可能是一个5状态的、或者100状态的（尽管效率不高）等价DFA。你直接断定 $k=2$ 是在定理保证范围之外添加了你自己的信息，这是无效的推理。
• 正确的应用: “根据定理2，由于 $L$ 是正则的，我们知道存在某个整数 $k \ge 1$，使得 $L$ 有一个 $k$ 状态的DFA。我们设这个DFA为 $M$，其状态数为 $k$。” 在后续的证明中，你只能使用这个抽象的、未定值的 $k$ 来进行推理。

这个模板讲解了如何证明一个存在量化陈述 $(\exists x \in S, P(x))$。这种证明被称为“构造性证明”(Constructive Proof)，因为它要求你“构造”出一个例子。

• 证明“存在一个...”: 这种证明的目标是展示至少有一个元素满足特定属性。
• 步骤 1: 选择一个特定的 $x \in S$。: 这是证明的起点。你的任务就是从论域 $S$ 中，像寻宝一样，找出一个能使命题为真的“宝藏” $x$。你需要明确地指出你选择的 $x$ 是什么。这与证明模板1中的“任意的x”形成鲜明对比。
• 步骤 2: 证明对于你选择的 $x$，$P(x)$ 为真。: 找到这个 $x$ 之后，你需要把它代入谓词 $P(x)$ 中，并通过计算或逻辑推理，验证 $P(x)$ 的确为真。
• 这里选择一个特定的 $x$ 值是可以的。: 这是关键。因为你的目标只是证明“至少有一个”，所以只要能成功地拿出一个例子，你的任务就完成了。

这个例子演示了如何应用证明模板2来证明一个关于形式语言的存在性命题。

• 命题: $\exists L \subseteq \{0,1\}^*, (\text{L has a 1-state DFA})$。
• 证明步骤分析:

1. 选择一个特定的 $L$: 证明者选择了 $L = \Sigma^*$，即在字母表 $\{0,1\}$ 上所有字符串的集合。这是一个非常好的选择，因为它是一个结构非常简单的语言。
2. 证明这个 $L$ 满足条件: 接下来，证明者必须展示如何为 $L=\Sigma^*$ 构建一个只有1个状态的 DFA (确定性有限自动机)。一个 DFA 由五个部分定义：状态集合 Q，字母表 $\Sigma$，转移函数 $\delta$，起始状态 $q_{start}$，接受状态集合 F。
   • 状态集合: $Q=\{q_0\}$。只有一个状态，满足了“仅有一个状态”的要求。
   • 字母表: $\Sigma=\{0,1\}$ (由题设给出)。
   • 起始状态: $q_{start} = q_0$。
   • 接受状态集合: $F=\{q_0\}$。因为我们要接受所有的字符串 (语言是 $\Sigma^*$)，所以起始状态本身就必须是接受状态，这样连空字符串 $\epsilon$ 都能被接受。
   • 转移函数 $\delta$: 这是核心。当机器处于状态 $q_0$ 时，无论读到输入符号 0 还是 1，它应该去哪里？因为我们想接受所有的字符串，所以无论读到什么，我们都应该保持在接受状态。因此，转移函数被定义为：
   • $\delta(q_0, 0) = q_0$ (在$q_0$读到0，回到$q_0$)
   • $\delta(q_0, 1) = q_0$ (在$q_0$读到1，回到$q_0$)
   • 结论: 证明者成功地构造出了一个具体的语言 ($L=\Sigma^*$)，并为它设计了一个完全合法的、只有一个状态的DFA。因此，原存在性命题成立。

这个模板讲解了证明蕴含式 $P \rightarrow Q$ 的最基本、最直接的方法，称为直接证明法 (Direct Proof)。

• 证明“如果 P 那么 Q”: 这是绝大多数数学定理的标准形式。$P$ 是前提/假设，$Q$ 是结论。
• 最简单的方法是说“假设 P 为真”: 这是直接证明的标志性第一步。你将前提 $P$ 暂时加入到你的“已知条件”集合中。你不是在断定 $P$ 在现实中一定是真的，而是在探索“如果 $P$ 碰巧是真的，会发生什么？”
• 然后推导出 $Q$ 必须为真: 在 $P$ 为真的这个假想世界里，你使用定义、公理以及其他已知的定理，通过一步步的逻辑演绎，最终推导出 $Q$ 也成立。
• 逻辑基础: 这个方法为什么有效？回顾 $P \rightarrow Q$ 的真值表。我们唯一需要避免的情况就是 $P$ 为真而 $Q$ 为假。直接证明法的思路就是：我们先假设自己处在 $P$ 为真的那两行（真值表的后两行），然后通过逻辑排除掉 $P=1, Q=0$ 的可能性，从而证明只能是 $P=1, Q=1$。对于 $P$ 为假的情况，无论 $Q$ 是什么，$P \rightarrow Q$ 都自动为真，所以我们根本无需考虑。

这个例子演示了直接证明法。

• 命题: $\forall n \in \mathbb{Z}, (\text{IsEven}(n) \rightarrow \text{IsEven}(n^2))$。虽然这里没有写 $\forall n$，但通常在数论陈述中这是默认的。证明本身是针对任意 $n$ 的，所以它是一个全称量化下的蕴含式证明。
• 证明步骤分析:

1. 假设 $n$ 是偶数。: 完全符合直接证明法的模板，假设前提 $P$ 为真。
2. 那么对于某个整数 $m$，我们可以写成 $n=2m$。: 这是使用了“偶数”的定义，将前提 $P$ 转化为了一个可用的代数表达式。
3. 所以 $n^{2}=4m^{2}= 2 \times\left(2m^{2}\right)$。:
   • $n^2 = (2m)^2 = 4m^2$。这是代数计算。
   • $4m^2 = 2 \times (2m^2)$。这是关键的代数变形。我们的目标是证明 $n^2$ 是偶数，所以我们需要把它写成 $2 \times (\text{某个整数})$ 的形式。我们成功做到了。
4. 所以 2 整除 $n^{2}$，这意味着 $n^{2}$ 必须是偶数。: 因为 $m$ 是整数，所以 $m^2$ 是整数， $2m^2$ 也是整数。令这个新整数为 $p=2m^2$。那么 $n^2 = 2p$。根据偶数的定义，这说明 $n^2$ 是偶数。我们成功地推导出了结论 $Q$。

这一段是一个过渡，引出了证明蕴含式的另外两种重要方法，并指出了一个印刷错误。

• 还有其他方法可以做: 直接证明法虽然直观，但并不总是最容易或最有效的方法。有时从前提P很难直接推导出结论Q。
• 两种最常用的方法: 这里预告了即将登场的反证法 (Proof by Contradiction) 和 逆否命题证明法 (Proof by Contraposition)。
• 重要记忆：$P \rightarrow B$ 的否定是 $P \wedge \neg P$: 这是一个明显的印刷错误！
• $P \wedge \neg P$ 是一个矛盾式 (Contradiction)，它永远为假。
• 正确的否定应该是：$\neg(P \rightarrow Q)$。
• 我们知道 $P \rightarrow Q \equiv \neg P \vee Q$。
• 所以 $\neg(P \rightarrow Q) \equiv \neg(\neg P \vee Q)$。
• 根据德·摩根定律，这等价于 $\neg(\neg P) \wedge (\neg Q)$。
• 最终得到 $P \wedge \neg Q$。
• 正确的记忆应该是: $P \rightarrow Q$ 的否定是 $P \wedge \neg Q$。它的意思是：“前提 $P$ 成立了，但结论 $Q$ 却没有发生。” 这正是蕴含式为假的唯一情况。这个正确的否定形式是反证法的逻辑基础。

这个模板讲解了反证法 (Proof by Contradiction)，一种强大但有时不那么直观的间接证明方法。

• 反证法: 拉丁语 "reductio ad absurdum"，意为“归谬”。
• 假设要证明的陈述是假的: 这是反证法的第一步，也是它与直接证明法的根本区别。
• 如果我们要证明命题 $S$，我们就假设 $\neg S$ 为真。
• 如果我们要证明蕴含式 $P \rightarrow Q$，我们就假设它的否定 $\neg(P \rightarrow Q)$ 为真。正如我们之前分析的，这等价于假设 $P \wedge \neg Q$ 为真。也就是说，我们同时假设“前提P为真”和“结论Q为假”。
• 然后得出矛盾: 在这个“被证陈述为假”的假设下，我们进行逻辑推导。我们的目标是推导出一个矛盾 (Contradiction)。
• 矛盾是指一个形如 $R \wedge \neg R$ 的陈述，即一个命题和它的否定同时为真。例如，“$n$ 是偶数并且 $n$ 是奇数”，或者 "$1=0$"。这是一个逻辑上绝对不可能为真的东西。
• 从而断定该陈述是真的: 如果一个假设能导出一个逻辑上绝对不可能的矛盾，那么根据排中律 (Law of Excluded Middle，即一个命题要么为真要么为假，没有第三种可能)，这个假设本身必定是假的。
• 既然假设“被证陈述为假”是错误的，那么“被证陈述为真”就必然是正确的。
• 它通常应用于形式为 $P \Rightarrow Q$ 的陈述: 这里的 ⇒ 和 → 是一样的。对于 $P \rightarrow Q$，反证法的假设就是 $P$ 为真且 $Q$ 为假。

这个例子演示了如何用反证法来证明一个蕴含式。

• 命题: $P \rightarrow Q$，其中 $P$: "$3n+2$ 是奇数"， $Q$: "$n$ 是奇数"。
• 证明步骤分析:

1. 为了进行反证，假设...: 这句话表明了要使用的证明方法。
2. 假设 $3n+2$ 是奇数，且 $n$ 是偶数。: 这一步是反证法的核心。它假设了前提 $P$ 为真 ($3n+2$ 是奇数)，并且结论 $Q$ 为假 ($n$ 不是奇数，即 $n$ 是偶数)。这完全符合假设 $P \wedge \neg Q$ 的模式。
3. 因为 $n$ 是偶数，所以... $n=2k$: 证明者抓住了假设中更有用的一部分 ($\neg Q$)，即 "$n$ 是偶数"，并使用了它的定义。
4. 这意味着 $3n+2=...=2(3k+1)$: 接下来进行代数替换和变形，目的是看看从 "$n$ 是偶数" 这个假设能推导出什么关于 $3n+2$ 的信息。
5. 我们可以定义 $t=3k+1$，因此 $3n+2=2t$: 这是一个清晰的整理步骤。因为 $k$ 是整数，所以 $t=3k+1$ 也是整数。
6. 这意味着 $3n+2$ 是偶数: 根据偶数的定义 ($2 \times \text{整数}$)，推导出 $3n+2$ 是偶数。
7. 这样我们就得出了一个矛盾: 关键的一步。我们现在有两个关于 $3n+2$ 的陈述：
   • 从我们的假设中，我们有 "$3n+2$ 是奇数" (来自 $P$)。
   • 从我们的推导中，我们有 "$3n+2$ 是偶数"。
8. 所以如果...必须为真: 因为我们的初始假设 ($P \wedge \neg Q$) 导出了一个逻辑矛盾，所以这个假设本身必须是假的。因此，它的否定 $\neg(P \wedge \neg Q)$，也就是 $P \rightarrow Q$，必须是真的。证明完成。

这是一个重要的提示和过渡。

• 另一个选择是逆否命题证明法: 明确提出了即将介绍的第三种证明蕴含式的方法。
• 不要将其与反证法混淆: 这是一个非常常见且重要的警告。因为这两种方法都是“间接证明”，它们的起始步骤看起来有些相似，所以初学者很容易混淆。

反证法 vs 逆否命题证明法 (证明 $P \rightarrow Q$)

总结: 逆否命题证明法的结构更像一个直接证明，它有明确的起点($\neg Q$)和终点($\neg P$)。而反证法的目标更开放，只要能找到任何矛盾就行，这使得它更灵活，但有时也可能让证明者迷失方向。

这个模板讲解了逆否命题证明法 (Proof by Contraposition) 的具体步骤。

• 不直接证明 $P \Rightarrow Q$，而是证明其逆否命题：$\neg Q \Rightarrow \neg P$: 这是该方法的核心思想。它利用了我们在前面学到的逻辑等价性 $(P \rightarrow Q) \leftrightarrow (\neg Q \rightarrow \neg P)$。既然两者是等价的，证明任何一个都等于证明了另一个。
• 过程是这样的...: 这描述了证明逆否命题 $\neg Q \rightarrow \neg P$ 的过程。

1. 说“假设 $\neg Q$ 为真”: 这是证明的起点。我们假设原结论 $Q$ 的否定为真。
2. 并推导出 $\neg P$ 为真: 以 $\neg Q$ 为出发点，通过一系列逻辑推导，最终得到原前提 $P$ 的否定 $\neg P$。
   • 与直接证明的相似性: 整个过程实际上就是对 $\neg Q \rightarrow \neg P$ 这个新的蕴含式进行直接证明。所以，如果你掌握了直接证明法，你就自动掌握了逆否命题证明法。

这个例子演示了逆否命题证明法。

• 命题: $P \rightarrow Q$，其中 $P$: "$x^2$ 是偶数"， $Q$: "$x$ 是偶数"。
• 证明步骤分析:

1. 该陈述的逆否命题是...: 证明的第一步就是清晰地写出我们要转而证明的逆否命题。
   • 原结论 $Q$ ("$x$ 是偶数") 的否定 $\neg Q$ 是 "$x$ 是奇数"。
   • 原前提 $P$ ("$x^2$ 是偶数") 的否定 $\neg P$ 是 "$x^2$ 是奇数"。
   • 所以逆否命题是 $\neg Q \rightarrow \neg P$，即 “如果 $x$ 是奇数，那么 $x^2$ 是奇数”。
2. 因此证明过程如下: 表明接下来是在证明这个新的逆否命题。
3. 假设 $x$ 是奇数。: 对逆否命题进行直接证明，假设其前提 ($\neg Q$) 为真。
4. 两个奇数的乘积是奇数，因此 $x \cdot x=x^{2}$ 是奇数。: 这里使用了一个已知的定理（“两个奇数的乘积是奇数”）来快速完成证明。
   • 如果不用这个定理，该如何证明？: 这就回到了 示例 7 的证明。假设 $x=2k+1$，那么 $x^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1$。因为 $2k^2+2k$ 是整数，所以 $x^2$ 是奇数。
5. 所以 $x^2$ 不是偶数。: 这是对“$x^2$ 是奇数”的另一种说法，它直接对应了逆否命题的结论 $\neg P$。
6. 因此，如果 $x^2$ 是偶数，那么 $x$ 是偶数。: 最后，明确声明由于逆否命题已被证明为真，与之等价的原命题也必然为真。

这是一个引言，预告了下一个证明模板，即如何证明逻辑等价或“当且仅当”($\leftrightarrow$) 的陈述。

• 证明 $P \leftrightarrow Q$: 这种形式的命题要求证明 $P$ 和 $Q$ 是“同进同退”的，它们的真值完全绑定。
• 你应该按以下方式进行: 暗示了这是一个有固定流程的标准任务。

这个模板讲解了证明“当且仅当”陈述的标准方法。

• 要证明 $P \leftrightarrow Q$，你必须证明...: 这个模板的核心是利用逻辑等价的定义：$P \leftrightarrow Q \equiv (P \rightarrow Q) \wedge (Q \rightarrow P)$。
• 步骤: 证明被拆分成了两个独立的子任务：

1. 证明 $P \rightarrow Q$: 这被称为“正向”或“充分性” (sufficiency) 的证明。即证明 $P$ 是 $Q$ 的充分条件。
2. 证明 $Q \rightarrow P$: 这被称为“反向”或“必要性” (necessity) 的证明。即证明 $P$ 是 $Q$ 的必要条件。（或者说 $Q$ 是 $P$ 的充分条件）。
   • 不要忘记证明这两个陈述: 这是一个非常重要的警告。只证明了单向，是蕴含式证明，不是等价证明。在评分时，双向证明通常各占一半的分数。
   • 你可以为每个陈述使用不同的技巧: 这一点非常灵活。在证明 $P \rightarrow Q$ 时，你可能会发现直接证明法最简单。而在证明 $Q \rightarrow P$ 时，逆否命题证明法或反证法可能更方便。你可以自由组合使用之前学到的所有模板。
   • 例子: “要证明 $P \leftrightarrow Q$，你可以证明 $P \rightarrow Q$ 和 $\neg P \rightarrow \neg Q$”。
   • 这其实是一个笔误或者不清晰的表述。$\neg P \rightarrow \neg Q$ 是 $Q \rightarrow P$ 的逆否命题吗？不是。
   • $Q \rightarrow P$ 的逆否命题是 $\neg P \rightarrow \neg Q$。
   • $P \rightarrow Q$ 的逆否命题是 $\neg Q \rightarrow \neg P$。
   • 所以，作者想表达的意思可能是：你可以通过证明 $P \rightarrow Q$ 和 $\neg Q \rightarrow \neg P$ 来完成。因为 $\neg Q \rightarrow \neg P$ 等价于 $P \rightarrow Q$ 的逆否命题。这仍然是笔误。
   • 正确的说法应该是：要证明 $P \leftrightarrow Q$，你可以证明：
3. $P \rightarrow Q$ (例如，用直接证明法)
4. $Q \rightarrow P$ (例如，用逆否命题证明法，即证明 $\neg P \rightarrow \neg Q$)
   • 或者：
5. $P \rightarrow Q$ (例如，用逆否命题证明法，即证明 $\neg Q \rightarrow \neg P$)
6. $Q \rightarrow P$ (例如，用直接证明法)
   • 总之，你必须完成两个独立方向的证明，至于每个方向具体用什么技巧，可以灵活选择。

这是一个引言，引出了最后一种，也是非常重要的一种证明技巧：数学归纳法。

• 数学归纳法 (Mathematical Induction)：这是一种专门用来证明关于自然数（或所有整数、或所有 $\ge$ 某个起始值的整数）的全称量化陈述的强大技巧。
• 常见的证明技巧: 它在离散数学、算法分析（证明循环不变式、递归算法的正确性）、图论等领域中无处不在。

这个模板详细讲解了数学归纳法的两种形式：标准归纳法和强归纳法。

• 目标: 证明一个关于自然数的谓词 $P(n)$ 对于从某个起点开始的所有值都为真。例如 $\forall n \in \{1, 2, 3, \ldots\}, P(n)$。
• 标准归纳法 (Standard/Weak Induction):

1. 基础步骤 (Basis Step): 这是多米诺骨牌的第一块。你需要证明命题对于起始值成立。如果命题是“对所有正整数”，起始值就是1，你需要证明 $P(1)$。如果命题是“对所有非负整数”，起始值就是0，你需要证明 $P(0)$。这是归纳的“锚点”。
2. 归纳步骤 (Inductive Step): 这是证明骨牌之间的“连锁反应”。
   • 证明 $P(k) \rightarrow P(k+1)$: 这是一个蕴含式证明。你需要证明的是：如果 命题对某个任意的正整数 $k$ 成立，那么它也必然对紧接着的下一个整数 $k+1$ 成立。
   • 归纳假设 (Inductive Hypothesis, I.H.): 在进行归纳步骤的证明时，我们假设其前提 $P(k)$ 为真。这个假设是合法的，因为我们是在证明一个蕴含式。
   • 证明 $P(k+1)$: 以归纳假设 $P(k)$ 为真作为已知条件，通过代数或逻辑推导，证明 $P(k+1)$ 也必须为真。
   • 调整基础步骤: 数学归纳法不一定从0或1开始。如果一个命题是“对于所有 $n \ge 5$ 成立”，那么你的基础步骤就是证明 $P(5)$。
   • 强归纳法 (Strong Induction):
   • 基础步骤: 通常与标准归纳法相同。有时可能需要验证多个基础案例 (如 $P(1)$ 和 $P(2)$)。
   • 归纳步骤: 这里的归纳假设更“强”。
   • 标准归纳法假设: 只假设 $P(k)$ 为真。
   • 强归纳法假设: 假设 $P(1), P(2), \ldots, P(k)$ 所有在 $k+1$ 之前的命题都为真。
   • 目标: 在这个更强的假设下，证明 $P(k+1)$ 为真。
   • 强弱之分: 看起来强归纳法的假设更强，似乎更难用。但实际上，强归纳法和标准归纳法是逻辑等价的。任何能用其中一种证明的，也都能用另一种证明。选择哪一种取决于哪个更方便。当 $P(k+1)$ 的真假不仅依赖于 $P(k)$，还可能依赖于更早的 $P(k-1)$ 或 $P(k-2)$ 时（例如，斐波那契数列相关的证明），强归纳法就变得非常有用。

这个例子完整地演示了如何使用标准数学归纳法来证明一个关于等比数列求和的公式。

• 命题: $\forall n \in \{0, 1, 2, \ldots\}, \sum_{i=0}^{n} 2^i = 2^{n+1}-1$。
• 证明步骤分析:

1. 设 $P(n)$ 为命题...: 这是一个很好的习惯，首先清晰地定义出我们要归纳的谓词 $P(n)$。
2. 基础步骤:
   • 因为命题是“对于所有 $n \ge 0$”，所以起始值是 $n=0$。我们需要验证 $P(0)$。
   • $P(0)$ 的内容是：$\sum_{i=0}^{0} 2^i = 2^{0+1}-1$。
   • 左边：$\sum_{i=0}^{0} 2^i = 2^0 = 1$。
   • 右边：$2^{0+1}-1 = 2^1-1 = 2-1=1$。
   • 因为左边=右边 (1=1)，所以 $P(0)$ 为真。基础步骤完成。
3. 归纳步骤:
   • 我们假设 $P(k)$ 对于一个任意的非负整数 $k$ 为真: 这是归纳假设 (I.H.)。我们假设对于某个 $k \ge 0$，下面的等式是成立的：
   • 目标: 我们需要利用这个假设，去证明 $P(k+1)$ 也为真。$P(k+1)$ 的内容是：
   • 推导过程:
   • 证明者从 $P(k+1)$ 的左边表达式入手：$1+2+\ldots+2^{k}+2^{k+1}$。
   • 他注意到这个表达式的前半部分 $(1+2+\ldots+2^{k})$ 正好是归纳假设 $P(k)$ 中的左边！
   • 我们在上述方程的两边都加上 $2^{k+1}$: 这是一个非常聪明且常见的技巧。它直接从归纳假设的等式出发，通过两边同时做一个操作，来凑出 $P(k+1)$ 的形式。
   • 左边变成了 $P(k+1)$ 的左边: $1+2+\ldots+2^{k}+2^{k+1}$。
   • 右边变成了: $(2^{k+1}-1) + 2^{k+1}$。
   • 化简右边:
   • $(2^{k+1}-1) + 2^{k+1} = 2 \cdot (2^{k+1}) - 1$ (合并同类项)
   • $2 \cdot (2^{k+1}) - 1 = 2^1 \cdot 2^{k+1} - 1 = 2^{1+(k+1)} - 1 = 2^{(k+1)+1} - 1$ (指数相加)
   • 结论: 我们最终得到的右边 $2^{(k+1)+1}-1$ 正好是 $P(k+1)$ 目标形式的右边！
   • 因此，如果 $P(k)$ 为真，那么 $P(k+1)$ 也为真: 这句话总结了归纳步骤的成功。
4. 通过数学归纳法...: 最后，根据归纳法原理，既然基础步骤和归纳步骤都已完成，那么命题对所有 $n \ge 0$ 都成立。

这是一个脚注，为理论概念提供了一个具体的、在编程实践中的类比。

• [^0]: 这是脚注的标记。
• ${ }^{1}: 这是另一个标记，似乎与前面的标记重复，可能是格式问题。核心内容是后面的文本。
• \epsilon: 这是在形式语言理论和自动机理论中广泛使用的，代表空字符串 (The Empty String) 的标准符号。
• 对应于 Python 中的字符串 "": 这是一个非常有帮助的类比。
• 在 Python (以及许多其他编程语言如 C++, Java, JavaScript) 中，一个字符串可以不包含任何字符。这个特殊的字符串通过一对紧邻的引号 "" 或 '' 来表示。
• 它的 len() 长度是 0。
• 它在字符串拼接中扮演着单位元的角色："abc" + "" = "abc" 并且 "" + "abc" = "abc"。
• 理论符号 $\epsilon$ 就拥有所有这些与 "" 完全相同的性质：$|\epsilon|=0$，对于任何字符串 $s$，$s\epsilon = \epsilon s = s$。
• 这个脚注的目的就是告诉有编程经验的读者：“别把 $\epsilon$ 想得太神秘，它就是你天天在代码里用的那个空字符串 ""。”