附录 B 集合等 (Sets, Etc.)

核心结论

集合基础：成员关系、集合相等、子集与真子集、并/交/差/补运算；空集 ∅、整数 ℤ、自然数 ℕ、实数 ℝ；幂集 \(2^S\) 的势 \(\lvert 2^S \rvert = 2^{\lvert S \rvert}\)。
集合代数定律：空集律、幂等律、交换律、结合律、分配律、吸收律、De Morgan 律（式 B.1, B.2）——所有后续证明和构造的基础。
关系 (Relations) 与分类：自反、对称、传递、反对称；等价关系（自反+对称+传递）、偏序（自反+反对称+传递）、全序（偏序+全关系）、全前序（自反+传递+全关系）。
函数 (Functions)：定义（\(f: A \to B\)，每元素唯一像）、单射（injective）、满射（surjective）、双射（bijective）；逆函数仅对双射有意义。
图 (Graphs)：有向图 \(G = (V, E)\)、无向图 \((V, E)\)、度（出/入度）、路径与简单路径、圈、强连通与弱连通、子图与导出子图、同构。
树 (Trees)：自由树（连通无圈）、根树（指定根节点）、有序树（子节点有序）、二叉树（左/右子节点区分）、k-叉完全树（\(n\) 叶子的高度 = \(\log_k n\)）。

附录主旨

本附录是全书的「离散数学基础」：集合与关系是后续图论、算法正确性证明的基础；函数是问题抽象（输入→输出）的核心；图与树是全书第 10-26 章、B-Tree、红黑树、并查集等数据结构的语言。本附录内容自成体系，对已熟悉者可快速浏览；对初学者应扎实掌握——后续所有章节都会用到。

一、核心概念

本附录围绕 6 个核心概念展开：集合运算、关系分类、函数类型、图的基本术语、树的分类。

概念	定义 + 重要性	实现提示
集合运算	并 \(A \cup B\)、交 \(A \cap B\)、差 \(A \setminus B\)、补 \(\bar{A}\)、对称差 \(A \triangle B\)；幂集 \(2^S\)；笛卡尔积 \(A \times B\)。	§B.1；幂集大小 \(\lvert 2^S \rvert = 2^{\lvert S \rvert}\)；笛卡尔积大小 \(\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert\)。
关系 (Relations)	二元关系 \(R \subseteq A \times B\)；性质：自反、对称、传递、反对称。	§B.2；等价类与划分一一对应（Theorem B.1）；偏序与全序区别在于全关系。
函数 (Functions)	\(f: A \to B\)，每个 a ∈ A 恰一个像；单射（不同元 → 不同像）、满射（每个 b 有原像）、双射（既单又满）。	§B.3；逆函数仅双射有意义；双射给出集合「势」的比较。
有向图与无向图	有向：边为有序对 (u, v)；无向：边为无序对 {u, v}；度（出/入度）、路径、圈、连通性、子图、同构。	§B.4；无向图连通分量是等价类；有向图强连通分量也是等价类。
自由树与根树	自由树 = 连通无圈无向图；根树 = 指定一个根；有根树引入父/子/深度/高度。	§B.5；Theorem B.2 给出自由树的 6 个等价刻画；根树中节点度 = 子节点数。
二叉树与 k-叉树	二叉树区分左/右子节点（即使只有一个）；k-叉完全树有 \(k^h\) 个叶子、高度 \(\log_k n\)。	§B.5.3；Kraft 不等式（练习 B.5-6）：\(\sum_x 2^{-d(x)} \leq 1\)。

概念

定义 + 重要性

实现提示

集合运算

并 \(A \cup B\)、交 \(A \cap B\)、差 \(A \setminus B\)、补 \(\bar{A}\)、对称差 \(A \triangle B\)；幂集 \(2^S\)；笛卡尔积 \(A \times B\)。

§B.1；幂集大小 \(\lvert 2^S \rvert = 2^{\lvert S \rvert}\)；笛卡尔积大小 \(\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert\)。

