嚴格的數學證明

數學基礎 數學課程 數學軟體 常用符號 Tex 數學式 數學用語 嚴格的證明 數學理論 集合論 數論 幾何學 三角函數 尤拉數 虛數 代數學 遊戲理論 幾何級數 動態系統論 作業研究 微積分 離散數學 線性代數 機率統計 數學應用 人工智慧 邏輯與程式 方程式求解 線性代數 最佳化 爬山演算法 遺傳演算法 神經網路 機器學習 訊號處理 影像處理 語音處理 自然語言 機器翻譯 數學文明 科學與數學 工業與數學 教學影片 訊息 相關網站 參考文獻 最新修改 簡體版 English

文章 前言 當我還是個學生時，我總是困惑著如何應付老師的考試，其中一個重要的數學困擾是，老師要我們「證明」某個運算式。 最大的問題不在於我不會「證明」，因為在很多科目的證明題當中，我也都「答對了」，但是這種答對總是讓我感到極度的沒有把握，因為有時老師說「這樣的證明是對的」，但有時卻說「這樣的證明是錯的」。 更神奇的是，老師的證明永遠都是對的，他們可以突然加入一個「推論」，而這個推論的根據好像之前沒有出現過，然後他們說：「由此可證」、「同理可證」….。 直到有一天，我終於懂了。 因為課堂上老師的證明往往不是「嚴格的證明」，因為嚴格的證明通常「非常的困難」，每個證明都可以是一篇論文，甚至在很多論文當中的證明也都不是嚴格的。 所以在課堂上，老師總是可以天外飛來一筆的，跳過了某些「無聊的步驟」，奇蹟式的證明了某些定理，而這正是我所以感到困擾的原因。 一般的證明 一般而言，日常生活中的證明，通常是不嚴格的。 舉例來說，我可以「證明」某人殺了死者，因為殺死死者的兇刀上有「某人」的指紋。 但是這樣的證明並不嚴格，因為有很少的可能性是「某人摸過兇刀、但是並沒有殺人」。 所以我們總是可以看到那個「外表看似小孩，智慧卻過於常人」的「名偵探柯南」，總是天外飛來一筆的「證明」了某人是兇手，這種證明與數學證明可是完全不同的。 嚴格的證明 數學的證明通常不能是「機率式」的，例如：「我證明他 99% 殺了人」，這樣的證明稱不上是嚴格的證明。 嚴格的證明也並非結果一定要是 100% 的正確 (當然也不是說結果不正確)，真正的證明是一種過程，而不是結果。 怎麼說呢？ 數學其實很像程式領域的演算法，或者就像是電腦的運作過程，當我們設計出一顆 CPU 之後，你必須用該 CPU 的指令撰寫出某些函數，以便完成某個程式。 那麼，數學的 CPU 是甚麼呢？ 答案是「公理系統」！ 只有透過公理系統，經由某種演算方式，計算出待證明定理在任何情況下都是真的，這樣才算是證明了該定理。 這些公理系統其實就是數學的 CPU 指令集。 布林代數大概是數學當中最簡單的系統了，因為布林代數的値只有兩種—「真與假」 (或者用 0 與 1 代表)。 為了說明嚴格的數學證明是如何進行的，我們將從布林代數的公理系統 (CPU?) 開始，說明如何證明布林代數的某些定理，就好像是如何用指令集撰寫程式一樣。 布林邏輯 對於單一變數 x 的布林系統而言，x 只有兩個可能的值 (0 或 1)。 對於兩個變數 x, y 的布林系統而言，(x, y) 的組合則可能有 (0,0), (0,1), (1,0), (1,1) 四種。 對於三個變數 x, y, z 的布林系統而言，(x, y, z) 的組合則可能有 (0,0, 0), (0,0,1), (0,1,0), (0,1,1), (1,0, 0), (1,0,1), (1,1,0), (1,1,1) 八種。 基本的布林邏輯閘有三種，AND (且), OR (或), NOT (反)，在布林代數當中，通常我們用減號 (-) 代表 NOT，用 & 代表AND，用 | 代表 OR。 NOT 閘的真值表如下所示。 x -x 0 1 1 0 AND 閘的真值表如下所示。 x y x&y 0 0 0 0 1 0 1 0 0 1 1 1 OR 閘的真值表如下所示。 x y x|y 0 0 0 0 1 1 1 0 1 1 1 1 假如我們想知到某個邏輯式，例如 (-x | y) 的真值表，只要透過列舉的程序就可以檢查完畢。 x y -x -x|y 0 0 1 1 0 1 1 1 1 0 0 0 1 1 0 1 接著，我們就可以定義一些公理系統，這些「公理系統」就像是數學推理的指令集，讓我們可以推論出哪些邏輯式在這個公理系統下是真的 (定理)，哪些邏輯式這個公理系統下不一定是真的。 公理系統 1 舉例而言，假如我們制定了一個公理系統如下所示。 x -x |y 那麼，我們就可以列出這個布林系統的真值表。 x y -x|y 0 0 1 0 1 1 1 0 0 1 1 1 在上述真值表中，凡是無法滿足公理系統的列，就代表該項目違反公理系統，因此在此公理系統下不是真的，可以被刪除。 於是滿足該公理系統的項目只剩下了一個。 x y -x|y 1 1 1 在這個滿足公理系統的真值表當中，我們可以看到 y 只能是 1，也就是 y 其實是個定理。 公理系統 2 假如我們定義了以下的公理系統： -p | q p | r 那麼我們可以列出真值表如下： p q r -p|q p|r 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 當我們將不符合公理系統的項目拿掉之後，以上的真值表就只剩以下這些項目。 p q r -p|q p|r 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 此時，如果我們檢查這些項目中 q|r 的真值表，會發現 q|r 為真者其結果全部為 1 ，因此 q|r 在這個公理系統下是真理。 p q r -p|q p|r q|r p|q 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 但是如果我們檢查這些項目中 p|q 的真值表，會發現有一項為 0 ，因此 p|q 在這個公理系統下並非真理。 所以 q|r 在此公理系統下是一個定理，但 p|q 則不是定理。 推論法則 現在，我們已經具備了足夠的基本知識，可以用來說明何謂嚴格的數學證明了。 假如我們將公理系統 2 中推論出 q|r 的程序，變成一條明文的規則，如下所示： (-P | Q) & (P | R) => (Q|R) 那麼，我們就可以用這樣的規則進行推論，這個推理方式乃是 Robinson 所提出的，稱為 Resolution 法則。 於是我們可以根據這條規則，推論出某個邏輯公理系統下的定理，舉例而言，假如有個公理系統如下所示。 x | -y -x | z -(-y | z) | w 則我們可以利用 Resolution 法則，進行推論如下： (x | -y) & (-x | z) => (-y|z) ; 令 P=x, Q=-y, R=z (-y|z) & (-(-y | z) | w) => w ; 令 P=(-y|z), Q=w, R=0 如此我們就可以不需要依靠真值表，直接從公理系統開始，透過嚴格的計算程序，推論出該公理系統中的定理了。 這種證明方式，就是一種為嚴格的數學證明。 這種證明所遵循的，乃是一種 [公理/推論/定理1/推論/定理2/…] 的方式，這種方式讓證明變成了一種計算過程，是可以寫成電腦程式的，這種證明方式乃是一種嚴格可計算的證明方式。 相關討論 為甚麼國中的數學證明是從「歐式幾何」開始教，而不從「布林代數」開始教呢？ https://www.facebook.com/ccckmit/posts/10151056707046893 參考文獻 數學中的公理化方法 (上) 吳開朗 http://w3.math.sinica.edu.tw/math_media/d171/17111.pdf 數學中的公理化方法 (下) 吳開朗 http://w3.math.sinica.edu.tw/math_media/d172/17203.pdf 後記 大部分的數學系統，都希望能達到這樣嚴格的程度，但可惜的是，並非所有數學系統都能完全達到這樣嚴格的程度。舉例而言：歐氏幾何可以說是公理化的早期經典之作，但其中仰賴圖形直覺的證明過程仍然有很多，並非完全達到公理化。而微積分等數學的嚴格公理化也一直是數學家還在研究的問題。 但對公理化數學體系最精彩的一段歷史是，希爾伯特對公理化的問題與歌德爾不完備定理對數學可完全公理化的反證，以下是這段歷史的簡要說明。 20 世紀的大數學家 Hilbert 曾經於 1900 年提出的 23 個數學問題中提到一個問題，就是「是否能為數學系統建立證明法則，讓數學證明可以完全被計算出來」，後來歌德爾 (Godel) 在 1926 年證明了一階邏輯的完備定理，讓大家看到了一線曙光，但歌德爾在 1929 年又提出了一個數論系統的不完備定理，證明了有些定理無法透過計算程序證明。 歌德爾的研究，後來在電腦領域，被圖靈 (Turing) 重新詮釋了一遍，圖靈證明了「停止問題」是電腦無法 100% 正確判定的問題，這也開啟了後來計算理論的研究之河。圖靈也因此而成為計算理論領域的第一人，所以 ACM 這個組織才會將電腦界的最重要獎項稱為「圖靈獎」(Turing Award)。 Facebook 留言 Facebook Wikidot Post preview: Close preview or Sign in as Wikidot user (will not be published) - + Help: wiki text quick reference 授權 本網頁的作者、授權與引用方式 作者 陳鍾誠，於金門大學資訊工程系，電子郵件：wt.ude.uqn|ccc#wt.ude.uqn|ccc，網站：http://ccckmit.wikidot.com。 授權 本文採用創作共用 (Creative Common) 3.0 版的 姓名標示─非商業性─相同方式分享 授權條款，歡迎轉載或修改使用，但若做為商業使用時必須取得授權，引用本文時請參考下列格式。 中文版 (APA格式) 陳鍾誠 (27 Jul 2012 03:48)，(網頁標題) 嚴格的數學證明，(網站標題) 陳鍾誠的網站，取自 http://ccckmit.wikidot.com/ma:proof ，網頁修改第 29 版。 英文版 (APA格式) Chung-Chen Chen (27 Jul 2012 03:48), Retrieved from http://ccckmit.wikidot.com/ma:proof , Page Revision 29.