窮舉法，亦稱作分類證明、分類分析證明、完全歸納法或暴力法，是一種數學證明方法, 它將所求證的命題分為有限種情形或是等價情形的集合，接著依每種類型分別檢驗該命題是否成立[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類情形.
一般而言, 分類的數目越多, 整個證明包含錯誤的概率就越大. 一個分類數目浩大的窮舉證明會給人留下這樣的印象, 那就是所證定理能夠成立僅僅是一種巧合, 而不是因為某些底層的原理或聯繫. 其它類型的證明——例如使用數學歸納法的證明——會被認為更加優美. 但是, 有一些重要的定理, 迄今並未發現不用窮舉法的證明, 諸如
相關條目
參考資料
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
