综述集合论与运算、关系矩阵与性质及特征函数，梳理离散数学的核心框架。
离散数学基础
参考书目：Discrete Mathematical Structures (Sixth Edition)
集合论 (Set Theory)
集合的基本概念
集合的定义与性质
- 集合 (Set)：由确定的、互不相同的对象组成的整体
- 元素 (Element)：组成集合的对象
- 性质：确定性、互异性、无序性
集合的表示方式
- 列举法：$A = {1, 2, 3, 4, 5}$
- 描述法：$A = {x | x \text{ 满足条件 } P(x)}$
- 图示法：文式图 (Venn Diagram)
特殊集合
- 全集 (Universal Set)：$U$ 或 $\Omega$
- 空集 (Empty Set)：$\emptyset$ 或 ${}$
- 自然数集：$\mathbb{N} = {0, 1, 2, 3, \ldots}$
- 整数集：$\mathbb{Z} = {\ldots, -2, -1, 0, 1, 2, \ldots}$
- 有理数集：$\mathbb{Q}$
- 实数集：$\mathbb{R}$
集合间的关系
基本关系
- 属于关系：$x \in A$（$x$ 属于集合 $A$）
- 不属于关系：$x \notin A$（$x$ 不属于集合 $A$）
- 子集关系：$A \subseteq B \Leftrightarrow \forall x (x \in A \Rightarrow x \in B)$
- 真子集关系：$A \subset B \Leftrightarrow A \subseteq B \land A \neq B$
- 相等关系：$A = B \Leftrightarrow A \subseteq B \land B \subseteq A$
笛卡尔积 (Cartesian Product)
设 $A$ 和 $B$ 是两个集合，则 $A$ 和 $B$ 的笛卡尔积定义为：
$$A \times B = {(a, b) | a \in A \land b \in B}$$
性质：
- $|A \times B| = |A| \cdot |B|$
- $A \times \emptyset = \emptyset \times A = \emptyset$
- $(A \cup B) \times C = (A \times C) \cup (B \times C)$
- $(A \cap B) \times C = (A \times C) \cap (B \times C)$
集合的重要性质
幂集 (Power Set)
集合 $A$ 的幂集 $\mathcal{P}(A)$ 是 $A$ 的所有子集组成的集合：
$$\mathcal{P}(A) = {S | S \subseteq A}$$
幂集的基数：若 $|A| = n$，则 $|\mathcal{P}(A)| = 2^n$（所以称幂）
示例：若 $A = {1, 2}$，则：
$$\mathcal{P}(A) = {\emptyset, {1}, {2}, {1,2}}$$
基数 (Cardinality)
集合 $A$ 的基数 $|A|$ 表示集合中元素的个数。
- 有限集：$|A| = n$（$n \in \mathbb{N}$）
容斥原理 (Inclusion-Exclusion Principle)
二集合容斥原理：
$$|A \cup B| = |A| + |B| - |A \cap B|$$
三集合容斥原理：
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$
一般形式（$n$ 个集合）：
$$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} \left|\bigcap_{i=1}^{n} A_i\right|$$
补集形式：
$$|\overline{A \cup B \cup C}| = |\overline{A} \cap \overline{B} \cap \overline{C}| = |U| - |A \cup B \cup C|$$
集合基数相关的证明：拆分为两个不相交的集合
$$|A \cup B| = |A - B| + |B| = |A| + |B - A|$$
集合运算
基本运算
- 并集 (Union)：$A \cup B = {x | x \in A \lor x \in B}$
- 交集 (Intersection)：$A \cap B = {x | x \in A \land x \in B}$
- 差集 (Difference)：$A - B = {x | x \in A \land x \notin B}$
- 补集 (Complement)：$\overline{A} = U - A = {x | x \in U \land x \notin A}$
- 对称差 (Symmetric Difference)：$A \triangle B = (A - B) \cup (B - A)$
$$A \triangle B = (A \cup B) - (A \cap B) = (A - B) \cup (B - A)$$
笛卡尔积：
划分：所有的元素唯一地分到不同的集合里面，那些集合的整体构成一个划分，其中某个集合叫原集合的分块
A的划分是A的幂集的子集
集合运算的性质
基本定律
交换律 (Commutative Laws)：
- $A \cup B = B \cup A$
- $A \cap B = B \cap A$
结合律 (Associative Laws)：
- $(A \cup B) \cup C = A \cup (B \cup C)$
- $(A \cap B) \cap C = A \cap (B \cap C)$
分配律 (Distributive Laws)：
- $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
- $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
德摩根定律 (De Morgan’s Laws)：
- $\overline{A \cup B} = \overline{A} \cap \overline{B}$
- $\overline{A \cap B} = \overline{A} \cup \overline{B}$
恒等律 (Identity Laws)：
- $A \cup \emptyset = A$
- $A \cap U = A$
零律 (Null Laws)：
- $A \cup U = U$
- $A \cap \emptyset = \emptyset$
补律 (Complement Laws)：
- $A \cup \overline{A} = U$
- $A \cap \overline{A} = \emptyset$
- $\overline{\overline{A}} = A$
乘积集合的运算性质：
- 分配律：$A \times (B \cup C) = (A \times B) \cup (A \times C)$
- 结合律：
关系 (Relations)
由笛卡尔积引出的内容
关系的定义：设 $A$ 和 $B$ 是两个集合，则称 $A \times B$ 的任意子集 $R$ 为从 $A$ 到 $B$ 的一个关系，记作 $R \subseteq A \times B$。
特殊关系：
- 空关系：$R = \emptyset$（空集）
- 全关系：$R = A \times A$（全集）
关系 $R$ 是一个特殊的集合（乘积集合的子集）
关系的表示：
- $a$ 与 $b$ 是 $R$ 相关的：记作 $(a, b) \in R$ 或 $aRb$
- 特征函数的记法：$\chi_R(a, b) = \begin{cases} 1, & \text{if } (a, b) \in R \ 0, & \text{if } (a, b) \notin R \end{cases}$
关系的基本概念：
- 定义域 (Domain)：$\text{dom}(R) = {a \in A | \exists b \in B, (a, b) \in R}$
- 值域 (Range)：$\text{ran}(R) = {b \in B | \exists a \in A, (a, b) \in R}$
- 集合 $A_1$ 对于关系 $R$ 的像集：$R(A_1) = {b \in B | \exists a \in A_1, (a, b) \in R}$
- $x$ 关于 $R$ 的像集：$R({x}) = {y | (x, y) \in R}$
关系矩阵 (Relation Matrix)
像使用特征函数表示集合一样，我们可以使用关系矩阵来表示关系。
设 $A = {a_1, a_2, \ldots, a_m}$，$B = {b_1, b_2, \ldots, b_n}$，关系 $R \subseteq A \times B$，则关系矩阵 $M_R = [m_{ij}]{m \times n}$，其中：
$$m{ij} = \begin{cases}
1, & \text{if } (a_i, b_j) \in R \
0, & \text{if } (a_i, b_j) \notin R
\end{cases}$$
关系的运算
合成运算 “$\circ$”：设 $R$ 是 $A$ 到 $B$ 的一个关系，$S$ 是 $B$ 到 $C$ 的一个关系，则称 $S \circ R$ 是 $A$ 到 $C$ 的复合（合成）关系：
$$S \circ R = {(a, c) | a \in A, c \in C, \exists b \in B, (a, b) \in R \land (b, c) \in S}$$
矩阵表示：$(S \circ R)$ 的关系矩阵等价为矩阵的乘法：$M_{S \circ R} = M_R \cdot M_S$
恒等关系：若 $R \circ S = S \circ R = R$，则 $S$ 对应的矩阵为单位矩阵 $I$
关系的幂运算：
- 定义：$R^n = \underbrace{R \circ R \circ \cdots \circ R}_{n \text{ 次}}$
- 公式：$R^0 = I_A$（恒等关系），$R^{n+1} = R^n \circ R$
传递闭包：
- $R$ 的关联关系（$R^{\infty}$）：$R^{\infty} = R^1 \cup R^2 \cup R^3 \cup \cdots$
- 可达关系：从 $a$ 到 $b$ 存在路径的关系
相对于看图来说，代数计算显然更方便
关系合成的性质
结合律：$(R \circ S) \circ T = R \circ (S \circ T)$
分配律：$R \circ (S \cup T) = (R \circ S) \cup (R \circ T)$
单位元：$R \circ I_A = I_B \circ R = R$（其中 $I_A$、$I_B$ 分别是 $A$、$B$ 上的恒等关系）
关系的性质
设 $R$ 是集合 $A$ 上的关系（即 $R \subseteq A \times A$），则：
自反性 (Reflexive)：$\forall a \in A, (a, a) \in R$
反自反性 (Irreflexive)：$\forall a \in A, (a, a) \notin R$
对称性 (Symmetric)：$\forall a, b \in A, (a, b) \in R \Rightarrow (b, a) \in R$
反对称性 (Antisymmetric)：$\forall a, b \in A, (a, b) \in R \land (b, a) \in R \Rightarrow a = b$
传递性 (Transitive)：$\forall a, b, c \in A, (a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R$
关系与有向图 (Relations and Directed Graphs)
图的定义：称序对 $G = (V, E)$ 为图。其中，$V$ 表示顶点集合，$E$ 表示边集合（顶点之间的连线，称之为边）。如果顶点之间的连线具有方向性，则称该图为有向图。
度的概念：
- 顶点的入度 (In-degree)：$\text{deg}^-(v) = |{u \in V | (u, v) \in E}|$（进入该顶点的边数）
- 顶点的出度 (Out-degree)：$\text{deg}^+(v) = |{u \in V | (v, u) \in E}|$（离开该顶点的边数）
路径 (Path)：从顶点 $v_0$ 到顶点 $v_n$ 的路径是顶点序列 $v_0, v_1, v_2, \ldots, v_n$，其中 $(v_i, v_{i+1}) \in E$，$i = 0, 1, \ldots, n-1$。
等价性：针对有限论域，关系、矩阵和图是相互等价的
- 关系 $R \subseteq A \times A$
- 关系矩阵 $M_R$
- 有向图 $G = (A, R)$
图论中的概念：
- 简单路径：所有顶点都不相同的路径
- 回路 (Cycle)：起点和终点相同的路径，即 $v_0 = v_n$
- 连通性：如果存在从顶点 $u$ 到顶点 $v$ 的路径，则称 $u$ 和 $v$ 是连通的
- 强连通图：对于任意两个顶点 $u, v$，都存在从 $u$ 到 $v$ 和从 $v$ 到 $u$ 的路径
矩阵运算与图的关系：
- $M_R^n$ 的第 $(i, j)$ 元素表示从顶点 $i$ 到顶点 $j$ 长度为 $n$ 的路径数
- 可达矩阵：$M_{R^*} = M_R^0 + M_R^1 + M_R^2 + \cdots$（布尔运算）
特征函数 (Characteristic Function)
集合 $A$ 的特征函数 $\chi_A: U \to {0, 1}$ 定义为：
$$\chi_A(x) = \begin{cases}
1, & \text{if } x \in A \
0, & \text{if } x \notin A
\end{cases}$$
特征函数与集合运算的关系
设 $U$ 是全集，$A, B \subseteq U$，则：
- 并集：$\chi_{A \cup B}(x) = \max(\chi_A(x), \chi_B(x)) = \chi_A(x) + \chi_B(x) - \chi_A(x)\chi_B(x)$
- 交集：$\chi_{A \cap B}(x) = \min(\chi_A(x), \chi_B(x)) = \chi_A(x) \cdot \chi_B(x)$
- 补集：$\chi_{\overline{A}}(x) = 1 - \chi_A(x)$
- 对称差：$\chi_{A \triangle B}(x) = \chi_A(x) + \chi_B(x) - 2\chi_A(x)\chi_B(x) = |\chi_A(x) - \chi_B(x)|$
- 差集：$\chi_{A - B}(x) = \chi_A(x) \cdot (1 - \chi_B(x)) = \chi_A(x) \cdot \chi_{\overline{B}}(x)$
特征函数将集合运算与代数运算联系起来，为集合论提供了代数化的处理方法。
可以使用特征函数证明集合相等
集合乘积的特征函数
设 $A \subseteq X$，$B \subseteq Y$，则笛卡尔积 $A \times B$ 的特征函数定义为：
$$\chi_{A \times B}(x, y) = \chi_A(x) \cdot \chi_B(y)$$
其中 $(x, y) \in X \times Y$。
性质：
- $\chi_{(A_1 \cup A_2) \times B}(x, y) = \chi_{A_1 \times B}(x, y) + \chi_{A_2 \times B}(x, y) - \chi_{A_1 \times B}(x, y) \cdot \chi_{A_2 \times B}(x, y)$
- $\chi_{(A_1 \cap A_2) \times B}(x, y) = \chi_{A_1 \times B}(x, y) \cdot \chi_{A_2 \times B}(x, y)$
- $\chi_{A \times (B_1 \cup B_2)}(x, y) = \chi_{A \times B_1}(x, y) + \chi_{A \times B_2}(x, y) - \chi_{A \times B_1}(x, y) \cdot \chi_{A \times B_2}(x, y)$
本文遵循非商业性使用-国际署名 许可协议，转载请说明。
