离散数学与证明研究什么

离散数学这门课有个很容易让人误会的名字。你看到“逻辑、集合、归纳、计数、图论”，可能会以为这是把五六种零散工具装进同一个课名里；真正学进去之后会发现，它们一直在做同一件事：把一个问题说准确，再说明结论为什么一定成立。

这和只求一个数值的体验不太一样。计算题常常已经替你规定好了对象、运算和目标，你沿着熟悉的步骤往下算就行。离散数学却会不停追问：研究对象到底是什么？两个对象之间的关系是什么？“对所有对象都成立”和“至少有一个对象成立”差在哪里？试了许多例子之后，凭什么敢说下一个例子也不会出错？

第一次学证明时，最难的通常不是某个符号，而是老师写完“显然”“于是”之后，中间那一步你根本不知道从哪里来的。本课程会把这种思考过程摊开讲：为什么先回到定义，为什么要取一个任意对象，为什么一个反例就够推翻全称命题，以及为什么归纳假设不是循环论证。我们既要让论证正确，也要让别人看得懂它为什么正确。

---

“离散”说的不是东西很少

先看最直观的区别。整数 $0,1,2,\ldots$ 一个接一个，可以逐个编号；一个有限字符串由有限个字符排成；一张课程表由课程、教室和时段组成；一个网络由节点和连接组成。这些对象彼此可区分，适合逐项讨论，我们把它们看成离散对象。

实数区间、曲线上的位置、连续变化的温度则不一样。任取两个不同实数，它们之间还能找到别的实数。研究这类对象时，我们常问极限、变化率、面积或连续性，这更接近连续数学的视角。

这里有两个常见误会。第一，离散不等于有限。自然数有无限多个，所有有限二进制串也有无限多个，但每个对象仍能被清楚地区分和按规则生成。第二，现实对象本身不会永远贴着“离散”或“连续”的标签，关键看我们准备回答什么问题。

例如，一天的时间可以看成区间 $[0,24]$，用来研究某个过程在任意时刻的变化；排课时又会把一天切成第一节、第二节、午间和晚间等有限时段。城市道路画在地图上是连续曲线，研究路由时却可以只保留路口和道路的连接关系。前一种模型保留位置与距离，后一种模型保留“能否从这里走到那里”。

你可以在下面的分类器里试几种对象。它的重点不是抢答，而是比较同一个对象在不同研究目的下为什么会有不同判断。

---

离散数学先做三件事：定对象、定关系、定问题

面对一个现实问题，离散数学不会急着套公式。我们先把题目压缩成一个可以推理的模型。这个过程通常有三步。

从排考试看抽象是否有用

假设有甲、乙、丙、丁、戊五门课。只要有学生同时选了两门课，这两门课就不能在同一时段考试。若一直盯着课程名称，我们很难看出问题的骨架；换一种表示就清楚了：

• 每门课程画成一个顶点；
• 两门课有考试冲突，就在对应顶点之间连一条边；
• 每个考试时段用一种颜色表示；
• 一个安排合法，意思是每条边的两个端点颜色不同。

这样一来，“最少需要几个考试时段”就变成了“最少用几种颜色能完成合法着色”。顶点并不是真的圆点，边也不是真的线，颜色更不是在研究美术。它们只是把课程、冲突和时段换成了更容易推理的语言。

抽象时不是保留的信息越多越好。学生姓名、课程教室在这个模型里可能不重要，冲突关系却不能丢。一个合适模型应当刚好保留决定答案的信息。如果删掉的信息会改变答案，模型就删过头了；如果保留了一堆不会影响答案的细节，后面的推理只会更乱。

下面的工作台把排课、网络、密码和树放在一起。切换场景时，可以一直盯着“对象—关系—问题”这条主线，看表面不同的问题怎样变成相似的离散结构。

---

证明为什么会成为整门课的主线

我们先把“证明”说得朴素一点：证明是一条从已经接受的起点出发，经过有根据的逻辑步骤，到达目标结论的推理链。起点可以是定义、题目条件、已经证明过的结论或课程明确采用的基本规则；中间每一步都要能说明依据；最后要真正回到原命题，而不是停在“差不多看出来了”。

为什么不能只靠实验和算例？如果只问 $37+45$ 是奇数还是偶数，算一次就能回答。但若命题是“任意两个奇数之和都是偶数”，它涉及无穷多对整数。你无法把这些整数一对一对全部试完。计算前一万组都成功，只能说明暂时没遇到反例，不能说明第一万零一组也一定成功。

更重要的是，证明不只给“正确”盖章，它还解释结论为什么成立。知道奇数的定义之后，下面这个证明几乎是被定义推着走出来的。

例题：任意两个奇数之和都是偶数

动笔前先说思路。结论里出现“奇数”和“偶数”，最自然的入口不是列举 $1,3,5,7$，而是把这两个词翻译成它们的定义。奇数能写成 $2k+1$，偶数能写成 $2k$。我们的目标因此变成：把两个奇数的和整理成 $2$ 乘某个整数。

