离散数学(本)复习题这门课很多人第一次翻开教材的反应是这也能叫数学——满篇的命题、谓词、关系矩阵、哈斯图定义一套接一套定理一抓一大把看起来像文科背诵真做起来又处处是逻辑推理。我带过几轮复习也自己把教材从头到尾啃过三遍最深的体会是离散数学(本)复习题不能当成背多分的科目来对待它更像是一套需要反复动手演算的手艺活。你光看别人怎么推导自己上手照样卡壳但只要你把题型归类、把每一步的动机想清楚这门课的性价比其实高得离谱。这篇文章我打算按知识地图—分模块拆解—考前节奏的顺序把离散数学(本)复习题里最常考、最容易丢分的地方挨个讲一遍。不管你是第一次接触还是已经挂过一次准备二战下面这些内容都能直接拿去对照练习。1. 先把离散数学(本)复习题的知识地图铺开考什么、几分、先做哪块很多人复习离散数学最大的问题是平均用力从第一页开始逐字看看到图论已经没时间了代数结构直接放弃。这种打法在时间充裕时没问题但在只有两三周的情况下基本等于自废武功。正确做法是先摸清地图再决定火力往哪里集中。1.1 这门课的五条主线各自管什么离散数学(本)的内容看着散其实骨架非常清晰就五块集合论与关系集合运算、幂集、二元关系的性质、等价关系与偏序关系、函数的单射满射。这块是后面所有内容的地基关系矩阵、等价类这些概念在图论和代数里都会反复出现。数理逻辑命题逻辑的真值表、等价演算、范式、推理证明再加上谓词逻辑的符号化和量词推理。这是最独立的一块学好了能单独拿分。图论度数、握手定理、欧拉图、哈密顿图、树与生成树、最短路和最小生成树。这块画图量大动手能力要求高。代数结构代数系统的运算性质、半群、群、子群、格、布尔代数。抽象度最高是很多人直接放弃的部分。组合与递推排列组合、容斥原理、鸽笼原理、递推关系的建立与求解。1.2 用题型反推复习顺序复习顺序不该按教材目录走而该按拿分效率排。下面这张表是我根据常见考卷结构整理的投入建议具体分值你还是要对照自己手里的考纲和历年卷子调整。模块典型题型拿分难度建议投入占比数理逻辑求真值表、化主范式、符号化、推理证明低25%集合与关系求幂集、判关系性质、画哈斯图、求等价类低20%图论度数计算、判欧拉/哈密顿、求生成树、最短路中25%组合与递推计数、列递推式、解递推方程中15%代数结构判群、求子群、格与布尔代数高15%这张表想说明的核心意思是数理逻辑和集合关系这两块是基本盘必须拿稳代数结构抽象度最高但考的题型反而很套路把固定动作练熟就能拿分千万不要因为看不懂就直接跳过。我自己第二次复习时就是先花两天把逻辑和集合过完心里立刻踏实了一半。2. 命题逻辑与谓词逻辑最容易看着会、做就错的一章逻辑这一章的特点是定义你都懂例题你也看得明白但一到自己写就各种小错。原因不是你不会而是你没把操作流程固定下来。逻辑题的每一步其实都是机械动作把它写成流水线错误率会断崖式下降。2.1 从真值表到主范式把流程固定成五步命题逻辑里最能拿分的就是求主析取范式和主合取范式。我的固定流程是这样的数清命题变元个数比如三个变元真值表就有八行。按二进制顺序列出所有赋值组合从 000 排到 111这样不会漏行。逐个计算原公式的值得到一个 0/1 的结果列。主析取范式取结果为 1 的那些行每一行写成一个极小项变元取 1 写它本身取 0 写它的否定项内用合取连接项间用析取连接。主合取范式取结果为 0 的那些行每一行写成一个极大项变元取 0 写它本身取 1 写它的否定项内用析取连接项间用合取连接。这里最容易翻车的是第 4、5 步里取 0 写否定、取 1 写本身的记忆。我给学生编过一个顺口的话小项取真大项取假——意思是求极小项时盯住成真行求极大项时盯住成假行而且两者的变元写法正好相反别记混。另外含三个变元的极小项一共八个记法就是 m0 到 m7极大项 M0 到 M7编码顺序就是二进制转十进制的那个数。2.2 谓词符号化的三个高频翻车点谓词逻辑的符号化题几乎每年都出而且只要错一个量词或联结词整题零分。下面三个坑我见过无数次全称量词配蕴含存在量词配合取。所有 S 都是 P写成 ∀x(S(x) → P(x))而不是 ∀x(S(x) ∧ P(x))有的 S 是 P写成 ∃x(S(x) ∧ P(x))而不是 ∃x(S(x) → P(x))。为什么要这样你代入一个不是 S 的个体试一下就知道如果用 ∀ 配合取那个非 S 的个体就会让整个命题为假而现实中所有 S 都是 P并不要求非 S 的个体满足什么。量词的辖域要写清楚。多个量词连着出现时顺序不能随便换。∀x∃y 和 ∃y∀x 的含义完全不同前者是对每个 x 都能找到一个对应的 y后者是存在一个 y 对所有 x 都管用。否定量词的等价变形。¬∀x P(x) 等价于 ∃x ¬P(x)¬∃x P(x) 等价于 ∀x ¬P(x)。求否定时先把量词翻过去再否定里面的谓词这个动作要练到条件反射。2.3 推理证明题的书写规范与踩分点推理证明题扣分往往不是因为推理错了而是因为过程写得不合规矩。评分通常看两点用的推理规则对不对、有没有写出前提和结论。我建议按下面这个格式写逐行编号左边写序号中间写公式右边用括号注明前提引入假言推理拒取式附加化简等规则名。需要额外假设时用附加前提或条件证明法把假设写清楚最后归到结论。常见的规则就那么几个假言推理P→Q 且 P 得 Q、拒取式P→Q 且 ¬Q 得 ¬P、析取三段论、附加、化简、合取。把这几个名字和形式背熟写推理时直接往上套。提示推理题里如果卡住先看看结论的形式。结论是蕴含式就用条件证明法把前件当前提结论是否定式就想想能不能用拒取式。方向上先定再往前倒推要找什么比从前提硬推到结论快得多。3. 集合、关系与函数把定义抠到字缝里集合论这部分看似最简单却是明明会做但还是错的重灾区。原因在于这类题考验的是你对定义的精确记忆差一个字答案就完全不同。3.1 关系五大性质的矩阵判定法关系性质的判断用关系矩阵比一个个列举有序对快得多。设集合有 n 个元素关系矩阵是 n 阶 0/1 矩阵性质矩阵特征自反主对角线全为 1反自反主对角线全为 0对称矩阵关于主对角线对称反对称主对角线外任意对称位置不同时为 1传递各元素在 M²布尔乘法中为 1 的位置在 M 中也必须为 1这里有两个观念要特别强调。第一反自反和不自反不是一回事考试里经常用这种措辞来设陷阱你要看清楚题干问的到底是哪一个。第二对称和反对称并不互斥一个关系完全可以既对称又反对称最典型的就是恒等关系——它对称也反对称。判断传递性时用矩阵平方比较稳妥手算集合比较小时也可以用若有 a 到 b、b 到 c就检查有没有 a 到 c这个逐条排查法。3.2 等价关系、划分与偏序哈斯图等价关系是自反 对称 传递三合一。求出等价关系之后题目通常会让你求各个元素的等价类或者求商集。做这类题的关键是先找出所有互相等价的元素把它们归成一组每组就是一个等价类所有等价类的集合就是商集。等价关系、商集、划分这三者是一一对应的考卷上经常在三种表述之间来回翻译练熟一种就能推其他两种。偏序关系是自反 反对称 传递画哈斯图的步骤要稳定先删掉所有自环再删掉所有能通过传递性推出来的边最后把剩下的边画成下层在下、上层在上的层级图。画完之后极大元是那些上面没有元素盖住它的点最大元必须唯一且盖住所有点极小元和最小元同理。注意最大元一定唯一但极大元可以不唯一上界和下界的范围是整个偏序集里的元素而上确界和下确界是最小的上界和最大的下界。这几个词每年都在考必须分清。3.3 复合关系与闭包的计算套路复合关系 R∘S 的定义方向特别容易记反。我的记法是**先右后左隧道接龙**算 R∘S 时先在 S 里走一步再从到达的点在 R 里走一步能接上就连成一个有序对。求逆关系就是把每个有序对前后调换写成矩阵就是把矩阵转置。至于自反闭包、对称闭包、传递闭包都有对应的固定操作自反闭包就是补上所有 (a, a)对称闭包就是把不对称的有序对补齐传递闭包用 Warshall 算法逐点扩展或者小规模时直接用不断接龙直到不再出现新对的办法。4. 图论部分画图能力决定你的做题速度图论是离散数学(本)里最手感化的一块。定理其实不多但你画图快不快、握手定理用得熟不熟直接决定你在这一块能省下多少时间。4.1 握手定理与度数列可图化的两步判断握手定理是整个图论里使用频率最高的工具所有顶点的度数之和等于边数的两倍即 Σdeg(v) 2m。它衍生出一个必考结论——任何图中奇度顶点的个数一定是偶数。这条结论是很多判断题的标准答案来源看到存在一个度数列为 3,3,1这种奇度个数为三的直接判不可图。判断一个度数列能不能构成简单图可图化我一般分两步先看度数和是不是偶数、最大度是否小于等于 n-1这两条是必要条件再用 Havel-Hakimi 方法逐步验证——每次都拿度数最大的点让它和后面对应数量的点各连一条边后面这些点的度数都减一然后删掉这个点重复操作如果过程中出现负数就说明不可图化。这个方法听着绕实际做两遍就顺了。4.2 欧拉图与哈密顿图一个能判、一个难判这两类图的差别用一个生活类比最好记欧拉图是每条路都走一遍哈密顿图是每个城市都逛一遍。欧拉回路存在的充要条件是图连通且所有顶点度数都是偶数。欧拉通路存在的充要条件是图连通且恰好有两个奇度顶点这两个顶点就是起点和终点。哈密顿图没有简洁的充要条件这是它最坑的地方。考卷上一般只让你用充分条件判断比如 Dirac 定理对 n 个顶点的简单图若 n 大于等于 3 且每个顶点的度数都大于等于 n/2则它一定是哈密顿图。反过来不满足这个条件不代表不是哈密顿图这两者别搞反。4.3 生成树与最短路径的手算流程最小生成数有两大经典算法两者都要会手算Kruskal 算法避圈法把所有边按权值从小到大排队依次取边只要不构成回路就留下直到凑够 n-1 条边。适合边比较少的图。Prim 算法加点法从一个顶点出发每次从已选点集到未选点集的所有边里挑权值最小的那条把新顶点拉进来重复到所有点都在树里。适合点比较少、边比较密的图。最短路径题一般考 Dijkstra 算法。手算时做一个表格行是每一步列是各顶点当前的最短距离估计值每轮选一个还没确定的最小值顶点标定再用它去松弛邻居的距离。这个表看着繁琐但只要按部就班列几乎不会错。5. 代数结构部分群、环、域、格与布尔代数怎么记才不混代数结构是很多人直接放弃的部分但它其实是全卷最套路化的一块。概念虽然抽象但题型非常固定把判定流程背下来就能得分。5.1 用运算表快速判断代数系统的性质代数系统说的是一个集合加上一个或几个运算。判断这个系统的性质最直接的工具就是运算表也叫做乘法表。封闭性表里所有结果都落在原集合里。交换律运算表关于主对角线对称。结合律要对所有三元组逐个验算比较繁琐但考试里的运算通常只要求你验几个特殊情况。单位元表里存在一行和一个元素使这行的排列和表头顺序完全一致左单位元同时存在一列同样规律右单位元两者重合处就是单位元。零元存在一行一个元素让整行都等于该元素左零元类似地找右零元。逆元每个元素都能在表里找到与它相乘等于单位元的搭档。这套判定方法的好处是把抽象的性质变成了看表的动作不用在脑子里反复推演。5.2 群与子群的判定题固定动作群的定义是一个代数系统满足封闭、结合律、有单位元、每个元素都有逆元。判定题就是把上面四条逐一验证写清楚每条为什么成立。子群判定有三条常用定理做选择题时非常省事判定一子集非空且对运算封闭、对求逆封闭。判定二子集非空且对任意两个元素 a、ba 与 b 的逆的运算结果仍在该子集内。判定三子群非空且元素个数有限只需验证对运算封闭。另外要记住循环群和生成元的概念如果一个群里的所有元素都能写成某个元素的幂这个群就是循环群那个元素就是生成元。有限循环群的性质很整齐考卷上经常用它来出计算题。5.3 格、布尔代数与命题逻辑的对应关系格是在偏序集里定义的任意两个元素都有上确界并和下确界交。有界格、有补格、分配格逐层加条件同时满足有界、有补、分配的格就是布尔代数。这里有个非常漂亮的知识连接点——集合代数、命题逻辑、布尔代数这三套系统在结构上是同构的。集合的并交补对应命题的析取合取否定也对应布尔代数里的加乘补。你学集合运算时记住的那些运算律分配律、德摩根律、吸收律换个皮就出现在布尔代数里。抓住这个对应关系代数结构这一章的记忆量能直接砍掉一大半。6. 组合计数与递推关系公式背了不会用怎么办组合这一章的痛点不在于不会公式而在于看了题目不知道套哪个公式。解决办法是按模型归类而不是按公式归类。6.1 排列组合的几类典型模型我一般把常见的计数模型整理成下面这张对照表做题时先判断属于哪一类再动手模型特征处理思路无重复排列n 个不同元素取 r 个排序直接用排列数公式无重复组合n 个不同元素取 r 个不排序直接用组合数公式可重复排列每个位置有 n 种选法共 r 个位置n 的 r 次方分组分配把元素分到不同的组注意组是否有编号、是否允许空组相邻问题某些元素必须挨在一起把相邻元素捆成一块再排不相邻问题某些元素必须彼此分开先排其他元素再插空其中插空法和捆绑法是考卷里的常客判断标志很明确看到相邻就用捆绑看到不相邻就用插空。这两种思路比硬列所有情况快得多也不容易漏。6.2 递推关系的建立与求解递推题分两步先根据题意建立递推关系再解出通项。建立递推关系的诀窍是看最后一步发生了什么。比如经典的台阶问题最后一步要么跨一级要么跨两级那么走 n 级的方案数 a(n) 就等于 a(n-1) 加 a(n-2)这就是一个二阶线性递推。汉诺塔问题则是看最大的那个盘子的移动次数得到 a(n) 2a(n-1) 1。求解时常系数线性齐次递推关系用特征方程写出特征方程比如二阶的写成 r² c1·r c2 的形式。解出特征根。两个不同实根就用两个指数项的线性组合出现重根时第二项要乘上 n。把初始条件代进去解出常数。非齐次的情形把通解拆成齐次通解 一个特解特解的形式跟非齐次项的样子对应。这套流程练熟之后递推题基本是送分题。6.3 容斥与鸽笼原理容斥原理用来处理至少满足一个条件的计数核心是两个集合加一次减一次交集三个集合加单减双加三交集以此类推。用韦恩图辅助理解最直观。鸽笼原理是证明存在性的利器n1 只鸽子放进 n 个笼子至少有一个笼子装了两只以上。它的推广形式是m 个物体放进 n 个盒子至少有一个盒子装了不小于 m/n 上取整个物体。考试里这类题往往藏在应用题里比如证明任意 n1 个整数中必有两个之差是 n 的倍数看到证明存在这四个字第一反应就该想鸽笼。7. 复习节奏与考场策略把会做的分全部拿到手知识点都过了一遍之后真正拉开分差的是时间管理和答题顺序。离散数学(本)的题量不小很多人不是不会而是没做完。7.1 考前十四天的冲刺安排我按两周的节奏整理了一个计划表可以根据自己的基础按比例缩放时间段主要任务目标第 1 到 3 天过逻辑与集合关系做课后题恢复基本手感第 4 到 6 天过图论重点练握手定理、生成树、最短路提速到能默写流程第 7 到 9 天过组合与递推整理模型表看到题能归类第 10 到 11 天过代数结构主攻判定题拿到基础分第 12 到 14 天整套限时模拟复盘错题稳定在及格线以上这个安排的关键在最后三天一定要整套限时做而不是分章节刷。分章节做你会觉得都会整套限时做才会暴露哪块拖时间的真实问题。7.2 答题顺序与时间分配我个人的习惯是先扫一遍全卷把有把握的题标出来先做这部分。一般来说逻辑的求真值表、集合的求幂集和关系性质判断、图论的度数计算这些题又稳又快先把它们拿下能快速积累信心。推理证明题和大题放在中间时段做代数结构的难题放在最后实在没时间就把能写的定义和判定步骤写上评分通常有步骤分。7.3 高频失分点自查清单每次模拟考完我都会拿这张清单核一遍看看自己是知识问题还是习惯问题求主范式时是否把取 0 写否定的规则记反了谓词符号化时量词和联结词的搭配是否搞错判断关系性质时题目问的是反自反还是不自反度数列判断可图化时有没有先检查奇度顶点个数判哈密顿图时是否误把充分条件当成了充要条件画哈斯图时有没有漏删传递性推出来的边递推题求出通项后有没有代回初始条件验证这套自查清单我自己用了很多年每次都能抓出一两个习惯性错误。最后分享一个我自己的体会离散数学(本)复习题真正难的从来不是某一道题而是我知道这块该怎么做但我做不快。把每类题的流程写成自己能看懂的步骤卡片贴在书桌前做三遍就能形成肌肉记忆。等到考场上看到题脑子里自动跳出下一步该写什么那种踏实感是刷多少道题都换不来的。