數學證明

在數學上，數學證明（mathematical proof）是在一個特定的公理系統中，根据一定的规则或标准，由公理和定理推導出某些命題的過程。比起证据，数学证明一般依靠演绎推理，而不是依靠自然归纳和经验性的理据。這樣推導出來的命題也叫做該系統中的定理。

數學證明建立在逻辑之上，但通常會包含若干程度的自然語言，因此可能會產生一些含糊的部分。

實際上，用文字形式寫成的數學證明，在大多數情況都可以視為非形式邏輯的應用。在證明論的範疇內，則考慮那些用純形式化的语言写出的證明。這個区别导致了对過往到現在的數學实践、數學上的擬經驗論（英语：Quasi-empiricism in mathematics）和民俗数学（英语：Folk mathematics）的大部分检验。

數學哲學就關注語言和邏輯在數學證明中的角色，和作為語言的數學。

数学上的证明包括两个不同的概念。

首先是非形式化的证明：一种以自然语言寫成的严密論證，用来说服听众或读者去接受某个定理或论断的真確性。由于这种证明使用了自然语言，因此對於非形式化证明在严謹性上的標準，将取决于听众或读者对課題的理解程度。非形式化证明出现在大多数的应用场合中，例如科普讲座、口头辩论、初等教育或高等教育的某些部分。有时候非形式化的证明被称作“正式的”，但這只是強調其中論證的嚴謹性。

而當逻辑学家使用“正式证明”一詞时，指的是另一种完全不同的证明——形式化证明。

在数理逻辑中，形式化证明并不是以自然语言书写，而是以形式化的语言书写：这种语言包含了由一个給定的字母表中的字符所构成的字符串。而证明则是一种由該些字符串組成的有限长度的序列。这种定义使得人們可以談論嚴格意義上的「证明」，而不涉及任何逻辑上的模糊之处。

研究证明的形式化和公理化的理论称为证明论。

尽管理论上来说，每个非形式化的证明都可以转化为形式化证明，但实际中很少會這樣做。对形式化证明的研究主要应用在探討關於可证明性的一般性质，或说明某些命題的不可证明性等等。

直接证明（英语：Direct proof）也称为逻辑演绎，是指从公认的事实或者公理出发，运用逻辑推演而导出需要证明的命题的真伪的方法。直接证明法一般使用谓词逻辑，运用存在量词或全称量词。主要的证明方式有肯定前件论式、否定后件论式、假言三段论式以及选言三段论式等等。比如说要证明命题：“任何奇数乘以另一个奇数仍然是奇数”，可以直接证明如下：

任何奇数都可以写成${\displaystyle 2a+1}$的形式，其中${\displaystyle a}$是整数。任取两个奇数，它们分别可以写作${\displaystyle 2a+1}$和${\displaystyle 2b+1}$，其中${\displaystyle a}$和${\displaystyle b}$是整数。它们的乘积为${\displaystyle (2a+1)\times (2b+1)=4ab+2a+2b+1=2(2ab+a+b)+1}$。所有能写成整数的两倍加1的数都是奇数。${\displaystyle 2ab+a+b}$是整数，所以${\displaystyle (2a+1)\times (2b+1)}$是奇数。证明完毕。

构造法一般用于证明存在性定理，运用构造法的证明称为构造性证明。具体做法是構造一個帶有命题裡所要求的特定性質的實例，以顯示具有該性質的物體或概念的存在性。也可以构造一个反例，来证明命题是错误的^[2]。例如证明命题“2的质数次幂减一后不总是质数”，便可用构造法：

只需证明存在某个质数${\displaystyle p}$，使得2的${\displaystyle p}$次幂减一后不是质数。为此，考察质数11。2的${\displaystyle 11}$次幂减一等于${\displaystyle 2047}$。${\displaystyle 2047=23\times 89}$不是质数。因此命题得证。

有些构造法证明中并不直接构造满足命题要求的例子，而是构造某些辅助性的工具或对象，使得问题更容易解决。一个典型的例子是常微分方程稳定性理论中的李亚普诺夫函数的构造^[3]。又如许多几何证明题中常常用到的添加辅助线或辅助图形的办法。

与构造法证明相对的是非构造性证明，即不给出具体的构造而证明命题所要求对象的存在性的证明方法。比如下面例子：

命题：存在两个无理数${\displaystyle x}$和${\displaystyle y}$，使得${\displaystyle x^{y}}$是有理数。

