How to Prove It: A Structured Approach（怎样证明：结构化方法）

引用

Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press.

章节概要

第三版包括引言和八章，正文约 450 页，其后是部分习题解答（约五十页）、延伸阅读建议和一页证明技巧总结。本书初版于 1994 年，第二版于 2006 年出版。序言阐明的核心思想是“结构化证明”：正如结构化程序由少数几种基本结构嵌套而成，证明也由少数几种基本结构嵌套而成，而待证命题的逻辑形式会告诉读者该用哪种结构。

引言

在讲任何理论之前，先让读者体会证明是什么样子。引言以素数和形如 2ⁿ − 1 的数为素材，展示表格中的规律如何变成猜想，一个反例如何推翻一个猜想，而一个证明又如何确立另一个猜想。引言还给出了欧几里得关于素数有无穷多个的证明，并预告在第3章之后会回过头来分析这些证明是如何构造出来的。

第1章：命题逻辑

讨论演绎推理与逻辑联结词、真值表，以及条件句和双条件句。变量、集合和集合运算也在本章引入，因为集合论贯穿全书，同时又能用来说明逻辑。

第2章：量词逻辑

包括量词、涉及量词的等价式（例如否定如何穿过“对所有”和“存在”），以及一节关于更多集合运算的内容。

第3章：证明

全书的核心。本章逐一考察命题可能具有的形式以及与每种形式相适应的证明结构：先讲一般的证明策略，再讲涉及否定和条件句、量词、合取和双条件句、析取的证明，随后是存在性与唯一性证明，以及一节更多的例子。序言提醒，前面的例子是为了展示结构而不是因内容而选的，因此相当平凡；随着可用技巧增多，证明在数学上也越来越有意思。

第4章：关系

讨论有序对与笛卡儿积、关系及其性质、序关系和等价关系。序言说明，第4、5章一方面为练习第3章的技巧提供素材，另一方面介绍数学各分支都会用到的基本概念。

第5章：函数

讨论函数、单射与满射、逆函数，以及集合在函数作用下的闭包（本版新增的一节），最后是一个以像与原像为题的“研究项目”短节。

第6章：数学归纳法

包括归纳法证明、更多例子、递归、强归纳法，以及再谈闭包。本章建立在第3章的技巧之上，序言期望读者此时已经掌握这些技巧。

第7章：数论

第三版新增的一章，内容包括最大公约数、素因数分解、模运算、欧拉定理和公钥密码。与第8章一起，它既为证明提供更多练习，也让读者初步领略更高深的数学是什么样子。

第8章：无穷集合

讨论等势集合、可数集与不可数集，以及康托尔–施罗德–伯恩斯坦定理。

核心概念

第1–2章：逻辑与集合

• 逻辑形式：命题在联结词和量词层面的结构，它决定了命题应当如何证明。
• 真值表与逻辑等价：检验两个命题是否总是具有相同真值的方法。
• 量词：“对所有”和“存在”，以及对它们取否定和组合的规则。
• 集合运算：并、交、差等运算，通过逻辑联结词和量词来定义。

第3章：证明

• 证明结构：诸如假设 P 直到推出 Q（用于“若 P 则 Q”）、或令 x 为任意（用于“对所有 x”）这样的模式，通过嵌套来证明复杂命题。
• 否定与析取：无论是证明它们还是把它们当作前提使用，都需要专门策略的命题，各有专节讨论。
• 存在性与唯一性：证明恰好有一个对象具有某种性质。

第4–6章：关系、函数与归纳

• 等价关系与偏序：对对象进行分类或排序的关系。
• 单射与满射：一对一的函数与映上的函数，以及它们所允许的逆函数。
• 闭包：包含给定元素并在某个函数下封闭的最小集合。
• 归纳与递归：证明关于所有自然数的命题，以及逐步定义数列，包括强归纳法。

第7–8章：数论与无穷集合

