简介《离散数学笔记》是一份面向计算机专业本科低年级、考研备考与自学者的系统梳理资料覆盖数理逻辑、集合论、数论、计数原理、概率论、关系论、代数系统群、格、布尔代数与图论八大模块。笔记以命题逻辑与谓词逻辑为起点详细整理永真式/永假式、逻辑等价式、自然推理规则、CNF/DNF等概念随后展开集合运算、函数、自然数公理化以及整除同余、素数定理、容斥鸽笼、生成函数、随机变量分布等离散数学核心考点。关系论部分对等价关系、偏序关系、闭包运算与Warshall算法做了专门归纳代数系统与图论部分则覆盖群论公理、陪集、格与布尔代数以及欧拉哈密顿图、匹配、树等内容结构清晰重点突出。资源为单个PDF文件大小仅630KB便于离线阅读或打印。目前已有2876人学习下载适合需要快速查阅公式判定、定理证明思路或考前集中复习的读者使用。1. 离散数学笔记.pdf为什么翻了三遍还是不会做题拿到一份离散数学笔记 PDF最常见的结局是什么收藏、打开第一章、读两页、退出下次再打开还是第一章。这不是自制力问题而是方法问题把笔记当书读天然会困。离散数学的特点是定义密集、例子少、定理互相引用线性阅读根本走不通。我见过不少同学资料攒了几十个 G真到期末或面试连偏序关系和等价关系的区别都要想半天。这篇笔记不是教背定义而是讲一条反直觉但走得通的路先看清笔记的模块结构再用三轮阅读法制造输出最后把定理映射到工程场景。适合备考、考研、补算法基础的人也适合想搞明白离散数学到底怎么用的人。2. 打开笔记前先有地图离散数学五大模块与一份自检清单拿到一份离散数学笔记第一件事不是从第一页开始读而是先翻目录。因为这门课的结构高度标准数理逻辑、集合论、关系与函数、图论、组合数学偶尔再加数论和代数结构。五大模块之间有明确的依赖链没有集合论关系讲不清楚没有逻辑证明方法无从谈起。先看清笔记覆盖了哪些模块、缺了哪些模块你才知道后面读到某个地方突然看不懂到底是自己没学会还是笔记本身就漏了。有一个容易被忽略的判断方法看笔记里有没有反例和带解答的例题。定义谁都会抄但只有带反例的定义才能暴露边界只有带推导的例题才能说明怎么用。如果一份笔记从头到尾只有定理陈述没有一道带答案的例题它的使用价值要打一个大问号。好的笔记应该是「定义 正例 反例 例题」四件套缺一项读的时候就要自己补一项。下面按模块拆开讲方便你对着手里的笔记逐条核对。2.1 数理逻辑与证明方法最容易被跳过但最值钱的部分数理逻辑是整套笔记里最容易被跳过的一部分因为它看起来又抽象又离代码远。但实际上逻辑决定了你往后所有证明题能不能写出来。笔记里这一部分至少要包含三件事命题逻辑的真值表和等价律、谓词逻辑的量词及其否定规则、常见的证明方法。三者缺一后面读图论和组合的证明都会吃力。一个很实用的自检动作合上笔记写出¬(∀x)(∃y)(P(x,y))的等价形式。答案是(∃x)(∀y)¬P(x,y)。如果你写的时候要犹豫说明量词否定这一节还没掌握。这个规则在后面的图论证明里会反复用到比如证明「不存在某个性质」时经常要先否定一个带量词的命题。另一种常见自检是看见「如果 P 则 Q」的证明题能不能立刻列出「直接证明、逆否证明、反证法」三个选项并选出合适的一个。证明方法这一节建议用表格把适用场景记下来而不是只记方法名字。证明方法适用场景从题面怎么认直接证明条件能一步步推出结论已知 P有明显路径通往 Q逆否证明原命题不好下手结论 Q 的否定比 P 更好表达反证法假设结论不成立能导出矛盾题目里出现「不存在」「唯一」之类数学归纳法涉及自然数 n 的命题题面出现「对所有正整数 n」逻辑部分最值得做的练习是把笔记里的每一条逻辑等价律自己用真值表推一遍比如德摩根律、蕴含式改写P→Q ≡ ¬P∨Q。看起来是小儿科但后续所有证明题里的「第一步怎么变形」都靠这个手感。如果笔记里没有单独的证明方法章节那这份笔记是不完整的建议立刻补充否则后面所有证明题你都只能靠猜。2.2 集合、关系与函数用一张表把三个模块串起来集合、关系、函数在大多数笔记里分成两到三章但本质上是一条链集合是原材料关系是笛卡尔积的子集函数是关系的特例。把这条链记在脑子里很多孤立的定义就能串起来。比如函数的单射、满射、双射本质上是关系满足某些限制条件函数的复合本质上是关系的合成。笔记里如果没点明这层关系你可以自己在页边补一句「关系 ⊆ 笛卡尔积函数 ⊂ 关系」。关系这一章四个性质是全部内容的骨架。建议把定义翻译成箭头图来理解自反就是每个点都有自环对称就是每条有向边都有反向边传递就是两条首尾相接的边一定有第三条边连过去。性质形式化定义箭头图特征自反对所有 aaRa每个点都有环对称aRb 则 bRa每条边都有反向边反对称aRb 且 bRa则 ab不存在两个点之间的双向边传递aRb 且 bRc则 aRc连续两条边必有第三条边这里有一个中文术语陷阱反对称不是「不对称」。不对称是「存在一对元素只有单向关系」反对称是「不允许存在一对不同元素之间有双向关系」。死记中文词特别容易翻车一定回到箭头图上去理解。等价关系和划分是关系这一章最重要的结论。一个等价关系能把集合分成若干互不相交的等价类反过来给定一个划分也能唯一构造一个等价关系。这两句话值得用费曼技巧讲给自己听。偏序关系和哈斯图则把「大小」「依赖」这类日常概念形式化后面第 5 章讲拓扑排序时你会发现那是同一件事。自检题目给你一个关系 R {(a,b) | a 与 b 同班}判断它是不是等价关系再把「同班」换成「两人身高相差不超过 1 厘米」重新判断。第二种不是等价关系它连传递性都不满足这种「差不多」的关系最坑人后面第 4 章会细说。2.3 图论与组合数学两个模块如何互相引用图论和组合数学在笔记里通常紧挨着其中一个原因是它们的工具互相借用。图论里有大量计数问题一棵树有多少条边、一个图最多有多少条边、欧拉回路的判定等组合数学里的鸽巢原理和容斥原理又经常被用来论证图的性质。读的时候不要把它们当两门课而是当一个工具箱的两层。图论部分重点不是背定义而是建立「图是一种结构」的直觉。欧拉回路的判定「所有顶点度数为偶」就是一个纯结构性的结论它和顶点的名字无关只和度数的奇偶性有关。这种「不变量」思维比任何一个具体定理都值钱。连通平面图的欧拉公式V - E F 2也是同理它说的是顶点数、边数和面数之间存在一个恒定关系不管图怎么变形都不变。组合数学部分鸽巢原理和容斥原理是两大支柱。鸽巢原理的表述简单到像废话——把 n1 个物体放进 n 个抽屉至少有一个抽屉有两个物体——但它的应用极其刁钻典型题型是「证明一群人里至少有两个人出生月份相同」。容斥原理则是处理「多个条件同时满足」的计算工具后面算并集概率、算系统故障率都会用到。把五个模块的笔记自检清单整理如下。每一行都过一遍你手里这份 PDF 值不值得精读心里基本有数了。模块笔记里必须有自测题目示例数理逻辑量词否定规则、四种证明法求 ¬(∀x∃y P(x,y)) 的等价式集合论幂集、笛卡尔积、划分求一个含 3 个元素的集合的幂集关系四性质、等价关系、偏序判断给定关系的性质并画哈斯图图论欧拉判据、树的性质证明所有树都是二分图组合数学鸽巢原理、容斥原理、递推用递推式计算网格路径数如果缺得不多可以边读边补如果整列整列地缺最好换一份完整笔记别在一棵树上吊死。笔记是工具不是藏品工具不合格就换没必要硬啃。3. 三轮阅读法把离散数学笔记读成能上手的推理能力结构摸清了接下来谈怎么读。我推荐三轮阅读法每一轮的目的不同第一轮建立问题清单第二轮通过输出来消化第三轮做反向索引。三轮加起来一份常规的离散数学笔记大约需要两周每天一小时比考前突击一周的效果稳得多。这个方法没有玄学成分核心就是一条认知规律人对「自己写过、讲过、用过的信息」记忆强度远高于「看过的信息」。3.1 第一轮速读把 PDF 变成可搜索的问题清单第一轮速读的目的只有一个把 PDF 变成你私人的问题清单。做法是给每个章节定一个时间盒比如一章 30 分钟到点就换绝不在一个证明上死磕。读的时候只看定义、定理陈述、例题的结论暂时跳过证明过程。不理解的定理在边上标记「存疑」继续往前。为什么要这样因为离散数学的章节内部是网状的一个定理看不懂往往是因为前置定理没读到不是因为你笨。第一轮的目标是把整张网走一遍知道哪里有线头等第二轮输出阶段再回头拆线头。为了快速定位我习惯先把 PDF 转成纯文本# 把整份 PDF 提取为纯文本方便搜索和定位需安装 poppler-utils # Ubuntu/Debian: sudo apt install poppler-utils # macOS: brew install poppler pdftotext -layout 离散数学笔记.pdf notes.txt # 用 grep 定位一个知识点在笔记中出现的位置 grep -n 哈斯图 notes.txt # 按页范围抽取比如只看第 10 到 20 页的集合论部分 pdftotext -f 10 -l 20 -layout 离散数学笔记.pdf set_theory.txt参数说明-layout尽量保留原始版面方便阅读但遇到表格混排的页面提取出来的文本可能会乱序这时去掉-layout用纯文本流反而更顺。-f 10 -l 20指定抽取第 10 到 20 页适合按章节拆文件。提取出来的文本能让你在一分钟内定位一个概念的上下文比在 PDF 阅读器里反复滚动翻页省力得多。速读结束后为每个章节写下 35 个问题。比如读完图论那一节写下「欧拉回路的判定为什么只看度数」「哈密顿回路为什么没有类似的简单判定」这些问题就是第二轮的工作入口。注意问题要写在纸上或 Markdown 里不要只存在脑子里因为第二轮你会需要逐条对着它们工作。3.2 第二轮定理 - 证明 - 反例三段式输出第二轮是三轮里最关键的一轮做的是输出不是输入。对每个核心定理合上笔记做三件事写定理、写证明骨架、造反例。写定理不是抄是默写成立条件一个都不能少。写证明骨架不是背整个证明而是用两三句话讲出「这个定理为什么成立」的核心思路。造反例最有意思把定理的某个条件去掉或减弱然后找一个具体反例。找不到反例就说明这个条件可能在证明里仅仅是个形式要求把你的思考过程写下来也有价值。举个最常见的例子。定义关系 R 为「两人住处相距不超过 1 公里」。这个关系是自反的自己到自己距离为 0也是对称的但它不传递A 和 B 相距 0.9 公里B 和 C 相距 0.9 公里A 和 C 可能相距 1.8 公里。这个反例一摆等价关系三个条件的独立性就一目了然了比背十遍定义都管用。第二轮的工作量比较大建议每天处理 58 个定理按周推进。产出物是每个定理的一段私人笔记可以写在纸本、记在 Markdown 里或者直接找一个朋友讲一遍。输出过的内容才是真正属于你的没输出过的只是「看过」。3.3 第三轮从习题反向索引定理让笔记变成查找表第三轮反过来从习题出发反向索引定理。具体做法是先不看笔记把章节习题做一遍。做不出来不要紧关键是把「卡在哪一步」记下来——是不知道用什么定理还是用了定理但推不下去然后带着记录翻笔记只读与这道题相关的定理和例题。这样笔记就完成了身份转变从「从头读到尾的材料」变成「按需查阅的手册」。这一步同时生成你的错题表格式很简单但很有效题号卡住的现象涉及的定理真正的错因3.7不知道第一步该用什么鸽巢原理没把「人数」和「月份」抽象成物体和抽屉4.2证明写到一半推不动数学归纳法归纳假设没在步进步骤里实际使用第三轮做完你会发现自己对笔记结构的熟悉程度远超一直刷第一遍的人。因为你在反复地「用」这份笔记而不是「看」它。错题表攒到一定规模后你会发现错因高度集中在某几个概念上那些就是你的知识盲区值得单独拉出来再做一轮三段式输出。三轮结束笔记已经不在 PDF 里了在你自己写的纸上。4. 读离散数学笔记的四个常见坑现象、原因与排查顺序以下这四个坑是我看人踩过最多次的写出来省的你再买后悔药。每个坑都按「现象 → 原因 → 解决」来拆读的时候可以对照自己当前状态中了几条就优先处理哪条。4.1 坑一只看不练把「眼熟」当成「会了」现象读的时候感觉自己全会了合上笔记做题第一道证明题就卡住。最典型的是反证法的第一步——明明知道该反证却不知道到底该否定哪个命题。原因阅读是输入做题是输出两者调用的认知通路完全不同。眼熟是输入阶段的假象大脑识别了文本的轮廓就产生了「我会了」的错觉实际上根本没法生成答案。刷一遍笔记比做一道题轻松得多所以人本能地选择前者。解决把阅读切成小块每读 23 页合上笔记在纸上默写这一节讲了哪三个要点、各是什么条件。写不全就回头补读。这不是低效恰恰是唯一能戳破眼熟幻觉的办法。记住一个判断标准能写出来才算看过能讲出来才算理解。4.2 坑二死记条件没有建立反例直觉现象背得住「等价关系是自反 对称 传递」但题目把场景换成「两人身高差不超过 1 厘米」「两点之间距离小于某个阈值」时判断就开始出错。特别容易错的是反对称经常和「不对称」混在一起。原因中文术语的表达有歧义。反对称按字面理解容易误读成「不是对称」实际定义是「只要 aRb 且 bRa就必须 ab」。死记中文词没有把定义翻译成箭头图或具体场景遇到实际问题就只能靠猜。解决给每个性质配一个正例和一个反例用箭头图画出来而不是写文字描述。判断一个给定的关系是否满足某性质时先画图、再对照定义原文不要凭语感。比如「身高差不超过 1 厘米」这个关系画三个人的身高线立刻能看到它不传递。4.3 坑三跳过证明导致换一个条件就翻车现象平时复习只看结论考试遇到底部「如果去掉连通性条件欧拉公式还成立吗」这类变体题直接懵住。这种题考察的恰恰不是结论本身而是结论对条件的依赖关系。原因定理是结论证明是告诉你这个结论为什么依赖这些条件。跳过证明等于不知道哪根柱子是承重的改一个条件就不知道会不会塌。很多同学觉得证明难读就放弃其实是把最值钱的抗风险信息丢了。解决用「条件依赖分析」的方式读证明。把证明拆成几步每步旁边标注它用到了定理的哪个条件再问自己如果这个条件不满足这一步会在哪里失败。这样分析过一遍之后变体题不再是冷门题而是白送分的题。4.4 排查一个定理读不懂时按什么顺序查原因读不懂一个定理时按下面四条顺序排查大部分情况都能定位到真正原因而不是在原地硬扛。检查定义定理里的每个名词都认识吗比如「连通平面图」里的「平面」和「连通」分别是什么含义缺一个条件定义还成立吗定义没吃透是最常见的原因。检查前置定理这个证明引用了哪个之前的结论前置定理没理解清楚当前定理必然卡住。回到笔记的前面章节把前置补上再回来。检查例题笔记里有没有配套例题有就先读例题看定理具体是怎么被使用的。很多情况下例题比定理本身好懂一百倍看懂用法之后反过来再看定理陈述会豁然开朗。检查版本口径不同教材对「树」「连通」「平面图」等概念的定义不完全一致。比如有的书定义树为「连通无圈图」有的定义为「任意两点之间存在唯一路径」。如果你手里的笔记和你参考的另一份资料口径不一致结论表述看起来冲突就是正常的。这是一种「笔记有病不是你有病」的情况不必怀疑自己。5. 笔记到代码的最后一公里离散数学在工程里的三处映射很多从业者学这门课时会问「到底有什么用」。答案不是某个公式被直接调用而是离散数学把常见问题抽象成结构让你在遇到问题时能一眼认出底下的数学模型。下面挑三处最直接的映射每一处都能在你的日常开发里找到对应物。5.1 数理逻辑与集合运算SQL 查询、布隆过滤器与集合操作谓词逻辑和 SQL 几乎是同构的。WHERE 子句就是在对每一行计算一个谓词EXISTS 对应量词NOT EXISTS 对应量词的否定。集合运算则直接对应 SQL 的并、交、差-- 学过离散数学但没学数据结构的学生集合差运算 SELECT name FROM students WHERE course 离散数学 EXCEPT SELECT name FROM students WHERE course 数据结构;逻辑说明EXCEPT就是集合论里的差集 A - B。这个查询真正有价值的地方在于它能让你意识到 SQL 里的表其实是一个集合、查询是集合运算的复合。注意不同数据库对EXCEPT的支持不一样有的需要改用NOT IN或LEFT JOIN ... WHERE ... IS NULL来模拟这种「语义相同、方言不同」的差异本身就是集合运算思想在工程落地时的边界。另一个更隐蔽的映射是布隆过滤器。它用若干哈希函数和一个位数组近似判断「一个元素是否属于集合」允许假阳性但不允许假阴性。这个设计本质上是在用集合思想解决「内存装不下全量数据」的工程约束典型应用是缓存穿透防护和恶意 URL 过滤——先判断「大概率不在」挡掉大部分无效请求真命中的再走精确查询。5.2 关系、图论与系统设计拓扑排序、并查集与最短路径偏序关系直接对应任务依赖关系。只要任务图是有向无环图就存在拓扑排序构建工具的依赖解析、服务启动顺序编排、编译器的依赖分析全是这个问题的工程形态。如果你读笔记时把哈斯图想成依赖图拓扑排序就是它的线性展开学习成本会直线下降。等价关系对应并查集。并查集做的事情是把「等价」的元素合并到同一个集合里并快速判断两个元素是否同属一个集合。这在社交关系聚类、图像连通域标记、编译器里的类型等价判定里都是核心结构。笔记里「等价关系划分集合」的定理就是并查集能工作的数学保证——并查集的合并操作本质上是在维护划分的等价关系。图论部分就更直接了。最短路径对应 Dijkstra 和 A*连通分量对应图像连通域分析欧拉路径对应巡检路线规划、文字一笔画检测。每当你面对一个「对象 对象之间的关系」的系统先问问自己能不能抽象成图抽象成图之后很多问题的解法是现成的不需要发明。5.3 组合数学与递推复杂度估算、哈希冲突与动态规划排列组合用来估算嵌套循环的执行次数鸽巢原理则决定了哈希表的宿命把 N 个元素放进 M 个桶只要 N M冲突必然发生。这不是概率问题是必然问题。理解这一点你就不会在设计哈希表时产生「能不能完全避免冲突」的幻想而是老老实实设计冲突解决策略和负载因子。容斥原理在可靠性工程里非常实用。计算多个组件至少一个出故障的概率、估算多个告警事件是否同源的并集规模都需要先对单事件概率做求和再减去交集部分。写代码的人平时不会碰到这个公式但一旦做监控系统的告警聚合分析它就会冒出来。递推关系是动态规划的直接前身。状态转移方程本质上就是「定义一个递推关系 明确边界条件」离散数学课上练的递推题练的正是这种建模能力。很多同学学动态规划觉得难不是不理解表格怎么填而是不会从问题里抽象出递推关系——这个能力在组合数学那一章就已经开始训练了。工程里能不能走远回头看大多取决于有没有建立这种「结构感」而不是记住了多少 API。6. 把离散数学笔记变成个人题库Markdown 转 Anki 的 40 行脚本三轮阅读法和错题表做完了还剩最后一公里长期记忆。我的习惯是把笔记里的定义和定理改写成问答卡导入间隔重复软件每天复习。不用做复杂的卡片结构一个 40 行的 Python 脚本就够了。先把笔记按固定格式整理成 Markdown 问答文件#!/usr/bin/env python3 # md_to_anki.py把 Q/A 文本转成可导入间隔重复软件的 CSV # 源文件格式每对 Q/A 之间用空行分隔 # Q: 等价关系需要满足哪三个性质 # A: 自反性、对称性、传递性 # # 用法python3 md_to_anki.py questions.md cards.csv import csv import sys def convert(src, dst): rows [] question None with open(src, encodingutf-8) as f: for line in f: line line.strip() if not line: continue if line.startswith(Q:): # 遇到新问题先检查上一个问题是否缺少答案 if question is not None: print(f警告问题 {question} 缺少答案已跳过) question line[2:].strip() elif line.startswith(A:) and question is not None: rows.append([question, line[2:].strip()]) question None # 文件读完做最后一次检查 if question is not None: print(f警告问题 {question} 缺少答案已跳过) with open(dst, w, encodingutf-8, newline) as f: writer csv.writer(f) writer.writerows(rows) print(f已生成 {len(rows)} 张卡片 - {dst}) if __name__ __main__: convert(sys.argv[1], sys.argv[2])逻辑说明脚本只认Q:和A:开头的行一个问题对应一个答案答案遇到下一个Q:或文件结束前必须出现否则会跳过并打印警告。csv.writer会自动处理答案里可能出现的逗号和引号不会破坏 CSV 格式。导入间隔重复软件时选择 CSV 导入分隔符选逗号第一列是问题、第二列是答案。几个参数细节。encodingutf-8保证中文不乱码如果你的系统导入后显示乱码把输出的 CSV 改成带 BOM 的 UTF-8 再试一次。答案如果需要换行在答案文本里直接写br间隔重复软件默认把字段内容按 HTML 解析。注意卡片数量不要贪多。每天新增 510 张、复习 20 张就足够了长期坚持比短期堆量有效得多。间隔重复软件的核心机制是「在快要遗忘的时候复习」半小时塞进去 50 张卡片并不会加强记忆只会让你第二天产生抵触情绪。这套流程走完你那份离散数学笔记 PDF 就不再是收藏夹里的装饰品而是一套可以持续复用的个人题库。我自己当年复习离散数学时吃够了只看不练的亏考前突击三天考完就忘。后来改成每天 20 分钟的间隔重复反而比突击稳得多而且不用在考前后悔。把它当成平时花小时间、长期有收益的事来做别等考前才想起它。希望帮到你。本文还有配套的精品资源点击获取