• 数学背景
  • 1.1 本章：读者的参考手册
  • 1.2 前置数学知识的概览
  • 1.3 阅读数学文本
    • 1.3.1 定义
    • 1.3.2 断言：定理、引理、主张
    • 1.3.1 证明
  • 1.4 基础离散数学对象
    • 1.4.1 集合
    • 1.4.2 特殊集合
    • 1.4.3 函数
    • 1.4.4 图
    • 1.4.5 逻辑运算符与量词
    • 1.4.6 求和与求积的量词
    • 1.4.7 解析公式：约束变量与自由变量
    • 1.4.8 渐近分析与大$O$表示法
    • 1.4.9 关于大$O$表示法的一些“经验法则”
  • 1.5 证明
    • 1.5.1 证明与程序
    • 1.5.2 证明的书写风格
    • 1.5.3 证明的方法
  • 1.6 扩展示例：拓扑排序
    • 1.6.1 数学归纳
    • 1.6.2 通过归纳证明结论
    • 1.6.3 最小性和唯一性
  • 1.7 本书所用到的符号及规范
    • 1.7.1 变量命名规范
    • 1.7.2 一些惯用表达
  • 1.8 习题
  • 1.9 参考书目

数学背景

在本章中，我们将会介绍一些将在本书中用到的数学概念。这些概念一般会在“计算机科学中的数学”或“离散数学”等课程或课本中讲解。有关这些主题的几份可在线免费获取优秀资源，请参阅“参考书目”部分（第1.9节）。

一个数学家的辩白。部分学生可能会好奇为什么这本书包含如此多的数学，这是因为数学就是一门能够简洁而精确描述概念的语言。在这本书中，我们使用数学来描述计算的概念。比如说，我们将思考诸如“是否存在一种高效算法来求取给定整数的质因数？”这样的问题（我们将看到这个问题尤为有趣，它甚至触及了从互联网安全到量子力学等跨度极大的问题！）若要精准的描述这些问题，我们需要对算法这一概念以及算法的高效性给出精准的定义。此外，由于无法通过实验证明某种算法不存在，唯一能证实算法不存在性的方式就是数学证明。

1.1 本章：读者的参考手册

基于你已有的数学背景，你有两种阅读本章的方式：

• 如果你已经学习过”离散数学“、”计算机科学中的数学“或任何类似课程，则无需阅读整章内容，只需要快速地阅读第1.2节来了解我们会用到什么数学工具与第1.7节来了解本书所用符号，便可跳转至后续章节。或者，你也可以放松心情通读本章，既熟悉本书所用的符号体系，顺便品味（或忍受）笔者融于字里行间的哲学思考与幽默尝试。
• 若相关基础较为薄弱，可以参考第1.9节中提供的学习资源。本章虽然已经涵盖了所有所需知识点，但系统性地学习相关知识点可能对你更有帮助。数学学习重在实践，通过独立完成练习才能真正掌握这些内容。
• 建议你同时开始回顾离散概率论的相关知识，本书后续章节（见第18章）将涉及这部分内容。

1.2 前置数学知识的概览

我们将使用的主要数学概念如下所示。此处仅列出这些概念，其具体定义将在本章后续部分给出。若您已熟悉所有这些内容，可以直接跳至第1.7节查看我们使用的完整符号列表。

• 证明：最重要的是，本书包含大量形式化数学推理，涵盖数学定义、陈述与证明。
• 集合及集合运算：我们将广泛使用数学集合。涉及到的集合关系包括属于（$\in$）与包含（$\subseteq$），以及集合运算，主要是并集（$\cup$）、交集（$\cap$）与差集（$\setminus$）。
• 笛卡尔积（Cartesian product）与克林星号（Kleene star）运算：两个集合$A$与$B$的笛卡尔积，记作$A\times B$（即由所有满足$a\in A$且$b\in B$的所有有序对$(a,b)$构成的集合），$A^n$表示$n$阶笛卡尔积（例如$A^3=A\times A\times A$），而$A^{\ast }$（称为克林星号）表示所有$n\in \{0,1,2,\dots \}$对应的$A^n$的并集。
• 函数：函数的定义域和陪域，以及函数的性质（如单射函数和满射函数），还有部分函数（即不同于全函数的，对于定义域内部分元素可能存在未定义情况的函数）。
• 逻辑运算：常用操作包括逻辑与（$\wedge$）、逻辑或（$\vee$）、逻辑非（$\neg$）等，以及存在量词（$\exists$）和全称量词（$\forall$）。
• 基础组合数学：诸如$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$（表示大小为$n$的集合中所有$k$元子集的数量）等概念。
• 图论：无向图和有向图、连通性、路径和环。
• 大$O$表示法：使用$O,o,\Omega ,\omega ,\theta$符号分析函数的渐进增长性。
• 离散概率：我们将使用概率论，特别是基于有限概率空间（如抛掷$n$枚硬币）的概率论，包括随机变量、期望和浓度等概念。概率论仅在本书后半部分使用，我们将在第18章先行复习。然而概率推理是一项精妙（且极其实用）的技能，尽早开始掌握总是有益的。

本章后续部分将简要回顾上述概念。既是为了帮助读者重温可能已经生疏的知识，也是为了介绍我们的符号与约定——这些约定有时可能与你之前接触过的版本有所不同。

1.3 阅读数学文本

数学家使用各种专业术语的原因，与工程、法律、医学等其他众多领域并无差别：我们需要精确的术语，并为频繁使用的概念引入简洁表达。数学文本往往在单个句子中蕴含极高的信息密度，因此关键在于缓慢而仔细地阅读，逐个符号解析。

随着练习时间逐渐增长，你将发现阅读数学文本变得越来越轻松，且专业术语也不再是问题。更重要的是，数学文本阅读能力是从本书中能够获得的极具迁移价值的技能之一。我们的世界正飞速变化——这不仅体现在技术领域，更延伸至医学、经济学、法律乃至文化等人类实践的方方面面。无论你未来方向如何，都很可能会接触到包含前所未见新概念的文本（参见图1.1与图1.2中两个当代“热点领域“的例子）。掌握内化并应用新定义的能力至关重要。在数学课程相对安全稳定的学习环境中，这种技能更容易被掌握——至少你可以确信所有概念都有完整定义，并能随时向教学人员答疑解惑。

图1.1：

摘自Silver等人2017年发表于《自然》期刊的《AlphaGo Zero》论文“方法“部分片段

图1.2：

摘自Ben-Sasson等人奠定加密货币Zcash项目基础的《Zerocash》论文片段

数学文本的基本构成要素有三：定义、断言与证明。

1.3.1 定义

数学家经常在已有的概念上定义新的概念。比如，以下是一个你可能曾经见过的数学定义（并且我们很快还会再见到）：

Definition 1.1 (定义1.1：单射函数).

令$S$与$T$为集合。我们称一个函数$f:S\to T$是单射的（one-to-one或injective）当其对于任意两个元素$x,x^{\prime }\in S$时，若$x\ne x^{\prime }$，则有$f(x)\ne f(x^{\prime })$。

定义1.1：单射函数阐述了一个简单的概念，但即便如此它也使用了大量符号。阅读此类定义时，一边阅读一边用笔进行标注往往很有帮助（见图1.3）。例如当看到诸如$f$、$S$或$x$等符号时，务必确认其指代的对象的类别：是集合、函数、元素、数字，还是小妖怪？你可能还会发现，向朋友（或对自己）用语言解释这一定义会很有帮助。

图1.3：

定义1.1：单射函数的注释版本，标出了定义的每个对象及其关联的定义

1.3.2 断言：定理、引理、主张

定理、引理、断言等都是对已定义概念的真命题。将特定命题称为“定理“、“引理“还是“断言“属于主观判断，并不改变其数学实质——三者均指代已被证明为真的命题。区别在于：定理指代值得铭记和强调的重要结论；引理通常指技术性结论，其自身未必重要但能有效辅助其他定理的证明；断言则是为证明更重大结论而使用的“过渡性“命题，其自身价值并不受关注。

1.3.1 证明

