前言

计算机科学的数学基础（Mathematical Foundations of Computer Science，又称为离

散数学或离散结构）是一门计算机类专业的核心课程。近年来，国内新设的网络空间安全

专业通常也开设一门或多门对应的课程，大多称为网络空间安全数学基础。

关于这一主题，国内外已有许多教材，其中不乏精彩之作。通常，教材的侧重点主要

在于对基础理论、基本知识的讲解，而非给予学生智力上的挑战。我绝对承认这是非常合

理的选择。但是，偶尔也会听到学生调侃说“大学教的比中学（竞赛）容易”。这句话启发

了我，让我考虑编写一本风格差异较大的教材的初衷。

自2020 年以来，我为南京大学信息与计算科学强基班的大一新生教授两门课程：秋季

学期为“信息与计算科学导论”，春季学期为“离散数学”。这两门课程合在一起，大致相

当于前面所说的计算机科学的数学基础，或者网络空间安全数学基础。考虑到较多学生具

有不错的数学背景，在入学时熟悉诸如模运算和抽屉原理之类的内容，因此我在授课时选

择不重复他们已经掌握的内容，而是试图引入更具挑战性和启发性的数学概念。

经过5 年的授课，我把讲义整理为这本教材。我最初为这本教材选择书名《思之趣》（The

Fun of Thinking）?，从而强调思考的乐趣。通过书名我想强调，我授课的目标并非强迫

学生去强记上百条相关定理以及相关解题套路——在我看来，这种做法其实并无意义。与

此相反，我希望我的课程紧密围绕创新性的思考，力求让学生体会思维本身的乐趣。我希

望在我的课上，学生们能够张开想象的翅膀，大胆寻求全新的思路，并且勇敢地将他们自

己的思路与来自成功的数学家、成功的计算机科学家的思路进行比较。我期待这种思考和

比较能对学生的成长有所裨益，使他们在未来的学习、科研中更加从容。

本书共分为6 章，每章探讨一个独立领域，简要介绍如下。

? 第1 章关注（朴素）集合论。本章开篇介绍集合的概念，并强调正则公理（Axiom

of Regularity）的重要性，随后定义常见的集合运算、关系和函数。为了帮助读者

理解如何比较集合的势，本章引入了康托的对角线论证（Cantor’s Diagonalization

Argument）和康托–伯恩斯坦定理（Cantor Bernstein Theorem）。此外，本章还包

括偏序、良序定理（Well Ordering Theorem）、序数、基数，以及作为数学归纳法

推广形式的超限归纳法。

? 第2 章介绍递推关系及其解法。本章开篇分析Karatsuba 算法，从而引出一个可解

的递推关系。接着展示了线性递推的一般解由齐次递推解和一个特解组成，并介绍

了如何将特征方程法用于解齐次递推以及将未定系数法用于求特解。对于非线性递

? 由于种种原因，本书出版时使用了另外一个书名。我只能希望将来有机会再改回来。

前言

推，本章还介绍了两种求精确解的方法——生成函数法和零化子法，以及两种分析

渐近行为的方法——递归树和主定理（Master Theorem）。

? 第3 章探讨群论。在介绍基本定义后，本章首先研究子群与循环群，接着介绍正规

子群、商群，并证明3 个同构定理。考虑到p-子群的重要性，本章还包括柯西定理

（Cauchy’s Theorem）和西罗定理（Sylow’s Theorem）。由于对称群和排列在实践中

应用广泛，本章也对它们分别进行了讨论。

? 第4 章专注于探讨数论相关的话题。本章首先介绍关于既约剩余系的几个定理，如

威尔逊定理（Wilson’s Theorem）、费马小定理（Fermat’s Little Theorem）和欧拉

定理（Euler’s Theorem）。随后转向二次剩余的研究，并最终通过佐洛塔列夫引理

（Zolotarev’s Lemma）给出高斯二次互反律的证明。本章还讨论了连分数，并在最

后两节讨论格与连续最小值问题。

? 第5 章是全书篇幅最长的一章，讲述图论。前两节介绍了图论的基本术语与概念，在

随后的章节探讨多个图论中重要的子领域，包括树与生成树、图的着色（包括色数

与着色多项式）、图匹配、欧拉回路与哈密顿回路等。

? 第6 章简要介绍理论计算机科学，这是与离散数学关系极为密切的领域。本章介绍

了图灵机与停机问题，这是计算理论的基础内容。此外，本章还包括两个简单的随

机化算法，以突出算法设计与分析的重要性，并在最后简要地选讲密码学与博弈论

中的专题各一个。

读者也许会注意到，以上所列内容并不包含数理逻辑，而计算机科学的数学基础或者

