電腦運算的基礎——布林代數，是麼搞出來的？│《電腦簡史》數位時代（三）

本文由 國立臺灣師範大學 委託，泛科學企劃執行。 

煮湯時看到調理包背面寫著「加水且加入鹽巴或味精，就大功告成了」。

這句話該怎麼解讀呢？邏輯思維好的人可能很快就能反應過來，意思是加水是必須的，鹽巴和味精至少要加一個。當然，兩者都加也行，但似乎不太健康。

你可能會說：「煮湯時誰會想那麼多？這太哲學了！」其實，19 世紀有位數學家將邏輯建立在數學而非哲學之上，他的貢獻深深影響了現代電腦的運算。他就是我們今天的主角——喬治．布爾（George Boole）。

在工作會議中，清晰的邏輯思維能幫助我們有條理地表達觀點，並迅速理解他人的意見；程式設計中，邏輯是核心，透過布林代數和邏輯運算，電腦能根據條件執行不同的任務，在智慧家電中利用邏輯閘判斷多個輸入條件來控制輸出結果。

因此，布爾提出的這一套邏輯思維與布林代數，不僅在學術領域至關重要，更是日常生活中不可或缺的工具。

更多、更完整的內容，歡迎上數感實驗室 Numeracy Lab 的 youtube 頻道觀看完整影片，並開啟訂閱獲得更多有趣的資訊！

「糾正我們推理的唯一方法，是使它們像數學家的推算一樣實在可靠，這樣我們就能一目了然地發現錯誤。當人與人之間爭論不休時，我們只要說：別再吵了，讓我們算算看誰才是對的。」

—— 萊布尼茲 1685 年致 Philipp Spener 信。

本文為系列文章，上一篇請見：易經、巴別塔、通用文字——萊布尼茲研究二進位之路│《電腦簡史》數位時代（二）

亞里斯多德開創邏輯系統好棒棒，but……

萊布尼茲提出只用 0 與 1 的二進位算術，成為現代電腦的運算方式。不過，現代電腦可不是之前的計算器，藉由齒輪轉動的圈數來做加減乘除，而是利用電子零件的開關狀態。開關狀態如何做二進位算術？這就需要藉助「邏輯運算」。

邏輯運算這個詞在現代聽起來理所當然，但你若拿去問十八世紀以前的人，他一定覺得莫名其妙，邏輯用的都是文字語句，又不是數學，怎麼運算呢？

是的，打從亞里斯多德開創有規則可循的邏輯系統，兩千年來表達邏輯的方式都是用自然語言做為陳述句，例如下面這個最具代表性的三段論。

大前提：所有人都會死。

小前提：蘇格拉底是人。

結論：蘇格拉底會死。

然而自然語言不免會有多重涵義，或是容易有歧義的問題，不僅翻譯成不同語言可能造成誤解，就算是使用同一種語言的人，也可能會對其中的邏輯關係有不同認知。例如「有關係就沒關係，沒關係就有關係」這句俗諺裡面，「關係」這個詞項顯然有不同涵義，而「有」與「沒」的用法也前後不一。

況且除了簡單的三段論，還有其它形式更複雜的邏輯陳述，用自然語言確實無法精確地表示各種邏輯形式和規律。

你以為數學式本來就長這樣？

其實數學早期也都是用自然語言，如果翻開當時的數學書籍，只見盡是長長的文字敘述，即使看得懂，恐怕也難以聯想到它就是代表一個簡單的公式而已。這是因為直到十六世紀，數學才開始用符號來表達，像加、減、乘、除、等於都是約莫那個時候才改用 ＋、－、×、÷、= 代表。而我們現在熟悉的數學式記法，包括用字母代表未知數，更是十七世紀才盛行。

數學符號化之後，表述方式更加簡短精確，計算也變得方便許多。而且由於符號不受語文隔閡，不同國家的數學家都能一目了然，因此得以加速數學與科學的傳播與交流，是促成科學革命的重要基石。

萊布尼茲本身遊歷德國、法國、英國三地，又曾為微積分創造新的符號，更能感受符號化的重要性，因此在他夢想有數學般的通用文字之前，就已經試圖把邏輯轉換為數學那樣的表示方式，也就是現代所稱的「數理邏輯」。

