窮舉法
窮舉法，亦稱作分類證明、分類分析證明、完全歸納法或暴力法，是一種數學證明方法, 它將所求證的命題分為有限種情形或是等價情形的集合，接著依每種類型分別檢驗該命題是否成立[1]，此乃一種直接證明法。
窮舉法證明包括兩階段：
- 證明分類是完全的, 也就是說每一個待證的個例皆符合（至少）一類情形的條件；
- 分別對每一類情形給出證明。
計算機（電腦）的普及大大提升了窮舉法的易用性，計算機專家系統可用窮舉法解答許多問題。理論上而言，窮舉法適用於任何有限情形，然而因數學的大部分集合是無限的，此法鮮少能夠用以導出一般的數學結論[2]。
在柯里-霍華德同構（Curry–Howard correspondence）中，窮舉法與ML-型模式匹配相關聯[來源請求]。
例
[編輯]試證明每一個完全立方整數皆為9的倍數，或比9的某倍數多1，或比9的某倍數少1。
證明：
- 每個立方數皆為某個整數n的立方。每個整數n或者為3的倍數，或者比3的某個倍數多1或少1。是故以下3種情形即窮舉所有可能。
- 情形1: 若 n = 3p, 則 n3 = 27p3, 這是9的倍數.
- 情形2: 若 n = 3p + 1, 則 n3 = 27p3 + 27p2 + 9p + 1, 這是9的一個倍數加上1. 例如, 若 n = 4 則 n3 = 64 = 9×7 + 1.
- 情形3: 若 n = 3p − 1, 則 n3 = 27p3 − 27p2 + 9p − 1, 這是9的一個倍數減去1. 例如, 若 n = 5 則 n3 = 125 = 9×14 − 1.∎
證明的美感
[編輯]數學家會儘量不用分類數目很多的窮舉法, 因為這看上去不優雅. 以下舉一個例子來解釋何以這樣的證明顯得不優雅, 這個例子是證明所有現代夏季奧運會的舉辦年份都能被4整除(忽略掉因兩次世界大戰而未能舉辦的1916年夏季奧林匹克運動會,1940年夏季奧林匹克運動會與1944年夏季奧林匹克運動會與受嚴重特殊傳染性肺炎疫情影響，延期至2021年舉辦的2020年夏季奧林匹克運動會)。
證明: 現代首屆夏季奧運會於1896年舉辦, 然後每4年舉辦一次. 因為 1896 = 474 × 4 能被4整除, 下一屆奧運會的年份為 474 × 4 + 4 = (474 + 1) × 4, 同樣能被4整除, 以下類推(這個證明用的是數學歸納法). 命題得證.
這個命題也可用窮舉法來證, 即列出所有曾舉辦過夏季奧運會的年份, 核實其皆能被4整除. 到2016年為止, 夏季奧運會共舉辦過28次, 所以這是一個分了28種情形的窮舉證明. 用到數學歸納法的證明不僅更優雅, 且連帶對未來無限多次夏季奧運會都證明了命題; 而用窮舉法則需在每次開過夏季奧運會之後再做一次核驗.
情形總數
[編輯]窮舉證明中所分情形總數沒有上限. 有時只需劃分兩三種情形, 有些時候卻可以有多達數千乃至數百萬種情形. 例如, 若要嚴格解答一個西洋棋殘局, 便可能須考察該殘局的博弈樹中所包含的數量甚巨的允許局面.
四色定理的第一個證明是一個分了1936類情形的窮舉證明. 這個證明曾引發爭議, 因為其中大多數情形是用電腦程式而不是手寫證明來核驗. 目前已知最短的四色定理證法仍需劃分超過600類情形.
一般而言, 分類的數目越多, 整個證明包含錯誤的概率就越大. 一個分類數目浩大的窮舉證明會給人留下這樣的印象, 那就是所證定理能夠成立僅僅是一種巧合, 而不是因為某些底層的原理或聯繫. 其它類型的證明——例如使用數學歸納法的證明——會被認為更加優美. 但是, 有一些重要的定理, 迄今並未發現不用窮舉法的證明, 諸如
相關條目
[編輯]參考資料
[編輯]- ^ Reid, D. A; Knipping, C, Proof in Mathematics Education: Research, Learning, and Teaching, Sense Publishers: 133, 2010, ISBN 978-9460912443.
- ^ S., Epp, Susanna. Discrete mathematics with applications. Brooks/Cole. 2011-01-01 [2019-04-12]. ISBN 0495391328. OCLC 970542319. （原始內容存檔於2019-12-14）.