CSC3001 离散数学 · LN0 绪论（Introduction）

课程从哪来

这门课是 CSC3001 离散数学（Discrete Mathematics）。讲义首页就写明了一个来源信息：所有 lecture notes 都基于香港中文大学 Prof. Lap Chi Lau 的讲义，而 Lap Chi 在编写这些讲义时又参考了 MIT 课程的资源。所以你手上这份材料的"血统"是 CUHK 加 MIT 的混合体，风格上偏重直觉与问题驱动，而不是一上来就给一堆定义。

首页还留了一个 A、B、C 的标记，这通常是讲义的版本或班次标识，不影响内容本身。第二页的 Plan 列出了本次课的三件事：课程信息与安排（Course Information and Arrangement）、课程主题（Topics of the Course）、课程目标（Course Objective）。旁边有一句加框的提示：Please read the course outline carefully，请仔细阅读课程大纲。这句话值得当回事，因为讲义里并不包含评分比例、作业截止日期、考试形式这些行政信息，它们只存在于 course outline 里。

什么是离散数学

要理解离散数学（Discrete Mathematics），最省事的办法是拿它跟我们已经学了很多年的连续数学（Continuous Mathematics）对照。

我们在中学和大学低年级接触的数学，绝大部分是连续的：研究对象是实数（Real Numbers），实数可以在数轴上连续地滑动，任意两个数之间永远还能再插入一个数；研究空间是几何空间（Geometric Space），点线面都是连续的；使用的主要工具是微积分（Calculus），核心动作是取极限、求导、积分。

离散数学恰好站在对面。它的研究对象是整数（Integers）——数轴上一个个跳着走的孤立点，5 和 6 之间没有别的整数；是图（Graphs）——用若干顶点和连接它们的边构成的离散结构；使用的主要工具是归纳法（Induction）和逻辑（Logic）。

不过这里有一个特别重要、也特别容易被误解的点，讲义专门用一行小字标了出来：这两个领域并不是不相交的（These two areas are not disjoint）。也就是说，连续的工具可以用来解决离散的问题。讲义举的例子是生成函数（Generating Functions）：我们要数一个离散的序列（比如第 $n$ 项有多少种方案），却可以把这个序列塞进一个幂级数的系数里，然后对它做求导、展开这类微积分操作，最后再把结果翻译回离散的答案。这是一个"用连续方法打离散问题"的经典招式，这门课后面讲计数时会用到。

一句话概括：连续数学研究平滑变化的东西，离散数学研究一个个分开的东西，两者有分工也有交叉。

为什么计算机科学需要离散数学

讲义给了三条理由，每一条都对应一种很实际的处境。

第一条是关于存储的。我们在数学里可以随手写下一个实数，比如 $\pi$，它是无限精度的。但计算机做不到这件事，因为内存只有有限多个 bits，能表示的数必然是有限精度（Finite Precision）的。所以计算机真正处理的世界，本质上就是一个离散的、有限的世界。

第二条是关于建模的。我们常常把一个计算机网络（Computer Network）建模成一张图：每台机器是一个顶点，每条链路是一条边。一旦建成了图，图论里积累的知识和技巧就可以直接拿来解网络问题。这是"把现实问题翻译成数学结构"的典型例子，也是这门课贯穿始终的一种能力。

第三条是关于技巧的。离散世界里常用的招数和连续世界不同，最典型的是归纳法（Induction）和递归（Recursion）。这两者其实是一体两面：递归是把大问题拆成小问题来写程序，归纳法是证明这个程序对所有输入都正确。你在这门课里会反复用到它们。

课程地图：四个主题

这门课的内容分成四个主题，讲义对每一个都给了三样东西：具体学什么、用在哪里、目标是什么。

主题一：逻辑与证明（Logic and Proofs）

逻辑部分包括命题逻辑（Propositional Logic）和一阶逻辑（First Order Logic）。这两者的区别在于"粒度"：命题逻辑把一句话当成不可再分的最小单位，只研究"与、或、非、蕴含"这些连接词怎么组合；一阶逻辑则把句子拆开，引入"对所有的 $x$""存在某个 $x$"这样的量词（Quantifier），以及谓词（Predicate），表达能力要强得多。

证明部分主要是两种：归纳法（Induction）和反证法（Proof by Contradiction）。反证法的思路是"先假设结论不成立，然后推出矛盾"；归纳法的思路是"先证明起点成立，再证明若第 $n$ 步成立则第 $n+1$ 步也成立，于是全部成立"。

