1. 为什么第二章是整个离散数学的分水岭

很多人学离散数学，第一章集合论还能靠直觉硬扛，到了第二章就开始出现明显的两极分化。我观察过身边不少同学，包括我自己当年也一样，第一章作业基本满分，第二章开始作业能对一半就算不错。问题不在于智商，而在于第二章的知识密度突然上了一个台阶——它把集合、逻辑、关系、函数这几块内容拧成了一股绳，任何一环松了，后面全盘皆输。

第二章通常涵盖关系与函数这一核心板块，具体包括二元关系的定义、关系的性质（自反、对称、传递）、关系的运算（复合、逆、闭包）、等价关系与划分、偏序关系与哈斯图，以及函数的定义、单射满射双射、复合函数与反函数。这些概念不是孤立的，它们之间有一条非常清晰的逻辑链：集合定义了"元素"，笛卡尔积定义了"有序对"，关系就是笛卡尔积的子集，而函数是一种特殊的关系。你如果只是零散地背定义，考试时稍微换个问法就懵了。

我写这篇笔记的目的很明确：把第二章从"一堆看不懂的符号"变成"一张能自己画出来的知识地图"。不管你是正在上课需要同步整理，还是期末突击想快速抓住重点，这篇内容都能直接拿来用。我会把每个概念的动机讲清楚——为什么数学家要定义这个东西，它解决什么问题，然后给出可操作的判断方法和我踩过的坑。全文基于我自己的笔记整理习惯和多次复习经验，补充了大量教材上不会明说的细节。

提示：第二章的复习切忌只看不写。关系性质的判断、闭包的计算、哈斯图的画法，这些必须动手练，光看定义等于没学。

2. 二元关系：从"有关系"到"关系矩阵"的思维转换

2.1 关系的本质是笛卡尔积的子集

先把这个最基础的定义说透。设A和B是两个集合，A×B表示所有有序对(a,b)的集合，其中a∈A，b∈B。从A到B的一个二元关系R就是A×B的任意一个子集。如果(a,b)∈R，记作aRb，读作"a与b有关系R"。

这个定义看起来简单，但它完成了一个关键的思维转换：关系不再是模糊的"有联系"，而是一个精确的集合。你可以对关系做集合的一切运算——交、并、差、补。这一点在后面判断关系性质时非常有用。

我当年理解这个定义花了很久，后来用一个类比想通了：把A×B想象成一张表格，行是A的元素，列是B的元素，每个格子对应一个有序对。关系R就是在这张表格上打勾——打勾的格子属于R，没打勾的不属于。这个"打勾表格"就是后面要讲的关系矩阵的雏形。

当A=B时，R称为A上的关系。这是第二章最常考的情形，因为只有A上的关系才能讨论自反性、对称性、传递性这些性质。从A到B的关系和A上的关系，区别一定要分清楚，考试时看错这个前提直接零分。

2.2 关系的三种表示方法及适用场景

关系的表示方法直接决定了你做题的速度和准确率。我总结下来有三种，各有各的适用场景：

集合表示法：直接把所有有序对列出来，比如R={(1,1),(1,2),(2,3)}。优点是精确无歧义，缺点是元素多了写到手软，而且不容易一眼看出性质。

关系矩阵法：设A有m个元素，B有n个元素，矩阵M是m×n的0-1矩阵，M[i][j]=1当且仅当(a_i,b_j)∈R。这个方法的威力在于，关系的复合对应矩阵乘法（布尔运算下），关系的逆对应矩阵转置。我考试时判断传递性经常用矩阵法，因为找"1的传递链"比在集合里翻来翻去快得多。

关系图法：当A=B且元素不太多时，画有向图最直观。每个元素一个节点，aRb就画一条从a到b的有向边。自反性看每个节点有没有自环，对称性看每条边有没有反向边，传递性看有没有"走两步能到但一步到不了"的情况。

注意：考试时如果题目没指定方法，判断性质优先用关系图（快），计算复合优先用矩阵（准），列举元素用集合（稳）。

2.3 五个核心性质的判断口诀与反例构造

关系的五个核心性质——自反、反自反、对称、反对称、传递——是第二章的绝对重点。我把判断方法编成了口诀，配合反例构造技巧，基本不会出错。