数学证明是用以证实定理、引理及断言真实性的论证过程。我们将在下文1.5节讨论证明，其核心在于数学证明的标准极为严苛。与其他领域不同，数学证明必须是“无懈可击“的论证，确保证明对象无可置疑为真。本节涉及的数学证明示例参见习题解答1.1及1.6节。如前言所述，总体而言：理解定义比掌握定理更重要，理解定理陈述比掌握其证明过程更重要。

1.4 基础离散数学对象

在本节中，我们将快速回顾本书中所用的一些数学对象（你当然也可以把这些叫做数学中的“基本数据结构”）。

1.4.1 集合

一个集合是一些对象的无序容器。例如，$S=\{2,4,7\}$表示$S$指代一个包含数字$2$、$4$、$7$的集合（我们使用$2\in S$来表示$2$是$S$中的一个元素。）注意集合$\{2,4,7\}$与$\{7,4,2\}$是相同的，因为它们拥有相同的元素。同时，一个集合要么包含一个元素，要么不包含一个元素，不存在“包含两次”的概念，因此我们甚至可以将同一个集合$S$写作$\{2,2,4,7\}$（尽管这样写有些奇怪）。有限集合的基数（cardinality），即一个集合包含的元素的数量，记作$|S|$（基数亦可以定义在无限集上，见第1.9节的参考资料）。因此在上例中$|S|=3$。若集合$S$的元素都是集合$T$的元素，则称$S$为$T$的一个子集，记作$S\subseteq T$（我们亦可以称$T$为$S$的一个超集。）比如，$\{2,7\}\subseteq \{2,4,7\}$。不包含任何元素的集合称作空集，写作$\varnothing$。如果$A$是$B$的一个子集且$A$不等于$B$，则我们称$A$为$B$的一个真子集，记作$A⊊B$。

我们可以通过将其元素全部列出来定义集合，也可以通过写下集合元素满足的一个条件来定义集合，例如： $$偶数集=\{x|对于某个非负整数y，有x=2y\}$$ 当然，同一集合有多种表示方式，我们常会使用直观的记号列出几个示例来说明规则。例如也可将$偶数集$定义为： $$偶数集=\{0,2,4,\dots \}$$ 注意集合可以是有限的（如$\{2,4,7\}$）或无限的（如$\text{偶数集}$）。集合的元素不必是数字，例如英语元音的集合$\{a,e,i,o,u\}$，或按2010年人口普查的美国百万人口城市集合$\{\text{New York, Los Angeles, Chicago, Houston, Philadelphia, Phoenix, San Antonio, San Diego, Dallas}\}$。集合甚至可以包含其他集合作为元素，例如$\{1,2,3\}$所有偶数大小子集构成的集合$\{\varnothing ,\{1,2\},\{2,3\},\{1,3\}\}$。

集合运算：集合$S$与的$T$的并集记作$S\cup T$，包含所有属于$S$或属于$T$的元素。交集记作$S\cap T$，包含同时属于$S$和$T$的元素。差集记作$S\setminus T$（部分文献中记作$S-T$），包含属于$S$但不属于$T$的元素。

元组、列表、字符串、序列：元组是有序的对象容器，例如$(1,5,2,1)$是包含四个元素的元组（称为$4$-元组或四元组）。由于元组是有序的，该元组不同于四元组$(1,1,5,2)$或三元组$(1,5,2)$。$2$-元组亦称为有序对。术语“元组”与“列表”可互换使用。若某个元组中的元素均来自于某个有限集$\Sigma$（如$\{0,1\}$），则称为字符串。类比集合，我们将元组$T$的长度记作$|T|$。与集合类似，元组亦有无限形式。例如由所有完全平方数组成的元组$(1,4,9,\dots )$。无限的有序容器称为序列，有时亦称作“无限序列”以强调这一点。“有限序列”是元组的同义词。（可将集合$S$中元素的序列$(a_0,a_1,a_2,\dots )$视为函数$A:\mathbb{N}\to S$（其中对任意$n\in \mathbb{N}$满足$a_n=A(n)$）。类似地，可将$S$中元素的$k$-元组视为函数$A:[k]\to S$。）

笛卡尔积：若$S$与$T$是集合，则其笛卡尔积记作$S\times T$，是由所有满足$s\in S$且$t\in T$的有序对$(s,t)$构成的集合。例如，若$S=\{1,2,3\}$且$T=\{10,12\}$，则$S\times T$包含六个元素：$(1,10),(2,10),(3,10),(1,12),(2,12),(3,12)$。相似的，若$S,T,U$为集合，则$S\times T\times U$为由所有满足$s\in S$、$t\in T$、$u\in U$的三元组$(s,t,u)$构成的集合。更加一般地，对任意正整数$n$及集合$S_0,\dots ,S_{n-1}$，用$S_0\times S_1\times \cdots \times S_{n-1}$表示满足对每个$i\in \{0,\dots ,n-1\}$有$s_i\in S_i$的有序$n$-元组$(s_0,\dots ,s_{n-1})$的集合。对任意集合$S$，将$S\times S$记作$S^2$，$S\times S\times S$记作$S^3$，$S\times S\times S\times S$记作$S^4$，依此类推。

1.4.2 特殊集合

在本书中会反复用到数个特殊集合。集合 $$\mathbb{N}=\{0,1,2,\dots \}$$

包含了所有的自然数，即非负整数。对于任意的自然数$n\in \mathbb{N}$，定义集合$[n]$为$\{0,\dots ,n-1\}=\{k\in \mathbb{N}:k<n\}$（$\mathbb{N}$与$n$均从$0$开始计数，与此同时诸多文献中这两个集合是从$1$开始的计数的。从零开始计数只是一个约定俗成的做法，只要保持一致性，并不会产生太大差异。）

我们偶尔也会使用集合$\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \}$来表示所有（负的和非负的）整数，同时使用$\mathbb{R}$来表示所有实数（这个集合不仅包含整数，同时也包含分数与无理数，例如，$\mathbb{R}$包含诸如$+0.5$、$-\pi$等的数字。）我们使用${\mathbb{R}}_{+}$来表示所有正实数的集合$\{x\in \mathbb{R}:x>0\}$。这个集合有时亦写作$(0,\infty )$。

字符串：另外一个我们经常会用到的集合是 $$\{0,1{\}}^n=\{(x_0,\dots ,x_{n-1}):x_0,\dots ,x_{n-1}\in \{0,1\}\}$$ 这个集合包含了所有长度为$n$（$n$为任意自然数）的二进制字符串。换句话说，$\{0,1{\}}^n$是包含所有由$0,1$组成的$n$-元组的集合。这与我们前文中的符号一致：$\{0,1{\}}^2$是笛卡尔积$\{0,1\}\times \{0,1\}$，$\{(0,1){\}}^3$是笛卡尔积$\{(0,1)\}\times \{(0,1)\}\times \{(0,1)\}$，依此类推。

我们将字符串$(x_0,x_1,\dots ,x_{n-1})$简单地写作$x_0{x}_1\cdots x_{n-1}$。例如， $$\{0,1{\}}^3=\{000,001,010,011,100,101,110,111\}$$ 对于所有字符串$x\in \{0,1{\}}^n$与$i\in [n]$，我们将$x$的第$i$个元素记作$x_i$。

我们也经常会使用包含所有长度二进制字符串的集合，即 $$\{0,1{\}}^{\ast }=\{(x_0,\dots ,x_{n-1}):n\in \mathbb{N},,x_0,\dots ,x_{n-1}\in \{0,1\}\}$$ 另一个表示这个集合的方式是 $$\{0,1{\}}^{\ast }=\{0,1{\}}^0\cup \{0,1{\}}^1\cup \{0,1{\}}^2\cup \cdots$$ 或者更为简洁的 $$\{0,1{\}}^{\ast }=\bigcup _{n\in \mathbb{N}}\{0,1{\}}^n$$ 集合$\{0,1{\}}^{\ast }$包含了“长度为$0$的字符串”或“空字符串”，我们将这个字符串记作$\text{""}$（此处我们使用与大部分编程语言一致的符号，其他文献可能会使用$ϵ$或$\lambda$来表示空字符串）。

推广星号操作：对于任意集合$\Sigma$，我们定义 $${\Sigma }^{\ast }=\bigcup _{n\in \mathbb{N}}{\Sigma }^n$$ 例如，若$\Sigma =\{a,b,c,d,\dots ,z\}$，则${\Sigma }^{\ast }$表示字母表a-z上所有有限长度字符串的集合。