讲义在这一页顶上写了一句话作为整个主题的出发点：How do computers (and humans) think? 计算机（以及人）是如何思考的？这不是一个修辞问题，逻辑学本来就是对"有效推理"这件事的形式化，而它恰好也是计算机能够机械地执行推理的理论基础。

应用方面列了四个方向：人工智能（Artificial Intelligence）、数据库（Database）、电路（Circuit）、算法（Algorithms）。数据库查询语言 SQL 的底子就是一阶逻辑，电路设计的底子就是命题逻辑，这两条是最直接的。

这个主题的目标写得很明确：to reason rigorously and learn basic proof techniques，也就是学会严谨地推理，并掌握基本的证明技巧。特别要提醒的是，归纳法是后面所有内容的地基——算法正确性证明、递归式的求解、图论里的大量定理，都要靠它。

主题二：数论（Number Theory）

讲义用两个谜题开场，这两个谜题基本上就是整个初等数论的缩影。

第一个是水壶问题（Water Jug Problem）：给你一个 3 加仑的壶和一个 5 加仑的壶，没有刻度，只能做"装满、倒空、把一个壶倒进另一个壶直到前者空或后者满"这三种操作，怎么量出恰好 4 加仑？

具体操作序列是这样的：先把 5 加仑壶装满，倒进 3 加仑壶直到后者满，此时 5 加仑壶里剩 2；把 3 加仑壶倒空，把那 2 加仑倒进去，此时 3 加仑壶里有 2；再把 5 加仑壶装满，往 3 加仑壶里倒——后者只差 1 就满了，所以只能倒出 1，5 加仑壶里剩下的正好是 4。

但讲义真正想让你看到的是背后的数学。这壶问题能不能解，取决于目标量能不能被两个容量的最大公约数（Greatest Common Divisor, gcd）整除。这里 $\gcd(3, 5) = 1$，而 1 整除 4，所以有解。反过来说，如果给你一个 4 加仑壶和一个 6 加仑壶，$\gcd(4,6) = 2$，那你就只能量出 2 的倍数，永远量不出 3。

更精确地说，解的存在性来自贝祖等式（Bézout's Identity）：存在整数 $x, y$ 使得 $ax + by = \gcd(a,b)$。对我们的例子，

$$4 = 3 \times 3 - 5 \times 1$$

右边 9 减 5 等于 4。这个式子的操作含义很清楚：装满 3 加仑壶三次（一共 9 加仑），倒掉 5 加仑一次（5 加仑），净剩 4。所谓"操作序列"，其实就是把 Bézout 等式翻译成倒水动作。

第二个谜题更有名：We have 1073 soldiers. How could he figure it out?! 这是中国传统的"韩信点兵"故事，数学上叫中国剩余定理（Chinese Remainder Theorem, CRT）。讲义这一页只写了 1073 这个数字和一句感叹，没有写分组方式，但最经典的设定是"三人一排余 2，五人一排余 3，七人一排余 2"，也就是解下面这个同余方程组（System of Congruences）：

$$x \equiv 2 \pmod 3, \quad x \equiv 3 \pmod 5, \quad x \equiv 2 \pmod 7$$

这里的 $a \equiv b \pmod n$ 读作"$a$ 与 $b$ 模 $n$ 同余"，意思是 $a$ 和 $b$ 除以 $n$ 的余数相同。

我们来验证一下 1073 确实满足这个方程组：$1073 = 3 \times 357 + 2$，所以余 2；$1073 = 5 \times 214 + 3$，所以余 3；$1073 = 7 \times 153 + 2$，所以余 2。三个条件全部成立。

那它是唯一的答案吗？不是。最小正整数解是 23，而通解是 $23 + 105k$，其中 $105 = 3 \times 5 \times 7$ 是三个模数的最小公倍数，每加一个 105，三个余数都不变。而 $1073 = 23 + 105 \times 10$，所以 1073 是这组方程的又一个解——只要士兵人数在千这个量级，答案就被唯一确定了。这就是为什么"数一遍余数"就能知道总人数。

古人把这个过程编成了口诀：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。它的算法是

$$x \equiv 2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 = 233 \equiv 23 \pmod{105}$$