关系 (Relations)

二元关系 \(R \subseteq A \times B\)；性质：自反、对称、传递、反对称。

§B.2；等价类与划分一一对应（Theorem B.1）；偏序与全序区别在于全关系。

函数 (Functions)

\(f: A \to B\)，每个 a ∈ A 恰一个像；单射（不同元 → 不同像）、满射（每个 b 有原像）、双射（既单又满）。

§B.3；逆函数仅双射有意义；双射给出集合「势」的比较。

有向图与无向图

有向：边为有序对 (u, v)；无向：边为无序对 {u, v}；度（出/入度）、路径、圈、连通性、子图、同构。

§B.4；无向图连通分量是等价类；有向图强连通分量也是等价类。

自由树与根树

自由树 = 连通无圈无向图；根树 = 指定一个根；有根树引入父/子/深度/高度。

§B.5；Theorem B.2 给出自由树的 6 个等价刻画；根树中节点度 = 子节点数。

二叉树与 k-叉树

二叉树区分左/右子节点（即使只有一个）；k-叉完全树有 \(k^h\) 个叶子、高度 \(\log_k n\)。

§B.5.3；Kraft 不等式（练习 B.5-6）：\(\sum_x 2^{-d(x)} \leq 1\)。

二、详细笔记

2.1 集合基础与运算

What：集合是无序、互异元素的聚集；常用集合：∅（空集）、ℕ（自然数，含 0）、ℤ（整数）、ℝ（实数）。

Why：集合是离散数学的基本对象；所有后续结构（关系、函数、图）都以集合为基础。

How：

运算	定义
子集 \(A \subseteq B\)	每个 \(x \in A\) 都有 \(x \in B\)
真子集 \(A \subset B\)	\(A \subseteq B\) 且 \(A \neq B\)
并 \(A \cup B\)	\(\{x : x \in A \text{ or } x \in B\}\)
交 \(A \cap B\)	\(\{x : x \in A \text{ and } x \in B\}\)
差 \(A \setminus B\)	\(\{x : x \in A \text{ and } x \notin B\}\)
补 \(\bar{A}\)	\(U \setminus A\)（U 为全集）
幂集 \(2^S\)	\(S\) 的所有子集
笛卡尔积 \(A \times B\)	\(\{(a, b) : a \in A, b \in B\}\)

运算

定义

子集 \(A \subseteq B\)

每个 \(x \in A\) 都有 \(x \in B\)

真子集 \(A \subset B\)

\(A \subseteq B\) 且 \(A \neq B\)

并 \(A \cup B\)

\(\{x : x \in A \text{ or } x \in B\}\)

交 \(A \cap B\)

\(\{x : x \in A \text{ and } x \in B\}\)

差 \(A \setminus B\)

\(\{x : x \in A \text{ and } x \notin B\}\)

补 \(\bar{A}\)

\(U \setminus A\)（U 为全集）

幂集 \(2^S\)

\(S\) 的所有子集

笛卡尔积 \(A \times B\)

\(\{(a, b) : a \in A, b \in B\}\)

集合代数定律（式 B.1, B.2）：幂等、交换、结合、分配、吸收、De Morgan（\(\overline{A \cap B} = \bar{A} \cup \bar{B}\)）。

When：所有涉及「分类」「组合」「枚举」的问题。

Example：包含-排斥原理（式 B.3）：\(\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert\)；推广到 n 个集合（练习 B.1-3）。

2.2 关系与等价类

What：二元关系 \(R \subseteq A \times B\)（集合 A 到 B 的关系）；若 \(A = B\) 称 A 上的关系。性质：

性质	定义
自反	\(\forall a \in A, (a, a) \in R\)
对称	\((a, b) \in R \Rightarrow (b, a) \in R\)
反对称	\((a, b) \in R \wedge (b, a) \in R \Rightarrow a = b\)
传递	\((a, b), (b, c) \in R \Rightarrow (a, c) \in R\)

性质