连接操作：两个字符串$x\in {\Sigma }^n$与$y\in {\Sigma }^m$的连接是指将$y$书写在$x$后形成的$(n+m)$长度的字符串$xy$。具体而言，若$x\in \{0,1{\}}^n$且$y\in \{0,1{\}}^m$，则$xy$等于满足以下条件的字符串$z\in \{0,1{\}}^{n+m}$：当$i\in [n]$时$z_i=x_i$，当$i\in \{n,\dots ,n+m-1\}$时$z_i=y_{i-n}$。

1.4.3 函数

若$S$与$T$为非空集合，则从$S$到$T$的函数（记作$F:S\to T$）会将每个元素$x\in S$关联到一个元素$F(x)\in T$。集合$S$称为函数$F$的定义域，集合$T$称为$F$的陪域。函数$F$的像是指集合$\{F(x)|x\in S\}$，即由所有被映射的输入元素对应的输出元素组成的$F$的陪域子集（有些文献使用“值域”一词表示函数的像，而另一些文献使用“值域”表示函数的陪域。因此我们将完全避免使用“值域”这一术语。）与集合类似，我们可以通过列出函数对$S$中所有元素给出的取值表或通过规则来定义函数。例如，若$S=\{0,1,2,3,4,5,6,7,8,9\}$且$T=\{0,1\}$，则下表定义了一个函数$F:S\to T$。注意该函数与规则$F(x)=(x\mathrm{mod}2)$定义的函数相同。

若$F:S\to T$满足对所有$x\ne y$均有$F(x)\ne F(y)$，则称$F$是单射（见定义1.1：单射函数，亦称为单射函数）。若$F$满足对每个$y\in T$均存在某个$x\in S$使得$F(x)=y$，则称$F$是满射（亦称作满射函数）。既是单射又是满射的函数称为双射函数或双射。从集合$S$到自身的双射亦称为$S$的排列。若$F:S\to T$是双射，则对于每个$y\in T$均存在唯一的$x\in S$使得$F(x)=y$。我们将该值$x$记作$F^{-1}(y)$。注意$F^{-1}(y)$本身也是从$T$到$S$的双射（你能明白为什么吗？）。

给出两个集合之间的双射通常是证明集合大小相同的有效方法。事实上，“$S$与$T$具有相同基数”的标准数学定义就是存在一个双射$f:S\to T$。此外，若存在从$S$到集合$\{0,\dots ,n-1\}$的双射，则定义集合$S$的基数为$n$。正如我们将在本书后面看到的，这个定义可以推广到无限集合的基数定义。

部分函数（又译偏函数）：我们有时会关注从$S$到$T$的部分函数。部分函数允许在$S$的某个子集上未定义。也就是说，若$F$是从$S$到$T$的偏函数，则对每个$s\in S$，要么（如标准函数的情况）存在$T$中的元素$F(s)$，要么$F(s)$未定义。例如，部分函数$F(x)=\sqrt{x}$仅定义在非负实数上。当需要偏函数和标准（即非部分）函数时，我们称后者为全函数。当我们不加限定地说“函数”时，指的是全函数。

部分函数的概念是函数的严格推广，因此每个函数都是部分函数，但并非每个部分函数都是函数（也就是说，对于任意非空集合$S$与$T$，从$S$到$T$的偏函数集合是从$S$到$T$的全函数集合的真超集。）当需要强调从$A$到$B$的函数$f$可能不是全函数时，我们写作$f:A{\to }_{p}B$。我们也可以将从$S$到$T$的偏函数视为从$S$到$T\cup \{\perp \}$的全函数，其中$\perp$是一个特殊的“失败符号”。因此，我们可以说$F(x)=\perp$，而不是$F$在$x$处未定义。

关于函数的基本事实：验证能否证明以下结论是复习函数知识的绝佳方式：

• 若$F:S\to T$和$G:T\to U$是单射函数，则它们的复合函数$H:S\to U$（定义为$H(s)=G(F(s))$）也是单射。
• 若$F:S\to T$是单射，则存在一个满射函数$G:T\to S$，使得对于每个$s\in S$均有$G(F(s))=s$。
• 若$G:T\to S$是满射，则存在一个单射函数$F:S\to T$，使得对于每个$s\in S$均有$G(F(s))=s$。
• 若$S$与$T$是非空有限集合，则以下条件相互等价：(a) $|S|\le |T|$；(b) 存在单射函数$F:S\to T$；(c) 存在满射函数$G:T\to S$。这些等价关系实际上对无限集合$S$和$T$亦成立。对于无限集合，条件(b)（或等价的条件(c)）是$|S|\le |T|$的公认定义。

图1.4：

我们可以将有限函数表示为有向图，其中从$x$到$f(x)$有一条边。满射条件要求函数陪域中的每个顶点的入度至少为$1$。单射条件要求函数陪域中的每个顶点入度至多为$1$，上图的示例中，$F$是满射函数，$G$是单射函数，而$H$既不是满射也不是单射

让我们以其中一个事实为例进行证明：

Lemma 1.1 (引理1.2).

若$S,T$是非空集合且$F:S\to T$是单射，则存在满射函数$G:T\to S$，使得对每个$s\in S$均有$G(F(s))=s$。

证明：选择某个$s_0\in S$。我们将定义函数$G:T\to S$如下：对每个$t\in T$，若存在某个$s\in S$使得$F(s)=t$，则令$G(t)=s$（由于$F$的单射性质，不可能有两个不同的$s,s^{\prime }$同时映射到$t$，因此$s$的选择是无歧义的）。否则，令$G(t)=s_0$。现在对于每个$s\in S$，根据$G$的定义，若$t=F(s)$，则$G(F(s))=s$。此外，这也表示$G$是满射，因为这意味着对每个$s\in S$都存在某个$t$（即$t=F(s)$）使得$G(t)=s$。

1.4.4 图

图在计算机科学及众多其他领域中无处不在。图可以用于建模非常多的数据类型，包括但不限于社交网络、调度约束、道路网络、深度神经网络、基因相互作用、观测值之间的相关性。几种图的正式定义将在下面给出，但如果你没有在先前的课程中了解过图，我强烈建议你从第1.9节中的资料中详细了解它们。

图有两种基本类型：无向图与有向图。

Definition 1.2 (定义1.3：无向图).

一个无向图$G=(V,E)$由一个顶点集$S$与一个边集$E$组成。每条边都是一个$V$的大小为2的子集。我们称两个顶点$u,v\in V$为相邻顶点，若边$\{u,v\}$在$E$中。

基于这个定义，我们可以定义关于图与顶点的几个性质。我们将$u$的相邻节点的个数成为$u$的度数。图中的一条路径是一个元组$(u_0,\dots ,u_k)\in V^{k+1}$（其中$k>0$），且满足对每个$i\in [k]$，$u_{i+1}$都是$u_i$的相邻节点。简单路径是指所有$u_i$均不重复的路径$(u_0,\dots ,u_{k-1})$。环是指满足$u_0=u_k$的路径$(u_0,\dots ,u_k)$。若两个顶点$u,v\in V$满足$u=v$或存在一条从$u_0=u$到$u_k=v$的路径，则称这两个顶点是联通的。当图中每对顶点都联通时，我们称该图是连通图。

下面是一些关于无向图的基本事实。我们将为它们给出一些非正式的论证，但完整证明作为练习留待读者自行完成（完整证明可以在第1.9节中的诸多资源中找到）。

Lemma 1.2 (引理1.4).

在任意的无向图$G=(V,E)$中，所有顶点的度数之和等于边数的两倍。

通过观察可知：每条边$\{u,v\}$会对度数总和贡献两次（一次作用于$u$，另一次作用于$v$），由此可证明引理1.4。

Lemma 1.3 (引理1.5).

连通关系具有传递性，即如果$u$与$v$相连，且$v$与$w$相连，则$u$与$w$也相连。

通过将路径$(u,u_1,u_2,\dots ,u_{k-1},v)$与路径$(v,u_1^{\prime },\dots ,u_{k-1}^{\prime },w)$拼接，得到连接$u$与$w$的路径$(u,u_1,\dots ,u_{k-1},v,u_1^{\prime },\dots ,u_{k^{\prime }-1}^{\prime },w)$，即可证明引理1.5。