其中 70 是"被 5 和 7 整除、除以 3 余 1"的数，21 是"被 3 和 7 整除、除以 5 余 1"的数，15 是"被 3 和 5 整除、除以 7 余 1"的数。把余数分别乘上这些"开关"再相加，每一项只影响自己那一个条件、不影响另外两个，于是三个条件被自动同时满足。这就是 CRT 的构造精髓。

这个主题的目标是 to learn elementary number theory and classical results，即学习初等数论与经典结论；应用列的是整除性（Divisibility）和密码学（Cryptography）。密码学这一条是整个数论部分最"值钱"的出口——现代公钥密码体系（比如 RSA）几乎整个建立在初等数论之上。

主题三：图论（Graph Theory）

这个主题的清单是：图（Graphs）、度序列（Degree Sequence）、欧拉图（Eulerian Graphs）、同构（Isomorphism）、树（Trees）、匹配（Matching）、着色（Coloring）。

这里先把几个术语说清楚，因为后面整个主题都建立在它们之上。一个顶点的度（Degree）就是连在它上面的边的条数，把所有顶点的度排成一个序列就是度序列。欧拉图（Eulerian Graph）说的是存在一条经过每条边恰好一次并回到起点的回路的图，也就是"一笔画"问题。同构（Isomorphism）说的是两张图虽然画得不一样、顶点名字不一样，但连接关系本质上完全一样——数学上认为它们是同一张图。树（Tree）是连通且没有环的图。匹配（Matching）是从图里选出一组两两不相邻的边，可以理解为"两两配对"。着色（Coloring）是给每个顶点染一种颜色，要求有边相连的两个顶点颜色不同。

讲义用三个问题来说明图论能干什么。How to color a map? 怎么给地图着色——这是平面图着色问题，著名的四色定理（Four Color Theorem）说任何平面地图用四种颜色一定够。How to send data efficiently? 怎么高效地传数据——这是网络流、最短路、生成树这一类问题。How to schedule exams? 怎么排考试——把每门课看成一个顶点，只要有学生同时选了两门课就在两者之间连一条边，然后给这张图着色，颜色相同就意味着可以安排在同一时段，颜色数就是所需的最少时段数。

应用列的是计算机网络（Computer Networks）、电路设计（Circuit Design）、数据结构（Data Structures）。

这个主题的目标写的是 to model problems and learn basic concepts，重点是"建模"两个字。也就是说，这个 topic 真正要练的能力不是背定理，而是看到一个实际问题能认出它其实是个图论问题。

主题四：计数（Counting）

内容清单是：集合与函数（Sets and Functions）、组合与排列（Combinations, Permutations）、容斥原理（Inclusion-Exclusion Principle）、映射计数（Counting by Mapping）、鸽巢原理（Pigeonhole Principle）、递归（Recursions）。

这里简单解释两个可能陌生的。容斥原理解决的是"数多个集合的并集大小"的问题：先把每个集合单独加起来，但重叠部分被算了多次，所以要减掉两两交集，减多了又要加回三个的交集，如此交替下去。鸽巢原理说的是：如果把 $n+1$ 个物体放进 $n$ 个盒子，那么至少有一个盒子里有不止一个物体——听起来像废话，但它是证明"必然存在某种结构"的利器。

讲义用排序问题引出计数最重要的应用：How many steps are needed to sort n numbers? 给 $n$ 个数排序需要多少步？

第一个算法是 Bubble Sort。它的思路是每一轮都从头到尾扫描，把当前最小的数"冒泡"到它该在的位置上，所以第 $i$ 轮之后第 $i$ 小的数就位了。它的递推式是

$$T(n) = T(n-1) + \Theta(n)$$

意思是"排 $n$ 个 = 排前 $n-1$ 个 + 再扫一遍 $n$ 个元素"。展开后得到 $T(n) = \Theta(n^2)$。

第二个算法是 Merge Sort。它把数组对半分成两半，各自排好，再把两个有序数组合并起来。递推式是

$$T(n) = 2T(n/2) + \Theta(n)$$

意思是"排 $n$ 个 = 排两个 $n/2$ 的半边 + 一次线性时间的合并"。解出来是 $T(n) = \Theta(n \log n)$。

讲义在这一页最后写了 Solving the recursion，解递归式——这正是这个主题的落脚点：不是靠跑一遍程序来比较快慢，而是把算法的运行时间写成递推式，然后解出闭式解来比较。$n \log n$ 比 $n^2$ 增长慢得多，所以 n 一大，Merge Sort 就明显更快。

