简介一份覆盖离散数学核心知识体系的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 风格描述就是# 输入关系矩阵 Rn 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)的差别只在模数是素数还是一般正整数欧拉定理是费马小定理的推广。计数原理章节的容斥原理和鸽笼原理相对独立公式本身不复杂。容斥原理的 n2 和 n3 情况必须背熟尤其是 n3 的展开式有三组并运算和一组交运算。鸽笼原理的加强版公式⌊(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)帕斯卡恒等式技巧性强球盒问题表格则把九种组合情况全部归纳出来球是否可辨、盒子是否可辨、盒子是否可空每种情况有对应公式做题时先判定这三属性再选公式能省一半思考时间。生成函数部分普通型母函数和指数型母函数的区别要抓住核心组合问题用普通型排列问题用指数型。笔记里给出的常用普通型母函数表(1x)^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 复习时间分配建议表章节建议天数核心产出易错点数理逻辑2能熟练用等值演算求主范式量词换序集合论与关系论3Warshall算法手算正确交集像的包含关系数论3中国剩余定理完整解法欧拉函数连乘范围计数原理2球盒模型九种情况判定错位排列公式推导概率论2全概率公式解题套路随机变量函数的分布代数系统2子群判定与陪集分解群阶和元素阶混淆图论2欧拉/哈密顿判定条件哈密顿图必要条件误当充分条件这个总量是 16 天每天 2-3 小时。如果时间只剩一周压缩方式是合并第 1 和第 2 天、合并第 6 和第 7 天、图论只保留连通性和树的部分。4. 离散数学避坑实录六个典型翻车场景与排查方向以下六条踩坑记录来自教学答疑过程中学生反复犯的错误每条都按“现象 → 原因 → 解决”展开可作为自查清单。4.1 现象真值表会画自然推理题永远卡在第一步画真值表很熟练但遇到“从前提推出结论”的证明题就不知道第一步该写什么。原因在于没有把自然推理规则表真正当作工具来用对规则的使用条件不熟。解决办法做题前把假言推理、取据式、假言三段论、析取三段论这四条最常用的规则抄在草稿纸边上每推一步标注用的是哪条规则和哪一步前提强迫自己显式写出推理依据。4.2 现象全称量词和特称量词直接换序推理结论出错看到∀x∃yP(x,y)就直接写成∃y∀xP(x,y)被反例一票否决。原因是没有意识到底两个量词的管辖范围对结论真值的影响。解决办法记住笔记里那个 y x 的反例——在整数范围内∀x∃y(yx)是真的每个 x 都能找到更大的 y∃y∀x(yx)是假的不存在一个 y 比所有 x 都大。遇到量词换序问题先用反例思维检验不要凭感觉。4.3 现象集合势的比较靠直觉判断碰到无限集合就懵判断题里给了一个无限集合和一个有限集合的映射关系直接下结论说无限集合势更大。原因是对“等势”的定义掌握不牢忘了两个集合等势的本质是存在双射。解决办法严格按定义来构造双射是证明等势的唯一途径。比如自然数和整数等势构造对应规则f(n) n/2n 为偶数、f(n) -(n1)/2n 为奇数就能得到双射。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 错题定位的逆向检索错题整理不按题目顺序记按错误的本质原因分类。比如把“量词换序错误”“集合运算分配律用错”“子群判定漏条件”各归一类每类标注对应的笔记页码。第二次复习时直接看错误类别列表而不是重做整套题。这样复习效率高的原因在于错题的本质原因往往集中在少数几个定理的理解偏差上针对性修正比广撒网刷题有效得多。这套学习法的底层逻辑是离散数学本身就是一门“工具学科”——学它的目的不是欣赏数学之美而是为将来的算法设计、数据库理论、编译原理提供语言和框架。从期末备考的角度看吃透这份笔记的八章内容覆盖所有核心考点没有问题。从那以后我每学一门新课程都会先把知识点压缩成一张索引卡再靠反例和应用来验证理解这套习惯帮我省掉了大量复习时的无用功。希望帮到你。本文还有配套的精品资源点击获取