Lemma 1.4 (引理1.6).

对于任意无向图$G=(V,E)$及连通顶点对$u,v$，从$u$到$v$的最短路径是简单路径。特别地，任意连通顶点对间均存在连接二者的简单路径。

通过“捷径修剪法”可证明引理1.6：若某路径中同一节点$w$出现两次，则移除其间的循环段（见图1.6）。将这一直观论证转化为形式化证明是很好的练习：

图1.6：

若图中存在从$u$到$v$的路径两次经过顶点$w$，则可移除$w$到自身的循环段，得到仅经过$w$一次的捷径路径。

度数和连通性的概念亦可自然推广至有向图，其定义如下：

Definition 1.3 (定义1.8：有向图).

一个有向图$G=(V,E)$由顶点集$V$和边集$E\subseteq V\times V$（由$V$的有序对构成）组成。有时将边$(u,v)$记为$u\to v$。若存在边$u\to v$，则称$v$是$u$的出邻居，$u$是$v$的入邻居。

有向图可能同时包含边$u\to v$和$v\to u$，此时$u$和$v$互为入邻居和出邻居。顶点$u$的入度是其入邻居的数量，出度是其出邻居的数量。图中的路径是指元组$(u_0,\dots ,u_k)\in V^{k+1}$（其中$k>0$），且对每个$i\in [k]$有$u_{i+1}$是$u_i$的出邻居。与无向图情形类似，简单路径是指所有$u_i$均不相同的路径$(u_0,\dots ,u_{k-1})$，环是指满足$u_0=u_k$的路径$(u_0,\dots ,u_k)$。我们经常关注的一类有向图是有向无环图（Directed Acyclic Graph，DAG），顾名思义即为不含环的有向图：

Definition 1.4 (定义1.9：有向无环图).

若有向图$G=(V,E)$中不存在顶点列$u_0,u_1,\dots ,u_k\in V$使得$u_0=u_k$且对每个$i\in [k]$有边$u_i\to u_{i+1}\in E$，则称其为有向无环图（DAG）。

上述引理在有向图中均有对应版本。其证明（与无向图情形基本一致）将作为习题留给读者。

Lemma 1.5 (引理1.10).

对于任意有向图$G=(V,E)$，入度之和等于出度之和，且均等于边数。

Lemma 1.6 (引理1.11).

对于任意有向图，若存在从$u$到$v$的路径和从$v$到$w$的路径，则存在从$u$到$w$的路径。

Lemma 1.7 (引理1.12).

对于任意有向图$G=(V,E)$及存在路径的顶点对$u,v$，从$u$到$v$的最短路径是简单路径。

1.4.5 逻辑运算符与量词

如果$P$和$Q$是可真可假的陈述，则$P$与$Q$（记为$P\wedge Q$）是一个当且仅当$P$和$Q$同时为真时才成立的陈述；而$P$或$Q$（记为$P\vee Q$）是一个当且仅当$P$或$Q$为真是成立的陈述。$P$的否定记作$\neg P$或$\overline{P}$，当且仅当$P$为假时该陈述为真。

假设$P(x)$是一个依赖于某个参数$x$（有时亦称为自由变量）的陈述，其特性在于：对于从集合$S$中取值的每一个$x$的具体赋值，$P(x)$都会有明确的真值。例如$x>7$这个陈述本身没有固有真值，但当我们用具体实数代入$x$时，它就会成为真或假的命题。我们用${\forall }_{x\in S}P(x)$表示这样一个陈述：当且仅当对所有$s\in S$都有$P(x)$为真时，该陈述为真。用${\exists }_{x\in S}P(x)$表示这样一个陈述：当且仅当存在某个$x\in S$使得$P(x)$为真时，该陈述为真。

例如下面这个形式化表达式，描述的是“存在大于100且不能被3整除的自然数$n$”这个真命题： $${\exists }_{n\in \mathbb{N}}(n>100)\wedge \left({\forall }_{k\in N}k+k+k\ne n\right)$$ “对于足够大的$n$”。本书中会反复出现“某个陈述对于足够大的$n$成立”这样的论断，其含义是：存在整数$N_0$，使得对于所有$n>N_0$，$P(n)$都成立。我们可以将其形式化为${\exists }_{N_0\in \mathbb{N}}{\forall }_{n>N_0}P(n)$。

1.4.6 求和与求积的量词

使用下列简记法来表示多个数的求和或求积往往更为便捷。若$S=\{s_0,\dots ,s_{n-1}\}$是有限集且$f:S\to \mathbb{R}$是函数，则${\sum }_{x\in S}f(x)$表示： $$f(s_0)+f(s_1)+f(s_2)+\dots +f(s_{n-1})$$ ${\prod }_{x\in S}f(x)$表示： $$f(s_0)\cdot f(s_1)\cdot f(s_2)\cdot \dots \cdot f(s_{n-1})$$ 例如，从$1$到$100$的所有整数的平方和可表示为：

式 1.1 (公式1.1). $$\sum _{i\in \{1,\dots ,100\}}{i}^2$$ 由于对整数区间求和极为常见，对此存在特殊记号。对于任意两个满足$a\le b$的整数，${\sum }_{i=a}^{b}f(i)$表示${\sum }_{i\in S}f(i)$，其中$S=\{x\in \mathbb{Z}:a\le x\le b\}$。因此公式1.1可改写为： $$\sum _{i=1}^{100}{i}^2$$

1.4.7 解析公式：约束变量与自由变量

在数学中，如同在编程中一样，我们常常会遇到符号化的“变量”或“参数”。给定某个公式时，理解特定变量在该公式中是约束变量还是自由变量至关重要。例如在如下陈述中，$n$是自由变量，而$a$和$b$是受存在量词$\exists$约束的变量：

式 1.2 (公式1.2). $${\exists }_{a,b\in \mathbb{N}}(a\ne 1)\wedge (a\ne n)\wedge (n=a\times b)$$ 由于$n$是自由变量，它可以被赋予任意值，因此公式1.2的真值取决于$n$的取值。例如当$n=8$时公式成立，但当$n=11$时则不成立。（你能看出原因吗？）

同样的问题在解析代码时也会出现。例如在下列C语言代码片段中：

for (int i=0 ; i<n ; i=i+1) {
    printf("*");
}

变量i在for循环块内是约束变量，而变量n则是自由变量。

约束变量的主要特性是：我们可以对其进行重命名（只要新名称不与其他变量名冲突）而不改变语句的含义。因此以下陈述

式 1.3 (公式1.3). $${\exists }_{x,y\in \mathbb{N}}(x\ne 1)\wedge (x\ne n)\wedge (n=x\times y)$$ 与公式1.2完全等价—它们对$n$值的真值判断完全相同。

同样地，代码：

for (int j=0 ; j<n ; j=j+1) {
    printf("*");
}

与使用i的代码段有完全相同的执行效果。

1.4.8 渐近分析与大$O$表示法

精确描述运行时间等量通常非常繁琐，且并无必要，因为我们通常主要关注的是“高阶项”。也就是说，我们希望理解该量随输入变量增长时的缩放行为。例如，就运行时间而言，一个$n^5$时间算法与一个$n^2$时间算法之间的差异，远比$100n^2+10n$时间算法与$10n^2$算法之间的差异更加显著。为此，大$O$表示法作为一种“简化表述”的方式极为有用，它能让我们的注意力集中在真正重要的内容上。例如，使用大$O$表示法，我们可以说$100n^2+10n$和$10n^2$都简单的属于$\Theta (n^2)$（可非正式地理解为“在常数因子范围内相同”），而$n^2=o(n^5)$（可非正式地理解为$n^2$“远小于”$n^5$）。

通常（尽管为非正式表述），若$F,G$是两个将自然数映射到非负实数的函数，则“$F=O(G)$”表示在不考虑常数因子的情况下$F(n)\le G(n)$，而“$F=o(G)$“表示$F$远小于$G$，其含义是：无论给$F$乘以多大的常数因子，只要取足够大的$n$，$G$都会更大（因此，有时会将$F=o(G)$写作$F\ll G$）。如果$F=O(G)$且$G=O(F)$，则写作$F=\Theta (G)$，这可以理解为：若不考虑常数因子，$F$与$G$相同。更形式化地，我们如下定义大$O$表示法：