自反性：每个元素都要和自己有关系。关系图上每个节点必须有自环；关系矩阵主对角线全为1。反例就是找一个元素没有自环。

反自反性：每个元素都不能和自己有关系。关系图上每个节点都不能有自环；矩阵主对角线全为0。注意自反和反自反不是互补关系——存在既不自反也不反自反的关系，比如有的元素有自环有的没有。

对称性：有a到b的边就必须有b到a的边。矩阵是对称矩阵。反例是找到一条"单向边"。

反对称性：如果a到b有边且b到a有边，那么a必须等于b。换句话说，不同元素之间不能有双向边。这里最容易和对称性搞混——对称性要求"有来有回"，反对称性要求"不同元素之间不能有来有回"。一个关系可以既对称又反对称，比如恒等关系。

传递性：如果有a到b的边和b到c的边，就必须有a到c的边。判断时找"长度为2的路径"，看起点到终点有没有直接边。反例就是找到一条"两步可达但一步不可达"的路径。

我踩过最大的坑是传递性的判断。当年做作业时，看到R={(1,2),(2,3)}就以为它不传递，因为"没有(1,3)"。但实际上，传递性的定义是"若有(1,2)和(2,3)，则必须有(1,3)"——这里确实有(1,2)和(2,3)，所以必须有(1,3)，没有就是不传递。但如果关系是R={(1,2)}，只有一条边，根本凑不出"两步路径"，那它自动满足传递性（前提为假，蕴含式为真）。这个逻辑陷阱坑了无数人。

2.4 关系复合与逆运算的矩阵速算法

关系的复合是第二章的计算重灾区。定义是这样的：设R是从A到B的关系，S是从B到C的关系，复合关系S∘R（注意顺序，有的教材写R∘S）定义为{(a,c) | 存在b∈B使得(a,b)∈R且(b,c)∈S}。

用集合法算复合，就是"搭桥"：找R中终点和S中起点相同的对，把桥两头接起来。但元素一多就容易漏。我的方法是矩阵乘法：把R的矩阵和S的矩阵做布尔乘法（乘法用"与"，加法用"或"），得到的矩阵就是复合关系的矩阵。这个方法机械、不易错，尤其适合考试时元素较多的情况。

逆关系R⁻¹就是把R中每个有序对的两个元素交换位置。矩阵表示下就是转置。关系图上就是把所有边反向。逆关系有一个重要性质：(S∘R)⁻¹ = R⁻¹∘S⁻¹，注意顺序要反过来，这个和矩阵转置的性质(AB)ᵀ=BᵀAᵀ是一致的。

我实测下来，复合运算用矩阵法比集合法快至少一倍，而且检查时可以直接看矩阵有没有算错。唯一需要注意的是布尔运算：1+1=1，不是2。这个在编程实现时也要特别注意。

3. 闭包运算：把关系"补"成想要的样子

3.1 闭包的动机：为什么需要"最小包含"

闭包这个概念，教材上往往直接给定义，不说为什么。我一开始也困惑：为什么要把关系补来补去？后来想明白了——闭包是在"保持原有信息"和"满足特定性质"之间找最小代价的方案。

举个例子：你有一个关系R={(1,2),(2,3)}，它不传递。你想让它传递，最粗暴的方法是加上所有可能的有序对，变成全关系。但这样丢失了原关系的信息。闭包的思想是：只加必须加的元素，能不加就不加。所以传递闭包就是包含R的最小传递关系。

这个"最小"是关键。自反闭包r(R)、对称闭包s(R)、传递闭包t(R)分别定义为包含R的最小自反关系、最小对称关系、最小传递关系。它们都是唯一的，这一点可以证明，但考试不要求，你只需要会算。

3.2 三种闭包的计算公式与手算技巧

三种闭包都有直接的计算公式，我整理如下：

自反闭包：r(R) = R ∪ I_A，其中I_A是A上的恒等关系{(a,a) | a∈A}。说白了就是把主对角线补全。关系图上给每个没有自环的节点加自环。

对称闭包：s(R) = R ∪ R⁻¹。把每条单向边补上反向边。矩阵表示就是M ∪ Mᵀ。

