布林代數

一八四七年英國數學家喬治‧布爾 George Boole 出版了一本小冊子《邏輯的數學分析》,用來響應 Augustus De Morgan 與  William Hamilton 之間的公開論戰。一八四九年他任職於愛爾蘭科克皇后學院 ── 現今之科克大學或者是 UCC ──,為數學教授。其後於一八五四年發行了《The Laws of Thought思維規律一書,在這本書中布爾介紹了現在以他的名字命名的『布林代數』Boolean algebra。同時布爾也撰寫了微分方程和差分方程的課本,這些教科書在英國學校一直使用,直到一九世紀末。

在布爾之思維規律中『且‧連言』與『或‧選言』並不是一組對偶的運算。大約一八六零年代,布林代數一詞出現在英國著名的經濟學家 威廉姆‧斯坦利‧傑文斯 William Stanley Jevons 的論文中;他的 著作《政治經濟學理論》【1871年】一書中提出了『價值』的『邊際效用』理論。與奧地利Carl Menger 【1871年】和瑞士的法國經濟學大家 Léon Walras 【1874年】齊名,共同開創了一個經濟學思想的新時代 。無獨有偶,美國的查爾斯‧皮爾士  Charles Sanders Santiago Peirce,生於麻薩諸塞州坎布里奇,早年在哈佛大學接受教育,後任教於霍普金斯大學,也於一八六零年代發表論文談論布林代數。他是是美國的通才,儘管受教育作為化學家並因為此作了三十年的科學家,然而現在他幾乎是被當成哲學家的了。到了一八九零年 Ernst Schröder 寫《Vorlesungen》時,世界上才首度有了布林代數和分配律之系統的表述。如果說就現代公理化意義上具有代數結構的布林代數而言,那就得等到 一九零四年 Edward Vermilye Huntington 之論文的了。

運算符號布林代數集合論邏輯學
00空集合 Φ
11論域
聯集
交集
補集
//差集
對稱差
若則推導


邏輯等價
|、↑|、↑
謝費爾豎線
NAND
孤虛
⊕、↓⊕、↓
皮爾士箭頭
NOR
皆虛

250px-Hasse_diagram_of_powerset_of_3.svg

500px-Vennandornot.svg

Venn diagram of  A ↑ B

120px-NAND_ANSI_Labelled.svg

220px-7400

100px-CMOS_NAND_Layout.svg

220px-NXP-74AHC00D-HD

由於電流的『有無』和電壓的『高低』,與邏輯上的『真假』二態相似,所以很自然的布林代數也就進入『邏輯電路』的『設計』領域之中了。今天在『電子工程』領域裡的專業化了的布林代數叫做『邏輯代數』,而在『計算機科學』領域中之專門化的布林代數又稱作『布爾邏輯』。

一八八零年皮爾士已經發現『NAND』── Not AND ── 和『NOR』── Not OR ── 的邏輯『功能完備性』,還特別用了一個希臘語詞『ampheck』ἀμφήκης 雙刃,來表達它們都是『自足算子』;也就是說所有的邏輯表達式,都可以只用『NAND』或『NOR』構成。但是由於他從未發表過,於是三十三年後,一九一三年美國Henry M. Sheffer  於一篇提交給『Transactions of the American Mathematical Society 』的論文中,使用『豎線|』Strock 表示 NAND,同時他也論證了這個公理系統的完備性;因此現今 NAND 被稱作『Sheffer豎線 』,而 NOR 也叫做『皮爾士箭頭』。不知又是誰先想到這給邏輯電路的『工程實作』帶來了巨大的『經濟性』和『簡易性』??

未知何年何月,有一

孤虛者言︰
物有無者,非真假也。苟日新,日日新,又日新。真假者,物之論也。論也者,當或不當而已矣。故世有孤虛者,言有孤虛論。孤虛何謂也?甲乙孤虛,言不得全真也,索其孤其虛而已。天地孤虛,去其上下也,善惡孤虛,何得善惡並真乎?是故孤虛論全矣!其法曰︰物物孤虛,言物之非也;孤虛之孤虛,此孤虛 之非也。使甲與並,此甲乙辜虛之非也,強使之或,乃非甲非乙之孤虛也。若云由此及彼,雖言之鑿鑿,若非彼與此之孤虛,无能以斷疑是也!!

假使依據孤虛 ── Sheffer豎線 ──所說則︰

P\sim P = P \mid P

PQP \cdot Q = P \wedge Q = (P \mid Q) \mid (P \mid Q)

PQP + Q = P \vee Q = (P \mid P) \mid (Q \mid Q)

PQP \rightarrow Q =  P  \mid (Q \mid Q)

近年來根據美國方言學會 ADS American Dialect Society Stephen Goranson 的研究,一八七七年的一次工程學會會議上 Alfred Holt 的報告上提出︰

It is found that anything that can go wrong at sea generally does go wrong sooner or later, so it is not to be wondered that owners prefer the safe to the scientific …. Sufficient stress can hardly be laid on the advantages of simplicity. The human factor cannot be safely neglected in planning machinery. If attention is to be obtained, the engine must be such that the engineer will be disposed to attend to it.

,由此看來,說不定是 De Morgan 錯記『莫非』Murphy 的

