0_绪论0.2.ZH解释

这段话是本节的开场白，作用是告诉读者接下来要讲什么。它强调了在深入学习计算理论这门学科之前，首先需要打好“地基”。这个“地基”就是所有数学和形式化科学都依赖的一套共同语言和工具。

• 任何数学学科一样：这句话表明，我们现在要做的，是任何严谨的数学领域（如代数、几何、微积分）在开始时都会做的事情——定义基础。这为学习设置了一个严谨、规范的基调。
• 基本数学对象：这些是我们要研究和操作的核心“物品”。在本课程中，这些“对象”不是传统数学中的数字或图形，而更多是像集合、字符串、语言、图这样的抽象结构。它们是构建自动机、文法和算法的“积木”。
• 工具：这些是用来操作“数学对象”的方法和概念。例如，函数可以描述一种转换规则，关系可以描述对象之间的联系，布尔逻辑可以用来进行推理和判断。
• 符号：这指的是我们将使用的记法系统。数学符号是一种精确、无歧义的语言。例如，用 $\in$ 表示“属于”，用 $\cup$ 表示“并集”，这些符号能够简洁地传达复杂而精确的含义，避免了日常语言的模糊性。

1. 集合的本质：集合（Set）在数学上是一个非常基础的概念。可以把它理解成一个“袋子”或者一个“容器”。
2. “一组作为整体表示的对象”：
   • “一组对象”：说明集合里装着不止一个东西（当然也可以只装一个，或者一个都不装）。这些“东西”就是对象。
   • “作为整体表示”：这是关键。我们关心的不是单个对象，而是把这一堆对象打包成的“一个”新东西，这个新东西就是集合。例如，$\{7, 21, 57\}$ 这三个数字打包在一起，形成了一个名为 $S$ 的实体。从此我们可以直接讨论 $S$ 这个整体，而不仅仅是 7、21、57 这三个独立的数字。
3. 元素的类型：集合的强大之处在于它的包容性。
   • 任何类型的对象：你可以把任何你能想到的东西放进集合。
   • 数字：如 $\{1, 2, 3\}$。
   • 符号：如 \{a, b, c\}，这是计算理论中定义字母表的基础。
   • 其他集合：这是集合论中一个稍微高级但非常重要的概念。一个集合的元素可以是另一个集合。例如，$A = \{1, 2\}$，$B = \{3, 4\}$，我们可以构造一个新的集合 $C = \{A, B\} = \{\{1, 2\}, \{3, 4\}\}$。注意，集合 $C$ 只有两个元素：集合A 和 集合B，而不是四个数字。
4. 元素与成员：元素（element）和成员（member）是同义词，都指集合里装的那些“东西”。
5. 描述方式1：列举法：这是最直观的表示方法。
   • 花括号 {}：这是集合的标志性符号。看见花括号，就要想到“这是一个集合”。
   • 列出元素：把集合里所有的成员都写在花括号里面。
   • 逗号分隔：成员与成员之间用逗号隔开。
   • 示例 $S = \{7, 21, 57\}$：这个表示法清晰地告诉我们，有一个名为 $S$ 的集合，它里面有且仅有 7, 21, 57 这三个元素。

1. 成员关系（Membership）
   • $\in$（属于）：这个符号用来判断一个对象是否是某个集合的成员。它的形状像一个圆润的 'e'，可以记成 "element of"（...的元素）。
   • $7 \in \{7, 21, 57\}$ 的意思是：“7 是集合 $\{7, 21, 57\}$ 的一个成员”。这句话是真的。
   • $\notin$（不属于）：这个符号是 $\in$ 上加了一条斜杠，表示否定。
   • $8 \notin \{7, 21, 57\}$ 的意思是：“8 不是集合 $\{7, 21, 57\}$ 的一个成员”。这句话也是真的，因为集合里没有8。
2. 子集关系（Subset）
   • $A \subseteq B$（子集）：这个符号用来描述两个集合之间的“包含”关系。它表示集合A里的所有元素，在集合B里也都能找到。
   • “如果A的每个成员也是B的成员”：这是子集的核心定义。要判断 $A \subseteq B$ 是否成立，你需要检查 $A$ 里的每一个元素，看它是否也在 $B$ 中。只要有一个不在，这个关系就不成立。
   • $\subseteq$ 这个符号很形象，像一个等号 $=` 上面加了一个开口的 `$\subset$`，可以理解为“小于或等于”，即 `$A$` 或者比 `$B$` 小，或者和 `$B$ 完全一样。
3. 真子集关系（Proper Subset）
   • $A \subsetneq B$（真子集）：这是一个更严格的子集关系。它要求 $A$ 是 $B$ 的子集，并且 $A$ 和 $B$ 不能是同一个集合。换句话说，$B$ 必须至少有一个元素是 $A$ 所没有的。
   • “A是B的子集且不等于B”：这是真子集的核心定义。它有两个条件：1. $A \subseteq B$ 成立；2. 存在至少一个元素 $x$，使得 $x \in B$ 但 $x \notin A$。
   • $\subsetneq$ 这个符号去掉了下面的横线，可以理解为“严格小于”，排除了相等的情况。

1. 集合的两大特性
   • 无序性 (Unordered)：在一个集合中，元素的排列顺序是无关紧要的。$\{a, b, c\}$ 和 $\{c, a, b\}$ 是完全相同的集合。这就像一个袋子里装了三个球，你伸手进去摸，没有“第一个”或“最后一个”的概念。
   • 互异性 (Distinct)：集合中的每个元素都是独一无二的。如果你尝试在一个集合中放入两个相同的元素，它们会自动“合并”成一个。所以，写 $\{7, 7, 21\}$ 是可以的，但它表达的意思和 $\{7, 21\}$ 完全一样。重复的元素不增加集合的“大小”或改变其内容。
2. 示例的解释
   • $\{57, 7, 7, 7, 21\}$ 和 $S = \{7, 21, 57\}$ 是相同的集合。为什么？
   • 无序性：$\{57, 7, 21\}$ 和 $\{7, 21, 57\}$ 只是顺序不同，所以是同一个集合。
   • 互异性：$\{57, 7, 7, 7, 21\}$ 中的重复的 7 被忽略，它实际上就是 $\{57, 7, 21\}$。
   • 结合两者，它们都表示包含7, 21, 57这三个元素的集合。
3. 多重集 (Multiset)
   • 这是一个与集合不同的概念，有时也叫“袋集”（bag）。
   • 多重集允许元素重复，并且重复的次数是有意义的。
   • $\{7\}`` 和 `$\{7,7\} 作为多重集是不同的。前者包含一个7，后者包含两个7。
   • 但作为集合，根据互异性，它们是相同的，都等价于 $\{7\}。
4. 无限集 (Infinite Set)
   • 当一个集合的元素个数是无限的，我们称之为无限集。
   • 显然，我们无法通过列举法写出所有元素。
   • 省略号 “...”：这是一个非正式但广泛接受的符号，用来表示一个明显的序列在无限延伸。
   • 自然数集 $\mathcal{N}$: $ \{1, 2, 3, \ldots\} $。这里的 ... 意味着“按照加1的规律一直下去，永不停止”。（注意：在不同上下文中，自然数有时包含0，但本书约定从1开始）。
   • 整数集 $\mathcal{Z}$: $\{ \ldots, -2, -1, 0, 1, 2, \ldots \}$。这里的 ... 用了两次，表示向正负两个方向无限延伸。

1. 空集 (Empty Set)
   • 这是一个非常重要但又有点抽象的概念。空集是一个特殊的集合，它的特殊之处在于它里面什么都没有。
   • 它是一个完全合法的集合，满足集合的所有定义。它是一个“袋子”，只不过这个袋子是空的。
   • 写法：$\emptyset$ 是一个专门的符号，代表空集。它也可以写成 $\{ \}`，一个里面没有任何东西的花括号。
   • 没有成员的集合：这意味着对于任何一个对象 $x$，$x \in \emptyset$ 这句话永远是假的。
2. 单例集 (Singleton Set)
   • 这是一个非常简单的概念，就是一个集合里只有一个成员。
   • 例如 $\{a\}$ 是一个单例集，它的唯一成员是 a。$\{7\}$ 也是一个单例集。
   • 强调：必须区分元素和包含该元素的单例集。$a$ 和 $\{a\}$ 是两种完全不同的东西。前者是一个元素，后者是一个集合。
