期末复习离散数学最让人头疼的不是某个知识点有多难而是知识点太多、太散学了后面忘了前面等合上书本一回想满脑子只剩下学过但记不清了。如果你是第一次面对这门课或者用的是《离散数学及其应用第8版》Rosen那本和屈婉玲《离散数学第三版》这两本主流教材里的任意一本我这份笔记就是按照期末考的出题习惯把必考的主干知识点压缩成一份可以直接拿来背、拿来练的精华版。它覆盖数理逻辑、集合论中的基数和幂集、关系与函数、图论、代数系统和布尔代数这几大板块每个板块都给了具体的题型套路和易错点适合考前两周到一个月做系统梳理时对照使用。1. 先整体把握考试权重离散数学的知识地图与复习主线离散数学严格来说不是一门课而是一组课的合集。数理逻辑讲的是怎么推理集合论讲的是什么是对象关系与函数讲的是对象之间怎么联系图论讲的是联系形成的网络结构代数系统讲的是抽象运算的规律。很多学校的培养方案还会塞进计数原理、树、布尔代数等衍生内容导致期末复习时根本不知道从哪儿下手。我自己的复习习惯是先把教材目录翻一遍画一张自己的知识主线图。Rosen的第8版目录大致是逻辑与证明、集合/函数/序列、算法、数论、归纳与递归、计数、离散概率、关系、图、树、布尔代数、计算模型知识铺得很广例题也丰富计算机专业用得最多。屈婉玲的第三版则走的是国内数学系的经典体系数理逻辑、集合论、代数系统、图论四篇逻辑更严密理论推导多。两本教材侧重点不同但期末考的核心考点高度重合无非就是下面这几块。期末试卷的考点占比我根据自己看过的多套期末题大致统计过你可以拿来做复习权重参考知识模块典型占分比例常考题型数理逻辑20%-25%真值表、等值演算、范式、推理证明集合论含基数、幂集15%-20%集合运算、幂集、等势判断关系与函数20%-25%关系性质、闭包、等价类、偏序与哈斯图图论含树20%-30%握手定理、欧拉图、最短路、最小生成树代数系统与格10%-15%群的判定、子群、格与布尔代数从这张表能看出图论和关系这两块的比重几乎占了半壁江山而它们恰好都依赖前面集合论的基础。所以复习主线我建议按逻辑 → 集合 → 关系/函数 → 图论 → 代数的顺序走千万别跳着复习。关系是集合上的有序对集合图是关系的可视化表达代数系统的运算对象还是集合。前面哪一块松了后面做题都会卡壳。2. 数理逻辑的三种考法真值表、等值演算与推理证明数理逻辑是整门课的起点也是很多人觉得简单但其实容易丢分的地方。它的题目类型非常固定基本逃不出三种真值表与范式、等值演算、推理证明。2.1 命题逻辑从真值表到主范式真值表的题属于纯送分题但有两个地方容易错一是变量多的时候漏行n个命题变元应该有2^n行写的时候按二进制顺序000、001、010这样列就不会漏二是蕴含联结词p→q的真值只有真前提推出假结论这一种情况为假其余全是真也就是假命题可以蕴含任何命题这个反直觉的点几乎是每届学生的丢分重灾区。等值演算的核心是熟记两组常用等值式第一组是德摩根律¬(p∧q) ⇔ ¬p∨¬q¬(p∨q) ⇔ ¬p∧¬q第二组是蕴含的转化p→q ⇔ ¬p∨q ⇔ ¬q→¬p逆否命题。期末考里经常要求把公式化成主析取范式或主合取范式套路其实就四步先用蕴含等值式消掉→再用德摩根律把否定号往内层推推到命题变元前面接着用分配律展开成析取范式或合取范式最后补全缺少的变元。比如公式m→p的析取范式展开如果m和p只是两个变元那m→p ⇔ ¬m∨p本身就已经是析取范式但写成主析取范式时要补全¬m∧(p∨¬p) ∨ p∧(m∨¬m)再分配展开成四项其中重复项合并。这个补变元的操作是很多同学卡住的地方你要理解它本质上是在用x ⇔ x∧(y∨¬y)这样的恒等替换逻辑上完全等价。2.2 谓词逻辑量词翻译与嵌套否定谓词逻辑的题目通常是翻译题把自然语言翻成带量词的公式或者反过来解释公式含义。翻译题最大的坑在量词顺序。∀x∃y表示对每一个x都能找到一个y强调的是y可以依赖x的选择∃y∀x表示存在一个固定的y它对所有x都成立性质完全不同。比如每个学生都有教材应该翻译成∀x(学生(x)→∃y(教材(y)∧拥有(x,y)))如果把括号位置放错变成∀x学生(x)→∃y教材(y)含义就变成只要有人是学生世上有教材完全错了。量词否定的规则也必须滚瓜烂熟¬∀xP(x) ⇔ ∃x¬P(x)¬∃xP(x) ⇔ ∀x¬P(x)。一句话概括就是否定一个全称量词把它变成存在量词同时否定后面的谓词。做题时如果遇到不存在……或并非所有……这样的自然语言第一步永远是先把否定号放到量词内层。2.3 推理证明三大规则与构造性两难推理证明题是逻辑部分最拉分的因为策略性最强。期末能用到的高频推理规则其实就这几条假言推理p→qp推出q、拒取式p→q¬q推出¬p、析取三段论p∨q¬p推出q、假言三段论p→qq→r推出p→r。其中拒取式是最容易被忽略的很多同学只会正着用假言推理遇到已知p→q和¬q就不知道下一步怎么办了。拿到一道推理证明题我一般这样安排证明思路先看结论是什么倒推结论成立需要什么条件再看前提给了什么从前提正推验证中间缺的环节能不能用等值式补上。常用的构造性两难p→qr→sp∨r推出q∨s在期末题里也出现过多次它本质上是分情况讨论的形式化写法如果你发现题目给了两个蕴含和一个析取多半要往这个规则上靠。3. 集合论的送分与拉分点都在基数与幂集集合论板块里普通集合运算交、并、差、补属于送分题认真画个文氏图就能做对。真正能拉开分差的是基数和幂集因为这块的概念比较抽象尤其是遇到无限集合时很多直觉会失效。3.1 幂集为什么是2的n次方幂集的定义很直接集合A的所有子集构成的集合记作P(A)也叫2^A。比如A{a,b,c}A的幂集就是{∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}一共8个元素而|A|382^3。为什么恰好是2的n次方你可以把每个子集看成一种选择方案对于A里的每一个元素它在子集里只有两种状态——选进去或者不选。3个元素就是2×2×28种组合。这和二进制编码是一个道理n位二进制数能表示2^n个不同的数每一位对应一个元素的取舍。期末如果考求某个集合的幂集你只要先把集合的元素个数数清楚套2^|A|就能确定数量再按元素个数从少到多列出来就行。这里有个细节我每次都会提醒学生空集∅的幂集不是∅而是{∅}它的基数是1。空集是任何集合的子集所以∅一定属于任何集合的幂集包括空集自己的幂集。这个点几乎每年都有人错。3.2 无限集合的基数可数无穷与不可数无穷有限集合的基数就是元素个数这个好理解。但期末题一旦涉及无限集合就要用到等势的概念两个集合A和B等势记作A≈B意思是存在一个从A到B的双射。双射就是既单射又满射也就是说两个集合的元素能一一对应起来。自然数集N、整数集Z、有理数集Q的基数是一样的都是可数无穷记号是ℵ₀阿列夫零。有理数看起来比自然数多得多因为它们稠密地分布在数轴上但康托尔证明了有理数是可以像排队一样一个个列出来的所以它与自然数等势。这个结论反直觉但你要记住它。实数集R的基数则是不可数无穷记作ℵ或c严格大于ℵ₀。康托尔用对角线论证证明了这一点把(0,1)区间里的实数排成一列总可以构造一个新数它的小数点后第n位和第n个数不同这个新数就不在原来的列表里所以实数是无法全部列出的。期末常考的一道证明题是证明(0,1)与R等势最常见的做法是把函数f(x)tan(πx - π/2)用在(0,1)到R上构造双射它的定义域正好是(0,1)值域是全体实数而且严格单调所以是双射。这类题的套路就是构造一个双射函数你只要选一个单调函数把区间映射到合适的范围就行比如指数函数e^x能把R映射到(0,∞)再加一个线性平移就能映射到(0,1)。3.3 集合作答中的常见扣分细节集合部分虽然基础但分数不好拿全。我自己批改作业时发现高频扣分点集中在三处第一元素与子集的符号混用。a∈{a}是属于{a}⊆{a}是包含于但a⊆{a}就是错的。考试碰到这种判断要格外小心。第二笛卡尔积的基数算错。|A×B||A|×|B|是对的但A×B的元素是有序对(a,b)和B×A不同除非A和B相同。基数相等不等于集合相等这个区分很重要。第三差集和补集的边界条件。A-B{x | x∈A且x∉B}如果题目没给全集U你只能用差集不能用补集符号因为补集是相对于全集的全集不确定补集就没意义。4. 关系与函数闭包、等价类、哈斯图的固定解法关系这一章是期末考试里最程序化的章节几乎每个知识点都有固定操作流程学会了就是稳稳拿分。4.1 关系性质判定别被对称和反对称绕晕集合A上的关系R有五个基本性质自反、反自反、对称、反对称、传递。判定方法可以用关系矩阵辅助主对角线全为1是自反全为0是反自反矩阵对称是关系对称传递最麻烦要逐个检查。最容易绕晕的是对称和反对称不是互斥的。一个关系可以既对称又反对称比如相等关系{(1,1),(2,2)}它对称因为(a,b)在关系里时(b,a)也在ab嘛它反对称因为(a,b)和(b,a)同时在时一定有ab。一个关系也可以既不对称也不反对称比如{(1,2),(2,3)}。所以做题时不要把不是对称直接当成是反对称这是概念理解的第一个坎。传递性的判断也有技巧。你不要每次都傻傻穷举而是用中间人思维关系里有(1,2)和(2,3)就必须有(1,3)只要有一组搭桥关系的终点没被接上传递性就不成立。4.2 三种闭包定义法直接算与Warshall算法闭包的题目分为两类一类是求自反闭包或对称闭包另一类是求传递闭包。自反闭包最简单r(R)R∪I_AI_A是A上的恒等关系即把所有主对角线位置补上1。对称闭包也简单s(R)R∪R⁻¹R⁻¹是把所有有序对的顺序反过来即关系矩阵的转置把对应位置对称地补上1。传递闭包t(R)则复杂一些定义上是R∪R²∪R³∪…一直并下去。对有限集合这个并集到某个有限步就停止了因为关系最多有n²个有序对。期末手算小规模关系时你完全可以一步一步合成先算R²即关系R和R的复合存在中间元素k使得(a,k)∈R且(k,b)∈R再算R³直到结果不再增大。但这个方法在n4以上的矩阵里就很痛苦了这时候用Warshall算法。Warshall算法的思路是逐步允许更大的中间结点集合。算法维护一个布尔矩阵W初始等于R的关系矩阵。然后最外层循环k从1到nn为集合元素个数内层两重循环遍历矩阵所有位置(i,j)执行W[i][j] W[i][j] ∨ (W[i][k] ∧ W[k][j])。这行的含义是从i到j是否可达要么原来就可达要么能经过中间结点k到达。三层循环结束后W就是传递闭包。我记得当年第一次看这个算法觉得像魔法后来理解了逐渐放宽中间结点限制这个思路就通了它能保证不会漏掉任何间接路径。4.3 等价关系与集合划分的对应等价关系是自反对称传递的关系它把一个集合划分成若干个互不相交的等价类。给定等价关系R和元素aa的等价类定义为[a]{x∈A | (a,x)∈R}所有等价类组成的集合叫商集记作A/R。期末典型题是A{1,2,3,4,5,6}定义关系R为模3同余即(a,b)∈R当且仅当a≡b(mod 3)。那么1、4属于同一个等价类2、5属于一个3、6属于一个商集是{{1,4},{2,5},{3,6}}。更常考的是反过来给你一个划分让你写出对应的等价关系那只要把划分里属于同一块的元素全部两两配对就可以。还要记住一个核心定理集合A上的等价关系与A的划分一一对应。这个定理的价值在于期末题会把求等价类和求划分当成同一个知识点反复考你只要抓住等价类互不相交、并起来是全集这两条性质就不会乱。4.4 偏序关系的哈斯图画法四步走偏序关系是自反反对称传递的关系。题目一般要求画出哈斯图并求出极大元、极小元、最大元、最小元。哈斯图的画法可以总结成四步第一步把关系图中所有自环指向自己的箭头去掉因为偏序必然自反画了没信息量第二步去掉由传递性能够推出的边比如有(a,b)和(b,c)就不用画(a,c)第三步把元素按偏序关系分层摆放关系的方向统一朝上第四步去掉箭头默认方向从下到上。举个例子如果A{1,2,3,6,9}关系是整除那么1在最下面2和3在中间6和9在顶部6被2整除、被3整除所以从2和3各有一条边指向69只被3整除所以只有一条边这张图一眼就能看出极大元是6和9没有元素比它们大极小元是1最大元不存在6和9互不整除最小元是1。4.5 函数的单射、满射与双射判断函数部分在期末通常考两类题一类是判断一个关系是否为函数另一类是判断单射、满射、双射。判断是否为函数只需验证两点定义域中每个元素都必须有像不能有元素漏掉每个定义域元素只能对应一个像不能一对多。从关系矩阵看就是每一行恰好有一个1。单射入射要求不同的定义域元素对应不同的值域元素即如果f(a)f(b)则ab满射要求值域中的每个元素都有原像。双射就是既单射又满射它直接和前面基数章节的等势呼应两个有限集合等势当且仅当存在它们之间的双射这个连接点在期末复习时一定要主动打通。5. 图论是期末重头戏握手定理、欧拉图与最短路图论在期末卷子里占比最大、题型最丰富但好消息是它套路特别明显。这一章值得多花点时间。5.1 握手定理的两个应用场景握手定理是图论第一个必考定理无向图G中所有顶点的度数之和等于边数的2倍即Σdeg(v)2|E|。它还有个推论奇数度顶点的个数一定是偶数。它的应用场景非常明确。第一类是已知一些顶点的度数和边数求未知顶点个数。第二类是判断一个非负整数序列是否可图化如果序列的和是奇数直接判死因为握手定理要求度数和是偶数如果和是偶数再检查最大度数是否超过顶点数减1。比如序列(4,3,3,2,2)度和为14是偶数5个顶点最大度4不超过4所以它是可图化的。要注意可图化不一定能画成简单图如果要进一步判断可简单图化要跑Havel-Hakimi算法把度数降序排列删掉第一个度数d把后面d个度数各减1重复直到出现负数不可行或全部为0可行。5.2 欧拉通路与哈密顿通路的判定差异欧拉问题问的是能不能一笔画答案有非常干净的充要条件无向连通图存在欧拉通路的充要条件是奇度顶点个数为0或2其中0对应欧拉回路起点终点相同2对应欧拉通路起点终点分别是那两个奇度顶点。这个条件是基于每条边恰好经过一次的遍历性质推导出来的经过一个顶点一次要消耗两条边一条进一条出只有起点和终点可以例外。哈密顿问题问的是能不能一次经过所有顶点这个问题没有简单的充要条件所以期末考试一般只考必要条件或充分条件。必要条件是删去S个顶点后剩下的连通分支数不能超过|S|即ω(G-S)≤|S|。这个条件常用来证明某个图不是哈密顿图只要找到某个顶点集合让不等式不成立就行。充分条件常用Dirac定理n≥3且每个顶点的度数至少为n/2时图必是哈密顿图。注意这个条件是充分不必要别反过来用。5.3 图的可达性与邻接矩阵图的矩阵表示有两类邻接矩阵和关联矩阵。邻接矩阵的幂有一个非常有用的性质A^k中第i行第j列的元素等于从vi到vj长度为k的路径条数。这里路径允许重复经过顶点和边。期末如果考从i到j有多少条长度不超过k的路径你只要把A、A²、…、A^k对应位置的元素加起来就行。这个知识点其实和前面Warshall算法求传递闭包是同一枚硬币的两面Warshall本质上是把邻接矩阵转成可达性矩阵只不过用了更高效的动态规划而直接算矩阵幂是更朴素的方法。5.4 最短路的Dijkstra算法手算模板Dijkstra算法是期末必考的一道计算题占分不小。它的思想是贪心维护一个已确定最短路的顶点集合S每次从未确定的顶点中选出dist值最小的加入S然后用它去更新邻居的dist值一直重复到目标顶点被加入S。手算时我推荐用标记法不容易乱。比如求从a到其他各点的最短路初始时dist(a)0其余dist∞。第一轮选a更新a的邻居第二轮在未确定点里找dist最小者把它确定再用它更新邻居如此反复。每次更新时如果发现经b到x比原来到x更短就把dist(x)改掉。期末常考的是一个带权无向图让你写各轮迭代的dist变化表你只要按选点-更新两步循环就能拿满分。注意Dijkstra要求边权非负如果题目里出现负权边这个方法就不能用不过期末基本不会考负权的情况。5.5 树与最小生成树Kruskal算法的贪心思维树章节的考点很集中树的等价定义连通且无回路、n个顶点n-1条边、任意两个顶点间有唯一简单路径这三个条件可以互相推出、生成树、最小生成树。最小生成树的Kruskal算法步骤非常容易记忆把所有边按权值从小到大排序然后一条条看如果这条边连接的两个顶点不在同一个连通分量里就选它否则跳过直到选出n-1条边为止。这个算法的正确性在于贪心选择性质权值最小的边一定属于某棵最小生成树因为如果它不在把加入它形成的环里的一条更重的边换掉总权值不会变大。Prim算法是另一种思路从一个点开始每次都选连接已在树中的点和不在树中的点的权值最小边加入。两相比较稀疏图用Kruskal方便稠密图用Prim方便期末手算时哪个简单用哪个。6. 代数系统与布尔代数群、格的概念辨析代数系统是很多同学的薄弱项因为它太抽象。但期末考得其实不深核心就是判断一个代数系统是不是群和判断一个偏序集是不是格。6.1 判断是不是群的五步检查法给定一个非空集合G和一个二元运算*判断(G,)是否为群按顺序检查五条封闭性任意a,b∈G都有ab∈G、结合律(ab)ca(bc)、单位元存在e∈G使aeeaa、逆元对每个a存在a使a*aa*ae。比如整数集Z关于加法构成群封闭性显然结合律成立单位元是0每个整数a的逆元是-a。但Z关于乘法不构成群虽然封闭、结合、有单位元1但除了1和-1以外的整数都没有整数逆元所以不是群。这个例子期末特别爱考你要能完整写出哪一步不满足。还有一个高频考点是运算表凯莱表判断如果运算表每一行每一列都是集合元素的排列说明这个有限代数系统有单位元且每个元素有逆元。剩下只需验证结合律而结合律在运算表上没有特别高效的检查方法规模小的时候直接暴力验证。6.2 子群判定与循环群判定子群时不需要把所有群的约束重新验证一遍只用一条判定定理设(G,)是群H是G的非空子集如果对任意a,b∈H都有ab⁻¹∈H则(H,*)是G的子群。这条定理把封闭单位元逆元压缩成一个条件使用频率很高。循环群是由一个元素生成的群即G{a^n | n∈Z}。比如整数加群Z就是由1生成的循环群。期末考循环群时常见题目是求某个群的所有生成元或者求子群。这个知识点考的学校不一样建议根据自己老师的PPT确认是否重点。6.3 格与布尔代数期末考得不多但概念要清楚格的定义是偏序集(L,≤)中任意两个元素a,b都有最小上界上确界和最大下界下确界记作a∨b和a∧b。注意任意两个元素这个条件如果只要求一部分元素有界就不是格。集合的幂集P(A)关于包含关系是最经典的格两个子集的最小上界是它们的并集最大下界是它们的交集。幂集格还额外满足分配律、有补律所以它构成布尔代数——布尔代数就是有补分配格。这个结论把前面集合论的幂集和代数系统的格联系起来了出题人很喜欢借此考跨章节综合题问P(A)关于交、并、补运算构成什么代数系统答案就是布尔代数。期末如果考布尔代数一般只考概念辨析或运算性质对偶原理把∧换成∨、0换成1定理仍然成立、德摩根律、吸收律。吸收律a∨(a∧b)a在化简布尔表达式时特别有用很多人化简卡住就是因为没想起来它。7. 考前两周冲刺易错点清单与刷题顺序到了考前两周我不建议再啃教材正文了直接进入刷题纠错模式效率最高。7.1 高频易错点清单这些是我在阅卷和答疑里见到的送命题你可以一条条自查易错点错误表现正确理解蕴含关系的真值认为假前提蕴含任何命题是错的p为假时p→q为真德摩根律用反¬(p∧q)写成¬p∧¬q否定号分配后∧和∨互换空集的幂集写成∅幂集是{∅}基数为1对称与反对称关系认为是互补关系可以同时成立也可以同时不成立欧拉图和哈密顿图把判定条件混用前者看度数后者看顶点遍历和连通分支群的单位元忘记验证唯一性单位元必须对任意元素都满足Warshall算法循环顺序把内层循环写成先i后j外层必须是k即中间顶点的循环7.2 刷题顺序与错题本用法我给学生的建议是先做课后题中带星号的题目再做往年真题最后回归错题本。课后题覆盖的知识点全但难度偏低适合第一轮用来唤醒记忆。往年真题的价值在于感受出题风格和难度特别是证明题的给分点在哪里。错题本不要抄整道题只记那个让你卡壳的关键坎比如原来这里要先用逆否命题转化原来等价类的并集要覆盖全集。期末复习的错题本越薄越好考前最后一天看的就是这一两页纸。7.3 我个人的考前巩固小技巧最后分享一个我当年复习离散数学时特别管用的办法用一张A4纸不看课本凭记忆把整门课的知识体系画出来。画不出来或者画错的地方就是你最薄弱的地方当天晚上重点补。这个办法听起来简单但做起来比刷三套题都见效因为它逼着你的大脑主动检索而不是被动看答案。第二天早上再快速扫一遍这张纸稳定感比什么都重要。如果你现在正被期末考试搞得焦头烂额不妨从这张知识地图开始先花一晚上把框架搭起来再按这份笔记的模块逐一填充细节你会发现离散数学其实比想象中有规律得多。