01 / 导读
导读
引用
Epp, S. S. (2020). Discrete Mathematics with Applications (5th ed.). Cengage Learning.
章节概要
全书共十二章，另有附录；Cengage 对学生解答手册的介绍中提到，部分习题的答案在附录B中。前四章建立语言、逻辑和证明技巧；第5–8章讨论归纳法、集合、函数和关系；第9–12章讨论计数与概率、图与树、算法效率和自动机。Cengage 对第五版的介绍说，字符串和图在第1章引入，并在全书中结合应用展开，握手定理从第12章移到了第4章。
第1章：Speaking Mathematically（用数学的语言表达）
开篇一章通过四节教授后面各章使用的词汇：变量、集合的语言、关系与函数的语言、图的语言。
第2–3章：The Logic of Compound Statements（复合命题的逻辑）；The Logic of Quantified Statements（量化命题的逻辑）
第2章涵盖逻辑形式与逻辑等价、条件命题、有效与无效论证，并以两个应用结尾：数字逻辑电路，以及数制与加法电路。第3章对量词重复这一结构：谓词与量化命题（两节）、带多个量词的命题，以及含量化命题的论证。
第4章：Elementary Number Theory and Methods of Proof（初等数论与证明方法）
这一章是本书讲授证明的核心。关于直接证明与反例的六节，依次介绍引言、写作建议、有理数、整除性、分情形讨论与带余除法定理，以及取整函数（下取整与上取整）。关于间接论证的两节讲反证法与逆否命题，以及两个著名的定理；本章最后是应用：握手定理和算法。
第5章：Sequences, Mathematical Induction, and Recursion（序列、数学归纳法与递归）
第5章从序列开始，随后依次是用归纳法证明公式、归纳法的应用，以及强归纳法与良序原理，接着是算法的正确性。后半部分转向递归：序列的递归定义、用迭代法解递推关系、常系数二阶线性齐次递推关系，以及一般递归定义与结构归纳法。
第6–8章：Set Theory（集合论）；Properties of Functions（函数的性质）；Properties of Relations（关系的性质）
第6章涵盖证明的元素法、集合的性质、反证与代数证明，最后一节讲布尔代数、罗素悖论和停机问题。第7章研究一般集合上的函数、单射、满射与反函数、复合，以及带有可计算性应用的基数。第8章处理集合上的关系、自反性、对称性与传递性、等价关系、带有密码学应用的模算术，以及偏序关系。
第9章：Counting and Probability（计数与概率）
第9章从引言出发，依次讲到可能性树与乘法法则、加法法则、鸽巢原理、组合、允许重复的 r 组合、帕斯卡公式与二项式定理、概率公理与期望值，以及条件概率、贝叶斯公式与独立事件。
第10–12章：Theory of Graphs and Trees（图与树的理论）；Analysis of Algorithm Efficiency（算法效率分析）；Regular Expressions and Finite-State Automata（正则表达式与有限状态自动机）
第10章涵盖迹、路径与回路，图的矩阵表示，同构，树与有根树，以及包含最短路径算法的生成树。第11章介绍实变量实值函数及其图像、O、Ω 和 Θ 记号、指数函数与对数函数，以及两个分析算法效率的应用。第12章涵盖形式语言与正则表达式、有限状态自动机，以及有限状态自动机的化简。
核心概念
第1–4章：语言、逻辑与证明
- 逻辑形式与逻辑等价：第2章分析复合命题的基础。
- 量化命题：第3章对谓词、多个量词和含量词的论证的处理。
- 直接证明、反例与间接论证：第4章借助数论教授的证明方法。
- 带余除法定理：4.5节引入的除法结果。
第5–8章：归纳法、集合、函数、关系
- 数学归纳法与强归纳法：5.2–5.4节的证明技巧，5.9节还有结构归纳法。
- 递推关系：用迭代法求解（5.7），二阶线性齐次情形则用一般方法求解（5.8）。
- 证明的元素法：第6章中证明集合性质的方式。
- 等价关系与偏序：第8章的关系类型。
第9–12章：计数、图、算法与自动机
- 鸽巢原理、组合与二项式定理：第9章的计数工具。
- 贝叶斯公式与期望值：第9章末尾的概率主题。
- 大 O、Omega 与 Theta 记号：第11章的记号。
- 有限状态自动机：第12章的机器。
评析
优点
- 证明是教出来的，而不是预设的。 第1章从数学的语言开始，第2–3章讲逻辑，第4章用十节的篇幅展开直接证明、写作建议和间接论证。Cengage 的介绍称本书“以易懂而精确的方法著称”，并强调数学思维背后的推理。第五版修订了关于量词使用、证明概念、证明写作建议和集合论证明的各节。
- 两步式结构的例题。 据 Cengage 的特点列表，本书有500多个问题–解答形式的例题，证明的解答分两步展开：先讨论如何着手证明，再给出解答概要。学生可以选择较快或较慢的节奏。
- 大量习题。 出版社称习题超过2500道，包括应用题，以及在线系统中引导学生完成证明的新型习题。
- 计算机科学应用。 Cengage 称书中有大量计算机科学应用，目录也印证了这一点：数字逻辑电路与二进制加法（2.4–2.5）、算法的正确性（5.5）、利用模算术的密码学（8.4）、算法效率分析（11.3、11.5）和自动机（第12章）。第五版的新内容包括二叉搜索树、密码学哈希函数和消息认证。
局限
- 计数与图出现得较晚。 计数、概率和图要到第9–10章才出现（第1章简要介绍了图的语言），因此以组合数学或图论为中心的课程需要跳着读；出版社称其组织方式允许把核心与选学内容混合。
- 没有专门的数论或密码学章节。 数论在第4章作为证明的载体出现，密码学在8.4节作为模算术的应用出现；想要更完整论述的读者需要其他资料。
- 篇幅。 亚洲版标注为984页，对一门入门课程来说内容很多；教师需要选择章节，而书的组织就是为此而设计的。
在课程中的定位
Epp 是本课程书单中以证明为中心的教材。Rosen 的《Discrete Mathematics and Its 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》留待以后学习：前者讲算法分析所需的求和、递推式和生成函数，后者是研究生水平的组合数学教材。
如何使用本书
Epp 面向需要学习如何阅读和写作数学论证、同时接触计算机科学所用离散结构的学生。它假定具备中学代数和对符号的基本熟悉，不要求微积分。
实用的学习安排如下：
- 核心（第1–5章）： 按顺序阅读。证明的习惯在第2–4章中养成，在做任何证明写作作业之前，4.2节（写作建议）值得一读。
- 结构（第6–8章）： 集合、函数和关系；它们为后面几乎所有内容提供词汇。
- 计数与图（第9–10章）： 本书的组合数学核心。
- 选学（第11–12章）： 算法分析和自动机适合准备学习计算机科学课程的学生。
请做每一节的习题，并把例题当作自己书写证明时的结构范本。