資源描述:
《布爾代數(shù)入門》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、布爾代數(shù)入門布爾代數(shù)是計(jì)算機(jī)的基礎(chǔ)。沒有它,就不會(huì)有計(jì)算機(jī)。布爾代數(shù)發(fā)展到今天,已經(jīng)非常抽象,但是它的核心思想很簡單。本文幫助你理解布爾代數(shù),以及為什么它促成了計(jì)算機(jī)的誕生。我依據(jù)的是《編碼的奧妙》的第十章。這是一本好書,強(qiáng)烈推薦。一、數(shù)理邏輯的起源19世紀(jì)早期,英國數(shù)學(xué)家喬治·布爾(GeorgeBoole,1815-1864)突發(fā)奇想:人的思想能不能用數(shù)學(xué)表達(dá)?此前,數(shù)學(xué)只用于計(jì)算,沒有人意識(shí)到,數(shù)學(xué)還能表達(dá)人的邏輯思維。兩千年來,哲學(xué)書都是用文字寫的。比如,最著名的三段論:所有人都是要死的,蘇格拉底是人,所以,蘇格拉底是要死的。喬治·布爾認(rèn)為,這種推理可以用數(shù)學(xué)表達(dá),也
2、就是說,哲學(xué)書完全可以用數(shù)學(xué)寫。這就是數(shù)理邏輯的起源。二、集合論喬治·布爾發(fā)明的工具,叫做"集合論"(Settheory)。他認(rèn)為,邏輯思維的基礎(chǔ)是一個(gè)個(gè)集合(Set),每一個(gè)命題表達(dá)的都是集合之間的關(guān)系。比如,所有人類組成一個(gè)集合R,所有會(huì)死的東西組成一個(gè)集合D。所有人都是要死的集合論的寫法就是:RXD=R集合之間最基本的關(guān)系是并集和交集。乘號(hào)(X)表示交集,加號(hào)(+)表示并集。上面這個(gè)式子的意思是,R與D的交集就是R。同樣的,蘇格拉底也是一個(gè)集合S,這個(gè)集合里面只有蘇格拉底一個(gè)成員。蘇格拉底是人//等同于SXR=S上面式子的意思是,蘇格拉底與人類的交集,就是蘇格拉底。將
3、第一個(gè)式子代入第二個(gè)式子,就得到了結(jié)論。SX(RXD)=(SXR)XD=SXD=S這個(gè)式子的意思是,蘇格拉底與會(huì)死的東西的交集,就是蘇格拉底,即蘇格拉底也屬于會(huì)死的東西。三、集合的運(yùn)算法則前面的三段論比較容易,一眼就能看出結(jié)論。但是,有些三段輪比較復(fù)雜,不容易立即反應(yīng)過來。請(qǐng)看下面這兩句話。"鴨嘴獸是卵生的哺乳動(dòng)物。鴨嘴獸是澳洲的動(dòng)物。"你能一眼得到結(jié)論嗎?鴨嘴獸X卵生=鴨嘴獸鴨嘴獸x澳洲=鴨嘴獸將第一個(gè)式子代入第二個(gè),就會(huì)得到:鴨嘴獸X卵生x澳洲=鴨嘴獸//相當(dāng)于卵生x澳洲=鴨嘴獸+其他因此,結(jié)論就是"有的卵生動(dòng)物是澳洲的動(dòng)物",或者"有的澳洲的動(dòng)物是卵生動(dòng)物"。還有更不
4、直觀的三段論。"哲學(xué)家都是有邏輯頭腦的,一個(gè)沒有邏輯頭腦的人總是很頑固。"請(qǐng)問結(jié)論是什么?這道題會(huì)用到新的概念:全集和空集。集合A和所有不屬于它的元素(記作-A)構(gòu)成全集(I),這時(shí)A和-A的交集就是一個(gè)空集(0)。A+(-A)=IAX(-A)=0因此,有下面的公式。B=BXI=BX(A+-A)=BXA+BX(-A)回到上面那道題。哲學(xué)家X邏輯=哲學(xué)家無邏輯X頑固=無邏輯根據(jù)第一個(gè)命題,可以得到下面的結(jié)論。哲學(xué)家X無邏輯=(哲學(xué)家X邏輯)X無邏輯=哲學(xué)家X(邏輯X無邏輯)=哲學(xué)家X0=0即哲學(xué)家與沒有邏輯的人的交集,是一個(gè)空集。根據(jù)第二個(gè)命題,可以得到下面的結(jié)論。無邏輯X頑
5、固=無邏輯X頑固X(哲學(xué)家+非哲學(xué)家)=無邏輯X頑固X哲學(xué)家+無邏輯X頑固X非哲學(xué)家=0X頑固+無邏輯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)無非就是一系列集合運(yùn)算。由于集合運(yùn)算的結(jié)果還是集合,那么通過判斷個(gè)體是否屬于指
6、定集合,就可以計(jì)算命題的真?zhèn)?。一名顧客走進(jìn)寵物店,對(duì)店員說:"我想要一只公貓,白色或黃色均可;或者一只母貓,除了白色,其他顏色均可;或者只要是黑貓,我也要。"這名顧客的要求用集合論表達(dá),就是下面的式子。公貓X(白色+黃色)+母貓X非白色+黑貓店員拿出一只灰色的公貓,請(qǐng)問是否滿足要求?布爾代數(shù)規(guī)定,個(gè)體屬于某個(gè)集合用1表示,不屬于就用0表示?;疑墓垖儆诠埣?,就是1,不屬于白色集合,就是0。上面的表達(dá)式變成下面這樣。1X(0+0)+0X1+0=0因此,就得到結(jié)論,灰色的公貓不滿足要求。這就是布爾代數(shù):計(jì)算命題真?zhèn)蔚臄?shù)學(xué)方法。五、布爾代數(shù)的運(yùn)算法則布爾代數(shù)的運(yùn)算法則與集合
7、論很像。交集的運(yùn)算法則如下。1X1=11X0=00X0=0并集的運(yùn)算法則如下。1+1=11+0=10+0=0集合論可以描述邏輯推理過程,布爾代數(shù)可以判斷某個(gè)命題是否符合這個(gè)過程。人類的推理和判斷,因此就變成了數(shù)學(xué)運(yùn)算。20世紀(jì)初,英國科學(xué)家香農(nóng)指出,布爾代數(shù)可以用來描述電路,或者說,電路可以模擬布爾代數(shù)。于是,人類的推理和判斷,就可以用電路實(shí)現(xiàn)了。這就是計(jì)算機(jī)的實(shí)現(xiàn)基礎(chǔ)。六、布爾代數(shù)的局限雖然布爾代數(shù)可以判斷命題真?zhèn)危菬o法取代人類的理性思維。原因是它有一個(gè)局限。它必須依據(jù)一個(gè)或幾個(gè)已經(jīng)明確知道真?zhèn)蔚拿},才能做