萊布尼茲致力於邏輯數學化，可惜無人知

萊布尼茲先於 1679 年設想各種基本概念都用某個質數代表，例如「動物」用 “2” 代表，「理性」是 “3”，那麼「人是理性的動物」這個句子就相當於 “6=2×3”，也就是說代表「人」的數字是 “6”。從 6=2×3 可以推導出 6÷3=2，代表「人失去理性等於動物」，這樣便能透過計算完成邏輯推論。

1686 年，萊布尼茲改用 A、B、C……等字母符號代表普通命題，並引入「非」、「等於」、「不等於」、「屬於」、「不屬於」等符號，然後用這些符號列出交換律、傳遞關係……等處理集合關係的運算規則。

到了 1690 年，他又將加法與減法納入邏輯演算之中，讓邏輯的符號化與數學化更加完整，可以說已經為數理邏輯打下堅固的地基。無奈這些手稿在萊布尼茲生前從未公開，直到二十世紀初世人才知道他這方面的研究，數理邏輯的發展因此延遲了一個半世紀，才由英國數學家布爾 (George Boole) 重新開創。

布爾公親變事主，重新開創數學邏輯

布爾於 1815 年出生在一個鄉下小鎮，父親是個鞋匠。因為家境清寒，他自小學畢業後就沒再受正式教育，而是靠自學習得語文與數學知識。

布爾十六歲時被當地一所學校聘為教師，成為家中經濟支柱；到了十九歲乾脆自己開辦學校，同時更投入數學的研究。布爾二十三歲開始發表數學論文，逐漸獲得倫敦學術圈的注意，其中一位數學家德摩根 (Augustus De Morgan) 與他結為好友，後來竟為他帶來開創邏輯新局的契機。

話說十九世紀的哲學家已經注意到亞里斯多德的三段論有許多問題，因此包括德摩根在內的一些學者開始思考如何將邏輯數學化（如之前所說，他們渾然不知萊布尼茲早已做了研究）。1846 年，德摩根發表了一篇關於三段論的論文，主要是針對命題中的「所有」、「有些」，或「大部分」提出量化的討論。

沒想到論文發表後，另一位英國哲學家漢彌爾頓 (Sir William Hamilton) 立即跳出來指控德摩根剽竊自己的想法。布爾身為德摩根好友，自然要關切兩人爭執的內容，沒想到他深入研究後，竟從原本的旁觀者搖身一變為一代宗師。

命題真偽改用 1 與 0 代表，邏輯關係化為數學運算

1847 年，布爾出版了《邏輯的數學分析》(The Mathematical Analysis of Logic)，這本僅僅 82頁的小冊子立即撼動了哲學界與數學界。這裡面完全用代數的形式來表達傳統邏輯，像「且」、「或」、「非」、「若……則……」等邏輯關係都化為乘法與加、減法；命題的真偽就用 1 與 0 兩種數值代表；另外布爾再訂出結合律、分配律、……等基本公理，成功地將邏輯數學化。

從此邏輯推論可以改用簡潔精確的數學式計算，不但避免語意模稜兩可造成的謬誤，也大幅增加處理命題的效能。在許多學者投入之下，數理邏輯這門全新的路線迅速發展，布爾自己也在 1854 年出版的《思維法則》(The Laws of Thought) 中，把整個系統補強得更完整。

其實布爾的研究成果有許多都是萊布尼茲已經做過的，但歷史就是這麼奇妙，萊布尼茲被視為二進位制的創立者，是因為一個世紀前的哈里厄特沒有公開發表論文。如今換成萊布尼茲自己沒有將邏輯代數的研究整理發表，而讓邏輯代數在一個半世紀後冠上布爾之名（稱為「布林代數」(Boolean algebra)，”Boolean”意指「布林的」）。

還有一點令人惋惜的是，萊布尼茲如此看重二進位制，卻沒有像布爾那樣，用 1 與 0 代表命題運算後的真偽。對於電腦運算而言，這是絕對必要的，因此從電腦發展的角度而言，即使萊布尼茲的文稿更早公開，布爾一定還是會在發明電腦的功勞簿上記上一筆。

二進位制與布林代數就緒，現代電腦只欠東風

