01 / 导读
导读
引用
Levin, O. (2025). Discrete Mathematics: An Open Introduction (4th ed.). Chapman & Hall/CRC. Free official edition: https://discrete.openmathbooks.org/dmoi4.html
章节概要
第0章：引言与预备知识
简短的开篇一章通过握手、数列和计数等小谜题说明数学中什么是"离散"的，随后对全书使用的离散结构——集合、函数、数列、关系和图——做一次非正式的初步介绍。这些结构在这里是"按需"引入的，第5章会给出更正式的处理。
第1章：逻辑与证明
本章是全书通往证明的桥梁。内容包括原子命题与复合命题、量词与谓词、蕴涵及其逆命题与逆否命题、真值表、逻辑等价（包括量化命题的等价）以及演绎推理。随后讲授直接证明、逆否证明和反证法，新增的一节把这些方法用于集合、函数、关系和图。章末总结以哥德巴赫猜想为例，说明命题的逻辑形式如何提示证明的结构。
第2章：图论
本章从哥尼斯堡七桥等问题出发定义图，研究树（性质、生成树和有根树）、平面图及欧拉公式与多面体的联系、欧拉迹与欧拉回路以及哈密顿路径，还有顶点着色和边着色。关于关系的一节说明如何把关系、等价关系和划分看作图，章末讨论二部图的匹配和霍尔婚姻定理。
第3章：计数
本章在这一版中重新组织，侧重于考察结果的集合而不是套用规则。它从通过格路、比特串和子集来理解的帕斯卡三角形开始，接着展开加法原理和乘法原理、处理重叠结果的容斥原理、带商原理的组合与排列、多重集（用比特串表示的"隔板法"）以及组合证明。新增的一节把计数应用于概率，包括条件概率；最后一节用容斥原理处理多重集、错排和函数计数。
第4章：数列
本章用通项公式和递推公式、部分和与差分来描述数列，并配以简短的 Python 示例。它研究等差数列和等比数列、通过有限差分得到的多项式数列，以及求和技巧（"倒序相加""乘、移、减"），并用特征根法求解线性递推。最后讨论数学归纳法和强归纳法，把数列的递推描述与归纳推理联系起来。
第5章：再论离散结构
这是自成一体的一章，对集合（记号、包含关系、运算和韦恩图）和函数（描述方式、单射、满射与双射、像与原像）作更完整的讨论。序言指出这一章可以独立于全书其他部分学习。
第6章：补充专题
两个补充专题为全书作结。母函数通过差分、乘法和部分和来构造和运算，并用于求解递推关系。数论导引涵盖整除、剩余类、同余的性质、解同余式以及解线性丢番图方程。
核心概念
第0章：引言与预备知识
- 离散结构：由彼此分离、各不相同的元素构成的数学对象——如集合、数列、关系或图——用于为实际问题建模。
- 作为离散结构的函数：给定义域中每个元素指定陪域中恰好一个元素的规则，常在有限集合之间考虑。
第1章：逻辑与证明
- 蕴涵："如果 P，那么 Q"形式的命题，仅当 P 真 Q 假时为假；其逆否命题与之逻辑等价，而逆命题则不然。
- 量词："对所有"和"存在"，它们的顺序与否定决定了命题的含义。
- 证明方式：根据命题的逻辑形式选择直接证明、逆否证明或反证法。
第2章：图论
- 树：没有回路的连通图；有 n 个顶点的树有 n − 1 条边。
- 欧拉公式：对连通平面图，顶点数减边数加面数等于 2。
- 欧拉迹：恰好经过每条边一次的路线，当且仅当图连通且奇度顶点个数为 0 或 2 时存在。
- 色数：使相邻顶点颜色不同所需的最少颜色数。
第3章：计数
- 加法原理与乘法原理：互斥的选择相加，独立的步骤相乘。
- 容斥原理：通过交替加减各交集的大小来校正重叠部分。
- 组合证明：通过说明等式两边计数的是同一集合来证明恒等式。
- 错排：没有不动点的排列，用容斥原理计数。
第4章：数列
- 递推公式与通项公式：由前面的项描述某一项，或直接由下标描述它。
- 特征根法：利用相关多项式的根求解斐波那契递推之类的线性递推。
- 数学归纳法：通过基础情形和归纳步骤对所有 n 证明命题；强归纳法使用此前所有情形。
第5章：再论离散结构
- 集合运算：并、交、差、补和笛卡儿积，用韦恩图加以说明。
- 双射：既是单射又是满射的函数，因而把两个集合的元素一一配对。
第6章：补充专题
- 母函数：以数列各项为系数的幂级数，用于运算和求解递推关系。
- 模 n 同余：两个整数除以 n 余数相同，就称它们同余。
- 线性丢番图方程：求整数解的方程 ax + by = c。
评析
优点
- 为探究式教学而设计。 每节都以开放性的"Investigate!"问题和结构化的预习活动开始，以阅读问题结束，然后是练习题和补充习题。序言介绍了多种用法——课前预习、课上小组活动等——这种结构同样支持自学。
- 题库大且类型多样。 第四版新增近 300 道习题，总数超过 750 道，分为预习、阅读、练习和补充习题，每章末还有章节复习；部分题目的提示和解答收在两个附录中。
- 交互式在线版。 在线版中许多预习活动和练习题可以即时反馈，有些还能随机生成不同版本，并提供 Python 草稿板；第4章包含关于数列的简短 Python 示例。
- 通过结果集合来计数。 改写后的计数一章强调识别结果的集合而不是死记公式，章末总结中的 Investigate! 要求学生按方法对表面相似的问题进行分类。
局限
- 选题服务于特定课程。 序言说明选题是针对北科罗拉多大学的学生；书中没有算法分析（渐近记号）、布尔代数、有限状态机或形式语言，计算机科学课程可能需要补充材料。
- 部分领域深度有限。 数论和母函数只是简短的"补充专题"，概率只占一节，图论止步于网络流或最短路径算法等内容之前。
- 归纳法出现较晚。 归纳法放在数列一章末尾，而不是与第1章的其他证明方法放在一起，有些教师可能希望提前讲授。
- 印刷版和 PDF 失去交互性。 即时反馈、随机练习和隐藏提示都是在线版的功能；使用 PDF 的读者需要依靠附录和自律来检查答案。
书中的应用
应用融入在例题和习题之中，而不是集中在单独的章节。图论以哥尼斯堡七桥、地图着色、多面体和匹配问题为动机；计数被应用于概率，包括条件概率；数列与现实情境的递推描述相联系，并用 Python 计算各项；强归纳法与分治思想相联系；数论部分则以解同余式和线性丢番图方程收尾。
在课程中的定位
在这份离散数学书单中，Levin 的书与 Lovász、Pelikán、Vesztergombi 所著 Discrete Mathematics: Elementary and Beyond（一般被视为以问题驱动、更侧重数论与组合的入门书）并列。Rosen 的 Discrete Mathematics and Its Applications 和 Epp 的 Discrete Mathematics with Applications 一般被描述为内容全面的教材；它们涵盖 Levin 未涉及的算法与复杂度等主题，可以在以 Levin 作为易读核心教材的计算机科学课程中充当参考书。
Graham、Knuth、Patashnik 的 Concrete Mathematics 以及 van Lint 与 Wilson 的 A Course in Combinatorics 则走得更远。Levin 的第3、4、6章（计数、数列与递推、母函数）是通往这两本书的良好准备；喜欢这些章节的学生可以转向 Concrete Mathematics 学习求和与渐近技巧，或转向 van Lint 与 Wilson 学习更深入的组合数学。
如何使用本书
本书面向数学和计算机科学专业的一、二年级本科生，也包括未来的中小学教师；它同时可以作为通往证明的过渡课程。开始学习只需中学代数，不要求有证明经验。
一学期课程可以按书中顺序进行：第0章、第1章（逻辑与证明）、第2章（图论）、第3章（计数）和第4章（数列与归纳法），第5章用作参考或复习，第6章作为拓展。序言指出各节相对独立，教师可以调整顺序。每一节都应在阅读前先尝试 Investigate! 问题和预习活动，读后回答阅读问题，然后做练习题——最好在线完成以获得即时反馈——再做补充习题和章末复习。按照作者的建议，尽量少看提示和解答。
版本与来源
本导读依据 Discrete Mathematics: An Open Introduction 第四版（© 2013–2025 Oscar Levin，CC BY-NC-SA 4.0；序言日期为 2024 年，PDF 生成于 2025 年 9 月），阅读的是官方版本页面 https://discrete.openmathbooks.org/dmoi4.html 链接的免费 PDF。导读参考了致谢、序言（目标、探究式设计和第四版的改动）、"如何使用本书"、细到小节的完整目录、第0章全文、第1–4章的章末总结，以及全书各节的开篇和主要结论（包括霍尔婚姻定理、鸽巢原理以及数列与归纳法的内容）。