简介：一份覆盖离散数学核心知识体系的PDF笔记，面向计算机专业学生、考研及期末备考者，系统整理了数理逻辑、集合论、数论、计数原理、概率论、关系论、代数系统与图论八大模块。内容从命题逻辑的永真式、逻辑等价、合取范式与析取范式，到集合的运算、函数单射/满射/双射，再到数论中的整除、同余、裴蜀定理、中国剩余定理，以及计数原理中的容斥原理、鸽笼原理、排列组合与生成函数，均有清晰条目式讲解。概率论部分涵盖古典概型、随机变量分布及期望方差；关系论深入等价关系、偏序关系、闭包与传递闭包；代数系统梳理群、格、布尔代数；图论部分包含欧拉图、哈密顿图、匹配与树。笔记编排层次分明，适合对照教材查漏补缺或考前快速回顾。资源为单个PDF文档，共1个文件，包体约630KB，目录层级分明，便于按章节检索。已有2876人学习，是高效掌握离散数学概念与证明方法的实用资料。

1. 别把离散数学当文科背：这份笔记到底在帮你省什么时间

期末前两周翻开几百页的教材，发现每章都有十几个新定义、几十个公式，这种绝望感经历过的人都懂。离散数学和微积分不一样，它没有一条主线串联全部内容，八章知识彼此独立又互相渗透，靠硬背很快会在考场上翻车。这份《离散数学笔记.pdf》的价值在于把数理逻辑、集合论、数论、计数原理、概率论、关系论、代数系统、图论八块内容压缩成了一份可检索的结构化提纲，公式直接给出、推理规则按表排列，省去自己整理的时间。适合三类人：期末复习需要快速过一遍考点的本科生、备考研究生入学考试想系统梳理知识框架的考生，以及自学入门需要一个完整知识地图的初学者。

2. 八章知识体系的骨架拆解：先认清每章在解决什么问题，再谈背公式

拿这份笔记之前，建议先建立一个大前提：离散数学的每一章都对应计算机科学里的一类具体问题。数理逻辑是程序判断和推理的基础；集合论是数据结构里元素组织方式的抽象；数论是加密算法和哈希函数的数学底座；计数原理直接服务算法复杂度分析；概率论支撑随机算法和机器学习；关系论对应数据库设计和图数据库；代数系统是抽象数据类型和形式化方法的理论源头；图论则是网络、路径规划和社交关系分析的模型。带着这个视角去读笔记，每个公式都有了落点，死记硬背的压力会小很多。

2.1 数理逻辑：真值表只是起点，推理规则才是落点

笔记第一章从命题逻辑切入。命题、命题变元、五种逻辑运算符（否定、合取、析取、蕴含、双蕴含）的优先级顺序是基本功，这里容易出的问题是运算符优先级搞反导致整个表达式理解错。优先级降序为：否定 > 合取 > 析取 > 蕴含 > 双蕴含，合取比析取优先，蕴含和双蕴含在最后。成真指派和成假指派的概念服务于真值表构建，永真式和永假式是后续判断逻辑等价、语义蕴含的工具。

笔记给出了完整的常见逻辑等价式表，包括双重否定律、幂等律、交换律、结合律、分配律、德摩根律、吸收律、支配律、恒等律、排中律、矛盾律、归谬律、假言易位、假言析取和蕴含互化。其中德摩根律和蕴含互化是用得最多的两个：¬(p ∧ q) ≡ ¬p ∨ ¬q和p → q ≡ ¬p ∨ q。很多推理题做不下去，就是因为没意识到蕴含式可以转化为析取式来操作。

自然推理规则表（假言推理、取据式、假言三段论、析取三段论、附加律、化简律、合取律、消解律）是命题逻辑的核心工具。消解律p ∨ q, ¬p ∨ r ⇒ q ∨ r是很多自动化定理证明算法的理论基础，它把语义蕴含变成纯语法操作，在程序里非常好实现。笔记里给出的合取范式（CNF）和析取范式（DNF）部分，强调最大项只有一种成假指派、最小项只有一种成真指派，主范式是唯一的标准形式。实际做题时，求主范式有两种路径：真值表法和等值演算法。真值表法慢但不易出错，等值演算法快但要求对逻辑等价式极其熟练，建议第一遍用真值表法验证结果，再用等值演算法提速。