事實上，布爾對計算機也不陌生。由於好友德摩根是愛達·勒芙蕾絲的數學家教，透過這層關係，布爾曾經跟巴貝奇書信往來。他在 1862 年寫給巴貝奇的一封信中，還特地感謝他為自己解釋差分機的細節。就像當年萊布尼茲曾設想過二進位的計算機，我們不禁要想像若是結合布爾的全新觀點與巴貝奇的設計天分，是否會改變計算機的歷史？

但這已無從得知了，因為布爾在兩年之後就死於非命。原來布爾冒著大雨到學校教課，因此感冒發燒，不料他那迷信順勢療法的老婆，竟繼續往布爾身上澆了好幾桶水，反而導致他嚴重肺炎，才四十九歲就因病過世。

無論如何，沒有電力還是不會有現代電腦，因此儘管二進位制與布林代數早已就緒，仍需等待東風——也就是電力系統與硬體零件，計算機才能航向全新的世代。當然，東風起了，還得有個諸葛孔明運籌帷幄呢……。

非古典邏輯：直覺主義

布勞威爾 （1881 – 1966）是最早脫離所謂「古典邏輯」系統的學者之一。他反對弗雷格和羅素將數學化約為邏輯的構想，認為數學根基於我們對某些基本數學物件（如數字和直線）的「直覺」，因此他的學說便稱為「直覺主義」。

惡魔論證

布勞威爾主要將焦點擺在無限集合和序列上，例如所有正數的集合和無理數（如 π 和）小數點後的數字形成的序列等等。他的論證大致如下：

我邏輯上能證明 666 這個序列一定會出現在任何無理數（如 π）的擴張裡。因為若主張 666 不在裡面，就代表 666 不出現在 π 的小數點後數字的任何地方，但這一點在數學上是無法證明的。就算世界上所有白紙都寫滿π的小數點後數字，還是有無限多的數字沒檢查到。

直覺邏輯的興起

雖然布勞威爾只想證明有些數學證明的方式和邏輯證明不同，但有些人發現他的論證也能用來證明某些數學領域的邏輯和其他數學領域不同，甚至有些人還據以建構出一套邏輯系統，並嘗試證明這套邏輯適用於所有數學領域。這套系統就叫「直覺邏輯」。

直覺主義 v.s. 歸謬法

直覺邏輯有一個關鍵特點，就是不能用萊布尼茲的歸謬法。歸謬法是先假設某個數學陳述的否定為真，然後導出矛盾，進而證明該陳述為真。但要從「某事的否定為假」推導出「某事為真」就得仰賴排中律，因此在某些數學領域裡，歸謬法並不符合數學應該運作的方式，也就是從公理推導出數學語句。

直覺主義的數學熱潮

上述問題在 1930 年代引發了一波新的數學熱潮，不少學者嘗試用直覺邏輯替一些常用的基本數學陳述找到證明，也確實找到了不少。

數學系和哲學系紛紛成立，新的學術領域也隨之誕生。就連希爾伯特的方法明明是直覺邏輯的對手，也被加以改造，只使用得到認可的直覺主義程序。直到這股風潮引起了哥德爾的注意。

儘管後來學者對這場爭辯的興趣削弱了一些，但「唯有構造性證明才能確保一個陳述句為真」的基本看法至今仍然得到不少邏輯學家、數學家、科學家和哲學家支持。

處理未來陳述句的老問題

大約同一時期，波蘭數學家盧卡西維茨（1897 – 1956）1920 年提出的構想勾起了一些學者的興趣。此前十多年，這個構想從來不曾在波蘭以外的地區引起多大反應。盧卡西維茨當時想解決的，是從亞里斯多德到羅素都面對過的老問題。

編按：「如何判斷大笨鐘一千年後會遇上大雪」這句話的真值？

——本文摘自《大話題：邏輯》，2023 年 3 月，大家出版出版，未經同意請勿轉載。

從簡單陳述句轉變為複合句——「連接詞」

大約一百年後，克律西波斯（c.280 – c.206 BC）改變了邏輯的關注焦點，從簡單的主述詞陳述句轉向「蘇格拉底是人，且芝諾也是人」之類的複合句。

這是很大的進展。當時甚至有人說「克律西波斯的邏輯就是神會用的邏輯」。我們稍後會見到，克律西波斯的邏輯也是人類使用的邏輯，只不過我們還得等兩千年才會明白這一點。