（这里的 $\Theta$ 读作 big-Theta，是"增长阶"的意思：$T(n) = \Theta(n^2)$ 表示当 $n$ 很大时，$T(n)$ 与 $n^2$ 只差一个常数倍。）

应用列的是概率（Probability）、数据结构（Data Structures）、算法（Algorithms）。计数是这两者的前置：不会数，就谈不上算期望，也谈不上算复杂度。目标是 to learn basic concepts (set, functions) and fundamental techniques。

如何学好这门课：四道判断题

讲义最后一页是本讲最有价值的一页。它先给了四道题让你判断对错，然后给出订正。这四道题全部是错的，而每一道都对应一类非常典型的思维陷阱。

第一题：$\emptyset \in \mathbb{R}$

订正是 $\emptyset \subseteq \mathbb{R}$。

这里的关键是两个符号的差别。符号 $\in$ 表示"是……的元素"（is an element of），它连接的是一个个体和一个集合；符号 $\subseteq$ 表示"是……的子集"（is a subset of），它连接的是一个集合和另一个集合。

$\emptyset$ 是空集（Empty Set），它本身是一个集合，里面没有任何元素。显然它不是一个实数，所以 $\emptyset \in \mathbb{R}$ 是假的。但是有一条基本性质：空集是任何集合的子集。这条性质其实是"空真地成立"的——因为要让 $\emptyset \subseteq \mathbb{R}$ 为假，你必须在 $\emptyset$ 里找出一个不属于 $\mathbb{R}$ 的元素，而你一个元素都找不出来，所以它只能为真。因此 $\emptyset \subseteq \mathbb{R}$ 成立。

记忆方法：$\in$ 看的是"个体对集合"，$\subseteq$ 看的是"集合对集合"。分不清的时候先问自己：左边那个东西是一个个体，还是一个集合？

第二题：$x^2 \neq y^2 \iff x \neq y$

订正是 $x^2 \neq y^2 \Rightarrow x \neq y$，双向箭头要改成一个方向。

符号 $\iff$ 表示"当且仅当"（if and only if），即左右互相推出；$\Rightarrow$ 表示"推出"（implies），只有一个方向。

先看从左往右：$x^2 \neq y^2 \Rightarrow x \neq y$。这个方向是真的，但直接证有点别扭，最好用逆否命题：它等价于"若 $x = y$ 则 $x^2 = y^2$"，而这是显然成立的。

再看从右往左：$x \neq y \Rightarrow x^2 \neq y^2$。这个是假的，因为反过来平方相等并不意味着数本身相等，只意味着它们相等或互为相反数。取 $x = 1, y = -1$，两个数的平方都是 1，但 $1 \neq -1$。一个反例就推翻了整个方向。

这道题的方法论价值很高：看到一个 $\iff$ 命题，第一反应应该是把它拆成两个方向分别验证，而推翻一个方向最快的方式就是找一个反例。

（附注：如果额外限定 $x, y$ 都是非负的，那么 $x^2 = y^2 \iff x = y$ 才重新成立。这说明一个命题的真假往往依赖于隐含的前提条件。）

第三题：$a > b, c > d \Rightarrow ac > bd$

订正写的是：$ac$ 可以大于、小于、或等于 $bd$，也就是结论不确定。

直觉上这看起来是对的——两个更大的数相乘，结果当然更大。但这个直觉只在所有量都是正数的时候才成立。一旦涉及负数，乘以一个负数会让不等号翻转，于是直觉就失效了。

举一个反例就够了：取 $a = 1, b = -5, c = 1, d = -5$。前提 $a > b$ 即 $1 > -5$ 成立，$c > d$ 即 $1 > -5$ 也成立；但 $ac = 1$，而 $bd = 25$，结论 $1 > 25$ 显然是假的。

这道题的教训非常实用：不等式两端不能分别相乘，除非你已经确认了所有量的符号（通常要求全为正）。这是这门课乃至之后所有课程里最常踩的坑之一。

第四题：奇数个连续正整数之和是奇数

订正是错的，讲义直接给了反例：$1 + 2 + 3 = 6$，是偶数。

（讲义原文是 1+2+3 is odd??，那个问号就是在提示你自己算一下。）