Mathematician Augustus De Morgan wrote on June 23, 1866: “The first experiment already illustrates a truth of the theory, well confirmed by practice, what-ever can happen will happen if we make trials enough.” In later publications “whatever can happen will happen” occasionally is termed “Murphy’s law,” which raises the possibility — if something went wrong — that “Murphy” is “De Morgan” misremembered (an option, among others, raised by Goranson on American Dialect Society list).

這個大名鼎鼎的『莫非定律』說︰

凡事要可能出錯,必定會出錯!!

從科學和演算法方面來講,它和『最糟情境』worst-case scenario 分析同義,然而就文化層面而言,它代表著一種反諷式的幽默,也許能排解日常生活中諸多遭遇的不滿。

那人們該如何設想『莫非之機率』的呢?一九零九年時法國數學家埃米爾‧博雷爾 Félix-Édouard-Justin-Émile Borel 在一本機率書中介紹了一個『打字猴子』的概念︰

讓一隻猴子在打字機上隨機地按鍵,當這樣作的時間趨近無窮時,似乎必然能夠打出任何指定的文本,比如說整套莎士比亞的著作。

他用這隻猴子來比喻一種能夠產生無窮的隨機語詞字串之『抽象設備』。這個『無限猴子定理』理論是說︰把一個很大但有限的數看成無限的推論是錯誤的。猴子能否完全無誤的敲打出一部莎士比亞的哈姆雷特,縱使它發生的機率非常之小然而絕非是零!就像戰國時期的列禦寇在《列子‧湯問》中寫到︰

愚公移山

太行、王屋二山,方七百里,高萬仞,本在冀州之南,河陽之北。

北山愚公者,年且九十,面山而居。懲山北之塞,出入之迂也。聚室而謀曰:「吾與汝畢力平險,指通豫南,達於漢陰,可乎?」雜然相許。其妻獻疑曰:「以君之力,曾不能損魁父之丘,如太行、王屋何?且焉置土石?」雜曰:「投諸渤海之尾,隱土之北。」遂率子孫荷擔者三夫,叩石墾壤,箕畚運於渤海之尾。鄰人京城氏之孀妻有遺男,始齔,跳往助之。寒暑易節,始一反焉。

河曲智叟笑而止之曰:「甚矣,汝之不惠。以殘年餘力,曾不能毀山之一毛,其如土石何?」北山愚公長息曰:「汝心之固,固不可徹,曾不若孀妻弱子。雖我之死,有子存焉;子又生孫,孫又生子;子又有子,子又有孫;子子孫孫無窮匱也,而山不加增,何苦而不平?」河曲智叟亡以應。

操蛇之神聞之,懼其不已也,告之於帝。帝感其誠,命誇娥氏二子負二山,一厝朔東,一厝雍南。自此,冀之南,漢之陰,無隴斷焉。

即使無需神助,應該也是移的了山的吧!!

就讓我們使用 THue 語言作個猴子打字的『想像實驗』,來看看一個隨機產生的『八位數』,是否能夠得到『25135214』這個數── 代表著猴子敲出了『愛我一生,我愛一世 』這一句話 ── ?由於這只有『一億分之一』的機會,你如果使用網路雲端上之『Thue interpreter in Javascript』的解譯器,就祇能玩玩它的單步模式 Step。假使你想要體驗真實『跑跑看』,就請拷貝這個程式存成  test.s ,然後用 Thue 的 python  解譯器,執行︰

python thue.py -d test.s 

───  程式起始 ───

□::=0
□::=1
□::=2
□::=3
□::=4
□::=5
□::=6
□::=7
□::=8
□::=9
》10::=✘》
》11::=》
》12::=✘》
》13::=✘》
》14::=✘》
》15::=✘》
》16::=✘》
》17::=✘》
》18::=✘》
》19::=✘》
》20::=✘》
》21::=✘》
》22::=》
》23::=✘》
》24::=✘》
》25::=✘》
》26::=✘》
》27::=✘》
》28::=✘》
》29::=✘》
》30::=✘》
》31::=✘》
》32::=✘》
》33::=》
》34::=✘》
》35::=✘》
》36::=✘》
》37::=✘》
》38::=✘》
》39::=✘》
》40::=✘》
》41::=✘》
》42::=✘》
》43::=✘》
》44::=》
》45::=✘》
》46::=✘》
》47::=✘》
》48::=✘》
》49::=✘》
》50::=✘》
》51::=✘》
》52::=✘》
》53::=✘》
》54::=✘》
》55::=》
》56::=✘》
》57::=✘》
》58::=✘》
》59::=✘》
㊣✘》。::=㊣》2□5□1□3□5□2□1□4□。
㊣✘✘》。::=㊣》2□5□1□3□5□2□1□4□。
㊣✘✘✘》。::=㊣》2□5□1□3□5□2□1□4□。
㊣✘✘✘✘》。::=㊣》2□5□1□3□5□2□1□4□。
㊣✘✘✘✘✘》。::=㊣》2□5□1□3□5□2□1□4□。
㊣✘✘✘✘✘✘》。::=㊣》2□5□1□3□5□2□1□4□。
㊣✘✘✘✘✘✘✘》。::=㊣》2□5□1□3□5□2□1□4□。
㊣✘✘✘✘✘✘✘✘》。::=㊣》2□5□1□3□5□2□1□4□。
㊣》。::=~愛我一生,我愛一世!!
::=
㊣》2□5□1□3□5□2□1□4□。

───  程式結束 ───

 

在〈布林代數〉中有 1 則留言

留言功能已關閉。