证明：考虑${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$，若它是有理数，则命题得证。若${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$不是有理数，则一定是无理数。考虑它的${\displaystyle {\sqrt {2}}}$次幂：

${\displaystyle ({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}={\sqrt {2}}^{{\sqrt {2}}\cdot {\sqrt {2}}}={\sqrt {2}}^{2}=2}$为有理数，命题仍然正确。

于是无论如何，都存在满足命题要求的无理数。

在这个证明里并没有给出使得${\displaystyle x^{y}}$是有理数的两个具体的无理数^[2]。

穷举法（英语：Proof by exhaustion）是一种列举出命题所包含的所有情况从而证明命题的方法^[4]。例如证明“所有两位数中只有25和76的平方是以自己作为尾数”，只需计算所有两位数：10至99的平方，一一验证即可。显然，使用穷举法的条件是命题所包含的可能情况为有限种，否则无法一一罗列。

在谓词逻辑裡，若同时否定一个命题的主词和谓词，则其结果称为原命题的换质。若交换主词和谓词的位置，则其结果被称作换位。先换质再换位则被称为换质位，同理先换位再换质则被称为换位质。例如“所有的S是P”的换质位是“所有的不是P的不是S”。换质位法是指利用换质及换位，将一个命题改为一个与其逻辑等价的命题，因此只要证明了后者就证明了原来的命题^[5]。例如，要证明鸽笼原理：“如果n个鸽笼裡装有多于n隻鸽子，那么至少有一个笼子裡有两隻或者两隻以上鸽子”，可以转证与其等价的逆否命题：“如果n个鸽笼的每一个中至多装有一隻鸽子，那么n个鸽笼裡至多装有n隻鸽子”。而后者是明顯的。

个案分析或分类讨论，是指將結論分成有限的個案，然後逐個證明的方法。

算两次是一种對同一個量進行兩種雖不同但都正確的分析，得到兩個雖不同但相等的表達式的方法，常用于证明恒等式^[6]。

反证法是一种古老的证明方法，其思想为：欲證明某命題是假命題，则反过来假設該命題為真。在这种情况下，若能通过正确有效的推理導致逻辑上的矛盾（如导出该命题自身为假，于是陷入命题既真且假的矛盾），則能證明原来的命題為假。^[7]無矛盾律和排中律是反證法的邏輯基礎。反证法的好处是在反过来假设该命题为真的同时，等于多了一个已知条件，这样对题目的证明常有帮助^[8]。

例子：证明命题“${\displaystyle {\sqrt {2}}}$不是有理数”。

命题：${\displaystyle {\sqrt {2}}}$不是有理数。

证明：假设${\displaystyle {\sqrt {2}}}$是有理数，那么存在正整数${\displaystyle p}$使得${\displaystyle p{\sqrt {2}}}$为整数。不妨设${\displaystyle a}$为其中最小的（根据良序原理，必然存在最小的${\displaystyle a}$）。考虑${\displaystyle b=a{\sqrt {2}}-a}$。${\displaystyle b}$是一个比${\displaystyle a}$小的正整数，但${\displaystyle \ b{\sqrt {2}}=2a-a{\sqrt {2}}}$也是整数。这与${\displaystyle a}$的最小性矛盾。所以根号2不是有理数^[9]。

數學歸納法是一種证明可數無窮個命題的技巧。欲證明以自然數${\displaystyle n}$編號的一串命題，先證明命題1成立，並證明當命題${\displaystyle n}$成立時命題${\displaystyle n+1}$也成立，则对所有的命題都成立^[5]。在皮亚诺公理系统中，自然数集合的公理化定义就包括了数学归纳法。数学归纳法有不少变体，比如从0以外的自然数开始归纳，证明当命題对小于等于n的自然数成立时命題${\displaystyle n+1}$也成立，反向归纳法，递降归纳法等等。广义上的数学归纳法也可以用于证明一般良基结构，例如集合论中的树。另外，超限歸納法提供了一種處理不可數無窮個命題的技巧，是數學歸納法的推廣^[10]。

例子：證明对所有自然数${\displaystyle n}$，命题${\displaystyle P(n):\;\;1^{2}+2^{2}+3^{2}+...+n^{2}={\frac {n(n+1)(2n+1)}{6}}}$

當${\displaystyle n=1}$，左邊=1，右邊=${\displaystyle P(1):\;\;{\frac {1(1+1)(2+1)}{6}}=1}$

假設对某个自然数${\displaystyle k}$，命题${\displaystyle P(k)}$成立：${\displaystyle 1^{2}+2^{2}+3^{2}+...+k^{2}={\frac {k(k+1)(2k+1)}{6}}}$，以下證明${\displaystyle P(k+1)}$成立，即：${\displaystyle 1^{2}+2^{2}+3^{2}+...+k^{2}+(k+1)^{2}={\frac {(k+1)(k+2)(2k+3)}{6}}}$：

左邊${\displaystyle =1^{2}+2^{2}+3^{2}+...+k^{2}+(k+1)^{2}}$

${\displaystyle ={\frac {k(k+1)(2k+1)}{6}}+(k+1)^{2}}$

${\displaystyle ={\frac {(k+1)(2k^{2}+7k+6)}{6}}}$

${\displaystyle ={\frac {(k+1)(k+2)(2k+3)}{6}}}$

${\displaystyle =}$右邊

所以，对任意自然数${\displaystyle n}$，都有${\displaystyle 1^{2}+2^{2}+3^{2}+...+n^{2}={\frac {n(n+1)(2n+1)}{6}}}$

直观证明或可视化证明是指用图像或表格等直观的手段证明命题的方法。这类证明可以达到不借助语言而证明的效果。如右图是勾股定理的一个图示证明。

電腦協助證明是二十世紀出現的證明方式。直到二十世纪中，人们一直认为任何的数学证明都应当能够被一个水平足够的数学家检验，以证实其正确性。然而，今天的数学家已经能够运用计算机来证明定理，并且完成人类難以做到的计算^[11]。1976年四色定理的证明是计算机辅助证明的经典例子^[12]。证明的方法是将地图上的无限种可能情况减少为1936种状态，并由计算机对每个可能的情况进行验证。有不少数学家对于计算机证明持谨慎态度，因为很多证明太长，不能由人手直接验证。此外，算法上的错误，输入时的失误甚至计算机运行期间出现的错误都有可能导致错误的结果。

有時在證明的結尾會加上Q.E.D.三個字母，這是拉丁文Quod Erat Demonstrandum的縮寫，意思是「證明完畢」。現在的證明完畢符號，通常是■（實心黑色正方形），稱之為「墓碑」或「哈爾莫斯（Halmos symbol）」（因保羅·哈爾莫斯最先採用此做法）。墓碑有時是空心的□。另一個簡單方法是寫「proven」、「shown」或「證畢」之類的文字。

• 證明論
• 模型論
• 自動定理證明
• 無效證明
• Q.E.D.
• 墓碑符号

1. ^ Bill Casselman. One of the Oldest Extant Diagrams from Euclid. University of British Columbia. [2008-09-26]. （原始内容存档于2012-06-04）. 
2. ^ ^{2.0 2.1} 余红兵; 严镇军. 《构造法解题》. 中国科学技术大学出版社. 2009 [2014-01-11]. ISBN 7312024831. （原始内容存档于2019-05-03）. 
3. ^ 王高雄; 周之铭; 朱思铭; 王寿松. 《常微分方程》（第三版）. 高等教育出版社. [2014-01-11]. ISBN 9787040193664. （原始内容存档于2019-05-03）. 
4. ^ Reid, D. A. & Knipping, C. (2010).Proof in Mathematics Education: Research, Learning, and Teaching （页面存档备份，存于互联网档案馆） Sense Publishers, p. 133.
5. ^ ^{5.0 5.1} 金岳霖; 杨宝星. 《形式逻辑》. 辽宁人民出版社. 1979 [2014-01-11]. ISBN 7010002037. （原始内容存档于2014-01-11）. 
6. ^ 单壿. 《算两次》. 中国科学技术大学出版社. 2009 [2014-01-11]. ISBN 7312024823. （原始内容存档于2014-01-11）. 
7. ^ 類似地，有更一般的歸謬法：若然假設該命題為真，在通过正确有效的推理后會得出邏輯上的矛盾、与某个事实或公理相悖的結論、或荒謬難以接受的結果，亦可以證明原来的命題為假。反證法是歸謬法的其中一種形式。
8. ^ Vinciane CAMBRÉSY-TANT，Dominique CAMBRÉSY，Stéphane CARPENTIER，''Autour du raisonnement par l'absurde''，IUFM Nord - Pas de Calais (PDF). [2014-01-11]. （原始内容 (PDF)存档于2013-12-28）. 
9. ^ THEODOR ESTERMANN，1975 (PDF). Blms.oxfordjournals.org. 2013-12-06 [2014-01-11]. 
10. ^ 苏淳. 《漫话数学归纳法》. 中国科学技术大学出版社. 2009 [2014-01-11]. ISBN 7312024866. （原始内容存档于2019-05-03）. 
11. ^ The History and Concept of Mathematical Proof, Steven G. Krantz. 1. February 5, 2007 (PDF). [2014-01-11]. （原始内容存档 (PDF)于2007-02-21）. 
12. ^ 相信數學，或相信電腦. 中國科普博覽. 2004-04-29 [2014-01-14]. （原始内容存档于2017-03-05）. 

• 證明，曹亮吉 （页面存档备份，存于互联网档案馆）