离散数学 1 第 5 章：集合与关系——集合运算与关系表示
前三章的谓词公式 P(x)，说到底就是在说"x 属于某个集合"，所以集合论不是另起一门课，而是把逻辑换了一套符号。这一章的实操目标有两个：把集合恒等式的证明训练成"逐条对译成逻辑定律"，以及把关系从"有序对的集合"翻译成矩阵和图——后面第 6、7、8 章所有关于关系的判定与运算，都是在这三种表示之间来回切换。集合恒等式不必背第二遍，它就是第 2 章定律表的镜像。
一、集合的基本概念与表示
集合是把确定、彼此可区分的对象汇成的整体，对象叫元素，记 a∈A。三种表示法各有用处：
- 枚举法：A = {1, 2, 3}，元素少时最清楚。
- 描述法：A = {x | x 是小于 10 的素数}，元素多或无限时唯一可行。
- 文氏图：画圆圈表示范围，用于直观判断运算结果，不能代替证明。
集合的元素有三个特征：无序、互异、确定。{1,2} 与 {2,1} 是同一个集合；{1,1,2} 与 {1,2} 也是同一个集合。
三个基本关系必须分清：
- 子集 A⊆B：∀x(x∈A → x∈B)。
- 真子集 A⊂B：A⊆B 且 A≠B。
- 相等 A=B：A⊆B 且 B⊆A。这是证明集合相等的标准套路——要证两个集合相等，就证互相包含，分两步走。
两条容易栽跟头的细节：空集 ∅ 是任何集合的子集，且空集唯一；∅ 与 {∅} 完全不同，前者没有元素，后者有一个元素（就是 ∅ 本身）。幂集 P(A) = {B | B⊆A}，若 |A| = n，则 |P(A)| = 2ⁿ。
二、并、交、差、补
- 并 A∪B = {x | x∈A ∨ x∈B}
- 交 A∩B = {x | x∈A ∧ x∈B}，若 A∩B = ∅ 称 A 与 B 不相交
- 差 A−B = {x | x∈A ∧ x∉B}，也叫相对补
- 补 ~A = U−A，必须先有全集 U 才有意义
- 对称差 A⊕B = (A−B)∪(B−A)
运算优先级：补 > 交 > 并、差。实际书写仍然建议加括号，理由和第 1 章一样——歧义是失分的头号来源。
三、集合恒等式：一张表和一条对译规则
| 名称 | 恒等式 |
|---|---|
| 幂等律 | A∪A = A，A∩A = A |
| 交换律 | A∪B = B∪A，A∩B = B∩A |
| 结合律 | (A∪B)∪C = A∪(B∪C)，(A∩B)∩C = A∩(B∩C) |
| 分配律 | A∩(B∪C) = (A∩B)∪(A∩C)；A∪(B∩C) = (A∪B)∩(A∪C) |
| 德摩根律 | ~(A∪B) = ~A∩~B；~(A∩B) = ~A∪~B |
| 吸收律 | A∪(A∩B) = A，A∩(A∪B) = A |
| 同一律 | A∪∅ = A，A∩U = A |
| 零律 | A∪U = U，A∩∅ = ∅ |
| 排中律 / 矛盾律 | A∪~A = U，A∩~A = ∅ |
| 差集化归 | A−B = A∩~B |
| 对称差展开 | A⊕B = (A∪B)−(A∩B) |
这张表和逻辑定律表一一对应，对译规则是：
∪ ↔ ∨，∩ ↔ ∧，~ ↔ ¬，U ↔ 1，∅ ↔ 0，⊆ ↔ →
所以德摩根律在两边长得一模一样，分配律也一样。记住对译规则，就不用背两套恒等式。
证明方法有两条。元素法（逻辑等价法）最稳：要证 A−B = A∩~B，就从"x∈A−B"出发，按定义写成 x∈A∧x∉B，再写成 x∈A∧x∈~B，最后写成 x∈A∩~B，每一步都是一次谓词等值替换，收尾说"由 x 的任意性得证"。恒等式代入法更快：从已知恒等式出发做代数变形，但要求每一步都能报出用了哪条定律。
给一个元素法的完整骨架，证 A−(B∪C) = (A−B)∩(A−C)：
x∈A−(B∪C) ⇔ x∈A ∧ x∉(B∪C)
⇔ x∈A ∧ ¬(x∈B ∨ x∈C) 德摩根
⇔ x∈A ∧ x∉B ∧ x∉C 结合
⇔ (x∈A∧x∉B) ∧ (x∈A∧x∉C) 幂等、交换
⇔ x∈(A−B) ∧ x∈(A−C)
⇔ x∈(A−B)∩(A−C)
每一行都能指到一条逻辑定律，这就是"集合恒等式不必背第二遍"的实际含义：你只是在把第 2 章的演算重写了一遍。
四、有序对与笛卡尔积
有序对
笛卡尔积 A×B = {
三条性质要记牢：
- 不满足交换律：A×B 与 B×A 一般不等，除非 A=B 或其中一个是空集。
- 不满足结合律：(A×B)×C 的元素是 <
- 对并、交满足分配律：A×(B∪C) = (A×B)∪(A×C)；A×(B∩C) = (A×B)∩(A×C)；还有 (A×B)∩(C×D) = (A∩C)×(B∩D)。
另外 A×∅ = ∅×A = ∅，因为找不到可配对的第二个分量。
五、二元关系：A×B 的子集
从 A 到 B 的二元关系是 A×B 的任意一个子集，记 R⊆A×B；当 A=B 时称 A 上的关系，R⊆A×A。
三个特殊关系必须认识：
- 空关系 ∅：没有任何元素满足关系。
- 全域关系 E_A = A×A：任意两个元素都满足。
- 恒等关系 I_A = {
一个常考的数字：若 |A| = n，则 A×A 有 n² 个元素，其子集有 2^(n²) 个，所以 A 上共有 2^(n²) 个不同的二元关系。n=3 时是 512 个，n=4 时已经 65536 个——这个增长速度说明"枚举所有关系"不可行，必须靠性质来分类，这正是第 6 章的动机。
顺带补两个记号，第 7、8 章要用：关系 R 的定义域 dom R = {x | 存在 y 使
六、关系的三种表示
以 A = {1,2,3}，R = {<1,1>, <1,2>, <2,3>, <3,1>} 为例：
集合表示：直接列出有序对，最精确，适合元素少的关系。
关系矩阵 M_R：行对应前件、列对应后件，
1 1 0
0 0 1
1 0 0
关系图：每个元素画一个结点，
| 表示 | 优点 | 最适合的用途 |
|---|---|---|
| 集合 | 精确、便于做集合运算 | 小规模关系、严格证明 |
| 矩阵 | 可做布尔运算，机械不易错 | 求复合、求闭包、判定性质 |
| 图 | 结构直观，一眼看出通路 | 判对称、传递，讲哈斯图 |
矩阵中 1 的个数等于关系图中边的条数（自环算一条），行下标与列下标就是元素的编号。这一点在第 7 章会派上用场：布尔乘法的语义正是"走两步能不能到"，矩阵里的一格 1，在图上就是一条边。
易错点
- ∅ 与 {∅} 不是一回事；∅∈{∅} 为真，∅⊆{∅} 也为真，但 ∅≠{∅}。
- A⊆B（包含）与 A∈B（属于）是两种完全不同的关系，前者比较集合，后者比较元素。
- 幂集元素个数是 2ⁿ，不是 n²；A 上关系个数才是 2^(n²)。
- 关系本身就是集合，所以并、交、差、补对关系照样适用，别把它当成另一种对象。
- 关系矩阵是方阵只限于 A 上的关系；从 A 到 B 且 |A|≠|B| 时是长方形矩阵。
这一章在整门课里的位置
本章把第 3、4 章的谓词语言落到具体对象上：A⊆B 就是 ∀x(x∈A→x∈B)，一个带量词的蕴含式。第 6 章用关系矩阵和关系图判定五个性质，第 7 章在同一套矩阵上做布尔乘法求复合与闭包，第 8 章则把满足特定性质组合的关系命名为等价关系与偏序关系。
本文是《离散数学 1：数理逻辑与集合论》第 5 章的知识点摘要。完整板书与例题见 课程页；上一章 谓词等价，下一章 关系的性质。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 离散数学 1：数理逻辑与集合论 14 讲
- 离散数学 2：图论 10 讲