离散数学及其应用

引用

Rosen, K. H. (2025). Discrete Mathematics and Its Applications (2025 release). McGraw Hill.

章节概要

McGraw Hill 为2025年版列出了十三章和附录；出版社提供的第七版目录中也列有相同的十三个章节主题。公开的目录只给出章节标题，因此下面的细节中，凡来自出版社的第八版（2019年）修订说明或第七版（2012年）前言的，都会注明出处。

第1–2章：Foundations: Logic and Proofs（逻辑与证明基础）；Basic Structures: Sets, Functions, Sequences, Sums, Matrices（基本结构：集合、函数、序列、求和、矩阵）

第1章以逻辑开篇，随后讨论证明方法。出版社的第八版修订说明提到了逻辑谜题，以及一个把 n 皇后问题建模为可满足性问题的例子。第2章汇集贯穿全书的基本结构：集合、函数、序列、求和与矩阵；同一份说明还记录了多重集从习题移入正文的变化。

第3–4章：Algorithms（算法）；Number Theory and Cryptography（数论与密码学）

第3章讨论算法；根据第八版修订说明，其中包括字符串匹配问题及其暴力算法。第4章涵盖数论与密码学；该说明提到扩展欧几里得算法、关于素数的最新发现与未解决的猜想，以及同态加密。

第5–6章：Induction and Recursion（归纳与递归）；Counting（计数）

第5章专门讲归纳与递归；第八版的修订包括扩充了数学归纳法证明的模板，并把它放在例题之前。第6章引入计数，同一份说明记录了对除法原理讲解的扩充。

第7–8章：Discrete Probability（离散概率）；Advanced Counting Techniques（高级计数技巧）

第7章涵盖离散概率，第8章涵盖超出基础的计数技巧。公开的目录对两章都没有更详细的说明。

第9–11章：Relations（关系）；Graphs（图）；Trees（树）

第9章讨论关系；第八版修订说明指出，数据挖掘中的关联规则在 n 元关系一节中讨论。第10章关于图，据同一份说明，包含一个把人工智能中的语义网络建模为图的新例子。第11章转向树。

第12–13章：Boolean Algebra（布尔代数）；Modeling Computation（计算建模）

最后两章涵盖布尔代数和计算的建模。第七版前言把这两章都列为偏重计算机科学时的选学内容。

附录

第七版前言描述了三个附录：实数和正整数的公理、指数函数与对数函数，以及用来表达算法的伪代码。第八版修订说明补充道，有一章关于抽象代数（群、环和域），作为单独的在线资源提供，可以加入定制版教材。

核心概念

第1–6章：逻辑、结构、算法、数论、计数

• 逻辑与证明：第1章标题中点出的基础，前言称之为后面讨论证明方法的基石。
• 集合、函数、序列、求和与矩阵：第2章的基本结构。
• 算法：第3章的主题；前言说，算法用文字和伪代码描述，并在初等层面上分析其计算复杂度。
• 数论与密码学：第4章的主题。
• 归纳与递归：第5章；前言强调了数学归纳法。

第7–13章：概率、关系、图、树与计算

• 离散概率与高级计数：第7–8章。
• 关系：第9章。
• 图与树：第10–11章。
• 布尔代数与计算建模：第12–13章。

评析

优点

• 一册涵盖广泛。 目录从逻辑与证明一直到图、布尔代数和计算模型，出版社表示本书面向数学、计算机科学和工程专业的学生，因此一本书可以服务多种类型的课程。
• 明确的教学主题。 第七版前言列出贯穿全书的五条线索：数学推理、组合分析、离散结构、算法思维，以及应用与建模。前言报告书中有800多个例题、4000多道按难度分级的习题（奇数题附有答案或解法提纲）、每章后的关键术语表和复习题，以及可选的计算机项目和写作项目（均为该版的数字）。
• 为灵活的课程设计。 同一份前言说章节之间的依赖被降到最低，并提供了核心与选学小节的表格，因此一学期的二年级课程、两学期的课程和偏计算机科学的课程可以各自选择不同的部分。
• 前提条件明确。 前言称唯一明确的先修要求是大学代数，涉及微积分的少数地方都有标注，所以没有学过微积分也可以使用。

局限

• 公开目录中的细节很少。 出版社只展示了2025年版的章节标题，没有列出相对第八版有哪些变化；在不同版本之间选择时，应当比较实际的目录。
• 证明是手段而非核心主题。 前言把数学推理作为五个主题之一。想要更系统地学习如何写证明的学生，可能更适合以证明写作为组织原则的教材，例如本课程书单中的 Epp 一书。
• 读者群体混合。 由于本书面向数学、计算机科学和工程专业的读者，第七版的表格把算法、布尔代数、计算建模等章在偏数学的课程中列为选学；而第5、6、9、10章包含对所有课程都属核心的小节。

在课程中的定位

Rosen 是一本内容宽泛、带有参考书性质的教材，一册之中涵盖证明方法、算法、数论、计数、概率、图和计算模型。Epp 的《Discrete Mathematics with Applications》涵盖相近的内容，但以学习推理和证明写作为组织主线，因此更适合在逻辑和证明写作上需要更多帮助的学生。Oscar Levin 的《Discrete Mathematics: An Open Introduction》是一门围绕计数、序列、图论和逻辑、以探究为主的免费入门课程；László Lovász、József Pelikán 和 Katalin Vesztergombi 的《Discrete Mathematics: Elementary and Beyond》则是一本以问题为主线的简短入门书。Graham、Knuth 和 Patashnik 的《Concrete Mathematics》以及 van Lint 和 Wilson 的《A Course in Combinatorics》应该在其后阅读：前者讲算法分析中的求和、递推式、二项式系数和生成函数，后者是研究生水平的组合数学教材。

如何使用本书

Rosen 适合修读一到两学期离散数学课程的计算机科学、数学和工程专业一、二年级学生；前言只要求大学代数。它最适合作为课程教材，课后继续当作参考书使用。

实用的学习安排如下：

• 核心： 先学第1章和证明方法各节，再学第2章的基本结构、归纳与递归（第5章）、计数（第6章）和图（第10章）。第七版的表格把第1、2、4、5、6、9、10章的大部分小节列为核心。
• 算法与数论（第3–4章）： 第七版的表格把第3章列为偏计算机科学的选学内容，第4章只有开头几节属于核心；计算机科学课程会希望完整学习这两章。
• 概率、高级计数与关系（第7–9章）： 第七版的表格在每章中只把一到三节列为核心，因此短课程可以只学这些，两学期课程则可学完其余部分。
• 选学（第11–13章）： 第七版的表格只把树这一章的开头一节列为核心，第12–13章（布尔代数、计算建模）则为偏计算机科学的选学内容，因此适合有这类侧重的课程。

请持续使用习题：据前言所述，奇数题附有答案或解法，章末的复习题要求用完整的文字回答，而不是做一个简短的计算。