Definition 1.5 (定义1.15：大$O$表示法).

设$R_{+}=\{x\in \mathbb{R}|x>0\}$为正实数集。对于两个函数$F,G:\mathbb{N}\to {\mathbb{R}}_{+}$，若存在$a,N_0\in \mathbb{N}$，使得对所有$n>N_0$有$F(n)\le a\cdot G(n)$，则称$F=O(G)$。若$F=O(G)$且$G=O(F)$，则称$F=\Theta (G)$。若$G=O(F)$，则称$F=\Omega (G)$。

若对任意$ϵ>0$，存在$N_0$使得对所有$n>N_0$有$F(n)<ϵG(n)$，则称$F=o(G)$。若$G=o(F)$，则称$F=\omega (G)$。

图1.7：

若$F(n)=o(G(n))$，则当$n$足够大时，$F(n)$将小于$G(n)$。例如，若算法$A$的运行时间为$1000\cdot n+10^6$，算法$B$的运行时间为$0.01n^2$，那么即使$B$在小输入时更高效，当输入足够大时，$A$的运行速度将远快于$B$

在大$O$表示法中使用“匿名函数”通常很方便。例如，当我们写$F(n)=O(n^3)$这样的语句时，我们的意思是$F=O(G)$，其中$G$是定义为$G(n)=n^3$的函数。Jim Apsnes的离散数学笔记第七章很好地总结了大$O$表示法；另可参阅本教程，以获得更温和且更面向程序员的介绍。

$O$并不表示相等。在大$O$表示法中使用等号极为常见，但这种用法其实并不准确，因为诸如$F=O(G)$的语句实际上表示$F$属于集合$\{G^{\prime }:{\exists }_{N,c}使得{\forall }_{n>N}{G}^{\prime }(n)\le cG(n)\}$。如果说有什么更合理的表示法，那就是使用不等式写作$F\le O(G)$和$F\ge \Omega (G)$，而将等号保留给$F=\Theta (G)$。因此，我们有时也会使用这种表示法，但由于使用等号的习惯已经根深蒂固，我们通常也沿用此习惯。（有些文献写作$F\in O(G)$而非$F=O(G)$，但我们不会使用这种表示法。）尽管等号可能引起误解，但请记住：诸如$F=O(G)$的语句表示在忽略常数的粗略意义上$F$“至多”为$G$，而诸如$F=\Omega (G)$的语句表示在相同粗略意义上$F$“至少”为$G$。

1.4.9 关于大$O$表示法的一些“经验法则”

在比较两个函数$F$和$G$时，有一些简单的经验法则可供参考：

• 在大$O$表示法中，乘性常数不影响结果。因此，若$F(n)=O(G(n))$，则$100F(n)=O(G(n))$。当两个函数相加时，我们只需要关注较大着。例如，在大$O$表示法的语句下，$n^3+100n^2$与$n^3$等价。一般而言，对于任意多项式，我们只需关注高阶项。
• 对于任意两个常数$a,b>0$，当且仅当$a\le b$时，$n^a=O(n^b)$成立，当且仅当$a<b$时，$n^a=o(n^b)$成立。例如，综合以上两点可知：$100n^2+10n+100=o(n^3)$。
• 多项式函数始终小于指数函数：对于任意两个常数$a>0$和$ϵ>0$（即使$ϵ$远小于$a$），都有$n^a=o(2^{n^{ϵ}})$。例如，$100n^{100}=o(2^{\sqrt{n}})$。
• 类似地，对数函数始终小于多项式函数：对于任意两个常数$a,ϵ>0$，$(\log n{)}^a$（记作${\log }^{a}n$）满足$o(n^{ϵ})$。例如，综合上述观察可得：$100n^2{\log }^{1}00n=o(n^3)$。

1.5 证明

许多人认为数学证明是从若干公理出发，通过逻辑推导最终得出结论的过程。事实上，某些词典也采用这种方式定义证明。这种理解并非完全错误，但从本质而言，对命题X的数学证明实质上是一个能让读者确信X为真且不容置疑的论证过程。

构建此类证明需要做到：

• 精确理解X的含义。
• 使自己确信X为真。
• 用清晰、准确、简洁的书面英语记录推理过程（仅在有助于明确性时使用公式或符号）。

多数情况下，第一步最为关键。理解命题含义往往比理解其真理性更耗费心力。在第三步中，为使读者毫无疑虑，我们常需将推理分解为若干“基本步骤“，其中每个步骤都应简单到“不言自明“的程度——所有步骤的叠加最终导出目标命题。

1.5.1 证明与程序

证明写作与程序编写具有高度相似性，且二者所需的技能也高度重合。程序编写包含：

• 理解程序需要实现的功能。
• 确信该功能可通过计算机实现（可通过在白板或记事本上规划如何拆解为子任务来实现）。
• 将规划转化为编译器或解释器可读的代码（通过将每个任务拆解为某种编程语言的基本操作序列）。

与证明过程类似，程序设计的第一步往往最为关键。核心区别在于：证明的阅读者是人类，而程序的阅读者是计算机（随着机器可验证证明形式的普及，这种差异正在逐渐消弭；此外，为确保程序的正确性与可维护性，人类可读性至关重要）。因此我们特别强调证明的逻辑流畅性与可读性（这对程序编写同样重要）。撰写证明时，应假想读者是聪明但极度多疑且挑剔的，他们会对任何未充分论证的步骤提出质疑。

1.5.2 证明的书写风格

数学证明是一种特定类型的写作形式，具有独特的惯例与偏好风格。如同所有写作类型，熟能生巧，且通过修改草稿提升清晰度至关重要。

在命题$X$的证明中，“证明：“与”证毕“之间的所有文字都应专注于论证$X$的真实性。题外话、示例或沉思应置于这两个标记之外，以免造成读者困惑。证明应具备清晰的逻辑流：每个句子或公式都应有明确目的，且读者能清晰理解其作用。撰写证明时，应对每个句子或公式进行审视：

1. 该句子/公式是否在声明某个命题为真？
2. 若是，该命题是从前述步骤推导而来，还是将在后续步骤中建立？
3. 这个句子/公式起什么作用？是通向原命题证明的一步，还是为证明先前所述的中间论断而设？
4. 最后，读者是否能清晰理解前三个问题的答案？若否，则需要调整顺序、重新表述或补充说明。

关于数学写作的推荐资源包括Lee的讲义、Hutching的讲义，以及斯坦福大学CS103课程中的若干优秀讲义。

1.5.3 证明的方法

正如编程一样，证明亦有数种常用的方法。以下是一些例子：

反证法：证明$X$的一种方式是展示，若$X$为假，则会导致导出矛盾。这种类型的证明通常由一句“假设，为了得出矛盾，$X$为假”作为开头，并以推导出一个矛盾作为结尾（如违反定理陈述中的某个假设）。以下是一个例子：

Lemma 1.8 (引理).

不存在自然数$a,b$使得$\sqrt{2}=\frac{a}{b}$。

证明：假设，为了得出矛盾，上述引理为假。令$a\in \mathbb{N}$为满足$\sqrt{2}=\frac{a}{b}$的最小自然数（其中$b\in \mathbb{N}$）。对此等式两侧平方有$2=a^2/b^2$，即$a^2=2b^2$ $(\ast )$。此式表明$a^2$为偶数。由于两个奇数之积亦为奇数，这表明$a$必须是偶数，即存在$a^{\prime }\in \mathbb{N}$使得$a=2a^{\prime }$。将此式代入$(\ast )$有$4a^{\prime 2}=2b^2$，即$b^2=2a^{\prime 2}$，且这表明$b^2$亦为为偶数。与$a$类似，我们亦可得到$b$为偶数。因此，$a/2$与$b/2$为两个满足$\frac{a/2}{b/2}=\sqrt{2}$的自然数，这与$a$的最小性相矛盾。

全称命题的证明：我们经常需要证明形如“所有类型为$O$的对象都具有性质$P$”的命题$X$。这类证明通常以“设$o$为类型$O$的一个对象”开始，并通过证明$o$具有性质$P$来结束，以下是一个简单的例子：