网络空间安全数学基础似乎不该把数理逻辑排除在外。事实上，南京大学开设有专门的数

理逻辑课程，与我讲授的两门课程相并列，这才是本书未包含数理逻辑的原因。笔者认为，

如果没有专门的数理逻辑课程，在计算机科学的数学基础或者网络空间安全数学基础中讲

授一点数理逻辑是颇有必要的，教师可以根据实际情况增补一些材料。另外，即便对于课

时数很多的课程而言，要在一两个学期的课程中讲完本书全部内容都不太容易。建议任课

教师大胆取舍，选择自己喜欢的部分教授给学生。作为一本注定不完美的教材，本书在您

的裁剪下，也许会变得更受学生欢迎！

本书的核心在于习题（和例题）。这些题目的覆盖面广，且大多具有一定难度。我尽量

选择那些表述简单、需要的知识较少、运算量较小、但需要“灵机一动”的题目。本书中

的例子如果是例题的话，也大致遵循同样的标准（本书还有部分例子并非例题，只是为了

帮助读者理解概念而给出的简单实例）。为了帮助学生选择适合的题目，本书中的大多数

题目标注了一个从0 到4 的难度估值。

? 0.0 — 完全平凡、只需要简单机械运算的问题（本书中避免出现）。

? 1.0 — 需要掌握基础知识的问题（常见于优秀大学的考试中）。

? 2.0 — 除了对知识的掌握，还要求扎实的问题解决能力（常见于数学竞赛中）。

? 3.0 — 极具挑战性的数学谜题（即使在顶尖竞赛中也被认为很难）。

? 4.0 — 完全不可能解出的问题（本书中也避免出现）。

建议学生在学习完相应内容后，先做几道相对简单的习题以建立信心，然后再尝试一

两道比较难的题目，挑战自己的极限。至于什么难度算简单，什么难度算困难，这完全因

人而异。成功解出一道难度3.0 的习题固然值得骄傲，在难度1.0 的习题上失败也大可不必

沮丧。记住你是在学习，不是在参加体育比赛！

请允许我再次强调：学生并不需要解出本书中的所有题目。事实上，即使是我——本

书作者——如果第一次遇到这些题目，也没办法把它们全部解出。面对难题感到痛苦、奋

力挣扎并不是让人羞耻的事情；困难本来就是学习的一部分。一些勤奋的学生可能误以为，

解出教材中的大量练习题是做一名“好”学生的必要条件。我强烈反对这一看法，认为这

是一种误解。这些题目的设计初衷并不是为了加重学生负担，而是为了激发他们的好奇心

和独立思考能力。只要学生认真思考了这些问题，就已经达到了目的。如果不得不给学生

的作业打分的话（近年来我在南京大学授课时已避免给学生作业打分），我建议，作为一名

好学生千万不要追求满分。追求80 分，甚至追求50 分、30 分也都毫无必要。我希望读者明

白，哪怕一个题目也没解出，只要学生从思考中得到享受、感受到乐趣，本书就已实现了

它的价值。

本书的一个重要特点在于，内容中穿插有较多的提示语，如“为什么”“您知道原因

吗”之类，不断提醒学生思考。这些提示语出现的地方一般是思路出现跳跃的地方。本书

尽量避免出现大幅度跳跃，因此这种跳跃多半是思路活跃、数学基础扎实的学生所能回答

的。建议授课教师在讲到这里时，对学生提出这些问题，尽量由学生而非教师给出问题的

答案。暂时未能想出答案的学生则应当借机将自己的思路与前人比较，考虑自己与前辈数

学家、计算机科学家的差距在哪里。当然，万万不可因为自己一时没有想到什么而感到自

卑。青年学生应当享受思考的乐趣，而不是将其视为负担。

本书中还穿插了一些数学史与科学史的片段。在讲述一些数学家、计算机科学家的成

果时，顺便也介绍他们的生平和趣事。希望读者能够理解，再伟大的数学家或者科学家也

是普通人，他们也一样有生老病死、喜怒哀乐。现在的年轻学子倘若有一点天赋，付出一

些努力，再加上一点点运气，或许有朝一日也能列名其中，成为未来传说的主角。

我由衷地感谢与我共同授课的张渊教授和姚鹏晖教授。同时，也感谢我那些辛勤工作

的助教们：陈哲敏、韩庭轩、卢林强、李尚敖、王崧睿、夏浩然、谢模阳、徐闽泽、张天

钰，他们在批改作业等工作中给予了宝贵帮助。同样应该得到感谢的还有高嘉成、欧丰宁，

他们做出的贡献不亚于各位助教。最后，也是最重要的，感谢我的家人，是他们不断激励

我思考教育的真正意义。他们的支持正是本书得以面世的首要原因。

作者

2026 年4 月