谓词逻辑部分要特别注意全称量词和特称量词的换序规则。笔记明确举了例子：∀x∃yP(x,y)与∃y∀xP(x,y)不一定等价，举例令 P(x,y) 表示 y > x，前者为真而后者为假。这个点几乎年年考，而且喜欢出成判断题。谓词逻辑的四条推理规则（全称例示、全称生成、特称例示、特称生成）在数学证明中反复使用，尤其是数学归纳法的归纳步骤，本质上就是全称生成规则的应用。

证明方法部分（直接证明、反证法、归谬法、存在性证明、任意性证伪）是整个离散数学的思维枢纽。反证法的核心是假言易位p → q ≡ ¬q → ¬p，归谬法则是证明p → F从而得出¬p。这些方法在集合论、数论、图论的证明题中会反复用到，值得在第一遍就有意识练习。

2.2 集合论与关系论：从元素到关系的层层抽象，Warshall算法是避不开的手算高峰

集合论章节从集合相等、基数/势、可数集开始。集合相等的两种判定方式（∀x(x∈A ↔ x∈B)以及A⊆B 且 B⊆A）是证明题的常用入口。势的比较引入了等势概念，康托尔-伯恩斯坦-施罗德定理说若|A|≤|B|且|A|≥|B|则|A|=|B|，这是处理无限集合等势的利器。可数集的定义、阿列夫零和阿列夫一的区别（整数集、有理数集都是阿列夫零，实数集是阿列夫一）是考研常考概念。

笛卡尔积、集合运算（并、交、补、差、对称差）和集合恒等式表格是后续概率论、关系论的直接基础。两个关于函数像的重要不等式值得留意：并集的像满足f(X∪Y) = f(X)∪f(Y)，但交集的像只满足f(X∩Y) ⊆ f(X)∩f(Y)，前者是等式，后者只是包含关系，这个差异在证明题里经常当陷阱出现。

函数部分重点在单射、满射、双射的判定。笔记给出一个关键结论：若 A 是有限非空集合，f 是从 A 到 A 的函数，则 f 是单射当且仅当 f 是满射。这个结论在有限集上成立，在无限集上不成立（比如正整数集上f(n)=2n是单射但不是满射），很多初学者在这里栽跟头。关系论章节是图的矩阵表示和闭包计算的重头戏。二元关系的性质（自反、对称、反对称、传递）判定贯穿整个章节。关系的复合运算、幂运算与矩阵乘法对应，关系的闭包（自反闭包、对称闭包、传递闭包）是高频考点。

传递闭包的 Warshall 算法是这章最大的手算难点。算法思路很清晰：对矩阵的所有中间节点 k 做迭代，如果R[i][k]和R[k][j]都为 1，则把R[i][j]也置为 1。以 Python 风格描述就是：

# 输入：关系矩阵 R（n x n），元素为 0 或 1 # 输出：传递闭包矩阵 T n = len(R) T = [row[:] for row in R] # 复制原矩阵 for k in range(n): # 枚举中间节点 for i in range(n): # 枚举起点 if T[i][k] == 1: # 起点能到中间节点 for j in range(n): # 中间节点能到终点，则起点到终点可达 if T[k][j] == 1: T[i][j] = 1

逻辑很直接：T[i][k]为 1 说明 i 到 k 有通路，T[k][j]为 1 说明 k 到 j 有通路，两者串联起来 i 到 j 就有通路。手算时最容易犯的错是只遍历一遍就结束，Warshall 算法必须按 k 从 0 到 n-1 依次迭代，每轮更新后的矩阵是下一轮的输入，这个过程要完整走 n 遍。笔记里给出的“闭包的矩阵构造”就是用来对照检查的。等价关系和偏序关系的性质差异也要记牢：等价关系必须同时满足自反、对称、传递，而偏序关系要求自反、反对称、传递。

2.3 数论与计数原理：整除同余是块硬骨头，容斥鸽笼是送分题

数论章节是这份笔记里公式密度最高的部分，也是很多学生觉得最像“数学课”的章节。整除、带余除法、同余、模 m 加/乘运算的定义是地基。模运算两条性质要刻进脑子里：(a ± b) mod m = ((a mod m) ± (b mod m)) mod m，乘法的同理。这条性质在编程里写取模运算时是隐形前提，比如计算(a + b) % m时防止中间结果溢出，就先对 a 和 b 分别取模。

裴蜀定理指出 gcd(a,b) 可以表示为 a 和 b 的线性组合，这一定理是扩展欧几里得算法的数学依据。素数理论部分，算术基本定理（唯一分解定理）是数论的基石，笔记写的n = p1^α1 * p2^α2 * ... * pk^αk这个形式在计算欧拉函数时直接用到。欧拉函数的计算公式φ(n) = n * Π(1 - 1/p)中的连乘遍历 n 的所有不同质因子，这个公式结合算术基本定理来记，比死记硬背有效得多。