定义

自反

\(\forall a \in A, (a, a) \in R\)

对称

\((a, b) \in R \Rightarrow (b, a) \in R\)

反对称

\((a, b) \in R \wedge (b, a) \in R \Rightarrow a = b\)

传递

\((a, b), (b, c) \in R \Rightarrow (a, c) \in R\)

Why：关系的分类（等价、偏序）是后续图论、动态规划排序、拓扑排序等的基础。

How：

类型	性质
等价关系	自反 + 对称 + 传递；例：「a + b 为偶数」
偏序	自反 + 反对称 + 传递；例：「≤」、「子集 ⊆」
全序	偏序 + 全关系（\(\forall a, b, (a, b) \in R \lor (b, a) \in R\)）
全前序	自反 + 传递 + 全关系；例：「≤」在含等值类时

类型

性质

等价关系

自反 + 对称 + 传递；例：「a + b 为偶数」

偏序

自反 + 反对称 + 传递；例：「≤」、「子集 ⊆」

全序

偏序 + 全关系（\(\forall a, b, (a, b) \in R \lor (b, a) \in R\)）

全前序

自反 + 传递 + 全关系；例：「≤」在含等值类时

Theorem B.1：等价关系的等价类与划分一一对应。

When：分类（如模 n 等价、图连通分量、状态机等价状态）；排序（偏序→全序：拓扑排序）。

Example：「模 3 同余」是整数集上的等价关系，等价类 = \(\{0, 3, 6, \ldots\}, \{1, 4, 7, \ldots\}, \{2, 5, 8, \ldots\}\)。

2.3 函数与类型

What：函数 \(f: A \to B\) 是满足「每个 \(a \in A\) 恰有唯一 \(b \in B\) 使 \((a, b) \in f\)」的二元关系。

Why：函数是「输入→输出」的形式化；算法就是从输入到输出的函数；单/满/双射决定可逆性。

How：

类型	定义	双射时
单射 (injective)	\(a \neq a' \Rightarrow f(a) \neq f(a')\)；\(\lvert A \rvert \leq \lvert B \rvert\)	\(\lvert A \rvert \leq \lvert B \rvert\)
满射 (surjective)	每个 \(b \in B\) 有原像；\(\lvert A \rvert \geq \lvert B \rvert\)	\(\lvert A \rvert \geq \lvert B \rvert\)
双射 (bijective)	既单又满；存在逆函数	既是单射又是满射
逆 \(f^{-1}\)	仅双射有意义；\(f^{-1}(b) = a \Leftrightarrow f(a) = b\)	唯一逆映射

类型

定义

双射时

单射 (injective)

\(a \neq a' \Rightarrow f(a) \neq f(a')\)；\(\lvert A \rvert \leq \lvert B \rvert\)

\(\lvert A \rvert \leq \lvert B \rvert\)

满射 (surjective)

每个 \(b \in B\) 有原像；\(\lvert A \rvert \geq \lvert B \rvert\)

\(\lvert A \rvert \geq \lvert B \rvert\)

双射 (bijective)

既单又满；存在逆函数

既是单射又是满射

逆 \(f^{-1}\)

仅双射有意义；\(f^{-1}(b) = a \Leftrightarrow f(a) = b\)

唯一逆映射

有限集函数定理：\(f: A \to B\) 单射 ⟹ \(\lvert A \rvert \leq \lvert B \rvert\)；满射 ⟹ \(\lvert A \rvert \geq \lvert B \rvert\)（鸽巢原理的函数版）。

When：描述算法（输入→输出）；证明双射用于集合势的比较；离散概率中样本空间上的随机变量。

Example：\(f(n) = (-1)^n \lfloor n/2 \rfloor\) 是 \(\mathbb{N} \to \mathbb{Z}\) 的双射（自然数与整数等势）。

2.4 图的基本定义

What：图 \(G = (V, E)\) 由顶点集 V 和边集 E 组成；有向图边为有序对，无向图边为无序对。