3. 无序对 (Unordered Pair)
   • 就是一个集合里正好有两个成员。
   • 例如 $\{a, b\}`。
   • “无序” 这个词再次强调了集合的无序性。$\{a, b\}$ 和 $\{b, a\}$ 是同一个无序对。这与后面将要学的有序对 (a, b) 形成对比，在有序对中 (a, b) 和 (b, a) 是不同的。

1. 描述法的动机：对于无限集或者元素非常多、有规律的有限集，列举法（$\{1, 2, 3, \ldots\}$）显得不够精确或不可能。我们需要一种更强大、更形式化的方法来定义集合。
2. 集合构建器表示法 (Set-Builder Notation)：$\{n \mid \text{规则}\}$ 就是这种方法。它不直接给出元素，而是给出一个“会员资格测试”的规则。一个对象要想成为这个集合的成员，就必须通过这个测试。
3. 结构分析：$\{ \text{变量} \mid \text{条件} \}$

• {}: 仍然是集合的标志。
• 变量 (例如 n): 这是一个占位符，代表了我们正在考虑的“候选成员”的一般形式。
• $\mid$: 这是一个分隔符，读作“使得 (such that)”。有时也用冒号 : 代替。
• 条件 (例如 关于 n 的规则): 这是一个逻辑断言或属性。只有当候选成员 n 使得这个条件为真时，n 才能被接纳进集合。

1. 示例的解读：$\left\{n \mid n=m^{2} \text{ 且 } m \in \mathcal{N}\right\}$

• “我们正在构建一个集合，里面的元素我们暂时叫它 n...” ($\{n \mid \ldots \}`)
• “...什么样的 n 才有资格进来呢？” ($\ldots n=m^{2} \text{ 且 } m \in \mathcal{N} \}$)
• 规则有两部分，必须同时满足（因为用了“且”）：

