简介离散数学笔记围绕计算机专业核心基础课“离散数学”展开系统覆盖数理逻辑、集合论、数论、计数原理、概率论、关系论、代数系统与图论八大经典模块适合在校大学生、考研备考生及需要巩固数学基础的程序员参考。资源压缩包内含1个PDF文件整体约630KB轻量易携带可离线阅读或打印复习。笔记内容以求精不求全的要点式归纳为主从命题逻辑的永真式与自然推理规则到集合函数性质、裴蜀定理、容斥原理、常见随机变量分布、等价关系与偏序关系、群与格、欧拉图与哈密顿图、生成树等均有覆盖并穿插Warshall闭包算法、生成函数等常用工具结构清晰便于按模块检索。目前已有2876人学习下载适合作为期末复习、考研强化或日常查缺补漏的速查型资料。1. 离散数学笔记.pdf一份能救命的复习资料长什么样期末前一周对着教材六百多页的密集符号多数人会意识到一个残酷事实离散数学这门课课堂上听懂了不等于会做题会做题不等于能扛住期末考试。很多人的第一反应是上网找一份“离散数学笔记.pdf”想用现成的知识框架给自己省时间。这个需求真实存在但问题也随之而来——网上的笔记海量有的只有框架没有推导有的推导跳步严重有的重点完全跟不上自己学校的考纲。这份笔记真正要解决的不是“看不懂定义”的问题而是“看完定义依然不会做真题”的问题。它应该是一份学习资料更是一份备考手册。适合的人有三类期末冲刺的在校生、考研要考离散数学的备考生以及自学到图论和群论阶段感到吃力的初学者。接下来的内容我会把一份能打的离散数学笔记拆开从知识骨架到使用方式再到复习技巧讲清楚每一步怎么做。2. 离散数学笔记的知识骨架五大模块怎么排、怎么取舍一份可用的离散数学笔记绝不是教材目录的复制粘贴。它需要体现授课老师强调的重点、历年真题的出题频率以及知识点之间的依赖关系。下面是五个核心模块以及笔记整理的标准。2.1 数理逻辑命题与谓词先过符号关再过推理关数理逻辑是整个离散数学的基础。命题逻辑部分需要掌握的核心单元包括命题的否定与复合、真值表构造、等值演算的常用公式、主析取范式与主合取范式以及推理理论中的基本推理规则。笔记里必须有的内容是一张完整的常用等值公式表比如德摩根律、吸收律、蕴含等值式。很多人在考场上翻车不是因为不会推而是公式表没记牢。给一个典型例子要证明(p→q) ∧ (q→r) ⇒ (p→r)用等值演算可以这样写(p→q) ∧ (q→r) ⇔ (¬p ∨ q) ∧ (¬q ∨ r) ⇔ (¬p ∨ q ∨ r) ∧ (¬q ∨ r) ∧ (¬p ∨ ¬q ∨ r)这里第一步是把两个蕴含式拆成析取形式第二步是分配律展开。如果笔记里只写了最后的结论没有过程复习时很容易卡住。所以做逻辑部分的笔记每个等值公式至少配一道完整例题。谓词逻辑部分核心是量词的否定、量词辖域的收缩与扩张以及带量词的推理证明。这里记笔记的原则是把每个公式的“使用条件”写清楚。例如¬∀xA(x) ⇔ ∃x¬A(x)这个公式使用的前提是量词管辖范围不变很多人做题时把否定作用范围搞错就是这个条件没吃透。2.2 集合论与关系闭包、等价关系、偏序关系是命题重灾区集合论这部分看似简单却是考试丢分的隐蔽区域。笔记必须覆盖集合运算律、幂集、笛卡尔积、关系及其表示、关系的性质自反、对称、传递、关系的闭包、等价关系与划分、偏序关系与哈斯图。关系的复合运算是一个高频考点但也是理解偏差最严重的地方。关系的合成R◦S的定义是存在某个中间元素t使得(x, t) ∈ R且(t, y) ∈ S那么(x, y) ∈ R◦S。很多人会把合成顺序搞反笔记里应该用一个具体例子标注顺序比如用“同学选课”这种关系来说明而不是只抄定义。等价关系与划分这块典型题目是给出一个关系判断它是不是等价关系然后写出对应的划分。这类题是送分题但前提是笔记里要有完整的判断流程先检查自反性再检查对称性最后检查传递性。三个性质必须逐条验证缺一不可。笔记里应该把这个三步流程做成一个固定模板考试时直接套。偏序关系的哈斯图也是必考内容。画哈斯图之前必须了解这个结论偏序关系可以省略自反边和传递边只保留覆盖关系。笔记里需要有一个“由偏序关系画哈斯图”的例子从矩阵到关系图再到哈斯图三步走通。2.3 图论图的存储与算法推导笔记里必须有图例图论是整个离散数学中内容最多、题型最活的模块。笔记要覆盖图的矩阵表示邻接矩阵、关联矩阵、欧拉图与哈密顿图、树的性质、最短路径算法、二部图与匹配。邻接矩阵的幂运算是一个容易被忽视的考点。A^n中(i, j)位置的值表示从vi到vj长度为n的路径条数。笔记里一定要有具体的矩阵乘法展开过程因为考试中常见的问法就是“求长度为 2 的路径有多少条”。只记结论不记推导过程考场上换个问法就懵。最短路径这一块Dijkstra 算法是重点。笔记里建议用一个大一点的图逐步展开每一步标注当前最短路径集合的变化。因为这类算法题最怕的是一步错步步错如果笔记里每一步都有据可查复习时就能快速定位错在哪一步。Floyd 算法的笔记重点则是三重循环的顺序外层枚举中间点内层枚举起点和终点。这个顺序写错整个算法就废了。树的部分核心公式是一棵有n个顶点的树有n-1条边。看似简单但考试常常结合生成树来考。笔记里要有一个“由图的深度优先遍历得到生成树”的例子这类题型比较固定掌握一个标准流程就能应对大部分题目。2.4 代数系统与组合数学群论和计数原理的笔记写法代数系统是很多人的学习难点原因是抽象。这部分笔记的核心是半群、独异点、群、子群、循环群、陪集。入门方式是从运算表和群的四个性质入手封闭性、结合律、单位元、逆元。笔记里做一个四阶或六阶群的运算表非常必要。给定一个集合和一个二元运算要判断它是否构成群必须逐条验证四个性质。很多人在封闭性和结合律上栽跟头就是因为没有逐条检查的习惯。围绕运算表展开笔记把每个性质对应的验证过程写出来这种做法肯定比抄定义要牢固。组合数学部分核心是加法原理、乘法原理、排列组合、鸽巢原理、容斥原理、生成函数。笔记的重点应该放在典型例题上。比如容斥原理公式好背难的是判断哪些元素属于“并集”。笔记里需要有一个集合图示把每个区域的元素数标注出来。鸽巢原理看似简单但应用起来需要有反证意识。记笔记时最好把“构造抽屉”这一步写清楚因为这才是解题的突破口。2.5 知识模块的依赖关系笔记怎么排才能越看越顺这五个模块不是孤立的。数理逻辑中的谓词逻辑是后面所有模块推理的工具集合与关系是图论和代数系统的语言基础图论和代数系统在知识点上看似不同但都会用到关系和运算。所以笔记的排序我一般建议逻辑 → 集合与关系 → 组合数学 → 图论 → 代数系统。这个顺序符合知识依赖关系复习时也能层层递进不必反复跳转。3. 从课堂笔记到备考手册改造一份能用的离散数学笔记光有知识骨架还不够如何把零散的课堂记录改造成一份能高效备考的手册这才是核心操作环节。这一章讲三步改造法每一步都对应具体的操作。3.1 第一步用知识点清单体检笔记的覆盖度拿到一份笔记先不要急着从头看到尾第一件事是做覆盖度体检。按下面这个清单逐项检查缺什么补什么模块必须覆盖的知识点检查结果数理逻辑真值表、等值演算、主范式、推理规则、量词否定逐项打勾集合与关系集合运算、关系性质、闭包、等价关系、划分、偏序与哈斯图逐项打勾组合数学加法/乘法原理、排列组合、鸽巢原理、容斥原理逐项打勾图论邻接矩阵、欧拉图、哈密顿图、树、最短路径、二部图逐项打勾代数系统运算表、半群、群、子群、循环群、同态同构逐项打勾体检时有个技巧每检查完一个知识点在笔记对应位置写下一个页码标记。这样后期翻查时所有知识点都能快速定位不用整本翻找。覆盖度体检做完之后你大概率会发现两个极端情况有些知识点笔记里只有定义没有例题另一些知识点例题多到冗余。处理原则是定义型知识点配一道基础题即可算法型知识点必须配完整流程题。如果你的笔记每一节都是大段定义那就是典型的“字典式笔记”考试时基本帮不上忙。3.2 第二步把例题按“题型-方法”重新归档课堂笔记的例题顺序往往对应讲课顺序而不是出题套路。备考期间建议把例题打乱重排按照“题型-方法”重新归档。这是整个改造过程中最有价值的一步。常见题型可以归成这几类题型典型方法笔记位置判断关系性质逐条验证自反、对称、传递关系章节求闭包按定义逐步补边或补序偶关系章节证明某个结构是群验证封闭性、结合律、单位元、逆元代数系统章节求最短路径Dijkstra 逐步标注图论章节逻辑推理证明等值演算或推理规则数理逻辑章节归档时把同一类题目的解题套路写在题目前面用一两句白话概括。比如“关系性质的判断画关系图最直观自反看对角线对称看矩阵是否关于主对角线对称传递需要两两检查”。这种口诀式总结比长篇论述好用得多。如果你发现某个题型下面只有一道题那说明这块练习量不够需要补充而不是题目本身不重要。3.3 第三步为每个模块做一份公式速查表公式速查表是考试前最后几天最重要的复习材料。它的存在意义不是代替理解而是帮你把高频公式浓缩到几页纸内考前反复扫读。每份速查表应包含公式、使用条件、典型例题索引三个部分。以图论为例速查表内容大概是公式或定理使用条件例题索引树中边数 顶点数 - 1连通无环图例题 08欧拉图存在欧拉回路的充要条件连通且每个顶点度数为偶数例题 12A^n中(i,j)为长度为 n 的路径条数邻接矩阵乘法例题 15这里有个容易被忽略的重点使用条件必须写清楚。欧拉回路的充要条件如果漏掉“连通”这个前提考试时会掉进陷阱——一个所有顶点度数都是偶数但不连通的图显然没有欧拉回路。速查表把这个条件写出来就相当于在考前给你打了一支预防针。4. 离散数学笔记避坑五个常见坑与排查思路笔记有了复习方法也定了但过程中依然存在着各种预料之外的问题。这一章整理五个比较典型的坑每一条都是可以定位到具体原因并解决的。4.1 坑一笔记记了定义做题时依然不会现象看完笔记里“传递闭包”的定义甚至能背出来但拿到一道求传递闭包的题完全不知道从哪里下手。原因这其实是笔记的锅。定义只能告诉你“是什么”不能告诉你“怎么求”。求传递闭包的方法有三种按定义逐步添加序偶、用 Warshall 算法、用关系矩阵的布尔幂运算。如果你的笔记里只有定义没有方法那这道题一定会卡壳。解决把每一个计算型知识点都至少配一种可操作的方法。求传递闭包的笔记应该写清楚 Warshall 算法的循环过程外层循环枚举中间点内层循环更新矩阵元素每轮更新规则是R[i][j] R[i][j] ∨ (R[i][k] ∧ R[k][j])。有了方法定义才有意义。4.2 坑二符号混淆同一道题两步之间就错了现象做题时把“属于”和“包含于”混用把“等价”和“蕴含”当成一个意思导致证明过程逻辑断裂。原因离散数学的符号密度极高有些符号长得相似含义却完全不同。比如⊂表示真包含∈表示元素属于集合这两个符号在第一眼看到时很容易搞混。笔记如果没有对这些高频混淆符号做专门的区分记录做错了都不知道错在哪。解决在笔记最前面专门开一页“符号对照表”把容易混淆的符号成对列出配上各自的含义和一个微型例子。例如a ∈ A元素a属于集合AA ⊆ B集合A是集合B的子集。考前翻一遍这一页能省下不少无谓失分。4.3 坑三图论题看着会做一动手就错现象Dijkstra 算法的步骤都懂但自己动手算的时候经常在第 4 步或第 5 步选错当前最短路径节点导致后面的结果全部偏移。原因图论算法题的翻车往往不是不会算法而是缺乏对“每一轮迭代结果”的记录习惯。脑子里推演算法一旦图的规模超过 6 个节点记忆就会乱。笔记如果只写算法思路没有完整跑一遍例题的每一轮结果这个能力就练不出来。解决笔记里的图论算法例题必须让每一步的中间状态都可见。Dijkstra 算法可以画一个表每一行记录一轮迭代后每个节点的当前最短距离并把已确定最短路径的节点标出来。这样复习时看到的是“过程”而不是一堆不可追溯的结论。4.4 坑四笔记太全等于没有笔记现象笔记是从教材大段抄录的每一节都密密麻麻写满文字看起来非常用功但考前根本看不完看了也留不下印象。原因抄书式笔记的根源是对考试重点不明确。害怕漏掉任何可能考的知识点就会想把一切都记下来。结果就是重点与次要点完全没法区分复习效率低是必然的。解决做笔记之前先看两三套目标考试的往年试题圈定高频考点。笔记中高频考点部分可以详写配两道例题低频考点只写一句话结论。比如“哈密顿图的判定条件”是一个充分非必要条件这句话就够具体细节可不写。4.5 坑五笔记从不复盘做着题才发现还是不会现象笔记做得工工整整但只是用一种“誊写”的态度在做从不回头看。到了考前两周翻开笔记像看一本新书。原因做笔记的过程如果只有记录没有复盘那就只是信息转移不是知识加工。解决给每章笔记设置一个“复盘日期”标记每次复习时尝试不看书把该章的核心公式和题型方法默写出来再对照笔记查漏。能默写出来的才算掌握默写不出的就是接下来的主攻方向。5. 把笔记变成考点检索表考前一周的提速复习法笔记改造完成后考前最后一周的复习策略值得格外讲究。我习惯的做法是把笔记的每一章压缩成一张 A4 大小的考点检索表。表头是四个列考点名称、题型、解题方法、笔记页码。图论部分可以整理成下面这样考点题型方法页码邻接矩阵的幂求长度为 k 的路径数矩阵连乘查对应位置P78欧拉图判定判断是否存在欧拉回路/通路检查连通性和奇度顶点数P82最小生成树求最小生成树Kruskal 或 Prim 逐步选边P85这张表就是考前一两天的快速浏览材料。每看一行先在脑中复现具体步骤再翻笔记核对。这样每行只需一两分钟整张表过一遍也只需半小时左右能覆盖大部分核心考点。这个习惯是我在第一次考离散数学吃了亏之后养成的。当时我的笔记完整度很高但没有这张检索表考前只能从头到尾翻时间不够且抓不住重点结果图论那道 15 分的题就差在邻接矩阵幂的符号细节上。后来每次备考我都先把笔记压成检索表再针对表上每一行做一次“默写式回忆”效果比反复通读笔记好得多。这个方法是实践过且稳定有效的有一个步骤还能进一步提速给每一行标一个难度星级复习时优先看三星考点。希望帮到你。本文还有配套的精品资源点击获取