Why：图是描述关系型数据的基本结构——网络、依赖、状态转移等都用图建模；BFS/DFS/最短路径等都是图算法。

How：

概念	定义
路径	顶点序列 \(\langle v_0, v_1, \ldots, v_k \rangle\) 满足相邻顶点有边
简单路径	路径中顶点互不相同
圈	\(v_0 = v_k\) 且至少含一条边的路径
简单圈	圈中除起终点外顶点互不相同
连通	无向图任意两顶点间有路径
连通分量	等价类（连通关系）
强连通	有向图任意两顶点互相可达
子图	\(V' \subseteq V, E' \subseteq E\)
导出子图	给定 \(V'\)，所有两端都在 \(V'\) 中的边
同构	双射 \(f: V \to V'\) 保持边关系

概念

定义

路径

顶点序列 \(\langle v_0, v_1, \ldots, v_k \rangle\) 满足相邻顶点有边

简单路径

路径中顶点互不相同

圈

\(v_0 = v_k\) 且至少含一条边的路径

简单圈

圈中除起终点外顶点互不相同

连通

无向图任意两顶点间有路径

连通分量

等价类（连通关系）

强连通

有向图任意两顶点互相可达

子图

\(V' \subseteq V, E' \subseteq E\)

导出子图

给定 \(V'\)，所有两端都在 \(V'\) 中的边

同构

双射 \(f: V \to V'\) 保持边关系

握手引理（练习 B.4-1）：\(\sum_{v \in V} \deg(v) = 2\lvert E \rvert\)；推论：度之和为偶数。

When：建模任何「关系网络」；图算法广泛应用于网络、社交、依赖关系分析。

Example：Figure B.2(a) 有向图：V = {1,2,3,4,5,6}，E 含 (1,2), (2,2)（自环）, (2,4), (2,5), (4,1), (4,5), (5,4), (6,3)；强连通分量 = {1,2,4,5}, {3}, {6}。

2.5 自由树 (Free Trees)

What：连通无圈的无向图；Theorem B.2 给出 6 个等价刻画。

Why：树是最简单的图结构，是许多数据结构（二叉搜索树、B 树、堆、Trie）的基础。

How — Theorem B.2 刻画：

编号	刻画
1	G 是自由树
2	任意两顶点间有唯一简单路径
3	G 连通，删任意一边后不连通
4	G 连通且 \(\lvert E \rvert = \lvert V \rvert - 1\)
5	G 无圈且 \(\lvert E \rvert = \lvert V \rvert - 1\)
6	G 无圈，加任意一边产生圈

When：证明某结构是树；选择合适刻画简化证明。

Example：含 3 个顶点的自由树：唯一是 K_3（路径 a-b-c）。

2.6 根树、有序树、二叉树

What：本节讨论四种与「树」相关的变体——从自由树加根开始，逐步引入有序、二叉、完全 k-叉的层次。

根树：自由树指定一个根节点；引入父/子/深度/高度术语。
有序树：根树中每个节点的子节点有顺序。
二叉树：每个节点有左/右子树（即使为空），区分左右位置。
完全 k-叉树：所有叶子同深度，所有内部节点度 = k。

Why：二叉树是有序树的「位置敏感」版本；完全 k-叉树是堆、B-树、Trie 的基础。

How：

概念	性质
父/子	路径上相邻节点
深度	根到节点的边数（根深度 0）
高度	节点到最深叶子的边数；树高 = 根的高度
叶子	无子节点
内部节点	非叶子
子树	节点 + 其所有后代
二叉树递归	空树 / 根 + 左二叉树 + 右二叉树
完全 k-叉树	\(k^h\) 个叶子、高度 \(\log_k n\)
Kraft 不等式	\(\sum 2^{-d(x)} \leq 1\)（练习 B.5-6）

概念

性质

父/子

路径上相邻节点

深度

根到节点的边数（根深度 0）

高度

节点到最深叶子的边数；树高 = 根的高度

叶子

无子节点

内部节点

非叶子

子树

节点 + 其所有后代

二叉树递归

空树 / 根 + 左二叉树 + 右二叉树

完全 k-叉树

\(k^h\) 个叶子、高度 \(\log_k n\)

Kraft 不等式

\(\sum 2^{-d(x)} \leq 1\)（练习 B.5-6）

When：所有树形数据结构；堆（完全二叉树）、B 树（平衡多叉树）、Trie（前缀树）。

Example：完全二叉树高度 3：8 叶子、7 内部节点、15 总节点；B 树节点分支因子通常 100+。

三、关键图表

核心公式对照表

公式编号

内容

式 B.1

分配律：\(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)

式 B.2

De Morgan：\(\overline{A \cap B} = \bar{A} \cup \bar{B}\)

式 B.3

包含-排斥：\(\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert\)

式 B.4

笛卡尔积大小：\(\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert\)

幂集大小

\(\lvert 2^S \rvert = 2^{\lvert S \rvert}\)

Theorem B.1

等价关系 ⟺ 划分

Theorem B.2

自由树 6 等价刻画

握手引理

\(\sum_v \deg(v) = 2\lvert E \rvert\)

Kraft 不等式

\(\sum_x 2^{-d(x)} \leq 1\)

四、思维导图

mindmap
  root((附录 B 集合等))
    集合
      成员子集
      并交差补
      幂集与积
      De Morgan律
    关系
      自反对称
      偏序全序
      等价类
    函数
      单射满射
      双射与逆
      域与陪域
    图
      有向无向
      路径圈连通
      同构子图
    自由树
      连通无圈
      6等价刻画
      边数V-1
    根树与二叉
      父子深度
      有序位置
      k叉完全树

五、重点与易错点

幂集大小 \(\lvert 2^S \rvert = 2^{\lvert S \rvert}\)：S 有 n 个元素就有 \(2^n\) 个子集；这是「指数级增长」最简单的例子。
De Morgan 律 \(\overline{A \cap B} = \bar{A} \cup \bar{B}\) 与 \(\overline{A \cup B} = \bar{A} \cap \bar{B}\)：常被混淆；记住「not (A and B) = (not A) or (not B)」。
等价关系 vs 偏序：前者满足对称（\(a \sim b \Rightarrow b \sim a\)），后者满足反对称（\(a \leq b \wedge b \leq a \Rightarrow a = b\)）；两者都不满足另两条性质。
「全前序 (total preorder)」 不同于「全序」：前者允许等值类（\(a \sim b\) 但 \(a \neq b\)），后者强制 \(a = b\)；全前序在含合并节点的偏序图中常见。
单射与满射对有限集的方向：\(f: A \to B\) 单射 ⟹ \(\lvert A \rvert \leq \lvert B \rvert\)；满射 ⟹ \(\lvert A \rvert \geq \lvert B \rvert\)；双射 ⟺ 等势。
逆函数仅双射有意义：非双射函数的「逆」是多值关系，不是函数。
有向图 vs 无向图：有向图邻接关系不对称（如 2→4 不蕴含 4→2）；无向图 (u,v) = (v,u)；有向图「自环」允许，无向图禁止。
「强连通」是有向图专有概念：无向图只有「连通」；有向图「连通」（忽略方向）不蕴含「强连通」。
自由树的 6 个等价刻画：证明中常需选择最适合的刻画——例如证「\(\lvert E \rvert = \lvert V \rvert - 1\) 且无圈 ⟹ 连通」常用刻画 5。
根树 vs 自由树：根树中节点「度」= 子节点数（不计父节点）；自由树中「度」= 邻居总数。
二叉树区分左右：即使只有一个子节点也分左/右——这是与「有序树度 ≤ 2」的关键区别（Figure B.7a vs b）。
完全 k-叉树高度 \(\log_k n\)：是堆、B 树等性能分析的基础；高 \(h\) 时 \(n\) 个叶子需要 \(\Theta(n/k)\) 内部节点。