Lemma 1.9 (引理).

对于任意自然数$n\in \mathbb{N}$，$n$和$n+1$中必有一个是偶数。

证明：设$n\in \mathbb{N}$为任意自然数。若$n/2$为整数，则$n=2(n/2)$，因此$n$是偶数，证毕。否则，$n/2+1/2$是整数，因此$2(n/2+1/2)=n+1$是偶数。

蕴含命题的证明：另一种常见情况是命题$X$形如“$A$蕴含$B$”。这类证明通常以“假设$A$成立“开始，并通过从$A$导出$B$来结束。以下是一个简单的例子：

Lemma 1.10 (引理).

如果$b^2\ge 4ac$，则二次方程$a{x}^2+bx+c=0$有解。

证明：假设$b^2\ge 4ac$。则$d=b^2-4ac$是一个非负数，因此存在平方根$s$。于是$x=(-b+s)/(2a)$满足：

式 1.4 (公式1.4). $$\begin{array}{rl}a{x}^2+bx+c& =a(-b+s{)}^2/(4a^2)+b(-b+s)/(2a)+c\\ & =(b^2-2bs+s^2)/(4a)+(-b^2+bs)/(2a)+c\end{array}$$ 整理公式1.4，我们得到： $$s^2/(4a)+c-b^2/(4a)=(b^2-4ac)/(4a)+c-b^2/(4a)=0$$ 等价命题的证明：如果命题形如“$A$当且仅当$B$”（通常简写为“$A$ iff $B$”），那么我们需要同时证明$A$蕴含$B$和$B$蕴含$A$。我们将$A$蕴含$B$的方向称为“仅当”方向，将$B$蕴含$A$的方向称为“当”方向。

通过中间结论组合的证明：当证明较为复杂时，将其分解为多个步骤通常是有帮助的。也就是说，为了证明命题$X$，我们可能先证明命题$X_1$、$X_2$和$X_3$，然后证明$X_1\wedge X_2\wedge X_3$蕴含$X$。（注：$\wedge$表示逻辑与运算符。）

分情况证明：这是上述方法的一种特殊形式，即为了证明命题$X$，我们将其分为若干情况$C_1,\dots ,C_k$，并证明：(a) 这些情况是穷尽的，即其中一种情况$C_i$必须发生；(b) 逐一证明每种情况$Ci$都能推导出我们想要的结果$X$。

数学归纳法证明：我们将在下面的第1.6.1节中讨论数学归纳法并给出示例。我们可以将这类证明视为上述方法的变体，其中我们有无穷多个中间结论$X_0,X_1,X_2,\dots ,X_k$，并证明$X_0$成立，且$X_0$蕴含$X_1$，$X_0\wedge X_1$蕴含$X_2$，依此类推。卡内基梅隆大学15-251课程的网站提供了一份有用的讲义，介绍了使用数学归纳法时可能遇到的常见陷阱。

“不失一般性”（without loss of generality，w.l.o.g）：这个术语最初可能令人困惑。它本质上是一种通过简化情况分析来简化证明的方法。其思想是，如果情况1和情况2在变量替换或类似变换下是相同的，那么情况1的证明也隐含了情况2的证明。但对此应始终保持怀疑态度。每当在证明中看到它时，问问自己是否理解为什么所做的假设是真正“不失一般性”的；而当使用它时，尝试确认这种使用是否确实合理。在撰写证明时，有时最简单的方法是直接重复第二种情况的证明（并添加注释说明该证明与第一种情况非常相似）。

1.6 扩展示例：拓扑排序

在本节中，我们将证明如下结论：每个有向无环图（DAG，参见定义1.9：有向无环图）都可以进行分层排列，使得对于所有有向边$u\to v$，顶点$v$所在的层都大于$v$所在的层。这一结论被称为拓扑排序，被广泛应用于任务调度、构建系统、软件包管理、电子表格单元格计算等场景（见图1.8）。事实上，在本书后续内容中我们也会用到这一结论。

图1.8：

拓扑排序示例。我们考虑某个计算机科学专业课程先修关系对应的有向图，其中边$u\to v$表示课程$u$是课程$v$的先修课程。对该图进行分层或“拓扑排序“等价于将课程映射到不同学期，使得若我们计划在学期$f(v)$修读课程$v$，则已在此前的学期修完$v$的所有先修课程（即其入邻居）

我们首先给出如下定义。有向图的分层是指为每个顶点$v$分配一个自然数（对应其所在层）的方法，要求$v$的入邻居处在更低编号的层，而出邻居处于更高编号的层。形式化定义如下：

Definition 1.6 (定义1.21：DAG的分层).

设$G=(V,E)$为有向图，$G$的分层是一个函数$f:V\to \mathbb{N}$，使得对于$G$的每条边$u\to v$，都有$f(u)<f(v)$。

本节将证明：有向图是无环的当且仅当其存在有效分层。

Theorem 1.1 (定义1.22：拓扑排序).

设$G$为有向图，则$G$是无环的当且仅当存在$G$的分层函数$f$。

要证明此类定理，首先需要理解其含义。由于这是一个“当且仅当”类型的陈述，定义1.22：拓扑排序对应两个命题：

Lemma 1.11 (引理1.23).

对于任意有向图$G$，若$G$无环，则存在对应的分层。

Lemma 1.12 (引理1.24).

对于任意有向图$G$，若其存在分层，则$G$无环。

要证明定义1.22：拓扑排序，则需同时证明引理1.23和引理1.24。引理引理1.24的证明实际上并不困难：直观上，若$G$包含环，则环上所有边的层数不可能全程递增—因为沿着环行进时必然会回到起点。形式化证明如下：

证明：设$G=(V,E)$为有向图，$f:V\to \mathbb{N}$是符合定义1.21：DAG的分层的分层函数。用反证法假设$G$不是无环图，即存在环$u_0,u_1,\dots ,u_k$满足$u_0=u_k$，且对每个$i\in [k]$都有边$u_i\to u_{i+1}$属于$G$。由于$f$是分层函数，对每个$i\in [k]$有$f(u_i)<f(u_{i+1})$，这意味着： $$f(u_0)<f(u_1)<\cdots <f(u_k)$$ 但这与$u_0=u_k$导出的$f(u_0)=f(u_k)$相矛盾。

引理1.23对应着更复杂（但更有用）的方向。要证明它，需要说明如何为任意有向无环图$G$构造分层，使得所有边“指向上层”。

1.6.1 数学归纳

证明引理1.23存在多种方法。一种做法是：首先针对小型图（如具有1、2或3个顶点的图，参见图1.9）进行证明——这类有限情形可通过穷举法验证，随后尝试将证明推广至更大规模的图。这种证明方法的技术术语称为归纳证明。

图1.9：

具有一、二、三个顶点的有向无环图示例及顶点分层标注的有效方式

归纳法本质上是显而易见的“肯定前件“逻辑规则（Modus Ponens）的应用，该规则指出：若(a) 命题$P$为真，且(b) $P$蕴含$Q$，则$Q$为真。

在归纳证明的框架中，我们通常有一个由整数$k$参数化的命题$Q(k)$，并通过证明以下两点来完成：(a) $Q(0)$为真；(b) 对任意$k>0$，若$Q(0),\dots ,Q(k-1)$均为真，则$Q(k)$为真（尽管证明(b)通常是难点，但也存在需要巧妙处理“基础情形“(a)的案例）。通过运用肯定前件规则，我们可以从(a)和(b)推导出$Q(1)$为真。继而基于$Q(0)$与$Q(1)$为真的事实，结合(b)再次运用肯定前件规则可推出$Q(2)$为真。如此循环往复，可证得对所有$k$均有$Q(k)$为真。其中(a)称为“基础情形“，(b)称为“归纳步骤“，(b)中假设$Q(i)$对$i<k$成立的条件称为“归纳假设“（此处描述的归纳形式有时被称为“强归纳法“，以区别于“弱归纳法“——后者将(b)替换为“若$Q(k-1)$为真则$Q(k)$为真“；弱归纳法可视为强归纳法的特例，即不要求使用$Q(0),\dots ,Q(k-2)$为真的条件）。

1.6.2 通过归纳证明结论