这个证明的计算只有一行，真正的工作却有四件：看出该展开哪个定义，选取任意对象，用变量保留一般性，再把整理后的式子送回目标定义。证明题常见的“没思路”，往往不是不会算，而是不知道该从哪个定义出发。

---

例子能发现规律，不能替所有情况作证

数学探索常常从算例开始，这没有问题。画图、列小规模情形、写程序试验，都能帮我们看见结构。需要分清的是，例子在推理链里扮演什么角色。

考虑前 $n$ 个奇数的和：

$$1+3+5+\cdots+(2n-1)$$

代入 $n=1,2,3,4$，得到 $1,4,9,16$。这些数恰好是 $1^2,2^2,3^2,4^2$，于是我们猜想：

$$1+3+5+\cdots+(2n-1)=n^2$$

这个观察非常有价值，因为它告诉我们可能要证明什么，还暗示了“把每次增加的奇数看成正方形外面的一层”这种图形思路。但此刻它仍是猜想。要把“前四个都成立”升级成“每个正整数 $n$ 都成立”，还缺一条覆盖任意 $n$ 的一般论证。

全称命题和反例并不对称

全称命题说“范围里的每个对象都有某个性质”。要证明它，我们必须给出能覆盖整个范围的理由；要推翻它，却只需找出一个落在范围内、但不具有该性质的对象。

例如，“每个奇数都是素数”在 $3,5,7$ 上都成立，但 $9$ 是奇数且 $9=3\cdot3$，所以命题立刻被推翻。反例不必多，一个合格的反例已经足够。

更能说明问题的是表达式

$$p(n)=n^2+n+41$$

从 $n=0$ 一直算到 $n=39$，结果都是素数。这样的连续成功很容易让人产生信心。可是在 $n=40$ 时，

$$p(40)=40^2+40+41=41^2$$

它不是素数。前面四十个正确样本没有被浪费，它们帮助形成了一个很有吸引力的猜想；只是这个猜想最终遇到了反例。数学上成熟的做法不是埋怨反例“太特殊”，而是回头修改命题，或者寻找真正能解释现象的条件。

1

一个程序通过了十万组测试，因此已经证明它对所有合法输入都正确。

正确错误

---

先看命题在说“所有”还是“存在”

证明方法并不是看到题目后随便挑一种。命题的逻辑形状会给出方向。尤其要先看清它说的是“对所有对象”“存在一个对象”“如果条件成立，那么结论成立”，还是“两个条件恰好等价”。

证明“所有”时，为什么要取任意对象

若目标是“所有偶数的平方都是偶数”，我们会取一个任意偶数 $n$，然后只使用“$n$ 是偶数”这个条件推理。因为没有利用 $n$ 的特殊数值，所以论证能够覆盖每个偶数。

反过来，只证明 $2^2,4^2,6^2$ 是偶数，覆盖的只是三个对象。这里最该问的不是“我还要再算几个”，而是“我能不能用定义一次处理任意偶数”。

证明“存在”时，一个见证就够了

若目标是“存在一个大于 $10$ 的偶素数”，这句话是假的，因为唯一的偶素数是 $2$。若目标改成“存在一个大于 $10$ 的偶合数”，给出 $12$ 并检查它满足条件，就已经完成存在性证明。

所以例子并非永远不能当证明。它不能证明全称命题，却常常正是存在命题所需要的见证。关键不在“例子多不多”，而在命题究竟要求覆盖多少对象。

证明条件命题时，从假设出发走向结论

面对“如果 $P$，那么 $Q$”，最直接的思路是暂时假设 $P$ 成立，再利用定义和已知事实推出 $Q$。如果走不通，还可以考虑证明逆否命题、分类讨论或反证。但无论使用哪种方法，我们都要清楚前件、后件和允许使用的条件。

2

下面哪些做法足以完成对应命题的证明？

A.用反例 9 推翻‘所有奇数都是素数’B.用例子 12 证明‘存在一个大于 10 的偶合数’C.检验 2、4、6 后证明‘所有偶数的平方都是偶数’D.只说‘结论很明显’来证明一个条件命题

提交

这些差别很快会变成逻辑符号中的全称量词、存在量词、蕴含和等价。现在先不用背符号，先养成一个习惯：每次证明前，用普通中文把命题的范围和方向读准确。

---

逻辑、集合、归纳、计数和图论怎样连起来

课程后面会出现不少新名词，但学习路线并不是每到一章就重新开始。前面的语言会一直留在后面的证明里。

逻辑先把句子说准

我们从命题开始，研究“且”“或”“非”“如果……那么……”和“当且仅当”。真值表会迫使我们检查所有真值组合，逻辑等价会帮助我们把难处理的命题换成更方便的形式。量词则让“每一个”“至少一个”“不存在”有准确含义。

这一步看起来像语法课，实际上是在清理证明的输入。如果一句话连真假条件都含糊，后面的推理不可能可靠。

