• 数学背景
  • 学习目标
  • 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 参考书目

数学背景

学习目标

• 学习基本的数学概念, 如几何、函数、数字、逻辑运算符及量词、字符串和图.
• 严格地定义大$O$表示法.
• 归纳证明法.
• 练习如何阅读数学 定义、陈述与证明.
• 将直观的论证转化为严谨的证明.

在本章中, 我们将会介绍一些将在本书中用到的数学概念. 这些概念一般会在“计算机科学中的数学“或“离散数学“等课程或课本中讲解. 有关这些主题的几份可在线免费获取优秀资源, 请参阅“参考书目“部分(第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.3.1 定义

数学家经常在已有的概念上定义新的概念. 比如, 以下是一个你可能曾经见过的数学定义(并且我们很快还会再见到):

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

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.1的证明

选择某个$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节中的资料中详细了解它们.

图有两种基本类型: 无向图与有向图.

基于这个定义, 我们可以定义关于图与顶点的几个性质. 我们将$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节中的诸多资源中找到).

通过观察可知: 每条边$\{u,v\}$会对度数总和贡献两次(一次作用于$u,$ 另一次作用于$v),$ 由此可证明引理 1.2.

通过将路径$(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.3.

通过“捷径修剪法“可证明引理 1.4: 若某路径中同一节点$w$出现两次, 则移除其间的循环段(见图 1.5). 将这一直观论证转化为形式化证明是很好的练习:

对练习 1.1的解答

此证明遵循图 1.6所示的思路. 需要注意的复杂性在于: 路径中可能有多个顶点被重复访问, 因此“捷径修建“不一定能直接得到简单路径. 我们通过考察$u$与$v$之间的最短路径来解决该问题. 具体如下:

设$G=(V,E)$为无向图, $u$和$v$为$G$中两个连通顶点. 我们将证明存在连接$u$和$v$的简单路径. 令$k$为$u$与$v$之间路径的最短长度, 并设$P=(u_0,u_1,u_2,\dots ,u_{k-1},u_k)$为一条长度为$k$的路径(可能存在多条此类路径, 若有则任选其一). (即$u_0=u,$ $u_k=v,$ 且对任意$l\in [k]$有$(u_l,u_{l+1})\in E.$ )我们断言$P$是简单路径. 假设存在某个顶点$w$在路径中出现两次: 即对某些$i<j$有$w=u_i$且$w=u_j.$ 此时可通过取$P$的前$i$个顶点(从$u_0=u$到$w$的首次出现)和后$k-j$个顶点(从$w$第二次出现后的顶点$u_{j+1}$到$u_k=v),$ 得到捷径路径$P^{\prime }=(u_0,u_1,\dots ,u_{i-1},w,u_{j+1},\dots ,u_k).$ 由于$w=u_i=u_j,$ $(u_{i-1},w)$和$(w,u_{j+1})$都是$E$中的边, 因此$P^{\prime }$是连接$u$和$v$的有效路径. 但$P^{\prime }$的长度为$k-(j-i)<k,$ 这与$P$的最小性矛盾.

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

有向图可能同时包含边$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), 顾名思义即为不含环的有向图:

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

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$的所有整数的平方和可表示为:

$$\sum _{i\in \{1,\dots ,100\}}{i}^2\text{\hspace{1em}(1.1)}$$ 由于对整数区间求和极为常见, 对此存在特殊记号. 对于任意两个满足$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$约束的变量:

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

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

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

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

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

$${\exists }_{x,y\in \mathbb{N}}(x\ne 1)\wedge (x\ne n)\wedge (n=x\times y)\text{\hspace{1em}(1.3)}$$ 与(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$表示法:

在大$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$为假“作为开头, 并以推导出一个矛盾作为结尾(如违反定理陈述中的某个假设). 以下是一个例子:

证明

假设, 为了得出矛盾, 上述引理为假. 令$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$来结束, 以下是一个简单的例子:

证明

证明: 设$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$来结束. 以下是一个简单的例子:

证明

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

$$\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}\text{\hspace{1em}(1.4)}$$ 整理(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.4)都可以进行分层排列, 使得对于所有有向边$u\to v,$ 顶点$v$所在的层都大于$v$所在的层. 这一结论被称为拓扑排序, 被广泛应用于任务调度、构建系统、软件包管理、电子表格单元格计算等场景(见图 1.7). 事实上, 在本书后续内容中我们也会用到这一结论.

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

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

要证明此类定理, 首先需要理解其含义. 由于这是一个“当且仅当“类型的陈述, 定理 1.1对应两个命题:

要证明定理 1.1, 则需同时证明引理 1.11和引理 1.12. 引理 1.12的证明实际上并不困难: 直观上, 若$G$包含环, 则环上所有边的层数不可能全程递增—因为沿着环行进时必然会回到起点. 形式化证明如下:

对引理 1.12的证明

证明: 设$G=(V,E)$为有向图, $f:V\to \mathbb{N}$是符合定义 1.6的分层函数. 用反证法假设$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.11对应着更复杂(但更有用)的方向. 要证明它, 需要说明如何为任意有向无环图$G$构造分层, 使得所有边“指向上层“.

1.6.1 数学归纳法

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

归纳法本质上是显而易见的“肯定前件“逻辑规则(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.11有多种方式. 我们将基于顶点数量$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.11证明的直观思路. 但在撰写正式证明时, 我们将基于后见之明进行优化, 将原本曲折的推理过程转化为从“证明: “开始到“证毕(QED¹)”(或符号$■)$结束的线性化逻辑流. 讨论、示例和旁注虽颇具启发性, 但应该置于这两个标记界定的空间之外——正如优秀的指南所述, 此空间内“每个句子都必须承担论证功能“. 如同编程, 我们可以将证明分解为小型“子程序“或“函数“(数学中称为引理或断言), 即通过辅助性小命题来证明主要结论. 但证明结构必须确保读者能清晰把握论证阶段, 理解每个句子的作用及所属部分. 现正式证明引理 1.11.

对引理 1.11的证明

证明: 设$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.1保证每个有向无环图$G=(V,E)$都存在分层函数$f:V\to \mathbb{N},$ 但这种分层不一定唯一. 例如, 若$f:V\to \mathbb{N}$是图的有效分层, 那么定义为$f\prime (v)=2\cdot f(v)$的函数$f\prime$也是有效分层. 然而最小分层却是唯一的——最小分层要求每个顶点都被赋予尽可能小的层数. 现正式定义最小性并陈述唯一性定理:

定理 1.2中的最小性定义意味着: 对每个顶点$v\in V,$ 我们无法在保持分层有效性的前提下将其移至更低层. 若$v$是源点(即入度为零), 则最小分层$f$必须将其置于$0$层; 对于其他顶点$v,$ 若$f(v)=i,$ 则由于存在满足$f(u)=i-1$的入邻居$u,$ 我们无法将$f(v)$修改为$i-1$或更小值. 定理 1.2表明最小分层$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.$

对定理 1.2的证明

设$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.2中“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: 一种方法是对阶乘函数使用斯特林近似.