第 1 章 · 集合、关系与函数

离散数学的所有后续内容(逻辑、图、组合)都建立在三个基本概念上:集合、关系、函数。它们听起来像高中复习,但本章给它们装上「严格定义」,因为严格性就是计算机的语言:数据库的关系模型(数据库课第 1 章)、哈希表的键值映射(数据结构课第 7 章),全是这三个概念的工程实体。

1.1 集合:不做定义,只做约定

集合是「一些确定对象的汇集」,元素与顺序、重复无关:{1, 2} = {2, 1} = {1, 1, 2}。表示法两种:枚举 {a, b, c} 与描述 {x | x 是偶数且 x < 10}(「竖线读作『使得』」)。

集合间的基本运算和逻辑运算一一对应(这是第 2 章的伏笔):

集合运算	定义	对应逻辑
交集 A∩B	同时属于	与(and)
并集 A∪B	至少属于一个	或(or)
补集 Ā	不属于	非(not)
差集 A−B	属于 A 不属于 B	与非
子集 A⊆B	A 的元素都是 B 的元素	蕴含

几个必背的恒等式(德摩根律): $\overline`{A \cup B}` = \bar`{A}` \cap \bar`{B}`$ 、「补的并 = 并的补」——它和第 2 章逻辑的「not (a or b) = (not a) and (not b)」是同一条定理的两个马甲。

幂集 P(A) = A 的全部子集构成的集合,n 元集合的幂集有 2ⁿ 个元素(每个元素「在/不在」二选一)。这个 2ⁿ 在计算机里随处可见:位掩码枚举子集、密码学的密钥空间(第 9 章),还有算法课的「指数爆炸」的数学根源(数据结构课第 1 章)。

1.2 笛卡尔积与关系:数据库的原型

笛卡尔积 A×B = 所有配对的集合,|A×B| = |A|·|B|。二元关系 R 就是笛卡尔积的一个子集(数据库课第 2 章「关系 = 笛卡尔积的子集」的原话出处)。「a 与 b 有关系 R」记作 aRb,集合视角就是 (a, b) ∈ R。

关系有几个关键性质(设 R 定义在 A 上):

自反:每个 a 都有 aRa(「≤」是,小于号不是);
对称:aRb 则 bRa(「同学」是,「≤」不是);
传递:aRb 且 bRc 则 aRc(「≤」、小于号、「祖先」都是,「朋友」不是,朋友的朋友不一定是朋友,社交网络的真实痛点)。

等价关系 = 自反 + 对称 + 传递。它把集合划分成互不相交的等价类(同一类里的元素「视为相同」)。计算机里的等价关系比比皆是:整数模 n 同余(第 9 章 RSA 的地基)、大小写不敏感的字符串相等、并查集(数据结构课第 11 章)维护的「连通等价类」。偏序关系 = 自反 + 反对称 + 传递(⊆、整除、任务依赖),它给出「部分可比」的顺序,拓扑排序(数据结构课第 6 章)就是偏序的线性化。

1.3 函数:特殊的、可计算的关系

函数 f: A → B 是「每个 a ∈ A 恰好对应一个 b ∈ B」的关系。按映射的形状分三类:

单射(injective):不同 a 到不同 b(无碰撞);
满射(surjective):每个 b 都被打到(无遗漏);
双射(bijection):又单又满,一一对应。

双射 = 「可逆」= |A| = |B| 的精确表述,它是「编码无歧义」「加密可解密」的数学前提(第 9 章)。哈希函数(数据结构课第 7 章)刻意放弃单射(无限输入空间压进有限桶),冲突处理就是为非单射买的保险。

复合函数 (g∘f)(x) = g(f(x)) 与逆函数 f⁻¹(仅双射有)是后续所有「变换叠加」的代数语言。一个值得记住的事实:|A×A| = n²,而 |A→A 的函数| = nⁿ,|A 上的关系| = 2^(n²) ——关系的数量比函数多得多,这就是「关系」比「函数」更难分析的原因。

1.4 计数第一课:几个经典问题

本章末尾用集合论解三道经典计数题(第 5 章系统展开):

从 n 人选 k 人(无序):C(n,k) = n!/(k!(n-k)!),先算有序排列 P(n,k) 再除以 k! 消序;
鸽巢原理:n+1 只鸽子进 n 个巢,必有一个巢 ≥ 2 只。应用:「任意 13 人中必有两人同月出生」;进阶版(第 9 章):任意 5 个整数中必有 2 个的差是 4 的倍数(按余数分 4 个巢);
容斥原理:|A∪B| = |A| + |B| − |A∩B|(交集被数了两次,减一次)。三个集合、四个集合的展开式同构(每层符号交替)。

常见错误

「⊆」和「∈」混用。{1, 2} ∈ {{1,2}, {3}} 对,但 {1,2} ⊆ {{1,2}, {3}} 错(元素是集合,子集判断要看元素);两层的层次感是集合论第一个坎。
幂集忘了空集。P({a}) = {{}, {a}},空集是任何集合的子集。
传递性想当然。「a 是 b 的朋友、b 是 c 的朋友 → a 是 c 的朋友」不成立;设计社交功能时把关系性质想清楚,是产品 bug 的常见源头。
等价关系三条件漏一。反对称 + 自反 + 传递是偏序;把「对称」和「反对称」记混,第 9 章的同余就推不动。

练习

手算:A = {a, b, c},写出 P(A) 的全部 8 个元素;再验证 |P(A)| = 2³。
手算:定义 A = {1, 2, 3, 4, 5, 6} 上的关系「整除」,列出所有对,判断它是不是偏序(逐条验证三性质)。
动手:用你熟悉的语言写程序枚举 A×B(A、B 各 3 元素)与 A 上所有关系(2⁹ = 512 个),数一数其中等价关系的个数(答案:5 个,想想为什么每个等价关系对应一种划分)。
思考:数据库的一张表(数据库课第 2 章)和「关系」的数学定义有哪些对应?表的主键约束对应关系的什么性质?为什么「表可以有重复行」时数据库课要强调 SQL 是「多重集」而非「集合」语义?