計算機基本原理—數學和邏輯

光電科學史 發佈 2019-12-23T09:43:12+00:00

在古埃及、古巴比倫、古印度和古代中國,數學是一門實用技術,被用於計算數量、幾何長度、面積和體積。古希臘人從古埃及、古巴比倫和古印度學習了那時所有的數學知識。他們出於對邏輯的嗜好與擅長,用邏輯對數學知識進行了演繹推理和證明。

在古埃及、古巴比倫、古印度和古代中國,數學是一門實用技術,被用於計算數量、幾何長度、面積和體積。古希臘人從古埃及、古巴比倫和古印度學習了那時所有的數學知識。他們出於對邏輯的嗜好與擅長,用邏輯對數學知識進行了演繹推理和證明。至今初中生學習的諸如「因為┄┄,所以┄┄」這類範式的數學證明題,就是古希臘人發明的。

古希臘以後的2000多年,邏輯一直是數學證明的工具,或者說是數學的基石。但是,數學與邏輯仍然是兩門不同的學問。僅僅從數學的完美性角度出發,將邏輯納入數學,應該是極具誘惑力的想法,因而一直有學者試圖用符號和數學運算來表示邏輯,完成邏輯推理,但都不太成功。

直到喬治.布爾才取得了決定性的突破。

布爾的父親是鞋匠,母親曾經是女僕。英國當時森嚴的等級制度使小布爾沒有受到好的教育。但是,他靠自身強烈的求知慾和父親的幫助(其父對科學、數學和文學都有濃厚的興趣),布爾自學了上層階級男孩才能學到的拉丁文、希臘語和數學。由於在數學學術刊物上發表過論文,1849年他被任命為愛爾蘭Cork市皇后大學數學系的首席教授。

布爾發明了一種與傳統代數相似的代數——布爾代數。

圖1是一道傳統代數題。

圖1 一道傳統代數題

在傳統代數中,以字母(x、y)表示未知數,用運算符(+、-、x、/)、等於號(=)和數字組成代數方程,遵循運算規則,就可以得到答案。

在布爾代數中,用字母代表集合,仍然用運算符、等於號和數字組成方程,只不過布爾代數運算符的含義與傳統代數不同。

在布爾代數中,運算符「+」意味著兩個集合合併,如圖2所示:A集合用紅色圓圈表示,B集合用藍色圓圈表示,A+B就是A集合與B集合的合併,圖中用綠色表示。

圖2 算符「+」示意

在布爾代數中,運算符「X」意味著兩個集合的交集,如圖3所示:A集合用紅色圓圈表示,B集合用藍色圓圈表示,A X B就是A集合與B集合的交集,圖中用綠色表示。

圖3 運算符「X」示意

布爾代數的運算規則多數與傳統代數相同。不同的有以下幾條:

1,表示全部集合;

0,表示空集;

1 – A, 表示排除了A以後的集合,即非A集合;

1 + A = 1, 全部集合與A集合的並集還是全部集合;

A x (1 – A)= 0,這是矛盾律,即A集合與非A集合的交集是空集,它表明一個事物不能同時是它自己和它自己的反面;

A x A = A, A集合與A集合的交集仍然是A集合;

A + A = A, A集合與A集合的並集仍然是A集合;

布爾代數只有兩個數,分別是:true(真)和false(假)。

圖4是十進位運算表,是小學一年級學生必須熟記得。

圖4 十進位運算表

圖5是布爾代數運算表,對比十進位運算,布爾代數具有一種驚人的簡潔美。

圖5 布爾代數運算表

布爾曾經是小學老師,他在教小孩子記住十進位運算表時一定被虐心過。或許這也是他發明布爾代數的動機之一。

我們現在來看看,布爾代數如何進行邏輯推理運算。首先考慮一個著名的亞里士多德三段論邏輯推理:

所有人都是要死的;

蘇格拉底是人。

因此蘇格拉底是要死的。

用P代表所有人的集合,用D代表所有要死的東西的集合(包括人、貓、狗、樹等等一切生命體),用S代表蘇格拉底,依題意:

P X D = P

這個表達式意味著「所有人是要死的」。如圖7所示,所有人是都要死的相當於所有人的集合P包含在要死的東西的集合D裡面,因此,交集運算就如上式。

圖6 「所有人是要死的」示意

蘇格拉底是人的集合表達式:

S x P = S

就是說蘇格拉底(S集合)包含在所有人(集合P)裡面。布爾運算如下:

運算結果:S X D = S 意味著「格拉底集合包含在要死的東西集合裡面」,因此,蘇格拉底是要死的。

假如布爾代數只能解決如此小兒科的問題,那麼就不會是偉大的發明了。下面舉一個略難的問題。

設:

M代表公貓

F代表母貓

W代表白貓

Y代表黃貓

B代表黑貓

O代表其它所有顏色的貓

N代表被閹割過的貓

U代表有生殖能力的貓

假如你對寵物店的店員說:「我要買一隻貓,一隻閹割過的公貓,白色或黃色的均可;或者要一隻閹割過的母貓,除了白色,其它顏色均可;或者只要是只黑貓,我也要。」

店員對你說:「看來您想要的貓是下面的式子表示的集合中的一隻:

對嗎?」你回答:「是的,完全正確!」

開始,店員拿出一隻有生殖能力的黃色公貓,你將這隻貓代入以上式子運算,結果如下:

因此,上式成為:

(Ture x False x(False + Ture) + (False x False x(1 – False))+ False

=(False x(False + Ture))+(False x(1 – False))+ False

=(False x False + False x Ture)+(False x 1 – False x False)+False

= False + False +False

= False

所以,有生殖能力的黃色公貓不符合我的要求。

接著,店員又拿出一隻閹割過的灰色母貓,你再將其代入表達式運算,結果如下:

(False x Ture x (False + False))+ ( Ture x Ture x Ture)+ False

=(False + False)+ Ture + False

= False + Ture +False

= Ture + False

= Ture

所以,閹割過的灰色母貓符合我的要求。

這個例子說明布爾代數是如何幫人們做出邏輯判斷的。讀者也許會說:「這樣做並不容易嘛!」。是的,用手算確實比較麻煩。但是請讀者想一想,假如你面對的是由成百上千集合,通過成百上千運算符組成的邏輯關係,用布爾代數運算,至少可以獲得正確的邏輯判斷。如果哲學家僅憑聰明的腦袋,估計弄錯的可能性極大。再來,一旦讓機器(比如計算機)掌握了布爾代數,情況可就大不一樣啦,人們只要事先按照邏輯關係設置好機器,就可以非常非常快地完成邏輯判斷。

布爾本人有沒有意識到他發明的意義呢?讓我們看看布爾那兩本偉大著作的名稱:《邏輯的數學分析,論演繹推理的運算》、《建立在邏輯和機率數學理論基礎上的思想規律研究》。每當我看到他這麼野心勃勃、甚至異想天開的書名,就會情不自禁地喟嘆:「布爾的思想具有多麼深邃的穿透力呵!他有可能預料到了人工智慧。」

關鍵字: