离散数学（本）复习题：分块突破与三遍刷题法

离散数学本这套复习题我前前后后陪人过了三轮从最开始自己也被主析取范式的下标绕得头晕到后来能一眼看出某个关系到底是不是等价关系中间踩过的坑足够写满两大本草稿纸。这门课有个很鲜明的特点概念密、符号多、计算题和证明题几乎各占一半但章节之间的耦合度出奇地低——集合论没学透照样不影响你把图论那几道大题做对。这个特性对复习来说反而是天大的好事它意味着你可以用分块推进、逐点突破的方式去啃完全不必担心前面一塌糊涂就导致后面全盘崩掉。下面这份东西是我把自己整理这套复习题的完整流程、每类题型的通用解法、以及那些教材上不会写但考场上一定会绊你一脚的细节一次性摊开讲清楚。不管你是第一次接触这门课还是补考二刷都能从里面挑到能直接上手用的东西。1. 拿到复习题先别做花两小时摸清这套题的出题底盘1.1 五个板块的分值权重与投入产出比绝大多数人拿到复习题的第一反应是从第一题开始往下做做到第三题卡住翻书翻到一半发现看不懂符号定义又回头去看第一章一天下来进度条停在集合的表示方法。这种推进方式在离散数学上极其低效因为这门课的章节难度分布非常不均匀。按我这几轮的实际感受整套复习题大致可以切成五块集合论与二元关系、数理逻辑、图论、代数系统、组合计数。这五块里集合论与关系、数理逻辑、图论这三块加起来通常能占到七成以上的分值而且它们的题型高度固定属于练熟了就能稳定拿分的类型。代数系统排在后面不是因为不重要而是它的题目形式相对收敛往往是判断某个代数系统是不是群、求子群的阶、判断是不是格套路性很强投入时间少但回报不低。组合计数则是最容易出偏题的地方题目变体多同一道题换个问法思路就完全不同性价比最差。我一般建议的复习顺序是先关系、再逻辑、再图论、再代数、最后组合。理由很实在——关系那一章的符号系统是后面好几章的基础谓词逻辑里的关系概念、图论里的邻接矩阵本质都是二元关系的另一种说法。先把关系的语言练顺后面几章读起来会顺畅很多。1.2 本字背后的考试定位决定你该练到什么深度很多人忽略了这个括号里的本字。它其实在告诉你两件事一是这门课的定位是本科层次的公共基础课二是它的考查重点会和计算机专业、数学专业本科阶段的全日制课程有明显区别。区别在哪全日制课程里离散数学经常承担着为后续数据结构、编译原理、算法课打地基的功能所以证明题会挖得很深比如要求你严格用数学归纳法证明某个递归定义的良基性、或者证明某类格是同态像。而复习题这一类课程考查重心会明显往概念辨析、标准计算、套路化证明这三块倾斜。说人话就是你更需要练的是把标准题型做对做快而不是想出别人想不到的证明。这个判断对你的复习策略影响很大。我见过太多人拿着一本厚厚的参考书花两周时间死磕那些难度很高的证明结果考试里压根没出而真正反复考的求主析取范式判断欧拉图这类题反而因为练得不够而丢分。复习题里出现频率高的题型就是你的主战场别跑偏。1.3 复习题和真题的关系把它当题型字典而不是考试预测复习题最容易被误用的一点是把它当成考试题目的预演。实际上它更像一本字典——它的价值在于覆盖题型而不是预测具体题目。所以你对待每一道复习题的态度应该是问自己这道题背后是哪一类题型换一组数据我还能做出来吗如果只是把答案抄了一遍、把数字换一下就算完那这套题基本白刷。我习惯的做法是每做完一道题在旁边用一句话写清这题的题型标签比如关系闭包的传递闭包计算——用矩阵幂法。做完一整章把这些标签收集起来你就得到了属于自己的一份题型地图比任何教辅目录都精准。提示复习题里那些看起来很简单、答案只有两行的题目往往才是真正的高频考点。复杂的证明题可能是老师为了凑齐知识点硬塞进去的简单的计算题才是反复出现的主力。2. 复习题的三遍刷法从看得懂到考场能做对2.1 第一遍只求认得题型允许自己翻书第一遍的目标非常低——不是做对而是认出这道题在考什么。这个过程允许你翻书、查定义、看例题甚至可以看完题干直接去翻答案看思路然后合上答案自己再写一遍。为什么第一遍要这么没出息因为离散数学最大的障碍从来不是计算难度而是符号语言不通。同一个概念教材里叫关系的复合另一本书叫关系的合成题目里可能只写一个圆圈符号同一个东西谓词逻辑里叫个体域集合论里叫论域图论里叫顶点集。第一遍的任务就是把这些说法在你的脑子里打通形成一张同义词表。这一遍花的时间通常占整个复习周期的四成左右看起来很长但它把后面两遍的阻力降到了最低。我自己的经验是第一遍如果硬撑着不翻书效率会低三到四倍而且极易产生挫败感直接弃坑。2.2 第二遍闭卷限时暴露真实水平第一遍过完隔两天再开始第二遍这次必须闭卷、限时。限时这一点特别重要因为它会暴露一个第一遍完全看不出来的问题你会做但做得太慢。离散数学的计算量不小尤其是主析取范式、传递闭包、哈夫曼树这类题步骤多、符号多稍不留神就要写满半页纸。如果不在平时就练出速度考场上很容易出现最后两道大题会做但没时间写的情况。我在这一遍里给每类题设了大致的时间上限比如一道求主析取范式的题控制在八分钟以内一道图论的判定题控制在五分钟以内超时就标记出来说明这个题型我还没练到条件反射的程度。2.3 第三遍只做错题建一份自己的错题索引表第三遍不要重头再刷一遍那样纯属浪费时间。做法是把前两遍里所有做错、超时、蒙对的题挑出来只做这些。数量通常只占全部题目的两到三成但价值密度极高。做错题的时候还有个技巧就是不要只改答案要写下错误的根源。我见过的高频错误原因其实就那么几类定义记混了、把充分条件和必要条件用反了、矩阵乘法顺序搞错了、量词否定时忘了变号。把这些原因单独抄在一个本子上考前半小时翻一遍比重新做十道题管用得多。下面这张表是我自己整理的第二遍时间记录模板你可以直接照着用题型建议用时我的实际用时是否超时错因分类求主析取范式3变元8分钟判断关系性质4分钟求传递闭包6分钟图的可达性/连通判定5分钟欧拉图/哈密顿图判定5分钟群与子群判定6分钟哈夫曼树构造与WPL8分钟谓词逻辑推理证明10分钟3. 集合论与二元关系分值最稳、最容易练成条件反射的一块3.1 集合运算与幂集先把元素个数这件事算明白集合论部分的题目看着零碎其实核心就围绕三件事转运算、元素计数、幂集。运算那部分要熟到不用想并、交、差、补、对称差。尤其是对称差很多人只记得公式不记得它的实际含义——A⊕B 就是恰好在 A 或恰好在 B 里的那些元素也就是并集减去交集。这个理解一旦建立涉及对称差的证明题就基本不会做错。元素计数这块幂集元素个数是必考题一个含 n 个元素的集合其幂集有 2 的 n 次方个元素。这个结论的来源很简单——构造子集时每个元素都有选和不选两种状态n 个元素就是 2 的 n 次方种组合。理解了这个推导就不会再出现忘了是 2 的 n 次方还是 n 的 2 次方这种低级错误。三集合的容斥原理也是高频考点公式是|A ∪ B ∪ C| |A| |B| |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| |A ∩ B ∩ C|记忆的窍门是奇加偶减——交叠个数为奇数的一律相加为偶数的一律相减。我见过有人死记硬背这个公式一遇到四集合的题就彻底懵但掌握了奇加偶减这个规律之后n 个集合的容斥公式其实是可以自己写出来的。注意容斥原理的题目里最容易出错的地方不是公式而是分类不重不漏。做完之后一定要回头检查一遍各个类别加起来是否恰好等于全集这一步能拦下大部分错误。3.2 关系性质判定一张表解决全部五问关系这一章的重头戏是五种性质的判定自反、反自反、对称、反对称、传递。这五问几乎每套复习题里都会出现而且经常是给一个具体的关系让你从五个角度分别判断。我的做法是同时看关系矩阵和关系图两套工具互相印证。下面这张表是我用了好几轮的速查表建议直接背下来性质关系图特征关系矩阵特征自反每个顶点都有自环主对角线元素全为 1反自反每个顶点都没有自环主对角线元素全为 0对称任意一条有向边都有反向边矩阵关于主对角线对称反对称任意两个不同顶点间至多一条边与转置矩阵的非对角位置不同时取 1传递任意两条首尾相接的边闭合边也存在布尔平方后不超过原矩阵这里要说一个反复被人问到的点自反和反自反不是一对反义词。存在既不自反也不反自反的关系也存在既是自反又是反自反的关系——但后者只在空集上成立因为空集上没有任何元素需要检查两个定义都被空洞地满足了。这个细节在判断题里经常出现属于典型的看你会不会较真的考点。还有一个易混点是对称和反对称。反对称不是反对对称它在允许自环这一点上和对称完全一致。准确的说法是反对称关系里任意两个不同元素之间不允许互相都有关系但自己和自己有关系是完全合法的。我一般跟人说把反对称理解成上下级关系就好——不能两个人同时是对方的下级。3.3 三种闭包和两类特殊关系等价与偏序闭包题是关系这一章的另一个重头考的是自反闭包、对称闭包、传递闭包。前两个非常简单自反闭包就是在原关系上补上所有 (a, a)对称闭包就是把所有反向对也加进去。真正需要练的是传递闭包。传递闭包有两种求法各有适用场景第一种是矩阵幂法。理论依据是传递闭包等于 R 的一次幂到 n 次幂n 是集合元素个数的并。实际操作时用布尔矩阵乘法逐次求平方再累加一直算到某一次的结果不再变化为止。这个方法稳但计算量大。第二种是沃舍尔算法。它通过 n 轮扫描每轮拿一个顶点当中转站更新所有顶点对之间的可达性。算法描述起来绕但实际上手比矩阵幂法快不少尤其是元素个数大于四个的时候优势明显。我的建议是两个方法都练一遍考试时选自己顺手的那一个。然后是两种最重要的特殊关系等价关系和偏序关系。等价关系的定义是自反、对称、传递三条同时满足。它最有意思的地方在于等价关系和集合的划分是一一对应的——给定一个等价关系它的所有等价类构成一个划分反过来给定一个划分把同一块里的元素两两配对就得到一个等价关系。这个一一对应关系几乎年年考常见问法是求由某等价关系诱导的划分或者反过来。偏序关系则是自反、反对称、传递三条同时满足。偏序题的核心工具是哈斯图画法有三条规矩去掉所有自环去掉所有因传递性而多余的边然后调整位置让箭头都朝上所以哈斯图不画箭头。哈斯图画对了后面求最大元、最小元、极大元、极小元、上界、下界、上确界、下确界这一整套概念就都好办了。这里有个概念特别容易搞混最大元和极大元不是一回事。最大元要求它和集合里所有元素都可比且都排在前面极大元只要求没有比它更大的元素就行。在一个菱形偏序集里可以有两个极大元但最多只能有一个最大元。做题时先找极大元集合再在那个集合里看是不是所有人都能互相比——只有这一个判定步骤走对了才不会把两个概念混用。4. 数理逻辑符号化、范式、推理证明三板斧4.1 命题符号化题目里的每个且都不一定真的是且命题逻辑的入门题是符号化看起来简单实际是丢分重灾区。原因在于自然语言里那些连接词和逻辑连接词并不是一一对应的。举几个典型的坑只要 p就 q这是p → q不是 q → p。 只有 p才 q这是q → p方向反过来。 除非 p否则 q这是¬p → q等价地写成 ¬q → p。 p 当且仅当 q这是等值联结词p ↔ q。 p 或者 q在逻辑里默认是相容或至少一个成立不是二选一。这些映射关系没有捷径只能靠练。我的建议是准备一个小本子专门抄这类句式每遇到一个新的表达方式就记下来。抄到二十条左右你会发现自然语言里翻来覆去也就那么几种说法。4.2 主析取范式和主合取范式掌握编号规则就够了这是整门课里最标准化、最套路化、也最值得优先练熟的题型。只要掌握编号规则任何一道题都能按固定流程做完。先说极小项。对于 n 个命题变元极小项是恰好包含 n 个文字每个变元出现一次或本身或否定的合取式一共有 2 的 n 次方个。编号规则是把变元按字母顺序固定下来极小项里变元本身出现记 1、否定出现记 0得到一串二进制数转成十进制就是这个极小项的编号 m。举个具体的例子三个变元 p、q、r极小项 p ∧ ¬q ∧ r按 p、q、r 的顺序取值是 1、0、1二进制 101十进制是 5所以这个极小项记作 m₅。极大项的规则刚好相反极大项是包含 n 个文字的析取式变元本身出现记 0、否定出现记 1。同样的三个变元极大项 ¬p ∨ q ∨ ¬r按规则取值是 1、0、1二进制 101记作 M₅。这里有一个非常好用的性质m 的下标和 M 的下标相同但两者互为否定也就是 ¬mᵢ 等价于 Mᵢ。知道这一点很多题目可以少算一半。求主析取范式的标准流程是先用等价变换把公式化成一般的析取范式然后检查每个合取项是否包含了全部变元缺哪个变元就补上 (A ∨ ¬A) 再用分配律展开最后按编号从小到大排序、合并相同的极小项。主合取范式的流程对称只是最后用的是极大项。我实测下来一道三变元的主析取范式题熟练之后能在六到八分钟内做完。如果你现在要花二十分钟那就是典型的知道方法但没练熟回去把复习题里这一类题连着做五道速度立刻上来。提示主析取范式和主合取范式之间还有一个换算捷径——所有使公式取真值的极小项构成主析取范式剩下的使公式取假值的极小项对应的极大项构成主合取范式。如果你已经求出了主析取范式主合取范式就能直接读出来不用重新算。4.3 谓词逻辑与推理证明量词否定是命门谓词逻辑部分复习题里出现最多的两类题是量词否定和推理证明。量词否定的两条基本规则必须背到条件反射¬∀x P(x) 等价于 ∃x ¬P(x) ¬∃x P(x) 等价于 ∀x ¬P(x)说人话就是否定号穿过量词时全称变存在、存在变全称同时把否定号塞给后面的谓词。这个操作在多层量词嵌套时要逐层进行一层一层剥千万别跳步。需要特别注意的是全称量词对合取可以分配对析取不能。∀x (P(x) ∧ Q(x)) 等价于 ∀x P(x) ∧ ∀x Q(x)这个成立但 ∀x (P(x) ∨ Q(x)) 和 ∀x P(x) ∨ ∀x Q(x) 是不等价的。存在量词反过来对析取可以分配对合取不行。这一对不对称性几乎每次都会在判断题或选择题里露脸。推理证明部分核心是把推理规则用熟。常用的就那么几条假言推理从 A 和 A → B 推出 B、拒取式从 A → B 和 ¬B 推出 ¬A、析取三段论、假言三段论、构造性二难。证明题写的时候我习惯在每一步后面标注用了哪条规则和哪几行比如 由 (1)(3) 假言推理这样即使最后结论错了中间的推理步骤也能拿到部分分数。5. 图论从握手定理到哈夫曼树全是套路5.1 基本概念与握手定理奇度顶点必为偶数个图论开篇的必考点是握手定理图中所有顶点的度数之和等于边数的两倍。Σd(v) 2m这条定理看起来简单但它的推论非常好用——任何图中度数为奇数的顶点个数一定是偶数。这个推论经常被用来做证明题和反证题比如证明不存在一个有 5 个顶点、每个顶点度数都是 3 的图直接用这条推论一秒出结果5 个奇度顶点是奇数个不可能。还有个常用的边界条件要记住n 个顶点的简单图无自环、无重边最多有 n(n−1)/2 条边取到这个上界的图叫完全图 Kₙ。这个数值在做最多多少条边类题目时是标准答案。5.2 欧拉图、哈密顿图、二部图三种判定别混在一起这三种图的判定条件是复习题里的常客但它们的性质完全不同混在一起记特别容易出错。我用一张表把它们彻底分开图类型判定条件判定难度欧拉回路连通且所有顶点度数均为偶数有充分必要条件判定简单欧拉路径连通且恰好有两个奇度顶点有充分必要条件判定简单哈密顿回路无简单的充分必要条件只能靠充分条件或构造二部图不存在长度为奇数的回路有充分必要条件判定简单这张表里最需要强调的是哈密顿图那一栏。欧拉图、二部图都有干净利落的充要条件判定起来是机械操作但哈密顿图至今没有简单的充要条件考试里只会考两件事一是用充分条件判断一定是比如著名的狄拉克定理——n 个顶点n ≥ 3的简单图中如果每个顶点的度数都不小于 n/2那它一定有哈密顿回路二是给你一个具体图让你实际找出那条回路。所以看到判断下列图是否为哈密顿图这种题如果图很小直接动手找回路反而更快如果图很大那就看看能不能套用度数充分条件。千万别试图去背什么判别公式那个东西不存在。5.3 树、最小生成树与哈夫曼树计算题的主力树是图论里结构最简单但考得最多的一类。关于树有四个等价定义记住其中一个就行n 个顶点的无向图是树当且仅当它连通且有 n−1 条边。等价地也可以说连通且无回路或者无回路且任意加一条边就产生回路。最小生成树部分两种算法都要会克鲁斯卡尔算法是每次挑权值最小的边只要不形成回路就加进去一直加到有 n−1 条边普里姆算法是从一个顶点出发每次把连接已在树中的点和不在树中的点的最小边加进来。两种算法结果一样但适用场景不同——边稀疏的时候克鲁斯卡尔更快边稠密的时候普里姆更省事。考试里通常只需要用其中一种我一般用克鲁斯卡尔因为按边排序的过程不容易出错。哈夫曼树的构造是另一个高频计算题流程很固定把所有权值放进一个集合每次取出两个最小的合并成新结点新结点的权值是两个子权值之和再放回集合重复直到只剩一个结点。构造完成后带权路径长度 WPL就是所有叶子结点的权值乘以它到根的路径长度层数之和。这里有个特别容易错的地方同一组权值可能构造出形状不同的哈夫曼树但它们的 WPL 一定相同。所以如果题目只要求算 WPL你不用纠结树形是否唯一如果题目给了具体的左右分支要求比如规定左小右大那就要严格按规则来。6. 代数系统判断、判定、找反例6.1 运算性质与代数系统层级先理清结构关系代数系统这一章的好处是层层递进、体系清晰。整个结构大致是这样一条链广群只要求封闭→ 半群封闭 结合律→ 独异点半群 有幺元→ 群独异点 每个元素有逆元这条链上每加一个条件系统的性质就强一层。做题时最常见的问法是判断给定的代数系统是不是群。这时候你就按这条链逐条检查先看封闭性再看结合律再看有没有幺元最后看每个元素有没有逆元。任何一环不满足直接给出反例即可。注意检查结合律时只要找到一个反例这个系统就不是半群了。所以题目里那些运算表特别小只有两三个元素的往往就是让你找反例的。反例要写得具体明确写出是哪三个元素、左边算出来是什么、右边算出来是什么两个结果不相等。光写不满足结合律是拿不到分的。6.2 群与子群的判定套路一条判定定理搞定群的部分除了上面的四条检查还有几个必记的性质群中幺元唯一、每个元素的逆元唯一、满足消去律若 ax ay则 x y。还有一条经常考的计算性质(ab) 的逆等于 b 的逆乘以 a 的逆顺序要反过来。这个和矩阵求逆的规律是一致的记的时候可以联系起来。子群判定是重点。教材上给的条件通常是非空子集 对运算封闭 对求逆封闭但实际做题时更省事的是那条等价判定H 是 G 的非空子集且对任意 a、b 属于 H都有 a 乘 b 的逆属于 H则 H 是 G 的子群。这个条件把封闭性和逆元一次性打包检查了步骤少、出错率低。还有一个绕不开的定理是拉格朗日定理有限群的子群的阶一定整除这个群的阶。它的用途非常直白——如果某个子群的阶不能整除群的阶那它一定不是子群一句话就判完了。反过来知道阶之后也常常能直接推出子群的可能阶数缩小枚举范围。6.3 格与布尔代数从偏序出发的另一种结构格的定义是从偏序集延伸出来的如果偏序集中任意两个元素都有上确界和下确界它就构成一个格。这里的上确界在两个元素的场景下就是最小上界下确界就是最大下界。判断一个偏序集是不是格最笨但最可靠的做法是画哈斯图然后把每一对元素都过一遍看它们有没有共同的上界且存在最小的那个有没有共同的下界且存在最大的那个。哈斯图上如果某一对元素有两个互不可比的极小上界那它就不是格——这是找反例的标准手法。在格的基础上再加分配律和有补性就得到了布尔代数。布尔代数这一块在复习题里通常只考基本判断和一些简单的等价变换难度不高。有一个小技巧布尔代数中的运算规律和集合论里并、交、补的规律是完全平行的所以如果你集合论学得不错这边的公式可以一一对应地搬过来用能省下不少记忆成本。7. 常见问题与排查技巧实录7.1 高频错误速查表下面这张表是我从自己和身边人的错题里归纳出来的考前翻一遍能拦下不少冤枉分症状真实原因对策主析取范式编号总出错变元顺序没固定死动笔前先写下按 p、q、r 顺序关系性质判断反复改只看矩阵没看图两套工具同时画互相验证传递闭包算不完用了无穷幂或者漏了上限记住只需算到 n 次幂n 是元素个数蕴含方向写反只有除非没区分单独整理句式对照本量词否定漏变号否定号只穿透了一层逐层剥剥一层检查一次握手定理算错漏数了自环的度数贡献自环对度数的贡献是 2哈夫曼 WPL 算错把内部结点也算进去了只有叶子结点参与 WPL 计算群判定找不到反例检查顺序不对按封闭、结合、幺元、逆元顺序逐条来7.2 考场时间分配与检查顺序最后说一下考场上怎么安排。我建议的顺序是先扫一遍全卷把题型在心里过一遍然后从最有把握的题型开始做不要按题号顺序硬推。理由是这样离散数学的题目之间基本独立先做熟的能快速积累信心并且锁定分数同时给后面难题留出充裕时间。如果你按顺序做前三道恰好都是难题半小时过去只做完两道心态很容易崩。时间分配上我的经验是计算题每道控制在八分钟以内证明题最多十二分钟超过就跳过做标记。全部做完之后剩下来的时间优先检查三类题涉及符号方向的蕴含、量词否定、涉及计数的容斥、WPL、边数以及所有画了图的题哈斯图有没有漏边、关系图有没有漏自环。这三类是错误最集中的地方。还有个细节值得单独提一句符号书写一定要规范。离散数学里符号形状相近的太多了——蕴含符号和等值符号、合取和析取、全称量词和存在量词、子集符号和属于符号手写的时候稍一潦草阅卷的时候就可能被判错。我自己的习惯是在草稿纸上也写得清清楚楚别等到誊写的时候才认真因为誊写时抄错符号的情况一点都不少见。我个人在这门课上最大的体会是离散数学的复习从来不是看懂多少的问题而是动手多少的问题。看教材的时候觉得每一步都理所当然一合上书自己写就到处卡壳这个落差只有靠实际动笔才能填平。复习题里每一道题的解题过程哪怕你觉得再简单也建议完整写一遍——包括那些你认为一眼就能看出来的判断题。写到第三遍的时候你会发现真正难的不是理解而是把理解稳定地转化成卷面上的正确书写。