简介这是一份系统梳理离散数学核心知识点的PDF笔记围绕数理逻辑、集合论、数论、计数原理、概率论、关系论、代数系统与图论八大板块展开适合高校本科生、考研复习者及程序员巩固理论基础。笔记从命题逻辑的永真式与范式讲起依次覆盖函数与基数、同余与素数定理、容斥与生成函数、随机变量数字特征、等价关系与偏序、群与布尔代数、欧拉图与树等内容。具体包含成真/成假指派、常见逻辑等价式、自然推理规则、合取/析取范式、皮亚诺公理、中国剩余定理、鸽笼原理、排列组合、期望与方差、关系闭包及Warshall算法、群与格的公理、欧拉图与哈密顿图等细节每个模块既有定义又有典型结论知识点衔接紧凑。资源包体积仅约630KB共1个PDF文档按章节目录清晰分节便于按需跳转复习。目前已有2876人学习下载作为考前冲刺梳理或平时查漏补缺的参考资料都很实用。1. 离散数学笔记把散课的骨架记下来而不是抄一遍定义离散数学这门课的难点从来不在某个定理多难而在它太散。集合论在讲结构数理逻辑在讲推理图论在讲连接组合数学在讲计数代数结构在讲运算规律每块单独拿出来都不算难凑到同一张卷子里就让人觉得无从下手。一份真正有用的离散数学笔记不是把教材抄一遍而是把这几块内容挂到同一条主线上让你在复习和做题时能一眼定位这个知识点属于哪个板块、它的前置条件是什么、最常见的考法是什么。这份笔记适合三类人正在期末复习的本科生、准备考研的二战选手以及自学离散数学准备转算法方向的从业者。2. 离散数学的知识骨架五大板块怎么串成一张图很多人的笔记按教材章节往下抄抄完第一章逻辑第二章集合第三章关系抄到第四章图论时已经忘了前面讲了什么。这不是记性差而是笔记没有建立板块之间的联系。我一般拿到任何一份离散数学笔记先不看正文只看目录和章节过渡判断作者有没有把五块内容串起来。离散数学的五个板块其实有一条隐含主线研究对象是有穷或可数的结构研究方法是构造与归纳研究目标是给计算机能处理的问题提供精确的形式化语言。数理逻辑提供这套语言本身集合论给出讨论对象的范围关系描述对象之间的联系图论把关系可视化组合计数研究有多少种可能代数结构研究运算服从什么规律。这五块不是并列关系而是一层一层搭上去的。2.1 数理逻辑为什么它是整门课的语法层数理逻辑这一章笔记里最该记的不是真值表那是最基础的内容而是推理规则和等价变换。为什么说它是语法层因为后面学到关系的传递闭包、图论中的可达性、代数结构中的同态本质上都是在做逻辑推理。比如关系的传递性用逻辑语言写就是若 aRb 且 bRc则 aRc和图论里从 a 到 b 有边、从 b 到 c 有边则 a 到 c 可达是同一个结构。笔记在这一章至少要覆盖三块内容命题逻辑的等值演算特别是德摩根律、蕴含等值式、双条件等值式、谓词逻辑的量词否定规则、推理理论中的直接证明与间接证明反证法、归结法。其中量词否定规则是最容易搞混的很多人在考试时把 ¬∀xP(x) 直接写成 ¬P(x)实际上应该先变成 ∃x¬P(x)。笔记里最好用左栏公式、右栏自然语言翻译的方式记量词规则比如逻辑公式自然语言理解常见错误¬∀xP(x) ⇔ ∃x¬P(x)不是所有人都……等价于存在某个人不……误写成 ¬P(x)¬∃xP(x) ⇔ ∀x¬P(x)不存在……等价于所有人都不是……误写成 ¬P(x)∀x(P(x)→Q(x)) ⇔ ∀x(¬P(x)∨Q(x))蕴含式换成语境式忘记量词作用域这一章笔记的另一项重要工作是记录证明策略。教材里会给出很多推理规则的名称比如假言三段论、析取三段论、构造性二难这些名称本身不重要重要的是在一道具体的证明题里怎么选。我一般会在每个推理规则旁写一道迷你例题只写证明思路不写完整过程。2.2 集合、关系与函数把结构画成图大半道题就出来了集合论本身不难难的是后面关系那一节。关系的五种性质自反、反自反、对称、反对称、传递是高频考点也是笔记最容易记成定义堆砌的地方。我的建议是每种性质旁边配一张小示意图用有向图表示一个满足该性质的关系。自反就是每个节点都有环对称就是每条边都有反向边传递就是两条首尾相接的边必有第三条直接连接。这还不够。性质之外三种闭包的计算方法是这一章的真正重点。自反闭包最简单把每个节点补上环对称闭包把每条边补上反向边传递闭包复杂要用 Warshall 算法或反复求关系复合。笔记里要把这三种闭包的求法分别用集合表达式写一遍R∪I、R∪R⁻¹、R⁺然后各配一个 3 元素集合的完整计算例子。我见过太多人栽在传递闭包上原因是只记了结论传递闭包是包含 R 的最小传递关系却不知道实际操作是不断做 R² 并到 R 里直到不出现新元素。函数这一节在考试里通常不会单独出大题但它是后面代数结构的预备知识。笔记里需要明确区分单射、满射、双射的定义以及函数复合与关系复合的记号差异。这一步踩坑的人非常多因为关系复合的记号是 R∘S先 S 后 R函数复合也写成这种方式但很多教材在函数部分会用 f∘g 表示先 g 后 f两套规则容易混。笔记里最好的做法是单独开一个框把两种复合的运算顺序写清楚。2.3 图论与树离散数学里最容易拿分也最容易丢分的板块图论是离散数学里最直观的板块因为可以画图但丢分点也最多。笔记里图论部分应该围绕判定来记欧拉回路存在的充要条件、哈密顿回路的充分条件、二部图的判定条件、平面图的欧拉公式。这些都是条件型知识点非常适合用表格对比比如欧拉路径与哈密顿路径一个看度数奇偶一个看连通性和顶点覆盖二者名字像、解法完全不同。我建议图论笔记按问题类型而不是按教材章节组织。分成如下几类可达性问题用邻接矩阵的幂或 BFS/DFS 判断涉及传递闭包欧拉路径 / 回路问题奇数度顶点数为 0 或 2哈密顿回路问题目前只有充分条件Dirac 定理、Ore 定理没有充要条件这是它与欧拉问题的根本区别最小生成树Prim 与 Kruskal 的适用场景最短路径Dijkstra正权、Floyd任意权树这一章的两个重点性质一定要记牢n 个顶点的树恰有 n-1 条边连通图 G 是树当且仅当任意两点之间恰有一条路径。后面那个性质在证明题里非常好用但容易被忽略。另外树的遍历与表达式求值在考试里也常出现笔记里把前序、中序、后序遍历与表达式的前缀、中缀、后缀表示法对应起来会省下不少临考时间。2.4 组合计数与代数结构两块常被低估的内容怎么记组合计数看起来简单排列组合公式谁都会背但一到做题就不知道用哪个。笔记要解决的是什么时候用哪个的判别问题。我会在笔记里画一张决策小表有顺序用排列没顺序用组合元素不可区分用多重集组合问题含至少用容斥原理或补集转换递推关系用特征方程。这张表的价值远大于公式本身因为它把题目特征和公式匹配起来了。容斥原理和鸽巢原理是这一章最容易考证明题的点。鸽巢原理的难点不在原理本身而在于构造鸽巢。笔记里应该记 3-4 个经典构造案例比如从 1 到 2n 中选 n1 个数必有两个数互质这类题看多了才会构造。代数结构这一章比较抽象群、环、域的定义容易记混。我的做法是画一张层级表半群 → 幺半群 → 群 → 阿贝尔群每加一个条件就多一条性质。同时把子群判定条件作为重点因为考试极爱考证明某集合是子群只需要记三个条件非空、对运算封闭、对逆元封闭。环和域通常考到定义层面笔记里注意区分整环无零因子和域非零元素都有逆元即可。3. 拿到一份笔记先翻这三处判断它值不值得当主线资料不在多在于能不能当主线用。一份可用的离散数学笔记应该能让你从零开始复习到上考场中途不需要再回头翻教材找定义。判断标准有三个拿到任何笔记先翻这三处五到十分钟就能得出结论。3.1 目录顺序好的离散数学笔记一定按这条线排一份结构合理的笔记目录应该大致是数理逻辑 → 集合 → 关系 → 函数 → 图论 → 树 → 组合计数 → 代数结构。这不是唯一的顺序但它的好处是每章都为下一章铺路逻辑是全书语言集合提供对象关系连接对象图论把关系画成图代数结构给运算定规则。如果目录乱跳比如把图论放在逻辑前面或者把组合计数拆成两半分别塞到不同章节这份笔记多半是长期修补的结果缺少整体规划。这种笔记不是不能用而是你需要在脑子里先重建结构学习成本会高很多。目录之前如果还有一页符号约定表那这份笔记至少证明作者认真整理过。3.2 检验定理条目条件、结论、反例缺一不可抽一个定理来检验比如鸽巢原理。合格的笔记会写三部分适用条件把多于 n 个物体放入 n 个盒子、结论至少有一个盒子含两个或以上物体、反例或边界情况恰好 n 个物体时结论未必成立。三部分里反例是最能看出笔记质量的。很多笔记只写结论不写条件和边界这种笔记在复习阶段看还行一到做题就出错。因为离散数学的定理几乎都有前提而考试题往往就考你条件不满足时结论是否仍成立。检验方法很简单随便翻十个定理看有几个写了若……则……的完整句式如果不足七个这份笔记不适合当主线。3.3 把笔记当索引用配合教材和题集的三段式打法笔记不能替代教材。教材有完整的推导过程和上下文笔记只有骨架和结论。正确用法是把笔记定位成索引从笔记定位知识点 → 回教材读推导 → 回笔记记结论。这样笔记既不会被教材的冗长拖累也不会因为缺少推导而看不懂。具体做题的流程我是这样跑的拿到一道题先在笔记目录里定位它属于哪个板块然后读该板块开头的题型与解法速查表找到匹配的题目类型。如果笔记里正好有类似例题就对照例题的结构走一遍如果没有回教材翻对应小节把新的题型补充到笔记里。这套流程坚持下来笔记会越用越厚而这个厚是围绕你的薄弱点长的不是教材的复读。4. 自己动手整理一份可复用的离散数学笔记方法、结构与工具市面上能找到的笔记再好也不如自己整理一遍。整理过程本身就是复习过程而且只有你自己知道哪里容易卡住。但整理要讲方法照着教材抄一遍是最低效的做法。这一章给出一个可以直接照搬的整理框架。4.1 用定理-条件-反例三层结构记而不是按教材顺序抄每一节笔记只记录三种内容核心定义、关键定理、经典反例。定义要写得短只保留数学对象的内涵定理必须写成若 A 则 B的完整句式把条件单独加粗每个定理旁边留一行写边界情况或反例。举一个例子关系的传递性。定义部分写R 是集合 A 上的关系若对任意 a,b,c∈A当 aRb 且 bRc 时必有 aRc则称 R 是传递的。 定理部分写若 R 是传递的则 R² 的分量 R 之中即 R∘R⊆R。 反例部分写A{1,2,3}R{(1,2),(2,3)}R 不是传递的因为缺少(1,3)。但注意若 R 为空集或只含一个有序对时传递性自动满足——这是容易误判的边界。这种三层结构的好处是强迫你在写笔记时对每个知识做三次加工理解定义、梳理逻辑、寻找例外。三次加工做完这个知识点基本就内化了。代价是慢但离散数学的内容量完全支撑得住这种精读式整理值得投入。4.2 统一符号约定让笔记在第一页之后就能顺畅查离散数学的符号在不同教材里不统一同一个符号 A∘B 在不同的书里可能表示先 A 后 B 或先 B 后 A。笔记必须在第一页固定一套符号约定之后所有章节都使用这一套不再跟随教材改变。我习惯用下面这组约定你可以直接采用符号含义说明R⁻¹逆关系与教材的 R^op 等价R∘S先 S 后 R函数复合同理|A|集合 A 的基数有穷集时表示元素个数∅空集不用 φ 表示⁄整除符号如 a⁄b 表示 a 整除 b≡ₙ模 n 同余避免与等号混淆4.3 最小整理步骤从教材目录到可用的章节定稿整理一份完整的离散数学笔记我建议按以下四步走每一步都有明确的产出物做完一步再进入下一步不要边学边整理第一步搭骨架。拿一份教材目录把五大板块的章节标题抄到笔记里每个章节标题下先留半页空白。这个阶段产出的是整个笔记的框架大概占最终篇幅的两成。不要在这个阶段做任何摘录。第二步填条目。按定理-条件-反例三层结构把每个章节的核心定义和定理填进去。这一阶段的产出是笔记的正文也是最花时间的一步。每填完一个章节停下来做本章节的课后习题不会做就回头补充笔记。这样能保证笔记是为做题服务的而不是为抄完服务的。第三步加速查表。每个章节完成后在章节末尾加一张公式速查表和一页常见题型与切入点。比如组合计数那一章速查表里直接列出特征方程为 r² - ar - b 0及三种解的写法题型表里写看到至少用容斥看到恰好用生成函数或容斥特例。第四步做符号统一。全部完成后从第一页开始检查把所有不符合约定的符号改掉同时把所有又见教材第 X 页这类批注清除干净。这一步完成后笔记就具备长期使用和反复翻阅的价值了。5. 避坑离散数学笔记常见的 5 个翻车现场这一章全部来自真实教训。笔记本身不会害人但整理方式不当会让笔记变成自我安慰工具——抄的时候觉得自己在复习抄完合上本子什么都想不起来。下面五条是我见过和踩过最多的坑按出现频率排序。5.1 笔记成了教材压缩版翻的时候找不到任何重点现象是笔记的每个章节都在复述教材篇幅压掉了三分之一但结构完全没变。翻笔记时每个字都认识却不知道哪里是重点、哪里是考点。原因整理时没有做结构化加工只是摘抄把教材里的核心句摘出来拼在一起。这种笔记本质上是教材的摘要而摘要有教材就够了不需要手写。解决按定理-条件-反例重写强制自己把每个知识点压缩成三行以内。如果某页超过三行就说明你还在抄而不是整理。血的教训是好的离散数学笔记应该让你一页纸就能回忆起整章内容而不是让你在几百页里慢慢翻。5.2 例题只抄不练笔记里全是别人的思路现象例题记录得非常完整步骤一字不漏但到了自己做题面对同样的题型还是不知道第一步写什么。原因抄例题时跳过了最关键的思维过程——我最初卡在哪一步、后来怎么跳出来的。完整抄下来的是答案不是思路。解决每道例题用两行记录元信息一行写第一次做卡在哪一行写突破口是什么。比如欧拉回路的题记卡在没检查连通性突破口是先把图分解成连通分量。这种记录的复习价值远大于题目本身。我后来做题的正确率高了不少就是因为翻笔记时先看这两行不看完整解答。5.3 符号混乱临考看错条件丢分现象笔记里同一个符号在不同章节代表不同含义比如用 A 既表示集合又表示关系用 R 既表示关系又表示实数集。考试时按笔记复习结果把关系复合当成集合运算整道题全错。原因笔记整理过程跨了好几周前面定义的符号到后面忘了随手拿起一个常用字母就用。大多数教材本身符号就不统一笔记如果不做统一约定就会把教材的混乱加倍放大。解决按上面 4.2 的符号约定表在第一页固定所有符号含义每次使用新符号时先查表确认不冲突。我见过最极端的做法是在笔记本侧面贴标签左边一列是符号速查右边是定义速查。这个习惯坚持下来临考翻笔记的速度能快一倍。5.4 只记结论不记条件做题时定理套得比谁都快现象鸽巢原理、欧拉定理、容斥原理的结论都背得滚瓜烂熟但题目稍微换个条件就套错。比如把n1 个物体放入 n 个盒子换成n 个物体放入 n 个盒子立刻误判至少有一个盒子为空其实这个结论根本不成立。原因定理只背了后半句结论没背前半句条件。离散数学里这种情况极为普遍因为很多定理的结论简洁有力条件却比较绕。解决整理时强制用若……则……完整重写定理把条件单独加粗并圈出来。复习时先看条件再看结论做题时先判断题设是否满足条件再决定是否套结论。坚持一段时间后你会发现离散数学的送分题和送命题之间只差一个条件判断。5.5 一份笔记想同时服务期末、考研和面试现象期末复习时往笔记里补公式考研复习时往里补证明题面试准备时往里补算法应用最后笔记变成了一个大杂烩每个考试阶段复习时都要在一堆无关内容里找重点。原因三种场景的深度和侧重点完全不同。期末考定义和计算考研考证明和综合面试考算法思维和手写代码能力。一份笔记很难同时满足三种需求。解决以当前主场景为准确定笔记深度其他场景只加标注。比如期末复习时笔记以定义和计算题为主证明题只记录大纲是否要求不展开若之后准备考研再在原有笔记基础上把每个定理的证明思路作为独立小节补充进去而不是混在正文里。我一般会在每章末尾留两页专门用于后期补充这样主场景不会被冲淡后期补充也有地方可去。6. 让笔记最后能闭卷翻页一页纸公式索引和反例集最后一个技巧也是整套整理方法里性价比最高的两样东西每章一页纸的公式索引和全书单独一个反例集。公式索引的做法是每个章节结束后单独用一页纸把所有公式和它们的适用条件列成表。左边写公式右边写使用前提和常见误用。比如图论那一章索引页长这样欧拉回路存在的充要条件是所有顶点度数为偶数且图连通右边写注意满足条件的是回路不是路径路径允许恰有两个奇度顶点最小生成树的 Kruskal 算法右边写适用于带权图不适用于有向图。考试前复习只翻索引页不翻正文能把复习时间压缩一半。反例集的做法更简单但更贵从学习第一天开始专门留出一个独立章节每遇到一个看起来成立但不成立的命题就记进去。比如偏序关系一定存在极大元和极小元这个命题在有限集合上成立在无限集合上不成立每个连通图都有欧拉路径需要所有顶点度数都为偶数否则只有欧拉路径没有欧拉回路。每记一条反例在旁边用一句话说明它像什么但实际是什么复习时直接看反例集胜过反复看十遍定义。这个习惯我坚持了半年整理完一整套离散数学笔记后最大的感受不是知识变多了而是翻笔记变快了——因为我知道什么东西在哪里、什么知识点处于什么条件之下。离散数学的复习到最后拼的不是记性而是检索速度。希望这些方法和坑位的经验能帮到你让你整理笔记时少走一段弯路。本文还有配套的精品资源点击获取