通过归纳法证明引理1.23有多种方式。我们将基于顶点数量$n$进行归纳，因此定义命题$Q(n)$如下：

$Q(n)$表示：“对于每个具有$n$个顶点的有向无环图$G=(V,E)$，都存在对$G$的分层赋值。”

当$n=0$（即图不含顶点）时命题显然成立。因此只需证明：对于每个$n>0$，若$Q(n-1)$成立则$Q(n)$成立。

为此，我们需要找到一种方法：给定具有$n$个顶点的图$G$，将寻找$G$分层的问题转化为寻找具有$n-1$个顶点的其他图$G\prime$的分层问题。核心思路是找到$G$的一个源点（即没有入边的顶点$v$）。随后将顶点$v$分配至0层，并依据归纳假设将剩余顶点分配至$1,2,\dots$等层。

以上是引理1.23证明的直观思路。但在撰写正式证明时，我们将基于后见之明进行优化，将原本曲折的推理过程转化为从“证明：“开始到“证毕（QED¹）”（或符号$■$）结束的线性化逻辑流。讨论、示例和旁注虽颇具启发性，但应该置于这两个标记界定的空间之外——正如优秀的指南所述，此空间内“每个句子都必须承担论证功能“。如同编程，我们可以将证明分解为小型“子程序“或“函数“（数学中称为引理或断言），即通过辅助性小命题来证明主要结论。但证明结构必须确保读者能清晰把握论证阶段，理解每个句子的作用及所属部分。现正式证明引理1.23。

证明：设$G=(V,E)$为有向无环图，$n=|V|$为其顶点数。采用对$n$归纳法证明。基础情形$n=0$时命题显然成立。当$n>0$时，归纳假设为：所有顶点数不超过$n-1$的有向无环图$G\prime$均存在分层。

首先建立如下断言：

断言：图$G$必存在入度为零的顶点$v$。

断言证明：假设反之，即每个顶点$v\in V$都有入邻居。任取顶点$v_0$，令$v_1$为$v_0$的入邻点，$v_2$为$v_1$的入邻点，依此重复$n$步构造序列$v_0,v_1,\dots ,v_n$，其中每个$i\in [n]$都有$v_{i+1}$是$v_i$的入邻点（即存在边$v_{i+1}\to v_i$）。由于图仅含$n$个顶点，该序列的$n+1$个顶点中必存在重复，即存在$i<j$使得$v_i=v_j$。此时序列$v_j\to v_{j-1}\to \cdots \to v_i$构成环，与有向无环图假设矛盾。（断言证毕）

