前言

至于数量，它可以是离散的，也可以是连续的。

——亚里士多德，《范畴论》（约公元前350年）

本书介绍了计算机科学家们应该通晓但通常不会在微积分和线性代数课程中学到的离散数学。本书旨在追求广度而非深度，并教授推理方法、概念和技能。

我们强调证明的技巧，希望计算机科学家们能够学会规范而准确地思考。几乎所有公式和定理都给出了充分的证明。这本书讲授数学的累积性，尽管所涵盖的主题非常广泛，但后面章节中看似不相关的结果都基于前期得出的概念。

本书内容需要读者具备一定的微积分基础，因为偶尔也会涉及微积分的知识。第21章用到了极限的概念，但也简单总结了所需基础内容，运用了导数和积分的基本知识（如L'Hôpital法则）的证明和练习可以跳过，而不会影响连续性。

哈佛大学快速的一学期课程涵盖了本书的大部分内容。该课程通常供大一和大二学生学习，作为计算理论（自动机、可计算性和算法分析）课程的预备课程。本书也适用于高中生，以及数学或计算机科学方向对数学学有余力且不满足于标准课程的学生。

本书以一系列简短的章构成，每一章都可以作为一或两节课的主题。每一章结尾都会有小结和习题，这些习题既可以作为课后作业，也可以作为小组合作的课堂练习。

选择不讲授所有主题的教师可以通过多种方式对本书进行删减。本书的核心内容包括介绍基本概念的第1~8章、介绍有向图和无向图的第13~18章，以及介绍阶的表示法和计数问题的第21~25章。有四部分彼此独立的内容是可选的，教师可自行决定是否讲授：

• 第9~12章关于逻辑；

• 第19、20章关于自动机和正则语言；

• 第26~29章关于离散概率；

• 第30、31章关于模运算和公钥密码学。

即使需要，这四部分的内容也无须全部讲授，因为只有同一模块中的后面章节依赖于该模块中前面章节的内容。

我们的目标是提供一本通俗易懂且适合广泛使用的教材，而非百科全书式的教科书。我们始终顾念学生的学习热情，以及他们有限的时间、精力和预算。

感谢CS20团队：Deborah Abel、Ben Adlam、Paul Bamberg、Hannah Blumberg、Crystal Chang、Corinne Curcie、Michelle Danoff、Jack Dent、Ruth Fong、Michael Gelbart、Kirk Goff、Gabriel Goldberg、Paul Handorff、Roger Huang、Steve Komarov、Abiola Laniyonu、Nicholas Longenbaugh、Erin Masatsugu、Keenan Monks、Anupa Murali、Eela Nagaraj、Rebecca Nesson、Jenny Nitishinskaya、Sparsh Sah、Maria Stoica、Tom Silver、Francisco Trujillo、Nathaniel Ver Steeg、Helen Wu、Yifan Wu、Charles Zhang，以及Ben Zheng。

感谢Albert Meyer在CS20开始时的慷慨帮助。

感谢Michael Sobin、Scott Joseph、Alex Silverstein和Noam Wolf在写作过程中提出的批评和支持。