中国剩余定理是必考点。解决形如x ≡ a1 (mod m1)、x ≡ a2 (mod m2)的一次同余方程组，核心步骤是令M = m1*m2*...*mk，对每个方程求出Mi = M/mi，再找Mi关于模mi的逆元ti，最后x = Σ(ai * Mi * ti) mod M。费马小定理：若 a 不是素数 p 的倍数，则a^(p-1) ≡ 1 (mod p)，它和欧拉定理a^φ(n) ≡ 1 (mod n)的差别只在模数是素数还是一般正整数，欧拉定理是费马小定理的推广。

计数原理章节的容斥原理和鸽笼原理相对独立，公式本身不复杂。容斥原理的 n=2 和 n=3 情况必须背熟，尤其是 n=3 的展开式有三组并运算和一组交运算。鸽笼原理的加强版公式⌊(n-1)/m⌋ + 1给出的是“至少一个笼子最少放多少个”的下界，应用题的难点在于识别哪边是鸽子、哪边是笼子。排列组合部分，错位排列公式Dn = n! * (1 - 1/1! + 1/2! - ... + (-1)^n/n!)，组合恒等式表格（特别是C(n,k) = C(n-1,k) + C(n-1,k-1)帕斯卡恒等式）技巧性强，球盒问题表格则把九种组合情况全部归纳出来：球是否可辨、盒子是否可辨、盒子是否可空，每种情况有对应公式，做题时先判定这三属性再选公式，能省一半思考时间。

生成函数部分，普通型母函数和指数型母函数的区别要抓住核心：组合问题用普通型，排列问题用指数型。笔记里给出的常用普通型母函数表（(1+x)^n对应组合数，1/(1-x)对应全 1 序列等）在解递推问题时非常实用。

2.4 概率论：离散概率难在把事件关系转成集合运算

这一章和前面的集合论、计数原理是联动的。笔记先列随机事件的基本概念表（随机试验、样本空间、基本事件、必然事件、不可能事件、互斥事件、对立事件、独立事件、完备事件组），然后强调随机事件间的关系和运算完全符合集合运算——这是打通知识点的关键：事件就是样本空间的子集，事件的并、交、差就是集合的并、交、差，概率函数 P 就是定义在事件上的集合函数。

概率的公理化定义里的三条公理（非负性、规范性、可列可加性）和四条重要性质（P(∅)=0、P(A-B)=P(A)-P(AB)、P(Ā)=1-P(A) 加法公式）构成了所有概率计算的规则基础。条件概率和贝叶斯公式在这份笔记里虽然着墨不多，但全概率公式和贝叶斯公式的框架都给出来了。做这类题不需要创造力，只需要把完备事件组的划分找对。

古典概型和几何概型的区分：等可能且样本空间有限时用古典概型，几何概型用“几何度量比值”来算概率。古典概型计算的核心是排列组合计数，所以计数原理那章的球盒问题表格在这里会被高频调用。几何概型的典型题型是“随机向区域投点，求落点落在子区域的概率”，直接用面积比或体积比。

随机变量部分的离散型分布（0-1 分布、二项分布、泊松分布）和连续型分布（均匀分布、指数分布、正态分布）需要掌握的是概率分布、期望和方差三件套。离散型和连续型的数字特征计算方式不同：离散型用和式E(X)=Σxi*pi，连续型用积分E(X)=∫xf(x)dx。随机变量函数的分布有一个典型坑：求Y = g(X)的分布时，不能简单地把 X 的分布参数直接代入表达式，需要先求出 Y 的分布函数再做处理。笔记中这块内容可以结合分布函数法来理解，具体做题时可以对照参考教材做两遍，第一遍按笔记思路做，第二遍用分布函数法核对。

2.5 代数系统与图论：群论抽象程度最高，图论考点最碎

代数系统章节，笔记从代数系统的定义出发（集合 + 运算 + 封闭性），随后进入群论。群的四条公理（封闭性、结合律、单位元、逆元）是判定群的唯一标准。群的阶和元素阶是两个容易混淆的概念：群的阶是集合元素个数，元素的阶是该元素自乘到单位元所需的最小次数，两者数值相等的情况出现在循环群中。子群判定用“非空子集 H 对成群运算封闭且逆元在 H 中”来验证即可。

