离散数学与证明研究什么
很多数学课的第一印象是“算”。给出一个式子，化简；给出一个函数，求导；给出一组数据，算平均数。这些训练很重要，但离散数学与证明把问题稍微换了一个方向：我们更关心对象之间的结构，以及一个结论为什么对所有相关对象都成立。
这门课会反复出现几个问题：对象是什么？对象之间有什么关系？我们要证明的是“总是如此”“至少存在一个”“不可能发生”，还是“有多少种可能”？这些问题听起来朴素，却正是算法、网络、排课、密码、数据结构和组合问题的共同语言。
先看对象：离散与连续
“离散”可以先理解为：对象由一个一个分开的单位组成，或者可以被看成一步一步的状态。整数、有限字符串、班级里的学生、网络中的节点、课程表里的时段，都是典型例子。它们之间可以有很多关系，但对象本身通常能被逐个点名、逐个编号、逐个比较。
“连续”更像是一整段没有断开的量。实数区间、曲线上的位置、温度随时间平滑变化的模型，常被连续数学处理。连续对象的典型问题是极限、变化率、面积和逼近；离散对象的典型问题是逻辑关系、组合数量、路径、结构和可证明的规则。
不过，“离散”和“连续”不是给现实贴永久标签。它们常常取决于建模方式。一天的时间可以被连续地看成从 0 到 24 的区间；排课时，它也可以被切成上午第一节、第二节、下午第一节这样的离散时段。地图上的路线可以用连续曲线画出；网络路由又会把它抽象成若干节点和边。
离散数学不是“只研究有限小东西”。自然数有无限多个，所有有限字符串也有无限多个，但它们仍然是离散对象，因为每个对象可以被清楚地区分出来。连续数学也不是“只研究画曲线”，它研究的是连续变化的结构。
离散数学的对象长什么样
离散数学不是一堆互不相干的技巧。它研究的对象看起来不同，但经常共享同一种思路：先把对象说清楚，再把关系说清楚，最后问一个能被证明或计算的问题。
例如，一个集合可以表示“选课学生的名单”；一个字符串可以表示“密码的一次输入”；一个序列可以表示“递归过程产生的状态”；一个图可以表示“谁和谁有冲突、谁和谁相连”；一棵树可以表示“从一个问题分解到多个子问题的过程”。
这些对象一旦被抽象出来，就能提出更一般的问题：
- 一个密码系统到底有多少种可能输入？
- 一个排课方案能不能避免冲突？
- 一个网络断掉一条边之后是否仍然连通？
- 一个递归算法会不会停下来？
- 一个数据结构为什么能在有限步内找到目标？
这些问题不只是要“算出一个例子”。我们往往要知道，对所有符合条件的输入，结论是否都成立。
一个很小的建模例子
假设有 5 门课：甲、乙、丙、丁、戊。如果两门课有学生同时选，就不能安排在同一考试时段。我们可以把每门课看成一个点，把“不能同一时段考试”的关系画成边。这样，排课问题就变成了图着色问题：相连的点不能使用同一种颜色。
这个例子里，点不是几何上的点，边也不是现实中的线。点代表课程，边代表冲突关系，颜色代表考试时段。离散数学关心的正是这种抽象：把现实约束变成可以推理的结构。
判断一个离散模型是否合适，不看图画得像不像现实，而看它是否保留了问题真正需要的对象、关系和目标。
为什么证明是主线
在这门课里，证明不是正文后的附属环节。它是连接定义、例子和一般结论的主线。
如果我们只想知道 是奇数还是偶数，计算一次就够了。可是如果我们想知道“任意两个奇数相加一定是偶数吗”，就不能靠列举几个例子结束。例子可以帮助我们发现规律，但证明要说明为什么没有遗漏的情形。
例题：两个奇数相加为什么一定是偶数
证明：任意两个奇数之和是偶数。
先回到定义。一个整数是奇数，意思是它可以写成 的形式，其中 是某个整数。不要直接说“奇数看起来隔一个出现”，那是直观，不是证明的起点。
设两个奇数分别为 和 ，其中 都是整数。这样写并没有限制具体是哪两个奇数，因为每个奇数都能这样表示。
这个证明很短，但它体现了证明训练的核心动作：展开定义、引入任意对象、保持变量的一般性、把结果重新落回定义。
“我试了很多例子都对”通常只能支持猜想，不能替代证明。离散问题尤其容易出现这种误判，因为前几十个例子可能非常整齐，直到某个反例才暴露问题。
从例子到猜想，再到定理
数学发现常常从例子开始。观察、试算、画图都很有用。问题在于，例子只能告诉我们“这些情况发生了什么”，不能自动推出“所有情况都会这样”。
一个适合入门的例子是前 个奇数的和：
当 时，我们得到 。这些结果像平方数，于是产生猜想。接下来有两条路：一条是继续试更多例子，增强直觉；另一条是写出能覆盖任意 的证明。只有第二条路能把猜想变成定理。
反例为什么有力量
证明一个全称命题通常要覆盖所有对象；推翻一个全称命题只需要一个反例。例如命题“所有奇数都是素数”是假的，因为 是奇数，但 ，不是素数。
更有迷惑性的例子是表达式 。当 时，它都给出素数。可是当 时，
这不是素数。这个例子说明，很多正确样本也不能保证全称结论成立。
命题“如果一个正整数能被 6 整除，那么它能被 3 整除”是真的。因为能被 6 整除表示这个数可以写成 ，其中 是整数，而 ，所以它能被 3 整除。命题“如果一个正整数能被 3 整除，那么它能被 6 整除”是假的，反例是 ：它能被 3 整除，但不能被 6 整除。
离散结构在哪里出现
离散数学常常出现在计算机科学和现实约束问题的底层。它的作用不是把所有问题都画成图，而是帮我们把“对象、关系、限制、目标”拆开。
在算法中，我们不仅问程序对某个输入会输出什么，还问它对所有合法输入是否都会给出正确结果。循环不变量、递归证明和归纳法会在这里出现。
在网络中，设备和连接可以抽象成图。我们关心两个节点之间是否有路径、最短路径有多长、删除某些连接后网络是否仍然连通。
在排课和资源分配中，冲突关系可以抽象成边，时间段或资源可以抽象成颜色。问题变成：能不能用有限个颜色给所有点着色，使得相连的点颜色不同。
在密码和安全问题中，计数帮助我们估计可能性的规模。一个 6 位数字密码若允许重复，有 种；若不允许重复，第一位有 10 种选择，第二位有 9 种选择，依此类推，共有 种。
在数据结构中，树、图、堆、哈希表都不是装饰性的名字，而是对“数据如何组织、如何查找、如何更新”的离散描述。
本课程不会把这些应用都做成工程项目。我们先学习它们共享的数学语言：逻辑、集合、函数、关系、归纳、计数和图。后续课程再把这些语言接到更大的算法和建模问题上。
本课程会怎样前进
本课程的前半段会建立语言：命题逻辑让我们说清“如果……那么……”；谓词逻辑和量词让我们表达“所有”“存在”“唯一”；集合、函数和关系让我们描述对象与对象之间的对应。
中段会集中训练证明方法。直接证明、分类讨论、逆否证明、反证法、存在唯一性证明和归纳证明，会让你逐步习惯从定义出发写出完整论证。
后半段进入离散结构的典型问题。计数会回答“有多少种可能”；图论会回答“哪些对象相连、是否能分配、是否有路径”；递归和归纳会帮助我们理解一步一步生成的系统。
学习这门课时要做的几件小事
看到新概念时，先问“对象是什么”。例如图论里的点可能是人、课程、网页、城市或状态，不一定是几何点。
再问“关系是什么”。两个对象之间的边可能表示认识、冲突、相邻、可达，也可能表示一次函数调用。
接着问“结论的量词是什么”。命题说的是所有对象、至少一个对象、唯一一个对象，还是不存在某种对象？量词会决定证明路线。
最后问“我是在算一个例子，还是在证明一类情形”。算例能帮你试探方向，但证明要能覆盖题目要求的整个范围。
章末自检
- 下面哪些对象更自然地建模为离散对象：全校学生名单、钟表指针转过的角度、社交网络中的好友关系、一杯水的温度随时间变化？
全校学生名单和好友关系通常更自然地建模为离散对象，因为可以把学生逐个列出，把好友关系表示成边。钟表指针角度和温度随时间变化常用连续模型。不过，如果问题只关心“每 5 分钟记录一次温度”或“把一天切成固定时段”，它们也可以被离散化。
- “某个算法在我试过的 100 个输入上都正确”是否已经证明算法正确？
还没有。测试很多输入能增加信心，也可能帮助发现错误，但算法正确性通常要求对所有合法输入都成立。证明要说明程序的每一步为什么保持正确性，或者说明递归、循环和终止条件为什么覆盖全部情况。
- 面对一个排课问题，为什么图可以成为合适的模型？
因为排课问题的核心不是课程名称本身，而是哪些课程彼此冲突。把课程看成点，把冲突看成边，就保留了“不能同一时段安排”的约束。接着把时段看成颜色，问题就变成相邻点不能同色的图着色问题。
这一章不要求你马上会写复杂证明。它的目标是让你知道，这门课会把“算出答案”的习惯扩展成三件事：清楚地定义对象，准确地表达关系，并用证明说明结论为什么可靠。