MIT 6.042J 计算机科学数学，秋季2010第1讲

引言

2010年秋季学期，麻省理工学院（MIT）经典课程《计算机科学数学》（6.042J）的第一讲，由Tom Leighton教授主讲。这堂课的主题是"证明"——数学与逻辑学的基石。 Leighton教授没有一上来就堆砌公式，而是用一系列生动的问题引导课堂讨论：什么是证明？人类如何确认一件事是真的？从法庭陪审团到宗教信仰，从科学实验到日常观察，他层层剥茧，最终指向数学证明的本质：一条从公理出发、经由逻辑推理、抵达结论的链条。这堂课为后续的算法分析、图论、概率论等内容奠定了严谨的逻辑起点，也回答了计算机专业学生最常问的一个问题：学这些有什么用？

证明的本质

Leighton教授首先让学生们思考"证明"的广义含义。在法庭上，真相由证据和陪审团来裁决；在科学中，真相通过观察和实验来确立；在宗教和商业中，真相有时来自权威——上帝的话、老板的话、客户的永远正确。但数学有一种独特的魅力：最年轻的学生也可以站起来质疑最有经验的教授，并用严密的逻辑证明他是错的。 Leighton坦言，每当有学生这样做时，他既感到尴尬，又由衷高兴——这正是数学对话最迷人的地方。

在此基础上，教授给出了数学证明的定义：从一组公理出发，通过逻辑推导链，验证一个命题的真假。这里的三个核心要素是：命题（Proposition）、逻辑推导（Logical Deductions）和公理（Axioms）。

命题的力量与陷阱

为了让学生理解"归纳不等于证明"，教授举了一个著名的反例：对于所有自然数n，n² + n + 41都是质数。

他带着学生在黑板上逐项计算：n=0时得41（质数），n=1时得43（质数），n=2时得47（质数），一直算到n=39，结果全部成立。在物理学或统计学中，40个样本已全部吻合，通常会被人视为"已经证明"。但教授随即抛出答案：当n=40时，40² + 40 + 41 = 1681 = 41²，不再是质数。命题在第一个反例处崩塌。

这个例子震撼了全场。它揭示了一个深刻的道理：无论观察了多少次"正确"，都无法替代严格的证明。数学史上，欧拉曾猜想a⁴ + b⁴ + c⁴ = d⁴没有正整数解，这个命题困扰了数学家两百多年，直到Noam Elkies用一组巨大的数字推翻了它：a=95800, b=217519, c=414560, d=422481。而另一个看似更难的方程313x³ + y³ = z³，其最短反例竟然超过了1000位数字——人类永远无法通过穷举发现它。

结语

这堂课的核心信息清晰而有力：数学证明是人类确认真理最可靠的方式，因为它不依赖于样本数量、不依赖于权威背书，只依赖于逻辑的严密性。对于计算机专业的学生而言，这种"严格推理"的能力正是算法设计与分析的底层基石。 Leighton教授的讲解既幽默又深刻，他用生动的例子让学生们明白：数学不只是公式和定理，更是一种思维方式——一种敢于质疑、善于论证、追求真理的思维方式。建议观看此课的读者不必急于消化所有证明细节，先体会"为什么需要证明"和"证明的思路如何产生"，再配合课程讲义练习，会有更好的收获。

---

📺 观看原视频：在 shipin.5l5l.net 观看