传递闭包：t(R) = R ∪ R² ∪ R³ ∪ ...，其中R²表示R与自身复合。这个公式看起来吓人，但实际手算时，对于有限集合A（|A|=n），只需要算到Rⁿ就够了，因为再往后不会产生新元素。更高效的方法是Warshall算法，用动态规划的思想，时间复杂度O(n³)，手算时按中间节点逐个"中转"。

我手算传递闭包的习惯是：先画关系图，然后找所有"两步路径"，补上直接边；再找"三步路径"，补上直接边；以此类推，直到没有新的边可补。这个方法比套公式直观，而且不容易漏。对于n≤4的情况，基本两三分钟就能搞定。

提示：传递闭包计算时，补上的新边可能又产生新的"两步路径"，所以要反复检查直到稳定。这个迭代过程是新手最容易漏的。

3.3 闭包性质的保持与破坏

闭包运算有一个容易被忽略的细节：做了一种闭包之后，可能破坏另一种性质。比如一个关系R是对称的，你求它的传递闭包t(R)，t(R)不一定还是对称的。反过来，R是传递的，求对称闭包s(R)，s(R)不一定还是传递的。

这个性质在考试中经常以判断题的形式出现，问"传递闭包是否保持对称性"，答案是不一定。反例很好构造：R={(1,2),(2,1)}是对称的，传递闭包需要加上(1,1)和(2,2)，加完之后还是对称的——这个例子不好。换一个：R={(1,2),(2,1),(2,3)}，它是对称的吗？不是，因为(2,3)没有反向边。那换R={(1,2),(2,1)}，传递闭包是{(1,2),(2,1),(1,1),(2,2)}，还是对称的。实际上对于对称关系，传递闭包确实保持对称性，这个可以证明。但对称闭包不一定保持传递性：R={(1,2),(2,3)}是传递的（凑不出两步路径），对称闭包加上(2,1)和(3,2)后，有(3,2)和(2,1)但没有(3,1)，不传递了。

这个细节教材上往往一笔带过，但考试爱考。我的建议是：每次做完闭包，回头检查一下其他性质是否还成立，养成习惯就不会被坑。

4. 等价关系与偏序关系：两种截然不同的"秩序"

4.1 等价关系：把集合切成互不相交的块

等价关系的定义是：同时满足自反、对称、传递的关系。这三个性质合在一起，产生了一个非常漂亮的结果——等价关系可以把集合划分成若干个互不相交的子集，每个子集叫一个等价类。

这个"划分"的概念是等价关系的核心。给定A上的等价关系R，对于每个a∈A，a的等价类[a] = {x∈A | xRa}。所有等价类的集合构成A的一个划分，即：每个元素恰好属于一个等价类，不同等价类不相交，所有等价类的并是A。

我理解这个定理的方法是画图：把等价关系的关系图画出来，你会发现它是一堆"完全图"的并——每个等价类内部的元素两两都有边（包括自环），不同等价类之间没有任何边。这个图像非常清晰，等价关系就是"把元素分成几坨，每坨内部全连接，坨与坨之间不连接"。

考试中常见的题型是：给定一个等价关系，求等价类；或者给定一个划分，求对应的等价关系。后者更简单——划分的每个块内部所有元素两两配对，加上自环，就是等价关系。我考试时遇到求等价类的题，习惯先画关系图，把连通分量找出来，每个连通分量就是一个等价类，又快又准。

4.2 偏序关系：哈斯图的画法与读法

偏序关系是同时满足自反、反对称、传递的关系。和等价关系不同，偏序关系描述的是"层级"或"顺序"，比如"小于等于"、"整除"、"包含"都是偏序关系。

偏序关系的可视化工具是哈斯图。画哈斯图的步骤我总结为"三步走"：

1. 去掉自环：偏序是自反的，每个节点都有自环，但哈斯图省略所有自环。
2. 去掉传递边：如果a到b有边，b到c有边，那么a到c的边是传递产生的，省略。
3. 调整层次：如果a到b有边，把a画在b的下方（或上方，看约定），用无向边连接。

画完之后，哈斯图是一个有层次的图，能一眼看出哪些元素"更小"哪些"更大"。极小元是没有下方邻居的元素，极大元是没有上方邻居的元素。最小元是比所有元素都小的元素（不一定存在），最大元是比所有元素都大的元素（不一定存在）。

