离散数学学到第三章很多人会突然卡住。前两章搞命题、搞逻辑推导还算是“顺着读”就能理解的内容一进第三章满屏集合符号、关系运算、函数性质难度像换了本教材。但我把第三章完整过完再做真题才发现第三章才是整门离散数学的地基后边的图论、树、代数系统全部建立在它的语言上。这篇笔记不是抄教材目录而是我把课堂例题、课后作业和历年卷子揉在一起后的复习版适合正在赶进度、或者准备期末冲刺的读者。为什么说它是分水岭因为这一章引入了三种层层递进的结构集合是离散对象的基本容器关系刻画对象之间的关联函数则是“最听话”的那类关系。三者从定义上就互相咬合一旦第一块没学透后面全塌。这篇文章我就按自己实际复习的顺序来写不追求面面俱到只把最常考的、最容易错的、最值得背的放出来。1. 第三章在整门课里的位置它到底在解决什么问题1.1 离散数学缺不了“一座桥梁”我一开始没搞明白为什么教材要把集合、关系、函数放在第三章而不是直接讲图论。后来做题被虐了几次才想通离散数学研究的对象绝大多数是“离散的、不连续的东西”这些东西要用准确的语言描述就得先有“集合”这个容器要描述两个集合内部元素之间的关系就得有“关系”这个概念而描述两个集合之间确定性的对应规则就得有“函数”。换句话说第三章不是在教三个孤立知识点而是在教一种“描写世界的语法”。你在图论里说的“顶点集合V、边集合E”本质就是集合运算的延伸你在代数系统里说的“二元运算”本质就是定义在集合上的特殊函数。没把这一章过掉后面翻教材基本等于看天书。1.2 一个“装东西”的视角转变在中学里我们习惯把集合当成“一堆元素的汇总”比如一个班的学生、一批整数。但离散数学中更重要的思维方式是把集合当成讨论问题的“论域”。元素不用纠结它是什么你关心的是它属于哪个集合、和别的元素有什么关系。举个例子哪怕是最简单的“子集”概念也会出现一个容易混淆的点空集是任何集合的子集这是对的但空集不一定是一个集合的元素。如果 A{1,2}那么 ∅⊆A 成立但 ∅∈A 不成立。很多题就喜欢拿这种差别做文章把“元素”和“子集”混在同一条选项里。这种视角看起来简单但它决定了你后面能不能看懂“幂集”和“笛卡尔积”。我第一次看到“集合的集合”时也发懵习惯性想把里面的元素全部铺平后来才意识到在集合论里一个元素本身也可以是一个集合。比如 A{1,{2,3}} 中{2,3} 是 A 的一个元素而 2 和 3 并不是 A 的元素。这个区分如果不建立起来幂集题必错。1.3 关系与函数的一张“递进表”为了不让自己在概念堆里迷路我把这一章总结成一张递进关系结构大致定义一句话本质集合满足某种条件的对象整体一个“容器”关系A×B 的一个子集描述哪两个元素有联系函数满足“每输入只给一个输出”的特殊关系确定性的联系规则这三个概念不是并列的而是层层包含关系是一种特殊集合函数是一种特殊关系。理解了这条主线后面所有定理都有了“挂靠点”。考试里经常会问“下列哪个是函数”判断标准只有一个每个定义域中的元素是否恰好对应一个值域元素。这就是把关系变成函数的那道门槛。我这部分复习下来最大的心得是不要急着背定理先把这三层递进关系刻在脑子里。只要你能说清楚“函数是关系、关系是集合的子集”第三章一半的基础就算打通了。2. 集合运算的“符号翻译法”从∈、⊆到∪、∩、−的思维转换2.1 核心符号要能反过来读很多同学看到符号就头疼但我发现只要把符号“翻译成一句话”正确率立刻上来了。比如(x \in A)x在A里面(A \subseteq B)A的每个元素都在B里面(A B)A⊆B 且 B⊆A也就是两边互相包含(A \cup B)至少属于其中一个的所有元素(A \cap B)同时属于两个集合的所有元素(A - B)属于A但不属于B的元素(A \oplus B)对称差属于A和B的并集但不属于它们的交集。你可能会觉得这就是翻译一下而已但考试真正考的是“反着读”。比如题干说“A−B\emptyset”你要立刻反应过来A没有B以外的元素即A⊆B。如果不经过符号翻译这一步直接空想往往要想很久。我在做题时养成一个习惯遇到任何关于集合的表述先在草稿纸上写成包含关系再往下推思路会清晰很多。2.2 笛卡尔积的“乘法思维”集合之间最重要的一种构造是笛卡尔积[ A \times B {(a,b) \mid a \in A, b \in B} ]它的元素是有序对。很多人只记住了基数公式[ |A \times B| |A| \cdot |B| ]却在题目里翻车因为不够注意“有序”。A×B 和 B×A 元素个数一样但内容一般不同只有当 AB 时两者才相等。另一个容易忽略的点是如果 A 或 B 是空集那么 A×B 也是空集。看起来是废话但求子集个数时一不注意就会把 \emptyset × B 当成一个非空集合来算。我在复习时用一个小例子做测试设 (A{1,2})(B{a})那 A×B 有 (1,a)、(2,a) 两个元素它的子集个数就是 (2^24)。如果不先数清元素个数直接用 2 乘以 1 再算子集就很容易走上错误的道路。核心是先确定集合元素是什么再谈基数顺序不能反。2.3 幂集元素自身的“二级集合”幂集的定义不算难[ P(A) {X \mid X \subseteq A} ]也就是说幂集是由A的所有子集组成的集合。容易栽跟头的地方在于计算元素个数时要看子集个数而不是原集合元素个数。比如 A 有 3 个元素它的幂集就有 (2^38) 个元素这8个元素里既包括空集也包括A本身。我自己的记忆技巧是把幂集中的每个元素想象成“是否选中原集合元素”的结果。对A中每个元素只有“选”和“不选”两种状态所以幂集元素总数是 (2^n)。这个思路还能推广到很多计数题比如“含某个固定元素的所有子集有多少个”答案是 (2^{n-1})因为它等价于在剩下 n−1 个元素中任选。这类“固定元素”的题在考试里极其常见掌握了生成逻辑就不需要背变形公式。关于集合运算还有一个日常容易忽略的习惯画文氏图只能辅助理解不能代替证明。考试里如果要求证明 (A\cup(B\cap C)(A\cup B)\cap(A\cup C))最好按“双向包含”来写先任取左边集合的一个元素推出它在右边集合再任取右边集合的元素推出它在左边集合。每次写“任取”的时候对象必须是集合中任意一个元素不能选特殊例子否则就是“以偏概全”。3. 关系运算与关系性质判断套路比死背定义更重要3.1 关系怎么“存放”在集合里关系的定义就是(R \subseteq A \times B)。它本质上是一个由有序对组成的集合。因此在处理关系题时第一件事往往是把R显式写出来而不是拿抽象定义硬套。比如集合 (A{1,2,3}) 上的一个关系“小于或等于”描述为[ R{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)} ]一旦写出来判断自反、对称、传递就变得极其直观。我在做题时最常犯的错误是光看表达式“xRy当且仅当xy是偶数”却不把元素实际列出来结果判断起来非常抽象、容易漏情况。后来我要求自己只要集合规模不大一律先把关系列成有序对或者画成关系图把问题可视化。关系还有两种常见运算。逆关系(R^{-1}{(y,x)\mid(x,y)\in R})就是把有序对的两个分量调换。关系复合(R\circ S) 表示“存在中间元素”的连接写作[ (x,z)\in R\circ S \iff \exists y,\ (x,y)\in S \text{ 且 } (y,z)\in R ]这个方向特别容易记混。我每次做复合都把中间变量 y 用“寻找转发人”的方式来理解x 通过 y 到达 z那么 x 和 z 之间的关系就是“经过一次中转”。先确定中间元素的取值范围再判断是否存在这样一条路径比死记公式稳妥。3.2 四种性质的“行为判据”关系的四种性质几乎是每章必考自反每个元素都和自身有关系即 (\forall x\in A, xRx)。反自反每个元素都不和自身有关系即 (\forall x\in A, \neg(xRx))。对称如果 xRy则 yRx。反对称如果 xRy 且 yRx则 xy。传递如果 xRy 且 yRz则 xRz。这里最坑的是“自反”的定义是“每个元素都必须满足”而不是“有一些元素满足”。集合 A{1,2,3} 上的关系 R{(1,1),(2,2)}如果不考虑3就不能说它自反但如果题目只要求“关系在某个指定集合上”那么必须检查该集合的每一个元素一个都不能漏。我身边很多同学都在这道题上丢分因为习惯了看“有没有”而不是“全都不能少”。对称和反对称也经常被误认为互补关系。实际上一个关系可以既对称又反对称例如恒等关系 (I_A{(x,x)\mid x\in A})也可以既非对称又非反对称比如 R{(1,2),(2,1),(1,3)}它有对称的 (1,2)、(2,1)也有反对称的 (1,1) 和 (1,3)不对(1,3)没有对应的 (3,1)但 (1,1)也算对称还同时满足反对称。所以这里要先搞清楚定义对称要求每一对有来有回反对称要求不同元素之间不能“双向奔赴”。把定义拆成“具体检查哪些有序对”就不容易踩坑。3.3 闭包给关系“补全缺陷”闭包是很多人的弱项其实核心想法很直白在保持原有关系的基础上最少添加多少有序对可以让它变得更“完整”自反闭包给每个元素补上 ((x,x))对称闭包如果已经有 ((x,y))则补上 ((y,x))传递闭包如果存在 xRy、yRz则补上 xRz反复检查直到稳定。我当初老是混淆这三者后来统一成一个观念闭包操作就是“给关系做修复”补上的东西必须是最必要的。例如 R{(1,2),(2,3)}它的传递闭包需要补上 (1,3)同时也要因为补入了(1,3)再检查是否还需要新关系。这个过程说穿了就是不断迭代直到不再产生新有序对为止。考试里如果你遇到“求传递闭包”用小规模集合可以把关系图画出来再逐个路径找从 x 到 z 存在一条有限长路径那么 xRz 就要放进闭包。图论那套“可达性”就是从这里来的。如果只列有序对很容易漏掉经过多步中转的情况。4. 等价关系与偏序关系到底要怎么判定、怎么用4.1 等价关系“物以类聚”的数学版定义很简单满足自反、对称、传递的关系是等价关系。它最大的价值是产生划分一个集合里所有互相等价的元素可以归成一类这些类互不相交并且它们的并集是整个集合。我复习时自己造了一个生活化例子把全班同学看成一个集合定义关系“在同一个讨论小组里”。显然每个同学和自己同组自反如果甲和乙同组那么乙和甲同组对称如果甲和乙同组、乙和丙同组那么甲和丙同组传递。所以这个关系是等价关系它把全班分成几个互不重叠的小组。做题时我总结了一个“三步判定法”先检查自反逐一看集合中每个元素是否有 ((x,x))再检查对称逐个看每个非空有序对是否有反向匹配最后检查传递这一步最麻烦建议用“路径法”把所有一步关系看成有向连线看是否存在两步路径没被一步路径覆盖的情况。如果题目要求“求等价类”本质就是找“互相能通过关系到达的元素组”。把关系图画出来整个连通块就是等价类非常直观。经典题目里让你“写出商集”A/R其实就是把所有等价类作为元素构成一个新的集合。4.2 偏序关系层级结构的骨架偏序关系需要自反、反对称、传递。它描述的是“比较大小、先后顺序”这类结构最常见的是实数上的“≤”。但离散数学里它可以是任意集合上的“包含关系”“整除关系”。我最容易混淆的是“极大元/极小元”和“最大元/最小元”的区别。判定方法记牢一套最大元它和所有元素都可比较并且大于等于所有人自己是唯一的极大元没有别的大于它但可以有不只一个最小元唯一地小于等于所有人极小元没有别的小于它也可以不止一个。举例说在集合 {2,3,5,30} 上定义“整除关系 a|b”30是最大元因为所有元素都能整除302、3、5都是极小元因为没有其他元素能整除它们除了它们本身。用哈斯图画出来之后顶上的是极大元底下的是极小元看图画比硬背定义轻松多了。4.3 判断“传递”时我用的一种笨办法传递性在等价关系和偏序关系里都至关重要也是最容易漏判的。我的笨办法是把所有有序对变成有向图然后检查所有长度为2的路径。如果有 (x \to y) 和 (y \to z)就一定要有 (x \to z)。在纸上做我会把每个元素作为中点分别检查一遍。比如 R{(1,2),(2,3)}找长度为2的路径1→2→3所以必须补 (1,3)。如果题目问“这个关系是否传递”答案就是否因为 (1,3) 不存在。但如果 R{(1,1),(2,2),(3,3)}虽然没有任何长度2的路径但它是传递的因为传递条件“如果存在就满足”是空真成立不需要补任何东西。这个小细节在考试里出现过很多次我每次都会跳进“必须有点对才算传递”的误区。实际上传递性的定义是条件句前件为假时整个句子为真。搞清楚这个逻辑连接词的含义比多刷十道题还有用。5. 函数与映射从“关系”到“规则”的升级5.1 判别函数最容易被题干绕进去函数是特殊关系要求定义域中每个元素有且只有一个像。我一开始看到“所谓函数就是单值关系”这句话没什么感觉直到做了一道判断题问 (R{(1,2),(1,3),(2,4)}) 是不是 (A{1,2}) 到 B 的函数才明白它考的就是“1对应了两个像”所以不是函数。判断函数时要注意三件事定义域是不是整个给定集合不是自然定义域而是题目指定的集合一个输入不能对应多个输出题目中的“值域”未必是满射的定义域对应全部目标集合。第二个坑特别常见题目说 (f: A\to B)但可能只有A里的部分元素有定义例如“平方函数”如果定义域是整数、值域也是整数那么并不是所有元素都映射到整个整数集这就是满射判断的问题了。5.2 单射、满射、双射的证明套路单射假设 (f(x_1)f(x_2))推出 (x_1x_2)。注意要使用“对于任意”的假设不能挑具体数字证明。满射任取值域中一个元素 y找出一个定义域中的 x 使得 f(x)y。这个“找”的过程实际上就是解方程。双射先证单射再证满射。我的经验是证明单射时最容易做反有人从“x1x2”推出“f(x1)f(x2)”这只能说明函数有定义并不能证明单射。必须反过来从像相等推出源点相等。另外否定单射时只需要举一个反例而证明单射需要一般化的代数推导两个方向要分清。有些同学喜欢画箭头图来判断这对有限集合很有用只要每个输入箭头都指向不同输出就是单射每个输出都被至少一个箭头指向就是满射。但到了无限集合比如整数到整数、实数到实数就必须要用代数法了。考试里数列、函数题几乎都靠后者不能只依赖图示。5.3 复合函数和反函数的方向容易搞反复合函数定义[ (f\circ g)(x) f(g(x)) ]先作用内层 g再作用外层 f。这个方向一定要写清楚。我在复习时自己设了一个具体例子g(x)x1f(x)x^2那么[ (f\circ g)(x) (x1)^2 ]但[ (g\circ f)(x) x^21 ]两者不同说明了复合顺序的敏感性。反函数的存在条件是函数必须是双射。这个条件常被忽略我犯过的错误是只考虑了单射而没有考虑满射。例如函数 (f:\mathbb{R}\to\mathbb{R})f(x)x^2它甚至连单射都不是更不可能有反函数。但如果定义域限制为非负实数、值域限制为非负实数就变成了双射反函数是根号函数。所以做题时一定要同时看定义域和值域一个都不能漏。复合函数与反函数结合时还有一个常见套路如果 f 和 g 互为反函数那么 f∘g 和 g∘f 都是恒等函数。这可以用作验证结果是否正确的手段。5.4 函数计数与鸽巢原理的“预感”有限集合之间的函数计数也是常考点设 (|A|m)(|B|n)那么 A 到 B 的函数总数是 (n^m)因为每个元素有 n 种选择选择之间是独立的。单射函数总数是排列数 (n(n-1)\cdots(n-m1))需要 (m\le n)满射函数的总数要用到容斥原理公式看着复杂但思路是总数减去没有覆盖到某个值域元素的函数数量。这部分如果你觉得太难先把“函数总数 (n^m)”记住再理解单射满射的容斥可以先放一放。鸽巢原理虽然常被放在组合数学里但和函数概念关系紧密如果从一个有 m 个元素的集合映射到另一个有 n 个元素的集合且 mn那么一定存在两个输入对应同一个输出也就是这个函数不可能是单射。这个“直觉结论”在第三章的证明题里经常作为理由出现可以提前积累起来。6. 复习收尾我把第三章浓缩成三个检查清单6.1 集合部分先数清元素再谈子集和基数我做集合题前会先问自己三句话题目里的元素到底是“单个对象”还是“一个集合”A×B 里的有序对到底有哪些我能不能完整列出来遇到子集计数时是在给“原集合元素”做选择还是在给“子集元素”做选择这三个问题能拦住大部分粗心错误。尤其是幂集题目最忌讳不看原集合大小就直接套 (2^n)。我每次都会先把原集合元素写在草稿纸上做个标记再数一遍基本不会再错。6.2 关系部分列有序对比空想要可靠一万倍对于任何“判断关系是否满足某种性质”的题我现在都会强制自己把 R 的有序对展开写出来。道理很简单性质判定是逐对检查的过程展开以后一目了然。如果你不想写全至少要把关键反例找出来比如“不满足自反的元素”或“能破坏传递性的两点路径”。等价关系和偏序关系的大题通常还有后续求等价类、划分、哈斯图、极大/极小/最大/最小元。这些内容一旦图画出来就非常直白。我在草稿纸上会先画图再写答案省下了很多反复检查的时间。6.3 函数部分定义域、值域、方向一个都不能漏函数题出错八成出在三个地方忘了函数定义的覆盖范围是整个定义域证明单射时方向和因果关系搞反复合函数内外层写反反函数条件判断漏了满射。我自己会在笔记本每一页顶部写一行提醒“函数是关系函数要单值反函数要双射。”复习到最后一天靠的就是这句话。最后聊点实实在在的学习建议。离散数学第三章并不难但它信息密度高、符号多、性质杂想要考场上反应快唯一捷径就是“把抽象关系具体化”能用集合展开的不用符号硬扛能画关系图的不用文字硬猜。把这套习惯练成本能后面的第四章、第五章学起来会顺很多。我在实际复习中还有一个笨功夫每次做完一道关系题都会自己试着换一个集合重新判断一遍虽然多花几分钟但对性质的理解会扎实非常多。如果你正卡在第三章不妨从今天开始少背定义多列有序对、多画图再去碰真题应该会有完全不一样的感受。