简介《离散数学及其应用》第八版电子版面向计算机科学与信息科学专业学生、研究人员及从业人员也可供准备相关课程考试或补强数学基础的读者使用。内容围绕离散对象及其关系展开帮助读者系统掌握逻辑与证明、集合、关系与函数、图论、树、递归关系、组合数学、数论、代数结构等核心知识并理解其在计算机网络、数据库、计算机图形学、人工智能与编程语言中的典型应用。资源包为1个PDF文件大小约9.92MB便于在电脑或平板上阅读检索书中配有大量例题与习题适合课堂同步学习、考前复习和概念查阅。目前已有1924人学习或下载说明该版本在离散数学学习群体中具有一定参考价值。对于需要一本体系完整、内容权威的英文原版教材的读者这份电子版可作为长期备查的学习资料。1. 离散数学到底是什么一堆一个一个跳的数字背后的学问先问一个很日常的问题六位数的手机解锁密码一共有多少种可能如果你脱口而出一百万那你刚刚用了一次离散数学。这个问题里没有平滑变化的曲线只有一个个分开的、数得过来的状态。离散数学通俗地说就是研究一个一个跳的数学研究对象是分散的、可数的关系是明确的、能判定真假的。它和微积分那条路子正好相反——微积分盯着连续变化的曲线琢磨无限接近离散数学盯着集合、整数、逻辑命题、图、树这些数得清的东西琢磨它们怎么连、怎么排、怎么证、怎么数。为什么值得搞懂因为计算机内部的世界本身就是离散的电平只有高和低数据是一串有限的 0 和 1程序状态是一步一步跳过去的。描述这个世界的语言就是离散数学。2. 计算机专业为什么绕不开它四件必须被解决的问题很多人对离散数学的第一印象是证明题——满屏的 ∀、∃、≡看上去和写代码毫无关系。真上手做项目才会发现它处理的恰恰是工程里最容易被含糊过去的那几件事条件写得对不对、算法快不快、结果会不会撞车、数据传出去安不安全。这四件事刚好对应教材里四块最硬的内容。2.1 把这句话对不对说清楚命题逻辑与布尔代数程序里最常见的动作是判断。if后面那串条件本质上是一个逻辑表达式而逻辑表达式有一套严格的化简规则。教材开篇讲的命题逻辑就是把这套规则摆到台面上命题只有真和假两种取值与、或、非、蕴含是联结词把所有取值组合列成一张表就是真值表。两个表达式如果在真值表的每一行结果都一样它们就叫逻辑等价。这件事听起来很数学落到代码里却天天在发生。最典型的是德摩根律非(A 且 B)等于非 A 或 非 B。看上去只是符号游戏但它直接决定了你写的条件判断能不能少一层嵌套。# 德摩根律not (A and B) 等价于 (not A) or (not B) def check_v1(is_admin, is_owner): # 写法一不是管理员 且 拥有者 return not (is_admin and is_owner) def check_v2(is_admin, is_owner): # 写法二不是管理员或者不是拥有者 return (not is_admin) or (not is_owner) # 把四种输入组合全跑一遍验证两种写法结果始终一致 for a in (True, False): for b in (True, False): assert check_v1(a, b) check_v2(a, b) print(四种输入组合下两种写法结果完全一致)这段代码没有任何技巧它做的事就是枚举真值表。a和b各取真、假两种值一共四种组合逐一比对两个函数返回值。四个都对上就说明这两个表达式逻辑等价选哪个只影响可读性不影响正确性。参数说明也很简单is_admin、is_owner是两个布尔入参代表两个原子命题assert在断言失败时会直接抛异常等于帮你自动跑完了那张真值表。到了教材后半部分的布尔代数同一套东西换了个面貌变量还是只有 0 和 1运算还是与、或、非但目标变成了用最少的门电路实现同一个真值表。芯片设计里那些化简步骤思路和你把三层if压成一行判断是一样的——只不过省下来的是晶体管不是代码行数。提示判断条件一旦超过三个布尔变量人眼就容易看错。这时候别靠感觉画一张真值表或者写段穷举比盯着屏幕猜快得多。2.2 说清跑得快不快增长函数与算法复杂度第二个绕不开的问题是性能。同样一个需求写法 A 在数据量一万时飞快到一百万时直接卡死这种事几乎每个开发者都遇到过。要提前判断谁会卡死就需要一套描述增长速度的语言也就是教材里的大 O、Ω、Θ 记号。它的核心思想非常朴素不看具体跑多少毫秒只看输入规模翻倍时工作量大概涨几倍。常数级 O(1) 不随规模变对数级 O(log n) 每翻一倍规模只多一点点线性级 O(n) 同比例涨平方级 O(n²) 规模翻十倍工作量翻一百倍。这套记号的好处是摆脱了机器性能的干扰——不用真的跑一遍看代码结构就能估出来。一个能立刻感受到差别的例子是查找。在一百万个有序整数里找一个数挨个比对最坏要一百万次二分查找每次砍掉一半二十次左右就定位了。def binary_search(sorted_list, target): low, high 0, len(sorted_list) - 1 steps 0 # 记录比较了多少轮 while low high: steps 1 mid (low high) // 2 # 每次砍掉一半区间 if sorted_list[mid] target: return mid, steps elif sorted_list[mid] target: low mid 1 # 目标在右半边 else: high mid - 1 # 目标在左半边 return -1, steps data list(range(1_000_000)) # 一百万个有序整数 print(binary_search(data, 999_999)) # 最坏情况也就二十来次比较low和high是当前搜索区间的两个端点mid取中点。每次比较之后区间长度缩一半所以循环次数是 log₂n 量级。steps变量只是拿来验证这个结论实际使用可以去掉。把常见复杂度放在一起对比量级差异会非常直观复杂度一亿次操作所需的规模感受典型场景O(1)一步到位哈希表取值、数组下标访问O(log n)二十几步二分查找、平衡树查询O(n)一亿步扫一遍遍历数组、单层循环O(n log n)约二十亿步归并排序、堆排序O(n²)一亿亿步基本不可行双重循环、朴素字符串匹配这张表最实用的地方在于它帮你在动手写之前就排除掉不可行的方案。数据量到千万级还在写双重循环那不是优化问题是方向问题。性能调优最怕玄学而复杂度分析恰好是反玄学的那部分。2.3 数得清才不会翻车计数、鸽巢原理与概率第三个问题是有多少种可能。这听起来像奥数题实际用途比想象中密得多密码强度评估、哈希冲突预判、抽样测试的覆盖率估算、接口幂等键的碰撞概率背后都是排列组合和概率。先看一个不讲道理但极其好用的结论——鸽巢原理n 个笼子放 n1 只鸽子必有一个笼子里至少两只。它简单到像废话可一旦用上很多会不会撞的问题立刻有了答案。哈希表的桶数量固定元素个数一旦超过桶数冲突就是必然事件不需要讨论运气。忽略闰年的情况下366 个人里必然有两个人生日相同因为一年只有 365 天。更有意思的是它的弱化版365 天里只要有 23 个人至少两人同生日的概率就已经过半。这个结论常被叫做生日悖论它反直觉的地方在于——我们习惯拿某个人和我同生日去想而真正该算的是任意两人配对配对数随人数是平方增长的。def same_birthday_probability(k, days365): # 先算“所有人都不撞”的概率365/365 * 364/365 * ... p_all_different 1.0 for i in range(k): p_all_different * (days - i) / days # 用 1 减去它就是“至少撞一次”的概率 return 1 - p_all_different print(round(same_birthday_probability(10), 3)) # 约 0.117 print(round(same_birthday_probability(23), 3)) # 约 0.507 print(round(same_birthday_probability(50), 3)) # 约 0.970循环里第 i 次乘的是(days - i) / days意思是前 i 个人都不重样第 i1 个人还得避开前面 i 个日期。k是人数days默认 365改成 1000 就能模拟其他取值空间的碰撞场景——比如一串短 ID 在数据库里撞车的概率。注意概率算出很低和不会发生是两回事。系统调用量足够大时百万分之一的碰撞每天都会来一次这就是很多线上事故的来源。2.4 让数据敢往外传数论与密码学的底座第四个问题是安全。教材里数论那一章看似最纯数学整除、模运算、素数、最大公约数、同余方程。但这些概念恰好是现代密码学的砖头——公钥加密依赖两个大素数相乘容易、把乘积分解回去极难这个不对称性而整个加密解密流程全是模运算。模运算的理解门槛其实很低它就是钟表算术9 点过 5 小时是 2 点因为对 12 取模。计算机里所有定长整数运算都是这个逻辑溢出回绕不是 bug是模运算的自然结果。def gcd(a, b): # 辗转相除每轮把 (a, b) 换成 (b, a mod b)直到余数为 0 while b: a, b b, a % b return a def modexp(base, exp, mod): # 快速幂把指数按二进制拆开边乘边取模避免大数爆掉 result 1 base % mod while exp: if exp 1: # 当前二进制位是 1就把它乘进结果 result result * base % mod base base * base % mod # 底数自乘对应指数翻倍 exp 1 # 指数右移一位 return result print(gcd(48, 18)) # 6 print(modexp(7, 222, 11)) # 5gcd里最妙的是那个循环每一轮都把较大的数换成余数规模迅速缩小几轮就到底。modexp则是把指数看成二进制从低位往高位扫每一位决定要不要把当前的底数乘进结果。第二个打印结果是 5——因为 7 的 10 次方对 11 取模等于 1指数 222 对 10 取余是 2最后等价于算 7 的平方对 11 取模得 5。这两段代码加起来不到二十行却把公钥体系的两块基石都演示了求最大公约数决定密钥是否合法模幂运算决定加密解密怎么算得快。教材里的推导更完整但先看懂这两段代码再回头看公式就不会觉得那堆符号是天上掉下来的。3. 这本教材是怎么排的十三章其实是一条递进的路翻开目录十三章看起来像十三座独立的山头实际上它们有明确的先后关系先把话说清楚再把对象装起来然后学会算、学会证明最后用这些工具去描述连接和结构。第 8 版沿用了这个骨架每章开头给概念、中间塞大量例子、章末配分级习题。3.1 起点先把话讲到没有歧义第 1 章第一章讲逻辑与证明命题逻辑、逻辑等价、谓词与量词、嵌套量词、推理规则、证明方法。它像是整本书的语法课。为什么放最前面因为后面每一章都要用到定义—定理—证明这套表达方式。集合相等的证明、图同构的证明、归纳法的证明用的都是这里的推理规则。对写代码的人来说这一章最有价值的其实是量词。∀对所有和∃存在这两个符号逼着你把某些情况下可以和所有情况下都必须分清楚。嵌套量词的顺序一换意思就完全变了——每个人都有一个母亲和有一个人是所有人的母亲结构一样真假天差地别。写接口文档、写断言、写测试用例时这种精确性直接决定需求有没有被理解错。3.2 打底把对象装进盒子第 2 章第二章处理集合、函数、序列与求和、集合的基数、矩阵。这一章像是给后面所有内容准备容器图要用顶点集和边集定义关系是笛卡尔积的子集概率是在样本空间上定义的函数递归式要用求和符号写出来。集合运算并、交、差、补、笛卡尔积看起来最基础但它的思维习惯很值钱把一堆东西当成一个整体来处理。数据库里的表、程序里的标签集合、权限系统里的角色都是这个思路。而函数那一节强调的每个输入对应唯一输出是后面理解哈希、映射、状态机的关键前提。3.3 中段从能算到敢说它永远对第 3、4、5 章这三章是全书的腰。第 3 章讲算法与复杂度把快慢变成可比较的量第 4 章讲数论与密码把模运算、素数、同余方程一路推到加密应用第 5 章讲归纳与递归包括强归纳、良序性、递归定义、结构归纳、递归算法和程序正确性。第 5 章值得单独说一句。递归在编程里是常用手法但很多人只会写出来能跑说不出为什么它一定收敛、一定正确。数学归纳法给的正是这个答案验证基础情况成立再证明若第 k 步成立则第 k1 步也成立整条链条就都立住了。程序正确性那一节更进一步用前置断言和后置断言去描述这段代码到底承诺了什么。血泪经验是线上出的那些诡异 bug追到根上常常是某段递归的边界条件没被认真证过。3.4 数量感数得清、算得准第 6、7、8 章第 6 章讲计数基础、鸽巢原理、排列组合、二项式系数第 7 章讲离散概率、条件概率、贝叶斯定理、期望与方差第 8 章讲递推关系、生成函数、容斥原理这些进阶工具。这三章连起来看解决的是一类问题当可能性多到无法枚举时怎么算出准确的数字。递推关系尤其典型——很多算法的运行时间本身就写成递推式比如分治法把问题对半拆开解出这个递推式才能说清它到底是 O(n log n) 还是 O(n²)。生成函数听起来抽象本质是把一个数列打包成一个多项式用代数运算代替繁琐的逐项推导。3.5 结构感谁和谁连着第 9、10、11 章第 9 章讲关系及其性质、表示方法、闭包、等价关系与偏序第 10 章讲图、图的术语、图的表示与同构、连通性、欧拉与哈密顿路径、最短路径、平面图、图着色第 11 章讲树、树的遍历、生成树与最小生成树。这三章是应用密度最高的部分。社交网络是图任务依赖是图路由是图编译器里的语法树是树文件系统是树决策过程是树。等价关系对应分类偏序关系对应分层图着色对应资源分配不冲突。很多看上去毫不相干的业务问题一旦抽象成图或树就会掉进已经被人研究透了的解法里。3.6 到底层摸到硬件的边第 12、13 章第 12 章讲布尔函数、布尔表达式、逻辑门、电路最小化第 13 章讲语言与文法、有限状态机、图灵机等计算模型。这两章的位置很有意思前面十一章是从现实问题往数学抽象走这两章反过来从抽象往物理实现走。逻辑门就是布尔运算的物理形态有限状态机则是对有状态的系统最简洁的描述方式——登录流程、订单状态、协议交互都能画成状态图。理解了状态机再看那些状态流转混乱的系统会立刻明白问题出在哪。4. 最容易混的五个地方这些概念到底差在哪学离散数学最容易踩的坑不是看不懂而是看着都懂一用就串。下面五组概念是初学者最容易糊在一起的地方。每组都按同一个思路拆先说你混成了什么再说为什么容易混最后给一条能立刻用的区分标准。4.1 离散数学和高等数学一个走台阶一个走滑梯易混点把离散数学当成高等数学的简化版觉得学完微积分再学它应该很轻松。为什么混两门课都在讲数学都用符号和证明考试都让人头疼名字听上去还像一对。怎么区分看研究对象连不连续。高等数学微积分研究连续量函数在某点附近怎么变化、曲线下的面积怎么算核心工具是极限。离散数学研究可数的、分离的对象整数值、有限集合、图、逻辑取值核心工具是计数、归纳和构造性证明。一个走滑梯可以滑到任意近的地方一个走台阶只能一级一级跳中间没有半级。这条区别决定了它们服务的技术领域不同连续量的数学支撑信号处理、数值计算、物理仿真离散的数学支撑算法、数据结构、编译原理、数据库理论。所以计算机专业把离散数学列为核心课而微积分更多是通识基础。4.2 集合、序列、多重集花括号、圆括号和允许重复易混点看到{1, 2, 3}、(1, 2, 3)、[1, 1, 2]觉得是同一类东西随便混用。为什么混它们都能表示一组元素日常说话里也不太区分三个数和这三个数排成的序列。怎么区分抓住两个维度——有没有顺序、允不允许重复。集合用花括号无序且去重{1, 2}和{2, 1}是同一个集合。序列用圆括号或尖括号有序且允许重复(1, 2)和(2, 1)是两个不同的序列。多重集允许重复但不管顺序适合描述每种东西有几个。结构有序允许重复典型用途集合否否标签集合、去重后的 ID 池序列是是数组、字符串、执行日志多重集否是词频统计、库存计数有序对 / 元组是是坐标、数据库记录判断标准很实用如果你需要交换两个元素的位置而结果应该不变那它是集合如果位置一换意思就变了那它是序列。4.3 关系、函数、等价关系三种配对规则的层级易混点把关系、函数、映射、等价关系当成四个并列的概念记下来结果越记越乱。为什么混它们确实是层层包含的教材里又分散在不同章节第一次学时很难看出从属结构。怎么区分用配对的自由度来排。关系最宽从一个集合到另一个集合的任意配对一个元素可以连多个。函数是关系里更严格的一种每个输入必须且只能对应一个输出不允许一对多也不允许有的输入没人管。映射基本可以当成函数的同义词只是语境偏抽象。等价关系是在关系的基础上再加三条性质自反、对称、传递。分清之后就能体会它们各自的价值函数适合描述计算你给我输入我给你确定结果等价关系适合描述分类它天然把集合切成一堆互不相交的等价类比如同余把整数分成若干类同一城市把人分成若干组。而偏序关系自反、反对称、传递描述的则是层级任务依赖、版本新旧、包含关系都是偏序。函数和等价关系最大的区别在于函数是多对一也可以的指向等价关系是对称的双向归类。4.4 图、树、生成树连通和环的差别易混点把树当成一种图记住就完事看到生成树又以为它是另一种树。为什么混三者确实都是图论对象名字上也没有明显提示而且画出来的样子经常都是点和线。怎么区分按约束的严格程度排。图最自由一堆顶点加一堆边可以成环可以不连通。树是加了硬约束的图连通且没有环任意两个顶点之间有且只有一条路径。森林更宽一点没有环但不一定连通可以看成若干棵树并排。生成树则不是一种新的树而是某张连通图里挑出来的那棵树——它包含原图所有顶点边是原图的子集并且恰好能连通所有点。这条区分在实际问题里很值钱。如果一个需求的关键是不能有环路那是树或森林的结构如果是要在所有点之间铺线且总成本最低那是最小生成树问题如果点之间可以有多条路径那就是普通图得用最短路径算法而不是树的结构。4.5 归纳法与递归一个负责证一个负责算易混点以为归纳法和递归是同一件事的两种叫法写递归函数时说自己在用归纳法。为什么混两者形式高度相似都是从基础情况出发一步步往上推而且常常结对出现。怎么区分归纳是证明工具递归是定义与计算方式。归纳法用来论证一个命题对所有自然数成立先证 n1 时成立再证若 nk 成立则 nk1 也成立于是整条链都成立。递归则是把一个大问题拆成同类型的更小问题来求解比如阶乘定义成 n! n × (n-1)!边界是 0! 1。关系在于递归定义要成立通常靠归纳法来保证递归算法的正确性也要靠归纳法来证明。但两者的产出完全不同——归纳法产出一个结论成立的保证递归产出一个能跑出结果的算法。写递归时真正该问自己的是两件事边界情况真的能停吗每一层有没有真的变小。这两个问题恰恰是归纳法逼你想清楚的部分。5. 什么时候该翻它什么时候别硬啃判断一份教材该不该放在手边标准不在于它有多权威而在于它能回答你哪类问题。这本第 8 版的定位很清楚它是一本系统性的入门到进阶教材覆盖逻辑与证明、基本结构、算法、数论与密码、归纳与递归、计数、概率、关系、图、树、布尔代数、计算模型。它擅长的场景和吃力的场景其实相当分明。你的处境建议动作优先翻期末或考研复习按章末关键词和分级习题倒推重点第 1、6、9、10 章转行补计算机基础只补工作里真用得上的部分第 3、10、11 章做权限、推荐、网络类需求直接查关系与图的结构第 9、10、11 章写文档要引用严格定义把它当定义来源别自己造词对应章节开头想搞清楚加密为什么安全从模运算一路读到同余方程第 4 章面试前补复杂度分析只读增长函数那一节配合例子第 3.2、3.3 节表格右边那一列最值得留意它提示了一个使用习惯——不要按顺序从头读到尾。教材的顺序是为教学编排的而你的问题是按需冒出来的。带着一个具体问题进去翻到对应章节读完概念和例题就走效率比通读高得多。电子版在这件事上有天然优势关键词一搜定义、例题、习题解析就在附近跳读成本几乎为零。不适合硬啃的情况也得说清楚。如果你想要的是一份三天速成这本书会让你失望它的价值恰恰在于慢——每个结论都给理由每类问题都给多个例子。如果数学基础特别薄弱一上来就啃第 4 章数论和第 8 章生成函数很可能连续翻车不如先在第 1、2 章把逻辑和集合的表达习惯养起来。还有一种常见误用把它当算法手册查。它讲的是概念和证明具体的工程实现、框架 API这里不会有。从那以后我每次遇到这个方案到底稳不稳的问题都强制自己做一遍很土的动作把它翻译成集合、关系或者图然后在纸上写两行——我要证明的到底是什么边界情况停在哪里。这个动作很少超过十分钟却救过我很多次也省掉了不少事后找后悔药的工夫。希望帮到你。如果你手上正好缺一本可以随时翻、随时查定义的书这份电子版值得放在手边——拿到之后先别从第一页开始翻到目录挑一个你眼下最想搞清楚的概念从那一节读起。本文还有配套的精品资源点击获取