陪集、群同态、群同构的定义笔记里都有，克莱因四元群作为最小非循环群的例子值得单独记一遍，它是理解“不是所有群都是循环群”的最直观反例。格论部分讲了偏序格和代数格的等价性，布尔代数的定义、布尔恒等式、有限布尔代数的表示定理则是后续学习数字逻辑课程的理论源头。

图论章节是内容最碎的一章。图的描述（顶点集、边集、邻接矩阵）、图的关系（邻接、关联）、图的连通性属于基础送分题。欧拉图和哈密顿图的区分是高频失分点：欧拉通路/回路看的是每条边走且只走一次，判定条件是奇度顶点个数（0 个或 2 个）；哈密顿通路/回路看的是每个顶点经过且只经过一次，判定条件没有一般性的简单定理，只能通过“满足必要条件”来排除。匹配问题中的霍尔婚姻定理在组合学中很重要，交错路径和可增广路径是寻找最大匹配的算法基础。树部分要掌握树的等价定义、有根树和二叉树的结构、生成树的计数（Cayley 公式n^(n-2)），这些是数据结构课程的直接前置内容。

3. 从翻书到刷题：一份可执行的三轮学习路径

笔记里公式密度高，顺序很重要。建议分三轮推进，每一轮有不同的目标和操作方式。

3.1 第一轮：通读笔记建立知识地图，标记所有公式位置

第一轮不追求掌握每个公式，任务是搞清全书的章节结构和每个公式在哪个位置。通读一遍笔记，把自己不熟悉的公式用荧光笔标出来，不熟悉的定义在旁边打一个问号。这一轮的速度大概是每天两章，四天过完全书。通读时重点关注每章开头的“相关概念”列表，这些是后续所有内容的公共基础。过程中遇到不会的很正常，第一轮的目的只是混个脸熟，后面两轮才是真正吃透。

3.2 第二轮：按章做证明题专项训练，重点攻数论和代数系统

第二轮以证明题为主。离散数学的考试题型里，证明题占比通常在 30%-40%，其中集合等式、数论同余、群论子群判定是三个高频出题点。每个考点找两三道典型题，按笔记中的方法逐步推导。这一轮建议每天只攻一个章节，宁可慢但不能跳。做证明题的关键动作是：每次写完证明后，回到笔记里找对应的公式或定理，确认每一步变形的依据。这会把理论知识和题目之间连成一条链，而不是各自孤立。

3.3 第三轮：混合刷题加错题回查，用笔记目录当检索索引

第三轮进入综合刷题阶段，目标是把跨章节的知识点串联起来。比如概率论的综合题往往同时用到计数原理的排列组合和数论的整除性质，关系论和图论的综合题经常用矩阵表示加图连通性分析。刷题时遇到不会的题目，不翻答案，先回笔记里找对应章节的公式和例题，尝试自己推。笔记的八章结构就是天然索引，查找速度快且定位准确。

3.4 复习时间分配建议表

这个总量是 16 天，每天 2-3 小时。如果时间只剩一周，压缩方式是合并第 1 和第 2 天、合并第 6 和第 7 天、图论只保留连通性和树的部分。

4. 离散数学避坑实录：六个典型翻车场景与排查方向

以下六条踩坑记录来自教学答疑过程中学生反复犯的错误，每条都按“现象 → 原因 → 解决”展开，可作为自查清单。

4.1 现象：真值表会画，自然推理题永远卡在第一步

画真值表很熟练，但遇到“从前提推出结论”的证明题就不知道第一步该写什么。原因在于没有把自然推理规则表真正当作工具来用，对规则的使用条件不熟。解决办法：做题前把假言推理、取据式、假言三段论、析取三段论这四条最常用的规则抄在草稿纸边上，每推一步标注用的是哪条规则和哪一步前提，强迫自己显式写出推理依据。

4.2 现象：全称量词和特称量词直接换序，推理结论出错

看到∀x∃yP(x,y)就直接写成∃y∀xP(x,y)，被反例一票否决。原因是没有意识到底两个量词的管辖范围对结论真值的影响。解决办法：记住笔记里那个 y > x 的反例——在整数范围内，∀x∃y(y>x)是真的（每个 x 都能找到更大的 y），∃y∀x(y>x)是假的（不存在一个 y 比所有 x 都大）。遇到量词换序问题，先用反例思维检验，不要凭感觉。

4.3 现象：集合势的比较靠直觉判断，碰到无限集合就懵

判断题里给了一个无限集合和一个有限集合的映射关系，直接下结论说无限集合势更大。原因是对“等势”的定义掌握不牢，忘了两个集合等势的本质是存在双射。解决办法：严格按定义来，构造双射是证明等势的唯一途径。比如自然数和整数等势，构造对应规则f(n) = n/2（n 为偶数）、f(n) = -(n+1)/2（n 为奇数）就能得到双射。

