前言

至于數量，它可以是離散的，也可以是連續的。

——亞里士多德，《范疇論》（約公元前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在寫作過程中提出的批評和支持。