根据该断言，取$v_0$为$G$中某个入度为零的顶点，令$G\prime$为移除$v_0$后得到的图。$G\prime$含$n-1$个顶点，由归纳假设存在分层函数f′:(V</span>v0​)→N。定义函数f:V→N如下： f(v)={f′(v)+10​v=v0​v=v0​​

需证$f$是有效的分层赋值，即对任意边$u\to v$满足$f(u)<f(v)$。分情形讨论：

• 情形1：$u\ne v_0$且$v\ne v_0$。此时边$u\to v$存在于$G\prime$中，由归纳假设有$f\prime (u)<f\prime (v)$，故$f\prime (u)+1<f\prime (v)+1$。
• 情形2：$u=v_0$且$v\ne v_0$。此时$f(u)=0$，而$f(v)=f\prime (v)+1>0$。
• 情形3：$u\ne v_0$且$v=v_0$。此情形不可能发生，因为$v_0$没有入邻居。
• 情形4：$u=v_0$且$v=v_0$。此情形亦不可能，因这意味着$v_0$存在自环（属于有向无环图禁止的环结构）。

故$f$是$G$的有效分层赋值，证明完成。

1.6.3 最小性和唯一性

定义1.22：拓扑排序保证每个有向无环图$G=(V,E)$都存在分层函数$f:V\to \mathbb{N}$，但这种分层不一定唯一。例如，若$f:V\to \mathbb{N}$是图的有效分层，那么定义为$f\prime (v)=2\cdot f(v)$的函数$f\prime$也是有效分层。然而最小分层却是唯一的——最小分层要求每个顶点都被赋予尽可能小的层数。现正式定义最小性并陈述唯一性定理：

Theorem 1.2 (定理1.26：最小分层的唯一性).

设$G=(V,E)$为有向无环图。若对每个顶点$v\in V$：当$v$无入邻居时$f(v)=0$，当$v$有入邻居时存在某个入邻居$u$满足$f(u)=f(v)-1$，则称分层函数$f:V\to \mathbb{N}$是最小的。

对于$G$的任意两个分层函数$f,g:V\to \mathbb{N}$，若$f$和$g$都是最小分层，则$f=g$。

定理1.26：最小分层的唯一性中的最小性定义意味着：对每个顶点$v\in V$，我们无法在保持分层有效性的前提下将其移至更低层。若$v$是源点（即入度为零），则最小分层$f$必须将其置于$0$层；对于其他顶点$v$，若$f(v)=i$，则由于存在满足$f(u)=i-1$的入邻居$u$，我们无法将$f(v)$修改为$i-1$或更小值。定理1.26：最小分层的唯一性表明最小分层$f$是唯一的，即任何其他最小分层都与$f$完全相同。

证明思路：对层数进行归纳。若$f$和$g$都是最小分层，则它们必然在源点处取值一致（因为都必须将源点分配至$0$层）。接着可证明：若$f$和$g$在第$i-1$层及以下取值一致，则最小性性质要求它们在第$i$层也必须一致。实际证明中使用了一个简化表述的技巧：不直接证明$f=g$（即对每个$v\in V$有$f(v)=g(v)$），而是证明较弱的命题—对每个$v\in V$有$f(v)leg(v)$（该条件弱于相等条件，因为$f(v)=g(v)$必然蕴含$f(v)\le g(v)$）。由于$f$和$g$只是两个最小分层的标注符号，通过互换符号标签即可用相同证明得到对每个$v\in V$有$g(v)\le f(v)$，从而证得$f=g.$

证明：设$G=(V,E)$为有向无环图，$f,g:V\to \mathbb{N}$是其两个最小有效分层。我们将通过对$i=f(v)$的归纳证明：对每个$v\in V$有$f(v)\le g(v)$。由于除最小性外未对$f,g$作任何假设，该证明同样可推出对每个$v\in V$有$g(v)\le f(v)$，故而对每个$v\in V$有$f(v)=g(v)$，此即所需结论。

当$i=0$时显然成立：此时$f(v)=0$，故$g(v)$至少等于$f(v)$。当$i>0$时，根据$f$的最小性，若$f(v)=i$则必存在某个入邻居$u$满足$f(u)=i-1$。由归纳假设得$g(u)\ge i-1$，而由于$g$是有效分层，必有$g(v)>g(u)$，这意味着$g(v)\ge i=f(v)$。

1.7 本书所用到的符号及规范

本书采用的大部分符号标记均为数学文本中的通用规范，主要差异点如下：

• 自然数集$\mathbb{N}$的索引从$0$开始（尽管许多计算机科学领域的文献亦采用相同约定）
• 集合$[n]$的索引从$0$开始，因此其定义为$\{0,\dots ,n-1\}$（其他文献常定义为$\{1,\dots ,n\}$）。类似地，字符串索引也从$0$开始，故字符串$x\in \{0,1{\}}^n$写作$x_0{x}_1\cdots ,x_{n-1}$
• 若$n$为自然数，则$1^n$不表示数字$1$，而是长度为$n$的字符串$11\cdots 1$（即连续$n$个“1”）。同理，$0^n$表示长度为$n$的字符串$00\cdots 0$
• 部分函数未必在所有输入上都有定义。符号$f:A\to B$默认表示全函数，若需强调函数为部分函数时，将采用$f:A{\to }_{p}B$的写法
• 本课程主要将计算问题描述为计算布尔函数$f:\{0,1{\}}^{\ast }\to \{0,1\}$，而其他教材常采用判定语言$L\subseteq \{0,1{\}}^{\ast }$的表述。这两种视角具有等价性：对于任意集合$L\subseteq \{0,1{\}}^{\ast }$，存在对应函数$F$满足$F(x)=1$当且仅当$x\in L$。计算部分函数对应文献中的“承诺问题”（promise problem）。鉴于语言表述在其他教材中更加常见，我们将适时提醒读者注意这种对应关系
• 使用$\lceil x\rceil$和$\lfloor x\rfloor$分别表示向上取整和向下取整函数，$(x\mathrm{mod}y)$表示$x$除以$y$的余数（即$x\mathrm{mod}y=x-y\lfloor x/y\rfloor$）。在需要整数的语境中，通常默认将数值隐式取整。例如“长度为$\sqrt{n}$的字符串$x$”实际指$x$的长度为$\lceil \sqrt{n}\rceil$（依据惯例采用向上取整，但多数情况下取整方式不影响结论）
• 遵循计算机科学文献惯例，默认对数以$2$为底，即$\log n$等价于${\log }_{2}n$
• 记号$f(n)=poly(n)$是$f(n)=n^{O(1)}$的缩写（即存在常数$a,b$使得对足够大的$n$满足$f(n)\le a\cdot n^b$）。类似地，$f(n)=polylog(n)$表示$f(n)=poly(\log n)$（即存在常数$a,b$使得对足够大的$n$满足$f(n)\le a\cdot (\log n{)}^b$）
• 依照数学文献惯例，通过添加撇号扩展标识符集：若$x$表示某对象，则$x^{\prime }$、$x^{\prime \prime }$等表示同类型的其他对象
• 为降低认知负荷，定理和习题陈述中常使用$10,100,1000$等整常数。这类“整齐“常数通常无特殊含义，仅为任意选取。例如定理“算法$A$在长度为$n$的输入上计算函数$F$至多需要$1000\cdot n^2$步“中的数值$1000$可视为足够大的任意常数，实际可用更小的常数$c$证明$c\cdot n^2$的界。同理，若问题要求证明某量至少为$n/100$，实际可能存在更小的常数$d$使得该量至少为$n/d$

1.7.1 变量命名规范

正如编程一样，数学中充满了各种各样的变量。当你看到一个变量时，追踪这个变量所属的类型至关重要（例如整数、字符串、函数、图等）。为了简化这一过程，我们尝试一致的为特定的类型使用特定的变量。部分命名规范在本节列出。这些命名规范并不是无法更改的法则，有时我们可能会稍微偏离这一规范。并且，这些规范并没有取代在声明新变量前明确指出其指代对象的要求。

本书中的变量命名规范：

标识符	通常指代的对象类型
$i,j,k,\ell ,m,n$	自然数（即集合$\{0,1,2,\dots \}$中的元素）
$ϵ,\delta$	趋近于$0$的正实数
$x,y,z,w$	通常表示$\{0,1{\}}^{\ast }$上的字符串，有时也表示数字或其他对象。我们常将对象与其字符串表示视为同一
$G$	图。顶点集一般表示为$V$，且通常$V=[n]$。边集一般表示为$E$
$S$	集合
$f,g,h$	函数。通常（非绝对）用小写标识符表示有限函数（映射关系为，常见$m=1$）
$F,G,H$	无限输入函数，映射关系为$\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$或$\{0,1{\}}^n\to \{0,1{\}}^m$（$m$为某定值）。根据上下文，$G,H$可指函数或图
$A,B,C$	布尔电路
$M,N$	图灵机
$P,Q$	程序
$T$	表示时间界限的函数，映射关系为$\mathbb{N}\to \mathbb{N}$
$c$	正数（常指未明确的常数，例如$T(n)=O(n)$表示存在常数$c$使得对所有$n>0$满足$T(n)\le c\cdot n$）。有时也以$a,b$来表示此类常数
$\Sigma$	有限集（通常用于表示字符串集合的字母表）

1.7.2 一些惯用表达

数学文本通常遵循特定惯例或“惯用表达”。本文使用的一些典型惯用表达包括：

• “设$X$为…”、“令$X$表示…”或“令$X=\dots$”：这些都是在表达$X$指代省略号所代表的内容。当$X$表示某些对象的属性时我们可能会通过“若…满足…条件，则称其具有性质$X$“的方式来定义。虽然我们尽量先定义后使用，但有时为了语句流畅会在定义前使用术语，此时会通过“其中$X$指…”的说明来解释前述表达中$X$的含义。
• 量词：数学文本涉及大量“对于所有”和“存在”等量词。有时我们会完整拼写为“对于所有$i\in \mathbb{N}$”或“存在$x\in \{0,1{\}}^{\ast }$”，有时则直接使用符号$\forall$和$\exists$。必须注意每个变量的量化方式及其依赖关系。例如“对于每个$k>0$，存在$n$”意味着$n$的选择依赖于$k$。量词顺序至关重要：命题“对每个大于$1$的自然数$k$，都存在质数$n$能整除$k$”为真，而“存在质数$k$能整除每个大于$1$的自然数$k$”则为假。
• 编号公式、定理、定义：为便于追溯已定义术语和已证明命题，我们通常为其添加（数字）标签，并在文中其他部分引用。
• (i.e.,)与(e.g.,)：数学文本中常见这类拉丁缩写。当$Y$与$X$等价时使用”$X$（i.e., $Y$）”；当$Y$是$X$的实例时使用“$X$（e.g., $Y$）”，如“自然数（i.e., 非负整数）”或“自然数（e.g., 77）”。
• “因此”、“故而”、“可得”：这些词引导的句子是由前文推导得出的结论，例如“具有$n$个顶点的图$G$是连通的，因此它至少包含$n-1$条边”。有时使用“实际上”引出的文本来论证前句主张，如“具有$n$个顶点的图$G$至少包含$n-1$条边。实际上这是因为$G$具有连通性。”
• 常数：在计算机科学中，我们通常关注算法资源消耗（如运行时间）随某些量（如输入长度）的变化规律。将不依赖于输入长度的量称为常数，因此常出现如下表述：“存在常数$c>0$，使得对任意$n\in \mathbb{N}$，算法$A$在长度为$n$的输入上至多运行$c\cdot n^2$步。”虽然严格来说“常数”这个限定词并非必要，但加上它可以强调$c$是与$n$无关的固定值。有时为降低认知负荷，我们会直接用10/100/1000等足够大的整数替代$c$，或采用大$O$表示法表述为“算法$A$的时间复杂度为$O(n^2)$”。

1.8 习题

1.9 参考书目

标题“一个数学家的辩白”指的是哈代所著的经典作品（Hardy, 1941）。即便哈代的观点存在谬误，其著作仍极具阅读价值。

本书所需的数学背景知识可参考众多网络资源。其中麻省理工学院6.042课程《计算机科学数学》（Lehman, Leighton, Meyer, 2018）的讲义内容极为全面，课程视频与作业均在线公开。伯克利CS70课程《离散数学与概率论》同样提供详尽的在线讲义。

离散数学的其他参考资料包括罗森著作（Rosen, 2019）及吉姆·阿斯彭斯的在线教材（Aspens, 2018）。刘易斯与扎克斯（Lewis, Zax, 2019）以及弗莱克的在线著作（Fleck, 2018）对相同内容作了更通俗的阐释。索洛（Solow, 2014）是证明阅读与写作的优质入门指南。库恩（Kun, 2018）为具有编程背景的读者撰写了数学导论。斯坦福CS103课程提供关于数学证明技巧与离散数学的精彩讲义合集。

定义1.3：无向图中“graph“（图）一词由数学家西尔维斯特于1878年参照用于分子可视化的化学图式所创。需注意该术语与通常表示数据图表（尤其是函数$f(x)$相对于$x$的图像）的“graph“存在语义混淆。二者可通过以下方式建立关联：将函数$f:A\to B$与定义在顶点集$V=A\cup B$上的有向图$G_f$相关联，使得对每个$x\in A$，$G_f$都包含一条从$x$指向$f(x)$的边。在此构造的有向图$G_f$中，$A$集内每个顶点的出度均为$1$。若函数$f$是单射，则$B$集内每个顶点的入度至多为$1$；若函数$f$是满射，则$B$集内每个顶点的入度至少为$1$；若$f$是双射，则$B$集内每个顶点的入度恰好为$1$。

卡尔·波默兰斯的引文出自多伦·齐尔伯格的个人主页。

---

1: QED即拉丁文quod erat demonstrandum”，意为“这被证明了”

2: 一种方法是对阶乘函数使用斯特林近似。