4.4 现象：Warshall 算法手算过程反复出错，传递闭包结果不唯一

算完一遍传递闭包后，对照答案发现少了一条边，或者矩阵某几位不对。原因通常是只遍历了部分中间节点就停止了，或者在进行到第 k 轮时误用了初始矩阵而不是上一轮的结果。解决办法：严格按照 k = 0, 1, …, n-1 的次序做 n 次完整遍历，每轮结束后在纸上划掉当前行和列，全程使用上一轮更新后的矩阵。算完后做一步自检：如果矩阵中R[i][k]=1且R[k][j]=1但R[i][j]=0，说明闭包不是传递的，算法必然有漏。

4.5 现象：群论里子群判定总是漏条件，循环群生成元找不全

判断非空子集 H 是否是子群时，只验证了封闭性就下结论。原因是对子群定义的三条要求（包含单位元、每个元素有逆元仍在 H 中、封闭性）记不全。解决办法：把判定条件固定成三步走——先验证单位元在 H 中，再验证任一元素逆元在 H 中，最后验证任意两个元素运算结果仍在 H 中。循环群的生成元问题，用“生成元个数等于 φ(n)”来检查，如果 n 阶循环群找出的生成元数量少于 φ(n)，一定是漏了。

4.6 现象：计数题分不清用排列还是组合，球盒模型套错公式

题目中“元素各不相同”和“分组内部不排序”两个条件同时出现时，公式选错导致结果差一个系数。原因是对球盒问题的三个判定维度（球是否可辨、盒子是否可辨、盒子是否可空）考虑不完整。解决办法：做题前先在这三个维度上各打一个勾或叉，再对照笔记里的球盒模型表格选公式。分组分配问题中，均匀分组需要除以组数的阶乘来消除重复计数，这个容易漏。

5. 把笔记用成工具箱：公式索引自测法与错题定位技巧

笔记读到最后阶段，最有效的使用方式不是整本重读，而是把它变成一个可以快速检索的工具箱。我一般会花半天时间把笔记里的公式和定理全部摘出来，做成一份带页码和章节号的索引卡，按数理逻辑、集合论、数论、计数、概率、关系、代数、图论的顺序编号。到复习后期，我只看索引卡上的公式名，如果能直接说出公式内容和适用条件，就算过关；说不出来就翻到对应页重新过一遍。

5.1 公式索引卡制作法

每张卡片只写三样东西：公式或定理的名称、完整表述、适用场景。举几个例子：欧拉定理的卡片写“若 gcd(a,n)=1，则 a^φ(n) ≡ 1 (mod n)，适用于模运算化简和加密算法”；错位排列的卡片写“Dn = n! Σ((-1)^k/k!)，适用于‘每个元素都不在自己原位置’的排列计数”；鸽笼原理加强版的卡片写“⌊(n-1)/m⌋ + 1，适用于证明存在性问题”。卡片全部做完大约 60-80 张，随身携带，等车和排队的碎片时间翻一轮，效果好于大块时间干坐着背。

5.2 用“定理-反例-应用”三步法验证掌握度

对一个定理，能背出来只是第一步。真正检验是否理解的方法是同时说出它的一个反例和一个应用场景。比如偏序关系的反例是“整数集合上的整除关系不是全序关系”（因为 2 和 3 互相不整除），应用场景是“拓扑排序中依赖关系的建模”。如果能把反例和应用都脱口而出，这个知识点基本不会在考场上掉链子。

5.3 错题定位的逆向检索

错题整理不按题目顺序记，按错误的本质原因分类。比如把“量词换序错误”“集合运算分配律用错”“子群判定漏条件”各归一类，每类标注对应的笔记页码。第二次复习时直接看错误类别列表，而不是重做整套题。这样复习效率高的原因在于：错题的本质原因往往集中在少数几个定理的理解偏差上，针对性修正比广撒网刷题有效得多。

这套学习法的底层逻辑是离散数学本身就是一门“工具学科”——学它的目的不是欣赏数学之美，而是为将来的算法设计、数据库理论、编译原理提供语言和框架。从期末备考的角度看，吃透这份笔记的八章内容，覆盖所有核心考点没有问题。从那以后我每学一门新课程，都会先把知识点压缩成一张索引卡，再靠反例和应用来验证理解，这套习惯帮我省掉了大量复习时的无用功。希望帮到你。

本文还有配套的精品资源，点击获取