複合句使用的連接詞不同，其真假受個別句子影響的方式也不同。

譬如「不是…就是…」這個連接詞組可以這樣用，也只有「不是…就是…」這個連接詞組可以這樣用：

編按：「不是」穆罕默德到山那邊，「就是」山到穆罕默德這邊。

其後一千五百年甚至更久，克律西波斯沒有對邏輯留下多少影響。不僅因為他的作品失傳了，只留下他人的轉述，也因為亞里斯多德成了天主教會的心頭好。

萊布尼茲定律

接下來兩千年，邏輯學家建構出愈來愈多三段論，有些甚至前提不只兩個。這些邏輯學家就像煉金術士，拿著概念拼拼湊湊，想辦法生出有效論證。最後有一個人在這股狂熱當中想出了方法，那人就是萊布尼茲（1646 – 1716）。

萊布尼茲想到的方法是將陳述句看成代數裡的等式。等式使用等號（＝）來表達式子兩邊數值相等。

例如：x2 + y2 = z2

萊布尼茲將等號帶進邏輯裡，用來指稱 a 和 b 等同。

自此之後，這個等同式就叫做「萊布尼茲定律」。萊布尼茲將 a = b 拆成兩個不可分割的述句「a 是 b」和「b 是 a」，意思是「所有 a 都是 b」和「所有 b 都是 a」。

例如：「所有單身漢都是沒結婚的男人，且所有沒結婚的男人都是單身漢。」

若 a 和 b 等同，那麼陳述句裡的 a 就算換成 b，這個陳述句的真假顯然不會隨之改變。例如，「蘇格拉底是沒結婚的男人，沒結婚的男人是單身漢，因此蘇格拉底是單身漢」。

這個定律很重要，因為有了它，我們就能以有限多的步驟來判斷近乎無限多的句子的真值。萊布尼茲使用的步驟數是四個。

1. a = a

例：「蘇格拉底是蘇格拉底。」

2. 若 a 是 b，且 b 是 c，則 a 是 c

例：「所有人都會死，蘇格拉底是人，所以蘇格拉底會死。」

說「a 是 b」就等於說「所有 a 都是 b」。

3. a =非（非 a）

例：「如果蘇格拉底會死，則蘇格拉底不是不會死的。」

4. a 是 b = 非 b 是非 a

例：「蘇格拉底是人，意思是如果你不是人，你就不是蘇格拉底。」

利用這四個簡單的法則，萊布尼茲就能證明所有可能出現的三段論。比起亞里斯多德的四角對當，這才是人類史上第一個真正的真理理論，因為它使用事先定下的法則，藉由代換等同的符號（同義詞）來導出結論。

非真即假的歸謬法

萊布尼茲最常用的證明方法是一個極為重要的邏輯工具，深受後世邏輯學家和哲學家喜愛。他稱呼這個方法為歸謬法。

這個工具很簡單，卻好用得驚人，自萊布尼茲發明以來便廣獲使用。我們用一個例子來講最清楚。

使用歸謬法時，我們先假設要檢驗的那個陳述句為真，再看它能導出哪些結論。如果導出的結論互相矛盾，我們就知道那個陳述句是假的，因為矛盾永遠為假。

歸謬法有一大好處，那就是即使我們不知道如何證明，也能判斷一個陳述句的真假；只要證明這個陳述句的否定會導出矛盾，就知道它是真的了。

新工具

「我發明的這個工具完全使用理性，是裁決爭議的判官、解釋概念的權威、衡量可能性的天平、指引我們穿越經驗之海的指南針，是萬物的清單、思想的表格、檢視事物的顯微鏡、預測遙遠事物的望遠鏡、通用的演算法、不使詐的魔術、不空妄的計謀，也是人人都能用自己的語言閱讀，所及之處皆會帶來真宗教的經文。」

萊布尼茲致信漢諾威公爵，1679 年

不難想見，天主教會將萊布尼茲視為異端。但「思想有其必然法則」的想法卻對西方哲學家產生了深遠的影響，包括康德、黑格爾、馬克思和羅素。

——本文摘自《大話題：邏輯》，2023 年 3 月，大家出版出版，未經同意請勿轉載。