我踩过的坑是混淆极小元和最小元。极小元是"没有比它更小的"，但可能有多个极小元互不可比；最小元是"比所有元素都小"，如果有则唯一。比如整除关系下，2和3都是极小元（没有比它们更小的除了1），但2和3互不可比，所以没有最小元（如果集合里只有2和3）。这个区别考试必考。

4.3 等价类与划分的相互推导实战

这部分我用一个具体例子走一遍完整流程，方便你直接套用。

设A={1,2,3,4,5}，R是A上的等价关系，关系矩阵如下（1表示有关系）：

1 2 3 4 5 1 [ 1 1 0 0 0 ] 2 [ 1 1 0 0 0 ] 3 [ 0 0 1 1 1 ] 4 [ 0 0 1 1 1 ] 5 [ 0 0 1 1 1 ]

第一步，观察矩阵，发现1和2互相有关系，3、4、5两两有关系。第二步，验证等价类：[1]={1,2}，[3]={3,4,5}。第三步，检查划分：{1,2}和{3,4,5}不相交，并集是A，符合划分定义。

反过来，如果给你划分{{1,2},{3,4,5}}，求等价关系：块{1,2}内部所有有序对加上自环，得到(1,1),(1,2),(2,1),(2,2)；块{3,4,5}内部所有有序对加上自环，得到9个有序对。合起来就是等价关系。

这个流程我练了大概十道题就完全熟练了，考试时基本是送分题。关键是不要漏掉自环，很多人求等价关系时只写不同元素之间的对，忘了自反性要求的(a,a)。

5. 函数：一种特殊的二元关系

5.1 函数的定义为什么要求"唯一性"

函数f从A到B，是一个满足两个条件的关系：第一，对每个a∈A，存在b∈B使得(a,b)∈f（存在性）；第二，如果(a,b)∈f且(a,c)∈f，则b=c（唯一性）。这两个条件合起来，就是"每个输入恰好有一个输出"。

唯一性这个条件把函数和一般关系区分开了。一般关系允许一个输入对应多个输出，函数不允许。这个限制使得函数具有"可计算"的性质——你给我一个输入，我能确定地告诉你输出是什么。

从关系图上看，函数的关系图有一个特点：每个节点恰好发出一条边。注意是"发出"，不是"接收"。一个节点可以接收多条边（多个输入映射到同一个输出），但不能发出多条边。这个图像判断法比背定义快得多。

我当年理解函数定义时，纠结过"为什么空集也算函数"。从空集到B的函数是空关系，它满足存在性（空集没有元素，不需要验证）和唯一性（没有有序对，不需要验证）。这个在考试中偶尔出现，记住结论就行。

5.2 单射、满射、双射的判定与计数

函数的三个重要性质：单射（入射）、满射、双射（一一对应）。

单射：不同输入对应不同输出。关系图上看，每个节点最多接收一条边。等价说法：f(a)=f(b)蕴含a=b。

满射：每个输出都被至少一个输入对应。关系图上看，B中每个节点至少接收一条边。等价说法：f的值域等于B。

双射：既是单射又是满射。关系图上看，每个节点恰好接收一条边，且A和B的元素个数相等。

计数问题是考试重点：从A到B的函数有多少个？如果|A|=m，|B|=n，每个A中元素有n种选择，所以共有nᵐ个函数。单射有多少个？第一个元素有n种选择，第二个有n-1种，以此类推，共n(n-1)...(n-m+1)个（要求n≥m）。满射的计数用容斥原理，公式是Σ(-1)ᵏC(n,k)(n-k)ᵐ，这个公式建议记住，考试直接套。

我踩过的坑是单射计数时忘了前提n≥m。如果n<m，单射个数为0，因为鸽巢原理——m个输入映射到n个输出，n<m时必然有冲突。这个前提考试时经常隐含，要自己判断。

5.3 复合函数与反函数的可逆条件

复合函数g∘f的定义是(g∘f)(x)=g(f(x))，注意顺序：先f后g。复合函数的性质：如果f和g都是单射，则g∘f是单射；如果都是满射，则g∘f是满射；如果都是双射，则g∘f是双射。反过来不成立——g∘f是单射不能推出g是单射，只能推出f是单射。

反函数存在的条件是f是双射。只有双射才能定义反函数f⁻¹，使得f⁻¹(f(x))=x且f(f⁻¹(y))=y。单射但不满射的函数，可以定义"左逆"；满射但不单射的函数，可以定义"右逆"；只有双射才有真正的双侧逆。

