布爾代數(shù)入門

1、布爾代數(shù)入門布爾代數(shù)是計(jì)算機(jī)的根底。沒有它，就不會(huì)有計(jì)算機(jī)。布爾代數(shù)開展到今天，已經(jīng)非常抽象，但是它的核心思想很簡(jiǎn)單。本文幫助你理解布爾代數(shù)，以及為什么它促成了計(jì)算機(jī)的誕生。我依據(jù)的是?編碼的微妙?的第十章。這是一本好書，強(qiáng)烈推薦。一、數(shù)理邏輯的起源19世紀(jì)早期，英國(guó)數(shù)學(xué)家喬治布爾(George Boole, 1815 1864)突發(fā)奇想：人的思想能不能用數(shù)學(xué)表達(dá)？此前，數(shù)學(xué)只用于計(jì)算，沒有人意識(shí)到，數(shù)學(xué)還能表達(dá)人的邏輯思維。兩千年來，哲學(xué)書都是用文字寫的。 比方，最著名的三段論： 所有人都是要死的，蘇格拉底是人，所以，蘇格拉底是要死的喬治布爾認(rèn)為，這種推理可以用數(shù)學(xué)表達(dá)，也就是說，哲學(xué)書完全

2、可以用數(shù)學(xué)寫。這就是數(shù)理邏輯的起源。二、集合論喬治布爾創(chuàng)造的工具，叫做"集合論"Set theory。他認(rèn)為， 邏輯思維的根底是一個(gè)個(gè)集合Set，每一個(gè)命題表達(dá)的都是集合之間的關(guān)系。比方，所有人類組成一個(gè)集合R，所有會(huì)死的東西組成一個(gè)集合D。所有人都是要死的集合論的寫法就是：R X D = R集合之間最根本的關(guān)系是并集和交集。乘號(hào) X表示交集， 加號(hào)+ 表示并集。上面這個(gè)式子的意思是， R與D的交 集就是R。同樣的，蘇格拉底也是一個(gè)集合S，這個(gè)集合里面只有蘇格拉底一個(gè)成員蘇格拉底是人/等同于S X R = S上面式子的意思是，蘇格拉底與人類的交集， 就是蘇格拉底。 將第一個(gè)

3、式子代入第二個(gè)式子，就得到了結(jié)論。S X (R X D)=(S X R) X D=S X D=S這個(gè)式子的意思是，蘇格拉底與會(huì)死的東西的交集，就是蘇 格拉底，即蘇格拉底也屬于會(huì)死的東西。三、集合的運(yùn)算法那么前面的三段論比擬容易，一眼就能看出結(jié)論。但是，有些三 段輪比擬復(fù)雜，不容易立即反響過來。請(qǐng)看下面這兩句話。"鴨嘴獸是卵生的哺乳動(dòng)物。鴨嘴獸是澳洲的動(dòng)物。"你能一眼得到結(jié)論嗎？鴨嘴獸X卵生=鴨嘴獸鴨嘴獸x澳洲=鴨嘴獸將第一個(gè)式子代入第二個(gè)，就會(huì)得到：鴨嘴獸X卵生x澳洲=鴨嘴獸/相當(dāng)于卵生x澳洲=鴨嘴獸+其他因此，結(jié)論就是"有的卵生動(dòng)物是澳洲的動(dòng)物 "，或

4、者"有的澳洲的動(dòng)物是卵生動(dòng)物"。還有更不直觀的三段論"哲學(xué)家都是有邏輯頭腦的，一個(gè)沒有邏輯頭腦的人總是很頑 固。"請(qǐng)問結(jié)論是什么？這道題會(huì)用到新的概念： 全集和空集。集合A和所有不屬于 它的元素記作-A構(gòu)成全集I，這時(shí)A和-A的交集就是 一個(gè)空集0。A + -A = IA X -A = 0因此，有下面的公式。B=B X I=B X (A + -A)=B X A + B X (-A)回到上面那道題。哲學(xué)家X邏輯=哲學(xué)家無邏輯X頑固=無邏輯根據(jù)第一個(gè)命題，可以得到下面的結(jié)論。哲學(xué)家X無邏輯=哲學(xué)家X邏輯X無邏輯=哲學(xué)家X 邏輯X無邏輯=哲學(xué)家X0=0即哲學(xué)家