那么真正成立的规律是什么？如果连续整数的个数 $n$ 是奇数，那么这 $n$ 个数的和等于 $n$ 乘以正中间那个数。原因是对称配对：中间数左边的数和右边的数，两两加起来都等于中间数的两倍，再加上中间数自己，就凑成了 $n$ 个中间数。用 $m$ 表示中间那个数，就是

$$S = n \cdot m$$

因为 $n$ 是奇数，乘积的奇偶性完全由 $m$ 决定。所以：中间数是偶数，和就是偶数（比如 $1+2+3 = 3 \times 2 = 6$）；中间数是奇数，和才是奇数（比如 $2+3+4 = 3 \times 3 = 9$）。换句话说，原命题把"个数是奇数"错当成了决定因素，而真正决定奇偶性的是中间那个数。

这道题同样体现了一个重要习惯：拿到一个全称命题，先拿最小的情形试一下。$n = 3$ 就足够推翻整个命题了。

三条忠告

讲义在这一页底部给出了三条，措辞相当重。

第一条：The most important thing in this course is NOT theory BUT a CLEAR MIND!!! 这门课最重要的不是理论，而是清醒的头脑。

第二条：Think twice for every step you have done! 你写下的每一步，都要再想一遍。

第三条：Sometimes, completing the solution may be far away from being correct. 有时候，"把解答写完了"离"做对了"还差得很远。

这三条合起来其实是一句话：慢下来。检查你的符号（$\in$ 还是 $\subseteq$），检查你的箭头方向（$\Rightarrow$ 还是 $\iff$），检查不等号有没有在乘以负数时翻转，检查你的命题有没有被一个小小的反例推翻。上面那四道题没有一道需要任何高级知识，它们考的全是细心。

自测

下面几道题用来检验你是不是真的掌握了这一讲。建议先自己想，再对答案。

一、各举两个离散数学和连续数学的代表对象或工具，并说明它们为什么不互斥。

二、3 加仑壶和 5 加仑壶为什么能量出 4 加仑？换成 4 加仑壶和 6 加仑壶，能量出 3 加仑吗？

三、把"排考试时间表"这个现实问题翻译成一个图论问题。

四、Bubble Sort 和 Merge Sort 的递推式分别是什么？哪个更快？

五、判断 $\emptyset \subseteq \{\emptyset\}$ 和 $\emptyset \in \{\emptyset\}$ 是否成立。

六、找一个反例推翻 $a > b \Rightarrow a^2 > b^2$。

答案：一、离散是整数、图、归纳法、逻辑，连续是实数、几何空间、微积分；不互斥是因为微积分可以通过生成函数来解决离散计数问题。二、因为 $\gcd(3,5)=1$ 整除 4；换壶后 $\gcd(4,6)=2$，只能量出 2 的倍数，量不出 3。三、每门课一个顶点，有学生同时选的两门课之间连边，给图着色，同色即同一时段，最少颜色数就是最少时段数。四、Bubble 是 $T(n) = T(n-1) + \Theta(n)$，得 $\Theta(n^2)$；Merge 是 $T(n) = 2T(n/2) + \Theta(n)$，得 $\Theta(n \log n)$，Merge Sort 更快。五、两者都成立：$\{\emptyset\}$ 是一个含有一个元素（空集）的集合，所以 $\emptyset \in \{\emptyset\}$ 为真；空集是任何集合的子集，所以 $\emptyset \subseteq \{\emptyset\}$ 也为真。六、取 $a = 1, b = -2$，$a > b$ 成立，但 $a^2 = 1 < 4 = b^2$。

待办

去找并读一遍 CSC3001 的 course outline，确认作业、考试的形式与比重和各项 deadline——讲义里没有这些信息。预习下一讲的主题一：命题逻辑里各联结词的真值表，特别留意蕴含（Implication）$p \Rightarrow q$ 在 $p$ 为假时被定义为真这一条，它是最反直觉、也最容易出错的地方。另外建议从这一讲的四道题开始建一个"反例本"，以后每遇到一个被推翻的命题就记一条反例。

---

说明：本笔记覆盖讲义 12 页的全部要点。其中水壶问题的 Bézout 解释、韩信点兵的同余方程与验证、排序复杂度的递推与求解、以及最后四道判断题的完整推导，属于为了便于理解而补充的标准数学内容，讲义上只有结论或一句提示。讲义未提供授课年份、评分方式等信息，请以课程大纲为准。