• 模运算与欧拉定理：余数的算术，公钥密码的基础。
• 可数集与不可数集：通过一一对应比较无穷集合的大小。
• 康托尔–施罗德–伯恩斯坦定理：两个方向相反的单射保证两个集合大小相同。

评析

优点

• 教方法，而不只是给例子。 本书的核心主张是：证明的结构取决于待证命题的逻辑形式。它先讲逻辑，再在第3章系统地考察每种形式及其所要求的结构，使初学者有办法动手开始证明，而不必坐等灵感。一页篇幅的证明技巧总结把这套方法集中在一处。
• 以普通证明为目标。 序言强调，用来显示结构的缩进提纲只是教学手段，目标是像数学家那样用段落写出证明。
• 习题丰富，附有部分解答。 每一节都以习题结束；第三版新增了 150 多道习题，带星号的习题在约五十页的附录中给出解答或提示，因此本书也适合自学。
• 有免费软件配套。 标有 PD 的习题可以用作者免费提供的 Proof Designer 完成；作者后来还发布了免费在线教材 How To Prove It with Lean，其章节与本书对应，用 Lean 证明助手讲授同样的技巧。

局限

• 有意放慢开头。 序言本身承认，第3章前面的证明是为展示结构而选的，相当平凡。已经能写简单证明的读者可能会觉得前半部分过于细致。
• 就其范围而言篇幅较长。 400 多页用于逻辑、集合、关系、函数、归纳法，以及关于数论和无穷集合的两个短章。其他一些过渡性教材中的实数、极限或组合计数等话题，本书没有涉及。
• 逻辑是工具而非研究对象。 第1–2章的逻辑是非形式化的，服务于证明写作；形式系统、可靠性和完备性留给数理逻辑的教材。

在课程中的定位

本书是本课程最自然的第一本书，应在数理逻辑教材之前阅读。Richard Hammack 的 Book of Proof 可免费获取，内容范围相近（集合、逻辑、标准证明方法、关系、函数和基数），既可以作为替代教材，也可以作为额外习题的来源；Velleman 的独特之处在于第3章把逻辑形式与证明结构系统地联系起来。Peter Eccles 的 An Introduction to Mathematical Reasoning、R. B. J. T. Allenby 的 Numbers and Proofs 和 Martin Liebeck 的 A Concise Introduction to Pure Mathematics 也是证明入门书，但更侧重数系和其他纯数学内容，适合在学习方法的同时希望接触更多数学内容的读者。

读完 Velleman 之后，课程转向以逻辑本身为研究对象。Leary 和 Kristiansen 的 A Friendly Introduction to Mathematical Logic 讲述一阶逻辑、完备性定理和哥德尔不完备性定理；Herbert Enderton 的 A Mathematical Introduction to Logic 面向已经熟悉数学推理的学生，对命题逻辑和一阶逻辑的处理更为严格。本书第1–3章为这两本书都打下了良好基础。

如何使用本书

本书面向第一次认真接触证明的数学或计算机专业学生，通常是一、二年级；具备中学代数即可。由于带星号的习题有解答，它也适合自学者。

阅读计划：

• 核心： 引言、第1–3章和第6章。不要赶第3章：它是全书其余部分所运用的方法，最后一节还会回到引言中的证明，说明它们是如何构造的。
• 练习与术语： 第4、5章，提供后续课程默认读者掌握的关系和函数知识。
• 任选其一或都读： 按兴趣选择第7章（以公钥密码结束的数论）或第8章（无穷集合）。第8章与分析和集合论课程中的基数话题自然衔接。

每一节都要做习题，可以先做带星号的题目，以便在附录中核对答案；动笔写证明之前，按第3章的方法写下已知条件和待证结论的逻辑形式，并把证明技巧总结放在手边。想要即时反馈，可以用 Proof Designer 做标有 PD 的习题，或在开始学习第3章后，配合阅读免费的 How To Prove It with Lean 中对应的章节。