1. $n=m^2$: n 必须是某个数的平方。
2. $m \in \mathcal{N}$: 那个数 $m$ 还必须是一个自然数 (根据本书约定，$\mathcal{N} = \{1, 2, 3, \ldots\}`)。
   • 实际构建过程（思维实验）:
   • 取第一个自然数 $m=1$，计算 $n = 1^2 = 1$。1 满足规则，所以 1 是集合的一个成员。
   • 取第二个自然数 $m=2$，计算 $n = 2^2 = 4$。4 满足规则，所以 4 是集合的一个成员。
   • 取第三个自然数 $m=3$，计算 $n = 3^2 = 9$。9 满足规则，所以 9 是集合的一个成员。
   • ... 以此类推。
   • 结论：这个集合就是所有自然数的平方组成的集合，即 $\{1, 4, 9, 16, 25, \ldots\}$，也就是完全平方数集。

这里介绍了对集合进行操作的三种基本“算术”。

1. 并集 (Union)
   • 符号：$A \cup B$
   • 含义：“或”的逻辑。一个元素只要在集合 $A$ 或在集合 $B$ 中（或者两者都在），它就在并集 $A \cup B$ 中。
   • 操作：想象把 $A$ 袋子和 $B$ 袋子里的所有东西都倒进一个更大的新袋子里。根据集合的互异性，如果某个东西两个袋子里都有，新袋子里也只保留一份。
   • “将A和B中的所有元素组合成一个集合”：这就是上述操作的文字描述。
2. 交集 (Intersection)
   • 符号：$A \cap B$
   • 含义：“与”的逻辑。一个元素必须同时在集合 $A$ 和集合 $B$ 中，它才能在交集 $A \cap B$ 中。
   • 操作：想象对比 $A$ 和 $B$ 两个袋子，只挑出那些两个袋子里共同拥有的东西，放入一个新袋子。
   • “是同时在A和B中的元素集”：这是交集的精确定义。
3. 补集 (Complement)
   • 符号：$\bar{A}$ (有时也写作 $A^c$ 或 $A'$)
   • 含义：“非”的逻辑。一个元素不在集合 $A$ 中，它就在 $A$ 的补集中。
   • 操作：这个操作有一个重要的前提，就是必须先定义一个“宇宙”或“全集” (Universe)，我们用 $U$ 表示。补集是相对于这个全集而言的。$\bar{A}$ 指的是在全集 $U$ 中，但不在 $A$ 中的所有元素。
   • “所考虑的所有元素中不在A中的元素集”：“所考虑的所有元素”指的就是这个隐含的全集。如果没有定义全集，讨论补集是没有意义的。

1. 文氏图 (Venn Diagram) 的基本思想：将抽象的集合关系转化为直观的几何图形关系。
   • 集合 -> 圆形区域: 每个集合用一个圆圈（或任何闭合曲线）表示。圈内的空间代表属于该集合的元素所在的位置。
   • 元素 -> 点: 单个的元素可以表示为区域内的一个点。
   • 全集 -> 方框: 通常，整个文氏图会画在一个大方框里，这个方框代表全集 U。
2. 图0.1 和 图0.2 的分析:
   • START-t: 一个圆圈，代表“所有以t开头的英文单词”这个集合。圈里面画了几个点，并标注了 "tea", "tent", "taco" 作为示例元素。
   • END-z: 另一个圆圈，代表“所有以z结尾的英文单词”这个集合。里面标注了 "buzz", "jazz", "quiz" 作为示例元素。
   • 这两个图分别独立地展示了一个集合。
3. 图0.3 的分析:
   • 重叠区域: START-t 和 END-z 的圆圈有一部分重叠了。这个重叠区域代表了两个集合的交集，即同时满足“以t开头”和“以z结尾”的单词。图中用 "topaz" 作为一个例子放在重叠区。
   • 非重叠区域:
   • START-t 圆圈中不与 END-z 重叠的部分，代表那些只以t开头，但不以z结尾的单词。
   • END-z 圆圈中不与 START-t 重叠的部分，代表那些只以z结尾，但不以t开头的单词。
   • 不相交的圆圈: 图中还有一个 START-j 的圆圈，它和 START-t 的圆圈完全分离，没有重叠。这直观地表示 START-j 和 START-t 的交集是空集 ($\emptyset$)，即不存在一个单词既以 'j' 开头又以 't' 开头。这种集合关系称为不相交 (disjoint)。
4. 图0.4 的分析:
   • 这是对上一节集合运算的通用、抽象的可视化。
   • 图(a) $A \cup B$: 阴影部分覆盖了圆圈A的全部和圆圈B的全部。这直观地展示了并集的“合并”特性：只要在一个圈里，就在阴影区里。
   • 图(b) $A \cap B$: 阴影部分只覆盖了圆圈A和圆圈B重叠的那一小块区域。这直观地展示了交集的“共同”特性：必须同时在两个圈里，才在阴影区里。

1. 序列 (Sequence) 的核心定义：“按一定顺序排列的列表”。这是序列与集合最根本的区别。
   • 列表: 意味着序列中的元素可以被一个个拿出来。
   • 按一定顺序排列: 这是关键。序列中有“第一个元素”、“第二个元素”...的概念。元素的位置是其身份的一部分。
2. 表示法：
   • 使用圆括号 ()（有时也用尖括号 <>）。这与集合的花括号 {} 形成对比。
   • 元素之间用逗号分隔。
3. 序列的两大特性 (与集合对比)：
   • 有序性 (Ordered): 元素的顺序很重要。交换两个元素的位置，会得到一个不同的序列。例如，$(7, 21, 57)$ 表示先是7，然后是21，最后是57。而 $(57, 7, 21)$ 表示先是57，然后是7，最后是21。这两个是不同的序列。
   • 可重复性 (Repetition Matters): 序列中可以包含重复的元素，并且重复的次数和位置都是有意义的。$(7, 7, 21, 57)$ 是一个合法的序列，它有4个元素。它与 $(7, 21, 57)$ (3个元素) 和 $(7, 21, 7, 57)$ (4个元素，但重复位置不同) 都是不同的序列。
4. 有限序列与元组 (Tuple)：
   • 当序列的长度是有限的时候，我们通常给它一个更具体的名字：元组。
   • k-元组: 一个长度为 k 的元组。
   • 3-元组: (7, 21, 57) 是一个3-元组。
   • 2-元组: 特别地，长度为2的元组有一个非常常用的名字：有序对 (Ordered Pair)。例如 (a, b)。这在定义坐标、关系等方面非常重要。

1. 复合结构的思想：数学的威力在于能够用简单的构建块（集合、序列）通过运算规则，创造出更复杂、更强大的结构。这里介绍了两种非常重要的构造方法：幂集和笛卡尔积。
2. 幂集 (Power Set)
   • 定义：一个集合 $A$ 的幂集，通常记作 $\mathcal{P}(A)$ 或 $2^A$，它本身是一个集合，但它的元素非常特殊：它们是 $A$ 的所有可能的子集。
   • “A的所有子集的集合”: 这是幂集的核心。要构建幂集，你需要找到一个集合的所有子集，然后把这些子集作为元素，装到一个新的大集合里。
   • 示例分析: $A = \{0, 1\}$
   • 首先，找出 $A$ 的所有子集：
   • 0个元素的子集：$\emptyset$ (空集)
   • 1个元素的子集：$\{0\}$ 和 $\{1\}$
   • 2个元素的子集：$\{0, 1\}$ (A自身)
   • 然后，把找到的这4个子集作为元素，放入一个新的集合中：$\{\emptyset, \{0\}, \{1\}, \{0, 1\}\}`。这就是 `$A$ 的幂集。
   • 重要：如果 $A$ 有 $n$ 个元素，那么它的幂集 $\mathcal{P}(A)$ 将有 $2^n$ 个元素。这就是为什么幂集有时记作 $2^A$ 的原因。对于 $A = \{0, 1\}$，$n=2$，所以幂集有 $2^2 = 4$ 个元素。
3. 笛卡尔积 (Cartesian Product) 或 叉积 (Cross Product)
   • 定义: 两个集合 $A$ 和 $B$ 的笛卡尔积 $A \times B$，是一个由所有可能的有序对 $(a, b)$ 组成的集合。
   • 规则:
   • 有序对的第一个元素 $a$ 必须来自集合 $A$。
   • 有序对的第二个元素 $b$ 必须来自集合 $B$。
   • 构造过程: 想象你有两套衣服，上衣集合 $A = \{\text{红T恤, 蓝衬衫}\}$，裤子集合 $B = \{\text{牛仔裤, 黑裤子, 卡其裤}\}$。笛卡尔积 $A \times B$ 就代表了所有可能的搭配方式：
   • 从 $A$ 中取出“红T恤”，与 $B$ 中所有裤子各搭配一次：(红T恤, 牛仔裤), (红T恤, 黑裤子), (红T恤, 卡其裤)。
   • 从 $A$ 中取出“蓝衬衫”，与 $B$ 中所有裤子各搭配一次：(蓝衬衫, 牛仔裤), (蓝衬衫, 黑裤子), (蓝衬衫, 卡其裤)。
   • 把所有这些搭配（有序对）收集起来，就构成了笛卡尔积这个集合。
   • 重要: 如果 $A$ 有 $m$ 个元素，$B$ 有 $n$ 个元素，那么笛卡尔积 $A \times B$ 将有 $m \times n$ 个元素。
   • “所有元素为0和1的有序对的集合”: 这是 $\{0, 1\} \times \{0, 1\}$ 的一个例子。
   • 从第一个 $\{0, 1\}$ 取 0，与第二个 $\{0, 1\}$ 的 0 和 1 分别配对，得到 (0, 0) 和 (0, 1)。
   • 从第一个 $\{0, 1\}$ 取 1，与第二个 $\{0, 1\}$ 的 0 和 1 分别配对，得到 (1, 0) 和 (1, 1)。
   • 最终结果就是 $\{(0,0),(0,1),(1,0),(1,1)\}$。

这个示例是笛卡尔积定义的一个直接应用，目的是通过一个具体的例子来帮助读者固化对笛卡尔积的理解。

1. 识别输入: 我们有两个集合。
   • 集合 $A = \{1, 2\}$。它有两个元素。
   • 集合 $B = \{x, y, z\}$。它有三个元素。
2. 确定目标: 我们要计算 $A \times B$。根据定义，这是一个由有序对 $(a, b)$ 组成的集合，其中 $a$ 必须从 $A$ 中选取，$b$ 必须从 $B$ 中选取。
3. 系统地构造有序对: 为了确保不重不漏，我们采用一种系统化的方法。
   • 第一步：固定A中的第一个元素。我们先从集合 $A$ 中取出第一个元素 1。
   • 第二步：与B中所有元素配对。将 1 与集合 $B$ 中的每一个元素 x, y, z 分别配对，形成有序对。
   • 1 和 x 配对得到 (1, x)。
   • 1 和 y 配对得到 (1, y)。
   • 1 和 z 配对得到 (1, z)。
   • 第三步：固定A中的第二个元素。现在处理 $A$ 中的下一个元素 2。
   • 第四步：与B中所有元素配对。将 2 与集合 $B$ 中的每一个元素 x, y, z 分别配对。
   • 2 和 x 配对得到 (2, x)。
   • 2 和 y 配对得到 (2, y)。
   • 2 和 z 配对得到 (2, z)。
4. 收集结果: 我们已经遍历了 $A$ 中所有的元素，并与 $B$ 进行了所有可能的配对。现在把所有生成的有序对收集起来，放入一个大集合中。
5. 最终结果: 得到的集合就是 $\{(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)\}$。
6. 验证: 集合 $A$ 的大小是 2，集合 $B$ 的大小是 3。根据之前的知识，笛卡尔积 $A \times B$ 的大小应该是 $2 \times 3 = 6$。我们数一下结果集合中的元素个数，正好是6个有序对。验证通过。
7. $\square$ 符号: 这个方块符号是数学文章和教科书中常用的标记，表示一个示例、一个证明或一个段落的结束。

1. 从2维到k维的推广: 前面讲的笛卡尔积 $A \times B$ 是两个集合之间的运算，产生的是有序对（2-元组）。这一段将这个概念推广到任意 $k$ 个集合。
2. k重笛卡尔积: $A_{1} \times A_{2} \times \cdots \times A_{k}$
   • 输入: $k$ 个集合，$A_1, A_2, \ldots, A_k$。这些集合可以是不同的，也可以是相同的。
   • 输出: 一个新的集合。
   • 输出集合的元素: 不再是简单的有序对，而是k-元组 $(a_1, a_2, \ldots, a_k)$。
3. k-元组的构成规则:
   • 元组的第一个元素 $a_1$ 必须来自第一个集合 $A_1$。
   • 元组的第二个元素 $a_2$ 必须来自第二个集合 $A_2$。
   • ...
   • 元组的第 $i$ 个元素 $a_i$ 必须来自第 $i$ 个集合 $A_i$。
   • ...
   • 元组的第 $k$ 个元素 $a_k$ 必须来自第 $k$ 个集合 $A_k$。
4. 结果: 最终的集合包含了所有满足上述规则的、可能的k-元组。
5. 元素个数: 如果集合 $A_i$ 的大小是 $n_i$，那么 $k$ 重笛卡尔积 $A_{1} \times A_{2} \times \cdots \times A_{k}$ 的大小就是 $n_1 \times n_2 \times \cdots \times n_k$。

这个示例是k重笛卡尔积的一个具体应用，其中 $k=3$，并且输入的集合有重复。

1. 回顾输入:
   • 从示例 0.5 我们知道 $A = \{1, 2\}$ 和 $B = \{x, y, z\}$。
2. 确定目标: 我们要计算 $A \times B \times A$。这是一个由3-元组 $(a_1, b, a_2)$ 组成的集合，其中：
   • 第一个元素 $a_1$ 来自 $A$。
   • 第二个元素 $b$ 来自 $B$。
   • 第三个元素 $a_2$ 再次来自 $A$。
3. 系统地构造3-元组:
   • 我们可以将 $A \times B \times A$ 看作是 $(A \times B) \times A$。
   • 我们已经从示例 0.5 知道 $A \times B = \{(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)\}$。
   • 现在，我们要计算这个新集合与 $A = \{1, 2\}$ 的笛卡尔积。
   • 这会产生形如 (有序对, 数字) 形式的元素。
   • 第一步: 取 $A \times B$ 的第一个元素 (1, x)。
   • 与 $A$ 的 1 配对，得到 ((1, x), 1)，我们将其“压平”理解为 (1, x, 1)。
   • 与 $A$ 的 2 配对，得到 ((1, x), 2)，理解为 (1, x, 2)。
   • 第二步: 取 $A \times B$ 的第二个元素 (1, y)。
   • 与 $A$ 的 1 配对，得到 (1, y, 1)。
   • 与 $A$ 的 2 配对，得到 (1, y, 2)。
   • ... 以此类推，对 $A \times B$ 中的所有6个有序对都进行同样的操作。
   • 继续:
   • 取 (1, z) -> (1, z, 1), (1, z, 2)
   • 取 (2, x) -> (2, x, 1), (2, x, 2)
   • 取 (2, y) -> (2, y, 1), (2, y, 2)
   • 取 (2, z) -> (2, z, 1), (2, z, 2)
4. 收集结果: 把所有这些3-元组收集起来，就得到了示例中给出的集合。
5. 验证:
   • |A| = 2, |B| = 3, |A| = 2。
   • |A \times B \times A| = |A| \times |B| \times |A| = 2 \times 3 \times 2 = 12。
   • 我们数一下示例结果中的3-元组个数，正好是12个。验证通过。

1. 动机: 在数学和计算机科学中，我们经常需要处理同一个集合与自身进行多次笛卡尔积的情况。例如，二维平面是实数集 $\mathbb{R}$ 与自身的笛卡尔积 $\mathbb{R} \times \mathbb{R}$，三维空间是 $\mathbb{R} \times \mathbb{R} \times \mathbb{R}$。每次都写一长串 $\times$ 很繁琐。
2. 引入简写:
   • 这个简写模仿了算术中的幂运算。在算术中，$a \times a \times \cdots \times a$ (k次) 被简写为 $a^k$。
   • 类似地，我们将 $A \times A \times \cdots \times A$ (k个A的笛卡尔积) 简写为 $A^k$。
   • 这里的上标 $k$ 不再是数字的指数，而是表示笛卡尔积运算的次数。
3. $A^k$ 的含义:
   • 它是一个由k-元组组成的集合。
   • 每个k-元组 $(a_1, a_2, \ldots, a_k)$ 中的所有元素 $a_i$ 都来自于同一个集合 $A$。
4. $\overbrace{...}^{k}$ 符号: 这是一个解释性的符号，叫做“上大括号”(overbrace)。它用来标识出它下面的表达式重复了k次，帮助读者理解 $A^k$ 这个简写是如何从 $A \times A \times \cdots \times A$ 定义而来的。

这个示例是 $A^k$ 记法的一个直接应用，其中 $A = \mathcal{N}$ 且 $k=2$。

1. 识别记法: $\mathcal{N}^2$。看到 (集合)^(数字) 的形式，我们立刻联想到刚刚学到的笛卡尔幂的简写。
2. 展开简写: 根据定义，$\mathcal{N}^2 = \mathcal{N} \times \mathcal{N}$。
3. 理解输入集合: $\mathcal{N}$ 是自然数集。根据本书前面的约定，$\mathcal{N} = \{1, 2, 3, \ldots\}$。
4. 应用笛卡尔积定义: $\mathcal{N} \times \mathcal{N}$ 是一个由有序对 (a, b) 组成的集合，其中 $a$ 和 $b$ 都必须是自然数。
5. 结果描述: 因此，$\mathcal{N}^2$ 这个集合里装的是所有可能的自然数的有序对。
   • 例如：(1, 1) 在 $\mathcal{N}^2$ 中。
   • 例如：(1, 2) 在 $\mathcal{N}^2$ 中。
   • 例如：(2, 1) 在 $\mathcal{N}^2$ 中。
   • 例如：(15, 1024) 也在 $\mathcal{N}^2$ 中。
   • 但 (0, 1) 不在，因为 0 不在 $\mathcal{N}$ 中。
   • 但 (1.5, 2) 不在，因为 1.5 不是自然数。
6. 另一种表示法: 示例中还给出了规则描述法的写法 $\{(i, j) \mid i, j \geq 1\}$。
   • $\{(i, j) \mid ... \}$: 表示这是一个由有序对 (i, j) 组成的集合。
   • $... i, j \geq 1\}$: 这是对有序对中元素 $i$ 和 $j$ 的限制条件。
   • $i \geq 1$ 且 $j \geq 1$ (并且隐含了i,j是整数) 正是“i和j都是自然数”的另一种说法（在本书约定下）。
   • 所以，$\{(i, j) \mid i \in \mathcal{N} \text{ and } j \in \mathcal{N}\}$ 和 $\{(i, j) \mid i, j \geq 1 \text{ and } i,j \in \mathcal{Z}\}$ 以及 $\mathcal{N} \times \mathcal{N}$ 都描述的是同一个集合。

1. 函数 (Function) 的核心思想: 函数是一个“规则”或一个“机器”，它定义了一种从输入到输出的明确对应关系。
2. “输入-输出关系”: 这是函数的本质。你给它一个东西（输入），它会给你一个东西（输出）。
3. 函数的两大铁律:
   • 确定性 (Deterministic): “相同的输入总是产生相同的输出”。这是函数最根本的性质。一个函数不能“心情不好”就改变结果。如果你把 2 输入给 abs 函数，它必须输出 2，无论你问多少次，在何时何地问。abs(2) 不可能这次是2，下次是-2。
   • 对每个输入都有定义: 对于一个函数所声称能处理的每一个合法输入，它都必须给出一个输出。它不能对某个输入说“我不知道”或“我算不出来”。（这是在定义域内的要求）
4. 表示法: $f(a) = b$
   • $f$: 函数的名字。
   • $a$: 提供给函数的输入，也称为自变量或参数。
   • $b$: 函数产生的输出，也称为函数值。
   • $f(a)$: 整个表达式代表“将输入 a 应用于函数 f 后得到的结果”。
5. 映射 (Mapping):
   • 函数和映射是同义词。
   • “f 将 a 映射到 b” 提供了一种更动态的想象方式：好像有一支看不见的笔，从输入 a 画了一条箭头指向输出 b。
6. 示例分析:
   • 绝对值函数 abs:
   • 输入：一个数字 x (比如，整数)。
   • 规则：如果 $x \ge 0$, 输出是 $x$；如果 $x < 0$, 输出是 $-x$。
   • abs(2) = 2。
   • abs(-2) = 2。注意，不同的输入 (2 和 -2) 可以产生相同的输出 (2)，这是完全允许的。
   • 加法函数 add:
   • 输入：一个有序对的数字 (x, y)。这里函数的输入不是单个数字，而是一个元组。
   • 规则：输出是这两个数字的和 $x+y$。
   • 例如，add((3, 5)) = 8。我们通常将其简写为中缀表示法 3 + 5 = 8。

[公式与符号逐項拆解和推导（若本段含公式）]

• f: 函数的名称或符号。
• (): 括号，用于包裹函数的输入参数。
• a: 函数的输入，也称为参数 (argument) 或 自变量 (independent variable)。
• =: 等号，表示左边的函数应用结果等于右边的值。
• b: 函数的输出，也称为函数值 (value) 或 因变量 (dependent variable)。

1. 域 (Domain)
   • 定义: 一个函数能够接受的所有合法输入构成的集合。
   • 域规定了函数的“工作范围”或“管辖范围”。你不能把域之外的东西作为输入喂给函数。
2. 值域 (Range / Codomain)
   • 定义: 函数的所有可能输出都必须属于的那个集合。它为输出提供了一个“容器”或“目标空间”。
   • 重要区分:
   • 值域 (Codomain): 官方定义的目标集合，如 $R$。它是一个比较宽泛的“靶场”。
   • 像 (Image): 所有实际输出值的集合。它是值域的一个子集。像才是所有“实际打中的点”。
   • “函数不一定使用指定值域的所有元素”: 这句话说的就是“像”不一定等于“值域”。
   • 例如，$abs: \mathcal{Z} \to \mathcal{Z}$。值域是所有整数 $\mathcal{Z}$。但 abs 的实际输出永远是 $\ge 0$ 的整数（即非负整数 {0, 1, 2, ...}）。所以 abs 的像是 {0, 1, 2, ...}，它是值域 $\mathcal{Z}$ 的一个真子集。 -1 在值域中，但不在像中。
3. 表示法: $f: D \to R$
   • 这是一种“函数签名”或“类型声明”。它没有告诉我们函数具体做什么，但清晰地定义了它的输入和输出的“类型”。
   • $f$: 函数名。
   • $D$: 域 (Domain)，输入的来源集合。
   • $R$: 值域 (Codomain)，输出的目标集合。
   • :: 分隔符，读作“是一个从...到...的函数”。
   • $\to$: 箭头，表示从域到值域的映射方向。
4. 示例分析:
   • $abs: \mathcal{Z} \to \mathcal{Z}$
   • 域是 $\mathcal{Z}$：abs 函数接受任何一个整数作为输入。
   • 值域是 $\mathcal{Z}$：abs 函数的输出保证是一个整数。
   • $add: \mathcal{Z} \times \mathcal{Z} \to \mathcal{Z}$
   • 域是 $\mathcal{Z} \times \mathcal{Z}$：add 函数接受一个整数的有序对作为输入，例如 (3, 5)。
   • 值域是 $\mathcal{Z}$：add 函数的输出（和）保证是一个整数。
5. 满射 (Onto / Surjective)
   • 这是一个函数的特殊性质。
   • 如果一个函数 f: D -> R 是满射的，那么它的“像”就等于它的“值域”。
   • 换句话说，对于值域 $R$ 中的任何一个元素 $y$，你都至少能找到一个域 $D$ 中的元素 $x$，使得 $f(x) = y$。值域里没有一个元素是被“浪费”的。
   • $abs: \mathcal{Z} \to \mathcal{Z}$ 不是满射，因为你找不到任何整数 $x$ 使得 $abs(x) = -1$。
   • 但如果我们把值域改小一点，定义一个新的函数 $abs': \mathcal{Z} \to \{0, 1, 2, \ldots\}$，那么这个 $abs' 就是满射了。

这里介绍了描述函数的两种主要方法，特别适用于域是有限集的情况。

1. 方法一：过程/规则描述 (Procedural/Rule-based Description)

• 思想: 给出一种算法或一个公式，告诉我们如何计算输出。
• 例子:
• f(x) = x^2 + 2x + 1。这是一个代数过程。给定任何 x，你都可以通过计算得到 f(x)。
• abs(x) 函数的描述：“如果x为正则返回x，如果x为负则返回-x”。这是一个过程性的描述。
• 优点:
• 紧凑: 一个简单的规则可以描述一个拥有无限域的函数。
• 普适: 只要是可计算的，就能用过程描述。
• 缺点: 有时规则可能非常复杂。

1. 方法二：表格描述 (Tabular Description)

• 思想: 当函数的域是有限的、且元素不多时，我们可以像列清单一样，把所有输入和对应的输出一一列出。
• 形式: 通常用一个两列表格，左边是输入，右边是对应的输出。
• 优点:
• 直观明了: 所有对应关系一目了然，无需计算。
• 可以描述任意关系: 即使一个函数毫无规律可言，只要域是有限的，就可以用表格描述。
• 缺点:
• 只适用于有限域: 对于像 square(x) 这样域是所有实数的函数，无法使用表格。
• 冗长: 即使域是有限的，如果元素很多，表格也会变得巨大无比。

1. 函数签名分析: $f: \{0,1,2,3,4\} \to \{0,1,2,3,4\}$
   • 域: $\{0, 1, 2, 3, 4\}。函数 f` 只接受这5个整数作为输入。
   • 值域: 也是 $\{0, 1, 2, 3, 4\}。f` 的输出结果也必须是这5个整数之一。
2. 表格分析: 表格清晰地列出了每个输入对应的输出。
   • f(0) = 1
   • f(1) = 2
   • f(2) = 3
   • f(3) = 4
   • f(4) = 0 (这是最特殊的一点)
3. 发现规律（从表格到过程）:
   • 对于输入 0, 1, 2, 3，规律很简单：f(n) = n + 1。
   • 但是对于输入 4，f(4) 不是 5，而是 0。这提示我们这不是简单的加法。
   • 4 + 1 = 5，而输出是 0。在 \{0, 1, 2, 3, 4\} 这个圈子里，5 和 0 是怎么联系起来的？
4. 引入模运算 (Modulo Operation)
   • “一个数模 m 是除以 m 后的余数”: 这是模运算的核心定义。
   • a mod m 等于 a 除以 m 的余数。
   • 例如, 7 mod 5：7 / 5 = 1 ... 2。所以 7 mod 5 = 2。
   • 例如, 10 mod 3：10 / 3 = 3 ... 1。所以 10 mod 3 = 1。
   • 例如, 5 mod 5：5 / 5 = 1 ... 0。所以 5 mod 5 = 0。
5. 用模运算解释函数 f:
   • 该函数的过程是：f(n) = (n + 1) mod 5。
   • 我们来验证一下：
   • f(0) = (0 + 1) mod 5 = 1 mod 5 = 1。正确。
   • f(1) = (1 + 1) mod 5 = 2 mod 5 = 2。正确。
   • f(2) = (2 + 1) mod 5 = 3 mod 5 = 3。正确。
   • f(3) = (3 + 1) mod 5 = 4 mod 5 = 4。正确。
   • f(4) = (4 + 1) mod 5 = 5 mod 5 = 0。正确！
   • 这个过程完美地解释了表格中的所有对应关系。
6. 时钟类比: “钟面上的分针是模60计数”。这是一个极佳的类比。
   • 分针走到58, 59，下一分钟不是60，而是回到00。
   • 我们的函数 $f$ 就像一个只有0, 1, 2, 3, 4 这五个数字的“5小时制”时钟。指针在4点时，再过一个小时，就回到了0点。这种循环往复的特性是模运算的精髓。
7. $\mathcal{Z}_m$ 符号:
   • 这是一个非常常用和重要的记号，$\mathcal{Z}_m = \{0, 1, 2, ..., m-1\}$，代表了模 m 运算下所有可能的余数的集合。
   • $\mathcal{Z}_5 = \{0, 1, 2, 3, 4\}$。
   • 因此，函数 $f$ 的签名可以更简洁、更专业地写成 $f: \mathcal{Z}_5 \to \mathcal{Z}_5$。这不仅指明了输入输出的数值范围，还强烈地暗示了函数内部可能涉及模5的运算。

1. 二元函数 (Binary Function): 这个例子中的函数 $g$ 与上一个例子中的 $f$ 有个关键不同：它的输入不是单个数字，而是一个有序对。这种接受两个输入的函数称为二元函数。
2. 函数签名分析: $g: \mathcal{Z}_{4} \times \mathcal{Z}_{4} \to \mathcal{Z}_{4}$
   • 域: $\mathcal{Z}_{4} \times \mathcal{Z}_{4}$。
   • $\mathcal{Z}_4 = \{0, 1, 2, 3\}$。
   • 所以域是 $\{0, 1, 2, 3\} \times \{0, 1, 2, 3\}$。这是一个由 $4 \times 4 = 16$ 个有序对组成的集合，例如 (0, 0), (0, 1), ..., (3, 3)。
   • 值域: $\mathcal{Z}_{4}$。输出结果是一个0到3之间的整数。
3. 二维表格描述法:
   • 当域是笛卡尔积 $A \times B$ 时，用简单的两列表格就不方便了。
   • 一个更自然的方式是使用二维表格（或叫运算表），类似于乘法表。
   • 行标签 (row labels): 代表有序对的第一个元素（这里是 $i$）。
   • 列标签 (column labels): 代表有序对的第二个元素（这里是 $j$）。
   • 表格内部的条目: 第 $i$ 行和第 $j$ 列交叉处的单元格，其值就是函数对输入 (i, j) 的输出，即 $g(i, j)$。
4. 读取表格:
   • 想知道 $g(2, 3) 的值是多少？
   • 找到行标签为 2 的那一行。
   • 找到列标签为 3 的那一列。
   • 在它们交叉的地方，我们看到数字 1。
   • 所以，$g(2, 3) = 1$。
   • 想知道 $g(1, 1)` 的值？找到第1行第1列，值是 `2`。所以 `$g(1, 1) = 2$。
5. 发现规律:
   • 表格的标题明确说，这个函数是模4的加法函数。
   • 这意味着 $g(i, j) = (i + j) \mod 4$。
   • 我们来验证一下刚才的计算：

• $g(2, 3) = (2 + 3) \mod 4 = 5 \mod 4 = 1$。与表格相符。
• $g(1, 1) = (1 + 1) \mod 4 = 2 \mod 4 = 2$。与表格相符。
• 我们可以验证表格中的任何一个条目，都会发现它满足这个规律。例如，$g(3, 3) = (3+3) \mod 4 = 6 \mod 4 = 2$，但表格中对应位置是 2，这说明原文的表格可能有误，或者我理解错了。
• 重新检查原文表格：| g | 0 | 1 | 2 | 3 |

• (3+3) mod 4 = 6 mod 4 = 2。表格是正确的。我的心算没错。
• (3+2) mod 4 = 5 mod 4 = 1。表格是正确的。

1. k-元函数 (k-ary Function)
   • 核心思想: 这是对函数输入复杂性的一种分类。我们根据函数需要“吃”掉多少个东西才能算出一个结果，来给它命名。
   • 形式化定义: 一个函数的域如果是k重笛卡尔积 $A_1 \times \cdots \times A_k$，那么这个函数就是一个k-元函数。
   • 输入: k-元函数的输入是一个 k-元组 $(a_1, \ldots, a_k)$。
   • 参数 (Argument): k-元组中的每一个分量 $a_i$，都称为函数的一个参数。
   • 元数 (Arity): 数字 $k$，即参数的个数，被称为函数的元数。
2. 常见元数的名称:
   • k=1, 一元函数 (Unary Function): 接受一个参数。例如 abs(x), square(x)。域是 $A_1$。
   • k=2, 二元函数 (Binary Function): 接受两个参数。例如 add(a, b), max(a, b)。域是 $A_1 \times A_2$。
   • k=3, 三元函数 (Ternary Function): 接受三个参数。
   • k=0, 零元函数 (Nullary Function): 接受零个参数。这听起来很奇怪，但它在数学和计算机科学中是有意义的。一个零元函数不需要任何输入，并且总是返回一个常量值。例如，一个函数 pi() 总是返回 3.14159...。
3. 函数表示法 (Notation)
   • 前缀表示法 (Prefix Notation): 这是最通用、最标准的函数表示法。函数名在前，括号里是逗号分隔的参数列表。例如 f(a, b, c)。几乎所有编程语言中的函数调用都采用这种形式。
   • 中缀表示法 (Infix Notation): 这是一种特殊的、只适用于二元函数的表示法。函数符号被放在两个参数的中间。
   • 例子: 我们不常写 add(a, b)，而是写 $a + b$。我们不写 less_than(a, b)，而是写 $a < b$。
   • 原因: 这是我们从小学开始就习惯的算术和关系表示法，它非常自然和可读。
   • 后缀表示法 (Postfix Notation): 符号放在参数之后，如 $a b +$。这在某些计算器（如惠普的RPN计算器）和编程语言（如Forth）中使用。

1. 谓词 (Predicate) 或 属性 (Property)
   • 核心定义: 一种特殊的函数，它的输出结果只有两种可能：TRUE 或 FALSE。
   • 它不像普通函数那样计算一个数值或返回一个新对象，而是对输入进行一个“是/非”的判断。
   • 谓词/属性: 这两个词基本可以互换使用。“属性”更侧重于描述输入对象本身具有的某种性质（例如，“是偶数”是数字4的一个属性）。“谓词”则更侧重于描述一个可以对输入进行判断的逻辑语句。
   • 示例分析 even:
   • 函数名：even
   • 域：$\mathcal{Z}$ (整数集)
   • 值域：{TRUE, FALSE}
   • 规则：输入 n，如果 n 能被2整除，输出 TRUE；否则输出 FALSE。
   • even(4) = TRUE
   • even(5) = FALSE
2. 关系 (Relation)
   • 核心定义: 关系是一种特殊的谓词，它的输入是一个 k-元组。
   • 换句话说，关系是用来判断多个对象之间是否存在某种联系的。
   • k-元关系: 输入是k-元组的关系。
   • 二元关系 (Binary Relation): 最常见的一种，输入是有序对 (2-元组)。它描述的是两个对象之间的关系。
   • 域: $A \times B$ 或 $A \times A$。
   • 值域: {TRUE, FALSE}。
3. 二元关系的表示法:
   • 前缀表示法: R(a, b)。例如，less_than(3, 5) = TRUE。
   • 中缀表示法: $a R b$。这是我们更习惯的方式。例如，$3 < 5$。
   • $a R b$ 这种写法是一个语法糖，它等价于说 R(a, b) = TRUE。当我们写下 $3 < 5$ 时，我们是在断言一个为真的命题。当我们写 $5 < 3$ 时，我们断言了一个为假的命题。
4. k-元关系的表示法: 对于k大于2的情况，通常只能用前缀表示法。例如，一个三元关系 Between(a, b, c) 可能用来判断 b 是否在 a 和 c 之间。

这个示例展示了如何用上一节定义的关系概念来形式化地描述一个我们都熟悉的游戏规则。

1. 确定论域 (Domain of Discourse): 游戏中的对象来自哪个集合？
   • 集合是 $S = \{\text{SCISSORS, PAPER, STONE}\}$。
2. 识别关系: 游戏的核心规则是“什么克制什么”。这是一个典型的两者之间的关系，所以它是一个二元关系。
   • 我们给这个关系起个名字，叫 $beats$。
3. 定义域和值域:
   • $beats$ 函数的输入是一个有序对 (player1_choice, player2_choice)，其中两个选择都来自集合 $S$。
   • 所以，$beats$ 的域是 $S \times S$。
   • $beats$ 的输出是 {TRUE, FALSE}，因为它判断“前者是否克制后者”。
   • 因此，函数签名是 $beats: S \times S \to \{\text{TRUE, FALSE}\}$。
4. 用二维表格描述关系:
   • 由于这是一个定义在有限集上的二元函数，使用二维表格来描述它非常合适。
   • 行: 代表有序对的第一个元素（攻击方）。
   • 列: 代表有序对的第二个元素（防御方）。
   • 单元格内容: TRUE 或 FALSE，表示行是否克制列。
5. 解读表格:
   • $beats(\text{SCISSORS, PAPER})$: 找到 "SCISSORS" 行和 "PAPER" 列的交叉点，内容是 TRUE。这意味着“剪刀克制布”是真的。
   • $beats(\text{PAPER, SCISSORS})$: 找到 "PAPER" 行和 "SCISSORS" 列的交叉点，内容是 FALSE。这意味着“布克制剪刀”是假的。
   • $beats(\text{SCISSORS, SCISSORS})$: 找到 "SCISSORS" 行和 "SCISSORS" 列的交叉点，内容是 FALSE。这意味着“剪刀克制剪刀”是假的，即平局。对角线上的所有元素都是 FALSE，这与游戏平局的规则相符。
6. 非对称性: 观察表格，它不是对称的。例如，$beats(\text{SCISSORS, PAPER}) = \text{TRUE}`，但 `$beats(\text{PAPER, SCISSORS}) = \text{FALSE}。这种性质称为非对称性 (asymmetric)，它是很多“竞争”关系（如大于、克制）的特点。

1. 两种视角，一个事物: 这里提出了描述谓词/关系的另一种等价方式。
   • 函数视角: 谓词是一个函数，它对输入进行判断，返回 TRUE 或 FALSE。
   • 集合视角: 我们只关心那些能让谓词返回 TRUE 的输入。我们可以把所有这些“成功的”输入收集起来，组成一个集合。
2. 从函数到集合的转换:
   • 给定一个谓词 $P: D \to \{\text{TRUE, FALSE}\}$。
   • 我们可以构造一个集合 $S_P$，它的定义是：$S_P = \{a \in D \mid P(a) = \text{TRUE}\}$。
   • 这个集合 $S_P$ 是域 $D$ 的一个子集。它精确地“圈出”了所有让谓词P成立的输入。
3. 等价性:
   • 知道函数 $P$，就可以唯一确定集合 $S_P$。
   • 反过来，知道集合 $S_P$（以及域D），也可以唯一确定函数 $P$ 的规则：如果输入 $a \in S_P$，则 $P(a) = \text{TRUE}$；如果输入 $a \notin S_P$ (但 $a \in D$)，则 $P(a) = \text{FALSE}$。
   • 因此，这两种表示法是完全等价的，可以相互转换。
4. 应用到关系上:
   • 关系是一种输入为k-元组的谓词。
   • 因此，一个k-元关系可以被表示为一个由k-元组组成的集合。
   • 这个集合包含了所有让该关系为 TRUE 的k-元组。
5. 示例分析:
   • 关系是 $beats: S \times S \to \{\text{TRUE, FALSE}\}$，其中 $S = \{\text{SCISSORS, PAPER, STONE}\}$。
   • 域是 $S \times S$。
   • 我们要构建一个集合，包含所有让 $beats(a, b) 为 TRUE 的有序对 (a, b)。
   • 查上一个例子的表格：
   • beats(SCISSORS, PAPER) = TRUE -> 将 (SCISSORS, PAPER) 放入集合。
   • beats(PAPER, STONE) = TRUE -> 将 (PAPER, STONE) 放入集合。
   • beats(STONE, SCISSORS) = TRUE -> 将 (STONE, SCISSORS) 放入集合。
   • 表格中其他所有对应的值都是 FALSE，所以我们不把那些输入（如 (SCISSORS, STONE)）放入集合。
   • 最终得到的集合就是 $\{(\text{SCISSORS, PAPER}), (\text{PAPER, STONE}), (\text{STONE, SCISSORS})\}$。这个集合简洁地编码了游戏的全部“克制”规则。

1. 动机: 在数学中，我们经常想说两种不同的东西“在某种意义上是等价的”。例如，分数 1/2 和 2/4 写法不同，但代表的数值相同。等价关系就是用来精确捕捉这种“在...方面相同”的概念的数学工具。
2. 核心: 等价关系是一种行为上非常类似“等于号 =”的二元关系。它必须满足以下三条“公理”。
3. 三公理详解:
   • 1. 自反性 (Reflexive):
   • 对于每个 x, x R x
   • 含义: 任何一个对象都与它自身“等价”。
   • 直觉: 就像 = 一样，$x=x$ 永远成立。一个东西总等于它自己。
   • 例子: “等于”关系满足自反性。但“小于”关系 < 不满足，因为 $x < x$ 不成立。
   • 2. 对称性 (Symmetric):
   • 对于每个 x 和 y，如果 x R y 则 y R x
   • 含义: 如果 x 与 y 等价，那么 y 也必须与 x 等价。关系是双向的。
   • 直觉: 就像 = 一样，如果 $x=y$，那么 $y=x$。
   • 例子: “是...的同学”关系是对称的。如果A是B的同学，那么B也是A的同学。但“是...的父亲”关系不是对称的。
   • 3. 传递性 (Transitive):
   • 对于每个 x, y, 和 z，如果 x R y 且 y R z 则 x R z
   • 含义: 等价关系可以“传递”。如果 x 与 y 等价，y 与 z 等价，那么 x 也与 z 等价。
   • 直觉: 就像 = 一样，如果 $x=y$ 且 $y=z$，那么 $x=z$。
   • 例子: “小于”关系 < 是传递的。如果 $x < y$ 且 $y < z$，那么 $x < z$。但“剪刀-石头-布”中的 beats 关系不是传递的：SCISSORS beats PAPER 且 PAPER beats STONE，但 SCISSORS beats STONE 是 FALSE。

这个例子是对上一节定义的等价关系的具体实例化和证明。它选择了一个非常重要的数学关系——模同余关系。

1. 定义关系:

• 名称: $\equiv_7$，读作“模7同余”。
• 作用域: 自然数 $\mathcal{N}$。即关系的输入 i, j 都来自 $\mathcal{N} = \{1, 2, 3, ...\}$。
• 规则: $i \equiv_7 j$ 这句话为真，当且仅当 $i-j$ 是7的倍数。
• “是7的倍数”的数学含义是：存在一个整数 $k$，使得 $i-j = 7k$。

1. 证明其为等价关系: 我们必须逐一验证自反性、对称性、传递性。

• 自反性 (Reflexivity):
• 目标: 证明对任意 $i \in \mathcal{N}$，都有 $i \equiv_7 i$。
• 证明: 根据定义，我们需要判断 $i-i$ 是否是7的倍数。$i-i = 0$。因为 $0 = 7 \times 0$，而0是整数，所以0是7的倍数。因此，$i \equiv_7 i$ 成立。自反性满足。
• 对称性 (Symmetry):
• 目标: 证明如果 $i \equiv_7 j$，那么一定有 $j \equiv_7 i$。
• 证明: 假设 $i \equiv_7 j$ 成立。根据定义，这意味着 $i-j$ 是7的倍数。即，存在整数 $k$ 使得 $i-j = 7k$。
• 我们要证明 $j \equiv_7 i$，也就是要证明 $j-i$ 是7的倍数。
• 从 $i-j = 7k$ 出发，两边乘以-1，得到 $j-i = -7k = 7(-k)。
• 因为 $k$ 是整数，所以 $-k$ 也是整数。因此 $j-i$ 可以表示为7乘以一个整数的形式，所以 $j-i$ 是7的倍数。
• 所以 $j \equiv_7 i$ 成立。对称性满足。
• 传递性 (Transitivity):
• 目标: 证明如果 $i \equiv_7 j$ 且 $j \equiv_7 k$，那么一定有 $i \equiv_7 k$。
• 证明: 假设 $i \equiv_7 j$ 和 $j \equiv_7 k$ 都成立。
• 根据定义，$i-j$ 是7的倍数，即存在整数 $k_1$ 使得 $i-j = 7k_1$。
• 根据定义，$j-k$ 是7的倍数，即存在整数 $k_2$ 使得 $j-k = 7k_2$。
• 我们要证明 $i \equiv_7 k$，也就是要证明 $i-k$ 是7的倍数。
• 我们尝试构造 $i-k$。一个巧妙的技巧是引入j：$i-k = (i-j) + (j-k)$。
• 将上面的假设代入：$i-k = 7k_1 + 7k_2 = 7(k_1+k_2)。
• 因为 $k_1$ 和 $k_2$ 都是整数，它们的和 $k_1+k_2$ 也是整数。
• 因此 $i-k$ 可以表示为7乘以一个整数的形式，所以 $i-k$ 是7的倍数。
• 所以 $i \equiv_7 k$ 成立。传递性满足。

1. 结论: 因为该关系同时满足自反性、对称性和传递性，所以 $\equiv_7$ 是一个等价关系。

1. 图 (Graph) 的本质: 图是一种数学结构，用来对“事物”以及它们之间的“连接关系”进行建模。
2. 核心组成部分:
   • 点 (Dots): 代表“事物”。在图论中，它们有更正式的名称：节点 (Nodes) 或 顶点 (Vertices) (单数是 Vertex)。
   • 线 (Lines): 代表事物之间的“连接关系”。它们的正式名称是 边 (Edges)。
3. 无向图 (Undirected Graph):
   • 这是最基本的一种图。
   • “无向”意味着边是没有方向的。如果节点A和节点B之间有一条边，那么这个连接是双向的、对称的。从A到B和从B到A是一回事。
   • 这就像一条双向的道路，或两个人之间的“朋友”关系。
4. 图示分析:
   • 图(a) 展示了一个有5个顶点和5条边的图。这些边连接成一个环。
   • 图(b) 展示了一个有4个顶点和6条边的图。每个顶点都与其他所有顶点相连，这种图被称为完全图 (Complete Graph)。
   • 重要: 图的画法不重要，重要的是顶点是谁、边连接了谁。图(a)的五个顶点可以画成一个五边形，也可以画得歪七扭八，只要连接关系不变，它们就是同一个图。

1. 度 (Degree)
   • 定义: 一个顶点 v 的度，记作 deg(v)，是指与该顶点相连的边的数量。
   • 直观意义: 度表示了一个节点的“连接程度”或“繁忙程度”。在社交网络中，一个人的度就是他的好友数量。
   • 示例分析:
   • 图 0.12(a) (五边形): 每个顶点都连接着两条边（一条“左边”的，一条“右边”的），所以每个顶点的度都是2。
   • 图 0.12(b) (四面体/完全图K4): 每个顶点都与其他3个顶点相连，所以每个顶点的度都是3。
2. 简单图的限制:
   • “任意两个节点之间最多只允许有一条边”: 这排除了“多重边”的情况。
   • “我们可能允许...自环”: 自环是一条连接顶点到其自身的边。通常在没有特殊说明时，我们假设图是简单图 (Simple Graph)，即既没有多重边也没有自环。
3. 边的表示:
   • 如何用数学语言精确地表示一条连接 i 和 j 的边？
   • 有序对 (i, j): 文本中使用 (i, j) 来表示。但马上又说“顺序无关紧要”，这说明这里的 (i, j) 是一种不严格的说法，它实际上代表了一个无序的概念。
   • 无序对 \{i, j\}: 这是表示无向边的更严谨、更常用的方式。它明确表示 i 和 j 之间的连接，且不区分 \{i, j\} 和 \{j, i\}。
   • 集合表示法 \{\{i, j\}\}: 这是最形式化的写法。一条边本身是一个包含两个顶点的无序对 \{i, j\}。而图的整个边集 E 则是这些无序对的集合。例如，$E = \{\{1,2\}, \{2,3\}\}$。

这一部分从直观的“点和线”的描述，转向了用集合论语言进行的严格数学定义。

1. 图的本质：一个有序对
   • 一个图 $G$ 被定义为一个有序对 $(V, E)$。
   • $V$: 第一个元素是一个集合，称为顶点集 (Vertex Set)。这个集合包含了图所有的顶点。
   • $E$: 第二个元素也是一个集合，称为边集 (Edge Set)。
   • 这个定义 G = (V, E) 非常重要，它是一切图论形式化讨论的起点。
2. 边集的构成
   • 对于一个无向图，边集 $E$ 是一个由顶点对组成的集合。
   • 更精确地说，$E$ 是由 V 中元素构成的无序对的集合。每一条边 e \in E，其形式都是 \{u, v\}，其中 u, v \in V 且 u \neq v (对于简单图)。
   • 所以 $E$ 是 $V$ 的所有可能的两元素子集的集合（即 $\mathcal{P}_2(V)$）的一个子集。
3. 示例分析:
   • 图 0.12(a) (五边形):
   • V = \{1, 2, 3, 4, 5\}: 顶点集，包含了图中的5个顶点。
   • E = \{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,1\}\}: 边集。
   • \{1,2\} 表示顶点1和2之间有一条边。
   • ...
   • \{5,1\} 表示顶点5和1之间有一条边。
   • 这个集合精确地描述了五边形的连接关系。
   • 图 0.12(b) (完全图K4):
   • V = \{1, 2, 3, 4\}: 顶点集。
   • E = \{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}: 边集。
   • 这个边集包含了从V中任取两个顶点组成的所有可能的无序对。这正是完全图的定义。
4. 两种描述方式的对比:
   • 图示: 直观、易于理解，但可能因画法不同而产生误导，且不适合计算机处理。
   • 形式化描述 G=(V,E): 抽象、精确、无歧义，是数学证明和计算机算法的基础。计算机存储一个图，就是存储V和E的信息（例如用邻接矩阵或邻接表）。

1. 图的应用: 前面的定义是纯数学的，这一段开始将其与实际应用联系起来。图之所以强大，就是因为它能对现实世界中的各种“网络”和“关系”进行建模。
2. 标签 (Labels):
   • 动机: G=(V, E) 只告诉我们“有哪些东西”和“谁跟谁连着”。但在很多应用中，我们还需要知道这些东西和连接的属性。
   • 节点标签: 顶点本身可以有名字或属性。例如，用字符串 "San Francisco" 来标记一个节点，而不是抽象的数字 1。
   • 边标签 (或 权重 Weights): 边也可以有属性。例如，边的标签可以是一个数字，代表两个城市之间的距离、旅行所需的时间、或者机票的成本。
3. 带标签的图 (Labeled Graph):
   • 一个图，其顶点和/或边附带有额外的信息（标签），就称为带标签的图。如果边的标签是数字，通常也称为加权图 (Weighted Graph)。
4. 图 0.13 分析:
   • 这是一个典型的带权无向图。
   • 顶点: {SF, LA, DEN, CHI, BOS, NY} (6个城市)。这些城市名就是节点标签。
   • 边: 两个城市间有直飞航班，则有一条边。
   • 边的标签/权重: 边上的数字，代表了两个城市间最便宜的直飞票价。例如，从NY到BOS的边权重是70。
   • 这个图不仅告诉我们哪些城市之间可以直飞，还告诉我们飞过去“要花多少钱”。
5. 应用场景: 这种带权图是许多经典算法的输入。
   • 最短路径问题: 如何从SF飞到BOS总花费最少？（这需要考虑转机，例如SF->DEN->BOS）。著名的Dijkstra算法就是解决这类问题的。
   • 最小生成树问题: 假设你是航空公司，想用最少的总成本连接所有这些城市（不一定需要所有城市间都有直飞），你应该保留哪些航线？

1. 子图 (Subgraph) 的概念: 子图就是从一个大图中“取出一部分”形成的小图。
2. 形式化定义: 令大图为 $H = (V_H, E_H)$，小图为 $G = (V_G, E_G)$。我们说 $G$ 是 $H$ 的子图，如果满足以下两个条件：
   • 顶点是子集: $V_G \subseteq V_H$。即，子图的所有顶点都必须是原图的顶点。
   • 边也是子集 (且保持连接): $E_G \subseteq E_H$。即，子图的所有边都必须是原图的边。并且，$E_G$ 中的任何一条边 \{u, v\}，其两个端点 u 和 v 都必须在 $V_G$ 中。
3. “G的边是H在相应节点上的边”: 这句话解释了第二个条件。你不能只取H的顶点，然后随便在它们之间画边。你选定的那部分顶点（$V_G$），它们之间的边，只能是原来在H中就已经存在的那些边。
4. 图 0.14 分析:
   • 图H: 一个有6个顶点和多条边的大图（所有细线和粗线合在一起）。
   • 图G (深色部分):
   • 顶点集 $V_G$: 包含了H中被深色标记的4个顶点。这显然是H的6个顶点的子集。
   • 边集 $E_G$: 包含了连接那4个顶点的3条深色粗线。这3条边在原图H中也存在（作为细线）。
   • 因此，图G满足子图的定义。
5. 如何获得子图 (两种操作):
   • 删除顶点: 从原图中删除一个或多个顶点。删除一个顶点时，所有与它相连的边也必须被删除。
   • 删除边: 从原图中删除一条或多条边，而不删除顶点。

这一段定义了图论

中一些最基本的子图结构和属性，它们是构建更复杂图算法和理论的基础。

1. 路径 (Path)
   • 定义: 一个节点序列 $(v_1, v_2, \ldots, v_k)$，其中序列中任意相邻的两个节点 $(v_i, v_{i+1})$ 之间在图中都存在一条边 $\{v_i, v_{i+1}\}$。
   • 直观意义: 路径就是沿着图的边从一个节点“走”到另一个节点所经过的顶点序列。路径的长度是它包含的边的数量，即 k-1。
   • 图0.15(a)分析: 该图用粗线标出了一条路径。这条路径可以被描述为 (v1, v2, v3, v4, v5) (假设顶点从左到右编号)。
2. 简单路径 (Simple Path)
   • 定义: 一条不重复任何节点的路径（除了可能首尾相同，那就成了环）。
   • 区别: 路径 (A, B, C, B, D) 不是简单路径，因为它重复访问了节点B。而 (A, B, C, D) 是简单路径。
   • 图0.15(a)中高亮的路径就是一条简单路径。
3. 连通图 (Connected Graph)
   • 定义: 如果一个图中，从任意一个节点到任意另一个节点都至少存在一条路径，那么这个图就是连通图。
   • 直观意义: 整个图是“一体”的，没有孤立的部分。你可以从任何一个顶点出发，通过走边的方式，最终到达任何其他顶点。
4. 环 (Cycle / Circuit)
   • 定义: 一条起点和终点是同一个节点的路径。路径的长度必须至少为1。
   • 例如，路径 (A, B, C, A) 就是一个环。
   • 图0.15(b)分析: 该图用粗线标出了一个由4个顶点和4条边组成的环。
5. 简单环 (Simple Cycle)
   • 定义: 一个环，其中只有起点和终点是重复的节点。为了排除 (A, B, A) 这种平凡情况，通常要求简单环至少包含三个节点。
   • (A, B, C, D, A) 是一个简单环。
   • (A, B, C, B, A) 不是一个简单环，因为节点B在中间被重复访问了。
6. 树 (Tree)
   • 核心定义: 一个图如果同时满足以下两个条件，就被称为树：
7. 图是连通的。
8. 图中没有简单环 (无环，Acyclic)。
   • 特性: 树是一种“最精简”的连通图。在任意两个节点之间，存在唯一一条简单路径。添加任何一条新的边都会制造出一个环；删除任何一条边都会使图不再连通。
   • 图0.15(c)分析: 该图是连通的，并且你在里面找不到任何环路，所以它是一棵树。
9. 树的附加术语:
   • 根 (Root): 我们可以从树中指定一个特殊的节点作为“根”。一旦指定了根，树就有了层次结构（上/下关系）。这种树称为有根树 (Rooted Tree)，在计算机科学中极为常见（如文件系统目录树、XML/HTML的DOM树）。根通常画在最上面。
   • 叶子 (Leaf): 在一棵树中，度为1的节点称为叶子。它们是树的“末梢节点”。如果是有根树，根节点即使度为1通常也不称为叶子。

1. 有向图 (Directed Graph / Digraph):
   • 这是对无向图概念的一个重要扩展。
   • 核心区别: 边是有方向的。它不再是简单的“连接”，而是从一个顶点到另一个顶点的“指向”。
   • 箭头 (Arrows): 在图示中，我们用箭头来表示有向边，明确指出其方向。一条从 u 指向 v 的边，表示可以从 u 到达 v，但不一定能从 v 回到 u。
   • 应用: 非常适合建模非对称关系，如单行道、网页链接、任务的先后依赖、函数调用关系等。
2. 度的新概念: 在有向图中，一个顶点的“度”被细分为两个部分。
   • 出度 (Out-degree): 从该顶点出发的边的数量。记作 deg+(v)。它表示该节点“影响”或“指向”了多少其他节点。
   • 入度 (In-degree): 指向该顶点的边的数量。记作 deg-(v)。它表示该节点被多少其他节点“影响”或“指向”。
3. 图 0.16 分析:
   • 这是一个有6个顶点和8条有向边的有向图。
   • 我们可以计算每个顶点的入度和出度：
   • 顶点1: 出度=2 (指向2, 5)，入度=2 (来自2, 6)。
   • 顶点2: 出度=2 (指向1, 4)，入度=1 (来自1)。
   • 顶点3: 出度=0，入度=1 (来自6)。这是一个“终点”或“汇点”(sink)。
   • 顶点4: 出度=0，入度=2 (来自2, 5)。
   • 顶点5: 出度=2 (指向4, 6)，入度=1 (来自1)。
   • 顶点6: 出度=2 (指向1, 3)，入度=1 (来自5)。
4. 有向图的握手定理: 所有顶点的出度之和，等于所有顶点的入度之和，且都等于图的总边数。
   • $\sum deg+(v) = \sum deg-(v) = |E|$
   • 在图 0.16 中，出度之和 = 2+2+0+0+2+2 = 8。入度之和 = 2+1+1+2+1+1 = 8。总边数是8。定理成立。
   • 直观理解: 每条有向边，都从一个顶点出发，进入另一个顶点。所以它会为一个顶点的出度贡献1，为另一个顶点的入度贡献1。

1. 有向边的表示:
   • 因为方向很重要，所以表示有向边必须使用有序对 (Ordered Pair) (i, j)。
   • (i, j) 表示一条从 i (尾部, tail) 指向 j (头部, head) 的边。
   • (i, j) 和 (j, i) 代表的是两条不同的、方向相反的边。这与无向边的无序对 \{i, j\} 形成鲜明对比。
2. 有向图的形式化定义:
   • 与无向图一样，一个有向图 G 也被定义为 (V, E)。
   • V 仍然是顶点集。
   • 关键区别在于 边集 E: 对于有向图，E 是一个由有序对组成的集合。
   • E 是笛卡尔积 $V \times V$ 的一个子集。
3. 示例分析 (图 0.16):
   • V = \{1, 2, 3, 4, 5, 6\}。
   • E = \{(1,2), (1,5), (2,1), (2,4), (5,4), (5,6), (6,1), (6,3)\}。
   • 这个集合 E 精确地列出了图中的8条有向边。例如，(1,2) 在集合中，表示有 1->2 的边；但 (2,3) 不在集合中，所以图中没有 2->3 的边。
4. 有向路径 (Directed Path):
   • 定义: 一个顶点序列 $(v_1, v_2, \ldots, v_k)$，其中对于任意相邻的 v_i, v_{i+1}，图中都必须存在一条有向边 $(v_i, v_{i+1})$。
   • 直观: 你必须顺着箭头的方向走。
5. 强连通 (Strongly Connected):
   • 定义: 一个有向图是强连通的，如果对于图中任意两个不同的顶点 u 和 v，既存在一条从 u 到 v 的有向路径，也存在一条从 v 到 u 的有向路径。
   • 直观: 这是一个比无向图的“连通”更强的条件。它意味着从任何一个点出发，你都可以到达任何其他点，并且还能回来。整个图是一个紧密联系的整体，没有“单行道”陷阱。
   • 图 0.16 不是强连通的。例如，你可以从1走到4 (1->2->4 或 1->5->4)，但你无法从4走回到1，因为4的出度是0。
6. 有向图与二元关系:
   • 这是一个非常深刻和重要的联系。一个定义在集合 D 上的二元关系 R 和一个顶点集为 D 的有向图 G 之间存在一一对应关系。
   • 关系 -> 图: 给定关系 R，我们可以画一个图。R 的论域 D 就是图的顶点集。对于 D 中每两个元素 x, y，如果 x R y 为 TRUE，我们就在图中画一条从 x 到 y 的有向边。这正是前面讲的“关系的集合表示法”：边集 $E = \{(x,y) \mid x R y = \text{TRUE}\}$。
   • 图 -> 关系: 给定一个有向图 G=(D, E)，我们可以定义一个二元关系 R：x R y 为 TRUE 当且仅当 (x, y) \in E。
   • 因此，有向图可以看作是二元关系的可视化。