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 中對應的章節。