我复习这部分时，把函数和关系的对应关系整理成了一张表，帮助很大：

这张表让我在复习时能把新旧知识串起来，不至于学了函数忘了关系。

6. 我整理第二章笔记的完整方法论

6.1 概念地图：把零散定义串成一张网

第二章的概念多且杂，如果线性地记笔记，复习时容易迷失。我的做法是画概念地图：中心写"二元关系"，向外辐射出"性质"、"运算"、"特殊关系"三大分支。"性质"下面挂五个性质，"运算"下面挂复合、逆、闭包，"特殊关系"下面挂等价关系和偏序关系。每个概念再往下挂定义、判断方法、典型反例。

这张图我画了三遍，第一遍照着书画，第二遍默画，第三遍用自己的话重新组织。画到第三遍时，我发现等价关系和偏序关系的区别其实就是"对称性"——等价关系要求对称，偏序关系要求反对称。这个发现让我一下子把两个概念彻底分清了。

概念地图的好处是全局感。考试时遇到一个题，你能立刻定位它在哪个分支，需要调用哪些知识。比如看到"求传递闭包"，你立刻知道这是"运算"分支下的"闭包"，方法有公式法和Warshall算法，注意事项是迭代到稳定。

6.2 错题归因：我踩过的五个典型坑

我整理了自己在第二章踩过的五个典型坑，每个都附上归因和修正方法：

坑一：传递性判断时忽略"前提为假"的情况。R={(1,2)}是传递的，因为凑不出两步路径。修正：判断传递性时，先找有没有"两步路径"，没有就直接判定传递。

坑二：混淆对称和反对称。对称是"有来有回"，反对称是"不同元素不能有来有回"。修正：用矩阵判断，对称看M=Mᵀ，反对称看M和Mᵀ的逐元素与运算结果只在主对角线非零。

坑三：求等价关系时漏自环。修正：等价关系必须自反，每个元素都要和自己配对。

坑四：哈斯图忘记去掉传递边。修正：画完哈斯图后检查，如果存在a→b→c的路径，就不能有a→c的直接边。

坑五：复合函数顺序搞反。(g∘f)(x)=g(f(x))，先f后g。修正：记口诀"右先左后"，和矩阵乘法一致。

这五个坑我反复练了二十多道题才彻底纠正。建议你也建一个错题本，每道错题写清楚"错因"和"修正方法"，考前只看错题本，效率极高。

6.3 考前自测：十道题检验第二章掌握程度

最后附上我自用的十道自测题，覆盖第二章所有核心考点。如果你能独立做对八道以上，第二章基本没问题：

1. 设A={1,2,3}，R={(1,2),(2,3)}，求r(R)、s(R)、t(R)。
2. 判断R={(1,1),(2,2),(1,2),(2,1)}在{1,2}上是否等价关系。
3. 画出整除关系在{1,2,3,4,6,12}上的哈斯图。
4. 求{1,2,3,4,5}上模3同余关系的等价类。
5. 设f:Z→Z，f(x)=2x，判断单射、满射、双射。
6. 设f:Z→Z，f(x)=x+1，求f⁻¹。
7. 计算从{1,2,3}到{a,b}的单射个数。
8. 判断R={(1,2),(2,1),(1,1),(2,2)}是否传递。
9. 设R是等价关系，[1]={1,2}，[3]={3,4}，写出R的所有有序对。
10. 证明：若R是对称的且传递的，则R是自反的吗？（答案：不一定，反例R=∅）

这十道题我考前刷了三遍，第一遍错四道，第二遍错一道，第三遍全对。刷题的目的不是背答案，而是暴露知识盲区。每错一道，就回到概念地图上定位对应的知识点，重新理解一遍。

提示：第10题是经典陷阱题。对称+传递推不出自反，因为空关系是对称且传递的，但不自反。这个反例一定要记住。

第二章的笔记整理到这里就完整了。我的体会是，离散数学第二章不是靠"看懂"就能掌握的，必须动手画图、算闭包、写证明。概念地图帮你建立全局观，错题本帮你堵住漏洞，自测题帮你检验成果。这三样东西配合起来，第二章从"分水岭"变成"送分章"只是时间问题。