5、與沒有邏輯的人的交集，是一個(gè)空集。根據(jù)第二個(gè)命題，可以得到下面的結(jié)論。無邏輯X頑固=無邏輯X頑固X 哲學(xué)家+非哲學(xué)家=無邏輯X頑固X哲學(xué)家+無邏輯X頑固X非哲學(xué) 家=0 X頑固+無邏輯X頑固X非哲學(xué)家=無邏輯X頑固X非哲學(xué)家=無邏輯也就是說，最終的結(jié)論如下。無邏輯X頑固X非哲學(xué)家=無邏輯/相當(dāng)于頑固X非哲學(xué)家=無邏輯+其他 結(jié)論就是頑固的人與非哲學(xué)家之間有交集。通俗的表達(dá)就 是：一些頑固的人，不是哲學(xué)家，或者一些不是哲學(xué)家的人， 很頑固。由此可見，集合論可以幫助我們得到直覺無法得到的結(jié)論， 保證推理過程正確，比文字推導(dǎo)更可靠。四、集合論到布爾代數(shù)既然命題可以用集合論表達(dá)，那么邏輯推導(dǎo)無非就是一

6、系列 集合運(yùn)算。由于集合運(yùn)算的結(jié)果還是集合，那么通過判斷個(gè)體是否屬于 指定集合，就可以計(jì)算命題的真?zhèn)?。一名顧客走進(jìn)寵物店， 對(duì)店員說："我想要一只公貓，白色或 黃色均可；或者一只母貓，除了白色，其他顏色均可；或者 只要是黑貓，我也要。"這名顧客的要求用集合論表達(dá)，就是下面的式子。公貓X 白色+黃色+母貓X非白色+黑貓店員拿出一只灰色的公貓，請(qǐng)問是否滿足要求？布爾代數(shù)規(guī)定，個(gè)體屬于某個(gè)集合用1表示，不屬于就用0表示?；疑墓垖儆诠埣?， 就是1,不屬于白色集合， 就是0。上面的表達(dá)式變成下面這樣。1 X (0 + 0)+ 0 X 1+ 0=0因此，就得到結(jié)論，灰色的公貓不

7、滿足要求。這就是布爾代數(shù)：計(jì)算命題真?zhèn)蔚臄?shù)學(xué)方法。五、布爾代數(shù)的運(yùn)算法那么布爾代數(shù)的運(yùn)算法那么與集合論很像。交集的運(yùn)算法那么如下。0 X 0 = 0并集的運(yùn)算法那么如下。1 + 1 = 11 + 0 = 10 + 0 = 0集合論可以描述邏輯推理過程，布爾代數(shù)可以判斷某個(gè)命題 是否符合這個(gè)過程。人類的推理和判斷，因此就變成了數(shù)學(xué) 運(yùn)算。20世紀(jì)初，英國(guó)科學(xué)家香農(nóng)指出， 布爾代數(shù)可以用來描述電 路，或者說，電路可以模擬布爾代數(shù)。于是，人類的推理和 判斷，就可以用電路實(shí)現(xiàn)了。這就是計(jì)算機(jī)的實(shí)現(xiàn)根底。六、布爾代數(shù)的局限 雖然布爾代數(shù)可以判斷命題真?zhèn)危菬o法取代人類的理性 思維。原因是它有一個(gè)局限。它必須依據(jù)一個(gè)或幾個(gè)已經(jīng)明確知道真?zhèn)蔚拿}，才能做出 判斷。比方，只有知道"所有人都會(huì)死"這個(gè)命題是真的，