分享本文至 E-mail 信箱

學術引用格式

MLA (點一下全選)

APA (點一下全選)

EndNote(.enw)

布爾與電腦——《科學月刊》

項潔/臺灣大學資訊工程系特聘教授,兼任臺大數位人文中心與臺大出版中心主任。

布爾邏輯使得二進制在電子元件上得以實現,並且能夠進行基本的算術演算。從前巴貝奇雖然能設計,卻無法建造的可變換程序的計算機,到二十世紀中葉終於在布爾邏輯的基礎上得以完成。布爾對於電腦與資訊時代人類文明的影響,絕不亞於其他更著名的科學家,但是這樣的成就,卻是他所不曾預料的。

1946 年,世界第一台電子計算機(以下簡稱電腦)誕生了, 它的名字叫做ENIAC(Electronic Numerical Integrator And Computer),主要設計者是莫克利(John Mauchly, 1907~1980) 和伊克特(J. Presper Echert, 1919~1995)(當時團隊裡負責除法和開方運算的是一位華裔科學家朱傳榘)。那一年,距離布爾誕生已經131年,布爾也已去世82 年,他有生之年大概沒有想像到現代電腦發展的圖景。所以為何要在布爾誕生200 周年之際,談論布爾和電腦的關係呢?這個問題要從更久遠的過去談起。

01

史上第一台電腦 ENIAC,當時被美軍用於計算火炮彈道。相比現今電腦,其體積可說相當龐大,占地 167 平方公尺,組件包含上萬個真空管與電容器,重量達 27 噸。 (Source: terren in Virginia

計算機的發展

早從人類文明開始有精緻的交易行為起,就知道快速計算的重要。人類的第一個算盤,在西元前2500 年西亞的蘇美文明中就已出現,而且全世界每一個文明幾乎都有類似的工具。隨著工業革命帶來的商業和科技的發展,西方世界對計算的需求也越來越複雜,除了加減乘除外,還需要計算不同的函數,以及能儲存部分計算成果的機制等。換句話說,也就是需要從單純的計算器(calculator)進化到計算機(computer)。1801 年,雅卡爾(Joseph-Marie Jacquard, 1752~1834)就透過打卡(punch card)的設計來編織複雜的布料花樣,從現代的角度來看,那已經是在寫初步的程式了。

02

雅卡爾所設計之打卡編織系統,影響了後來計算機的誕生。(Source: John R. Southern

另一個更重要的發展,是比布爾年長24 歲的巴貝奇(Charles Babbage, 1791~1871)在1834 年開始設計的分析引擎(Analytical Engine)。巴貝奇花了數十年功夫改進這個機器,但一直到1871 年巴貝奇去世,分析引擎始終沒有被製造出來。(巴貝奇設計的另外一個比較簡單,專做多項式運算的差分引擎(Difference Engine),終於在1991 年被完整實現。)雖然如此,巴貝奇的分析引擎已經有了現代計算機的大致模樣。這個分析引擎的設計也是用雅卡爾的打卡機制,不同的是一個分析引擎的運作需要兩組卡片,一組描述要計算的函數及運算的指令,另一組包含函數中各個參數的值。熟悉1970 年代以前電腦的讀者,一定看得出這已經和當時的打卡機與電腦運作類似了。值得一提的是,巴貝奇最重要的同事叫做奧古斯塔‧ 愛達‧ 拜倫(Augusta Ada Byron, 1815~1852), 她是大詩人拜倫的女兒,也被公認為全世界第一位程式設計師。1980 年代美國國防部發展的程式語言Ada 就是以她命名的。

雖然分析引擎已經是一個通用的(general purpose)的計算機:具備中央處理器、記憶體、I/O 設計,甚至可以寫程式,而且距今150 年左右就已經被設計出來。但是,這個機器始終沒有被完全實現,關鍵就是因為分析引擎是機械式的,按照巴貝奇的設想,它必須靠蒸汽機動力來運轉,而當時的零件並沒有精細到如此地步;另一個問題則是經費,當時巴貝奇估計的需求用現在的價格來看,造價將超過8.5 億新臺幣。

NEW

巴貝奇所設計的差分引擎,包含超過 8000 個組件,重量達 5 噸。 (Source: Jitze CouperusMarcin Wichary

布爾和巴貝奇有數面之緣,在一封1862 年給巴貝奇的信裡,他感謝後者為他解釋差分引擎的細節。但布爾兩年後就去世了,所以如果他對巴貝奇的工作產生實質的興趣,兩人會激發出怎樣的火花呢?這部分也就只能靠後人的想像了。布爾的專注點是數學和邏輯,其中一個他感興趣的問題是,如何將人的思維透過數學的方法來呈現。在他1847 年的《邏輯之數學分析》和1854 年的《思想法則之探討》這兩部重要著作裡,布爾發展出一個後世所稱的布爾邏輯(或稱布林邏輯)(Boolean logic)。布爾邏輯的細節在本期中董世平教授〈布爾與邏輯〉的文章裡有深入的介紹,在此不再重複。不過這裡要提的一個重點是布爾的邏輯系統不但往上呼應到比他早2500 年的亞理士多德的邏輯,而且蘊含一個可以運算的方式,也就是布爾代數(Booleanalgebra)。布爾代數使得邏輯(或者說人類思維的方法)得以運算,這是個了不起的發現。

04

在倫敦科學博物館展示的巴貝奇的大腦。 (Source: Ross Huggett

何謂布爾代數?

布爾代數是由AND(x ∧ y),OR(x ∨ y),和NOT(¬x)三個運算組成。我們可以用布爾代數把一個邏輯命題表示成一個數學公式,如「x 或y 為真」變成x ∨ y=1,而「非x和y 為假」就成了¬x ∧ y=0。在這裡我們介紹一個和布爾代數等價,比布爾代數更容易運算但較不為人知的布爾環(Boolean ring)。布爾環和布爾代數不同的是將OR 用另一個運算XOR(Exclusive OR,⊕)代替,這個環的架構使得兩個運算(XOR 和AND)更接近我們熟悉的加法和乘法,所以在邏輯公式的運算上就更加直接。我們以下直接用+ 代表⊕,× 代表∧,推導出一個轉換系統:

05

A 的三個轉換將布爾代數的運算變成布爾環的運算;C 的四個等式僅用來表示 + 和 ×都符合交換律和結合律,所以不用管參數的前後順序;重要的是,B 的六個轉換,可以用來將任何一個用命題邏輯符號表示的布爾公式,簡化成一個唯一的標準型,如下:

06布爾代數造就電腦時代

布爾邏輯和布爾代數雖然在邏輯領域造成很大的影響,但長久以來除了數學界和哲學界之外,並沒有受到太多的重視,直到1937 年一個22 歲美國MIT 的研究生向農(Claude Shannon, 1916~2001)寫了一篇碩士論文〈繼電器與交換電路的符號分析》(A Symbolic Analysis of Relay and Switching Circuits)〉。在這篇劃時代的文章裡,向農觀察到任何電路(circuit)均可用一個方程式來代表,而這個方程式是由AND、OR 和NOT 三個運算(在電路學中稱為gates)組成,透過電壓的強弱可以呈現每個變數(電路學裡的開關,或switch)是正(true)或負(false)的狀態,而布爾代數正是從事這些運算的現成武器。其實不止是電路而已,數字本身也可以用二進制(binary)的方法來表現,如二是10(需要兩個開關),五是101(需要三個開關)等等。換言之,用二進制的開關電路(binary switching circuits)不但可以表示數字、函數,甚至可以透過開關的運作進行運算。這個發現開啟了電腦時代的蓬勃展開,直到今日。

07

向農。(Source: Tekniska museet

回到巴貝奇的分析引擎。前面說過,電腦大致所需要的核心組件,巴貝奇在一百多年前都已經想到了。然而,為何他沒有成功呢?差別在什麼地方?最大的差別,就在於現在的電腦只需要考慮兩個值(0 和1,也就是二進制),一切複雜的運算和數據都可以用這兩個值堆砌出來,而且電壓又是一個精確、快速、又不容易出錯的動源。半導體的發展已可以讓當初ENIAC 一間房子那麼大的電腦的功能濃縮在幾乎看不到的晶片裡還綽綽有餘,如果計算機還是停留在巴貝奇那時機械式的設計裡,這些都是無法想像的。電腦革命可以開展,布爾代數佔了極重要的地位,而布爾當初的純粹學理的研究,造成後代那麼大的影響,恐怕也是他未曾預料過的。

10〈本文選自《科學月刊》2015年11月號〉

延伸閱讀:
喬治.布爾─自學成大器的數學家
布爾與邏輯

什麼?!你還不知道《科學月刊》,我們46歲囉!
入不惑之年還是可以
當個科青

泛科學姊妹站 NPOst 公益交流站 推出【NPOst 公益學院】,將與你一起探討,新世代工具如何主導未來,如何結合公益應用,讓你社群翻倍、擁有過人的溝通力和精準的開源力!

覺得複雜議題很難解釋嗎?(勞基法是什麼可以吃嗎)覺得外面流言蜚語很難做風險管理嗎?覺得社群都很難懂、義賣只能大喊大叫很困擾嗎?無論你是求知若渴的 NPO 從業人員,或時刻觀注公益的新生代創業家,快參加 3/17(五)的課程說明會,掌握公益學院的課程內容 !

活動詳情: 2017 NPOst 公益學院|掌握新工具,成就新時代

關於作者

科學月刊

非營利性質的《科學月刊》創刊於1970年,自創刊以來始終致力於科學普及工作;我們相信,提供一份正確而完整的科學知識,就是回饋給讀者最好的品質保證。