集合、函数和关系给对象安位置

集合回答“我们正在讨论哪些对象”；函数回答“每个输入对应哪个输出”；关系回答“哪些对象彼此有关”。图的边本身就是一种关系，计数问题经常是在数某个集合的元素，递推过程又常由函数或序列描述。

所以集合不是单独的一小章记号。后面说图的顶点集、边集，说函数是不是一一对应，说两种对象能否配对计数，都要回到集合语言。

证明方法负责把条件送到结论

直接证明适合从定义一路推出目标；分类讨论把全部情况分开处理；逆否和反证会改变推理入口；存在唯一性证明要分别处理“至少有一个”和“至多有一个”。方法名并不是固定模板，它们提醒我们当前要承担什么证明义务。

归纳处理一步一步生成的对象

当命题按自然数编号，或者对象按递归规则逐层生成时，归纳法会出现。它先固定一个起点，再证明“只要当前一步成立，下一步也会成立”。归纳步骤证明的是一个条件关系，不是在无条件假设最终结论。

递归算法、递推数列、树的层次和字符串结构都带着“从较小对象生成较大对象”的味道。归纳正好沿着同一生成方向验证性质。

计数研究怎样不漏也不重

计数不只是把数字乘起来。我们会问：一次选择分几步？不同情形是否互斥？同一个结果被重复数了多少次？能否在两个集合之间建立一一对应？

密码空间的大小影响穷举难度，算法运行时间常来自操作次数，概率的分母和分子也依赖计数。一个可靠的计数解法必须解释为什么每个合法对象恰好被数到一次，或者为什么重复次数正好可以除掉。

图论把关系本身当作研究对象

在图论里，顶点表示对象，边表示成对关系。路径、连通、树、匹配、平面性和着色看起来是图形问题，本质上都在研究关系结构。考试排程是着色，网络路由是路径，任务依赖可用有向图表示，配对问题会进入匹配。

普通图可以有环，也可以让一个顶点连接多个邻居。树则是更受约束的图：它连通且无环。选定一个根之后，除根以外的每个顶点都能沿唯一方向追溯到父节点。正因为路径不会绕圈，树很适合表示文件目录、递归分解和层级关系。

---

一份能让人读懂的证明应该怎样写

逻辑正确是底线，但一串形式上没错的符号未必能帮助读者理解。刚开始写证明时，可以把它当成一篇很短的说明文：先告诉读者准备怎么走，再让每一步按顺序接上，最后亲手把结论扣回题目。

先交代路线

如果要分类讨论，就先说明按什么标准分、为什么这些情况没有遗漏；如果要反证，就说明准备假设目标结论不成立；如果要展开定义，就直接告诉读者“目标出现偶数，因此先把偶数写成 $2k$ 的形式”。

这几句话有时不属于形式推演，却能回答学生最关心的问题：“你是怎么想到第一步的？”

让推理保持线性

证明中的一句话应该接着上一句，并为下一句服务。不要在末尾突然调用一个从未说明的条件，也不要把关键理由藏在“显然”“容易看出”后面。真正简单的步骤可以简写，但首次出现的新动作最好交代依据。

方程旁边也要有句子

只有一长串等号，读者很难知道每个等号为什么成立。公式适合承担计算，句子负责说明变量的含义、使用了什么定义，以及这一行怎样接近目标。证明不是把所有中文删掉之后剩下的式子。

结尾要回到原命题

当你已经得到 $x+y=2(a+b+1)$，还应补上“$a+b+1$ 是整数，所以 $x+y$ 是偶数”。这不是多余重复，而是把计算结果和目标定义接起来。许多不完整证明的问题，正是作者在最后一步觉得“读者自己会懂”。

写完后可以按下面的顺序做一次“证明对账”。

---

带着四个问题开始后面的学习

这一章不要求你立刻写出复杂证明。它更像是在调整读题方式。以后看到一个新概念或一道题，先停几秒，依次问：

1. 对象是什么？ 是整数、集合、字符串、函数，还是图中的顶点和边？
2. 关系和限制是什么？ 哪些对象允许配对，哪些选择互相冲突，哪些步骤只能按某个方向进行？
3. 命题说的范围是什么？ 是所有对象、至少一个对象，还是在某个条件下成立？
4. 我现在拥有的是例子、猜想还是证明？ 如果只是试算成功，还缺什么才能覆盖题目要求的范围？

3

看到命题‘若一个整数能被 6 整除，则它能被 3 整除’，最合适的第一步是什么？

A.把‘能被 6 整除’按定义写成该整数等于 6kB.随机试十个整数C.直接写‘显然成立’D.先假设它不能被 2 整除

下一章会从最小的推理单位开始：什么样的语句能叫命题，几个命题怎样用“非、且、或、如果……那么……”连接，真值表又怎样穷尽检查所有真假组合。先把句子的逻辑结构看清楚，后面的集合证明、归纳、计数和图论论证才有可靠的起点。