零基礎學習計算機原理:布林邏輯和邏輯閘

Hello World!我是老喬,歡迎來到超智星球。在這裡,每篇都學一個小知識。

微號:超智星球 網站:chaozhixingqiu。com

這期呢,還是計算機原理系列,上期最後講到了自動製表機和IBM。本期接著講計算機歷史。

## 前言與內容提綱

上集,我們談了計算機最早是機電裝置,一般用十進位制計數,比如用齒輪數來代表十進位制。再到電晶體計算機電子計算機的電晶體可以開啟或關閉電流(二進位制)。

只用開/關兩種狀態也可以代表資訊,這叫二進位制。二進位制計算機運算的核心,是各種開關。那麼,為什麼一堆開關,就能完成運算呢?這就是本期我們要講的內容。

* 為什麼用二進位制, 布林代數與布林邏輯

* 3個基本操作:NOT,AND,OR——或且非

* 對應的:非門、且門、或門的電路實現

* 基於上述門,製作一個XOR——異或門

## 二進位制的工程優勢與數學基礎

你可能覺得電晶體只有兩種狀態不多,功能很有限。事實上,電晶體的確可以不只是開/關,還可以讓不同大小的電流透過,一些早期電子計算機是三進位制的,有3種狀態(比如蘇聯的某些計算機),甚至五進位制,5種狀態。

問題是,狀態越多,越難區分訊號-如果手機快沒電了或者附近有電噪音(因為有人在用微波爐),訊號可能會混在一起。。。而每秒百萬次變化的電晶體會讓這個問題變得更糟!

所以我們把兩種訊號儘可能分開 - 只用“開”和“關”兩種狀態,可以儘可能減少這類問題

這是計算機使用二進位制的好處,但是,我們關心的問題是,為什麼只憑借開關兩種狀態,就可以完成這麼複雜的運算呢?

最關鍵的原因是,在當時,有一整個數學分支存在,專門處理“真”和“假”,它已經解決了所有法則和運算,叫“布林代數”(Boolean Algebra)!

布林代數是計算機的基礎。沒有它,就不會有計算機。所有數字晶片,從設計到生產,每一個環節都離不開布林代數。事實上,它是現在計算機類學科必修的知識,從大學一年級課程開始,AND, OR, NOT 邏輯運算,CNF, DNF, 笛摩根定理…等等等等,就已經植根到每一個業者的腦海裡。

## 布林代數因布林而得名

布林代數的本質,是透過符號化和代數化來有系統地進行邏輯推理。它為邏輯推理發明了一套可以像算術演算一樣的計算方法。

說起邏輯,這其實本來是哲學和語言學的一個分支,研究怎們樣有條理的說話和寫文章,遠在古希臘時代就已經存在了。比如,與或非等邏輯的思想,從亞里士多德時代就有了。著名的三段論,就是亞里士多德提出的。

但哲學領域的邏輯學,都是用文字標書的。人的思維過程能用數學表示嗎?在這個問題上,最早的可以追溯到萊布尼茨,他曾試圖將邏輯思想形式化,就是將它們用簡潔的數學形式表達出來,但沒有獲得成功。

> 我想尋求這樣一張特殊的字母表,其元素表示的不是聲音而是概念。有了這樣一個符號系統,我們就可以發展出一種語言,我們僅憑符號演算,就可以確定用這種語言寫成的哪些句子為真,以及它們之間存在著什麼樣的邏輯關係。——萊布尼茨的願望

這個問題在萊布尼茨的一百多年後,終於被布林解決(萊布尼茨和牛頓的微積分大約是在布林出生前150年出現)。

零基礎學習計算機原理:布林邏輯和邏輯閘

布林應用代數方法研究了邏輯,把一些簡單的邏輯思維數學化,建立了邏輯代數【在之前,1843年,漢密爾頓已經發明瞭四元數代數,這個東西肯定對布林有所啟發】

1847年,32歲的布林出版了一本書,將他的研究成果整理發表,只有86頁。名字叫做《邏輯的數學分析》The Mathematical Anaysis of Logic。這也是布林代數第一次公之於眾。

## 布林代數的內容

現在的數學書上已經把布林代數講的雲裡霧裡,非常抽象,看起來就讓人頭大,但其實它本來是很簡單的。本文幫助你理解布林代數,以及為什麼它促成了計算機的誕生。

所謂邏輯,就是判斷真假或者是非。邏輯的基礎是三段論,這是古希臘的哲學家亞里斯多德發明的,包括一個大前提、一個小前提和一個結論。我們舉個例子來看一下:

1。 所有人都是會死的。(這是大前提)

2。 蘇格拉底是人。(這是小前提)

3。 所以,蘇格拉底也是會死的。(這是結論)

在這個推理的三段論中,我們關心的是最後的結論是真的,還是假的。當大前提和小前提都是真的時,那麼結論也必然是真的。

前面的例子是一個單一的判斷。布林代數是關於幾個判斷之間的邏輯關係的演算,所以稱為邏輯代數。

假設,關於蘇格拉底,有下面兩種說法:

* 蘇格拉底是一個人————這個大家都知道是 **真** 的

* 蘇格拉底還活著————這顯然是 **假的** ,蘇格拉底已經死了兩千多年了

在這兩種說法的基礎上,我們來看看下面幾種說法的真假:

* 蘇格拉底是一個人 **並且** 蘇格拉底還活著。

這種說法自然不能成立。因為,‘並且’是一個並列的邏輯關係,其前後的條件都必須為真,整個判斷才能成立;如果其中的任何一個條件是**假**的,那麼整個判斷就是假的,這個事件就不會發生。

在上面的說法中,如果把表示邏輯關係的詞‘並且’換成‘或者’,像下面這樣:

* 蘇格拉底是一個人,或者,蘇格拉底還活著。

那麼,這種說法就是成立的,因為,‘或者’是一個選擇性的邏輯關係,所有的條件中,只要其中任意一個條件是真的,那麼,這個判斷就是**真**的,這整個事件就會發生。

這是兩種最基本的邏輯關係。除此之外,我們還有關於‘否定’的邏輯關係,就是‘非’邏輯。‘非邏輯’就是對一個判斷作相反的操作,‘真’的一否定,就變成了‘假’的;‘假’的一否定,就變成了‘真’的。比如:

* 蘇格拉底不是人————這顯然是假的

喬治·布林就是用數學的方法來研究我們前面講的這些邏輯關係。在“常規”代數里(你在高中學的那種)變數的值是數字,可以進行加法或乘法之類的操作。

簡單代數系統可以表達為:

數量屬性:

1。 變數是自然數

2。 每一個自然數a都有一個後繼a+1

數量值運算:加減乘除

運演算法則:結合律、分配率等等

但在布林代數中,變數的值是 true 和 false,能進行邏輯操作。

邏輯代數有下面幾個規則和運演算法則,因為邏輯運算不是算術計算,所以有以下規定:

(1)布林代數中,數值只能取true和false或者0和1

用字母來代替我們前面那些例子中的具體的人和事,並且他用數字1表示‘真’,用數字0表示‘假’。這樣一來,邏輯判斷就變成了數學運算。

* 用A代表‘蘇軾是詩人’,所以A = 1

* 用B代表‘蘇軾還活著’,所以B = 0

* 用C表示‘蘇軾已經死了’,所以C = 1

(2)布林代數中,變數可以進行“或且非”三種邏輯操作

用‘乘法’來表示‘且’運算,用‘加法’來表示‘或’運算,在字母上面加一撇‘’‘表示’非‘運算,那麼,這三個判斷之間的邏輯關係就可以變成這樣:

* A + B = 1 + 0 = 1

* A + C = 1 + 1 = 1

* A·B = 1·0 = 0

* A·C = 1·1 = 1

* B’ = C = 0‘ = 1

(3)邏輯運算滿足以下定律:

* 交換律:

* A + B = B + A

* A·B = B·A

* 結合律:

* (A+B) + C = A + (B + C)

* (A·B)·C = A·(B·C)

* 吸收律:

* A + A·B = A

* (A + B)(A + C)=A + B·C

* 反演律:

* (A·B·C……)’ = A‘ + B’ + C‘ + ……

有了吸收率和反演律,有些看似非常複雜的邏輯關係,就可以化簡合併。比如:

零基礎學習計算機原理:布林邏輯和邏輯閘

這個式子中字母上面的短橫和前面式子中的’‘’是同樣的意思,代表‘非’運算。

去掉算術系統中數字的屬性及其意義,保留對數字的操作;用邏輯值(true和false)代替數值,而邏輯值有自己的屬性和意義,就形成了布林邏輯系統。

運算可以參照代數邏輯推演出來。這樣布林就把邏輯歸約成代數運算系統,發現代數系統中的運演算法則(結合,交換,分配法則)同樣也適用於邏輯系統。

有了邏輯系統,我們就可以對句子進行推理,也就實現了開頭萊布尼茨的願望。這樣代數系統就有了推理能力。

推理能力正是布林邏輯產生的原因,也是其最重要的意義所在。而推理是比代數運算更具有普適性的運算,因此,推理反過來又可以構建代數系統,甚至可以用來構建任何系統(計算機的強大就是證明)。

明白這一點也就明白了計算機中的抽象的本質,明白瞭如何去構建一個可用的抽象系統,計算理論中有一個名詞,圖靈可歸約,其實是一個意思。

## 布林代數因夏農而不凡

講了這麼多,大家可能要問,布林搞出這些無聊的字母遊戲有什麼用?

這個問題,不僅你我疑惑,在當時,整個學界也是疑惑的。布林代數發明後很久都不受重視。數學家們曾輕蔑地說它:沒有數學意義,在哲學上也屬於稀奇古怪的東西。

直到20世紀初,羅素在《數學原理》中提到:“純數學是布林在一部他稱之為《思想規律》的著作中發現的”,人們這才關注到布林代數。但還是認為它是毫無實際用途的“純數學”。

直到1938年,一位年僅22歲的美國年輕人在《繼電器與開關電路的符號分析》中,將布林代數與開關電路聯絡起來了。這篇文章是他在麻省理工學院(MIT)獲得電氣工程碩士學位的畢業論文。

上世紀八十年代,被譽為“多元智慧理論”之父的哈佛大學教授霍華德。加德納(HowardGardner)曾經評論這篇文章:“它可能是本世紀最重要、最著名的一篇碩士論文”。

這位年輕人就是克勞德。艾爾伍德。夏農(這位後面我們也會講到)

零基礎學習計算機原理:布林邏輯和邏輯閘

## 用布林代數製作計算機

我們前面已經說過,這個東西用處非常巨大。它是我們現代這個電子時代和資訊社會最底層的基本原理。如果沒有布林代數,什麼計算機、自動控制、手機、網際網路等等這一切,都不可能存在。

數學公式和科學原理,並不能直接產生任何實際的用途,還必須有相應的實現這些功能的物理元件。恰好,咱上期繼電器、電子管和電晶體的發明,為實現邏輯控制和資訊的數字化處理,鋪平了道路。沒看過的同學,可以關注超智星球公號,看一下。

我們知道,計算機、手機、自動控制系統、人工智慧等等這些東西,都是用積體電路——也就是電子晶片組裝起來的。而積體電路是由幾千萬、上億個電晶體組成的。

而電晶體,我們上一篇文章說過了,就是個受控制的開關。可以接收控制訊號,改變是否導電。我們可以假設開關接通的狀態為‘1’,開關不通的狀態為‘0’,這樣就可以用開關電路模擬邏輯狀態,組成邏輯電路。而這最最基本的邏輯電路,我們稱為**“邏輯閘”**。之所以叫 “門”,是因為它能控制電流的路徑。

邏輯閘可以由電阻、電容、二極體、三極體等分立原件構成,成為**分立元件門**。也可以將閘電路的所有器件及連線導線製作在同一塊半導體基片上,構成**整合邏輯閘電路**。

對應布林代數中有三個基本操作:NOT, AND 和 OR。構成計算機最基本的邏輯閘就是:與門、或門、非門。將這三個基本邏輯電路透過不同的組合關係,就形成了人們所需要的各種數位電路。

我們來看下如何使用晶體管制作這三個邏輯閘。

## NOT 和 “非門”

NOT 操作把布林值反轉,把 true 進行 NOT 就會變成 false,反之亦然。我們可以根據 NOT 操作的輸入和輸出,做出這個表。我們叫NOT操作表。

零基礎學習計算機原理:布林邏輯和邏輯閘

我們先來看一個電晶體。電晶體只是電控制的開關,有3根線:2根電極和1根控制線。

零基礎學習計算機原理:布林邏輯和邏輯閘

控制線通電時,電流就可以從一個電極流到另一個電極。就像水龍頭一樣- 開啟水龍頭,就有水流出來;關掉水龍頭,就沒水了。

可以把控制線,當做輸入(input);底部的電極,當做輸出(output);所以 1 個電晶體,有一個輸入和一個輸出。

零基礎學習計算機原理:布林邏輯和邏輯閘

如果我們開啟輸入(input on),輸出也會開啟(output on),因為電流可以流過;如果關閉輸入(input off),輸出也會關閉(output off),因為電流無法透過

或者用布林術語來說,輸入為真,輸出為真;輸入為假,輸出為假,我們也可以把這個做成“真值表”

零基礎學習計算機原理:布林邏輯和邏輯閘

這個電路沒什麼意思,因為它沒做什麼事-輸入和輸出是一樣的,但我們可以稍加修改,實現NOT。

與其把下面那根線當做輸出,我們可以把輸出放到上面,如果開啟輸入,電流可以流過然後 “接地”,輸出就沒有電流,所以輸出是off。如果用水來舉例,就像家裡的水都從一個大管子流走了,開啟淋浴頭一點水也沒有。

零基礎學習計算機原理:布林邏輯和邏輯閘

如果輸入是on,輸出是 off;當輸入是 off,電流沒法接地,就流過了輸出,所以輸出是 on;如果輸入是off,輸出是on。和NOT操作表一樣!太棒了

零基礎學習計算機原理:布林邏輯和邏輯閘

我們做了個有點用的電路!我們叫它 “非門”-。

## AND 和 “且門”

在布林代數中,“AND”操作有 2 個輸入,1 個輸出;和上次一樣,可以給“AND”做個表。

零基礎學習計算機原理:布林邏輯和邏輯閘

為了實現 “AND 門”,我們需要2個電晶體連在一起,這樣有2個輸入和1個輸出

零基礎學習計算機原理:布林邏輯和邏輯閘

如果只打開 A,不開啟 B 電流無法流到 output,所以輸出是 false;如果只打開B,不開啟 A,也一樣,電流無法流到 output;只有 A 和 B 都打開了,output 才有電流。

## OR 和 “或門”

最後一個是OR—— 只要 2 個輸入裡,其中 1 個是 true,輸出就是 true

零基礎學習計算機原理:布林邏輯和邏輯閘

實現 “OR 門” 除了電晶體還要額外的線,不是串聯起來。而是並聯,然後左邊這條線有電流輸入。用“小拱門”代表2條線沒連在一起,只是跨過而已(雖然看起來像連在一起

零基礎學習計算機原理:布林邏輯和邏輯閘

如果 A 和 B 都是 off,電流無法流過,所以輸出是 off;如果開啟 A,電流可以流過。輸出是 on。如果只打開 B 也一樣,只要 A OR B是on,輸出就是 on;如果 A 和 B 都 on,結果是on。

## 一次抽象:製作“異或門”-XOR

好,現在 NOT門, AND門, OR門 都搞定了,我們可以基於它們構建更復雜的門了。

但在開始之前呢,我們先進行一次抽象,我們只是用符號來代表這三個門,這樣我們構建其他電路的時候,就不再管底層的細節(也就是那些開關),可以集中精力用來構建更復雜的系統。

NOT門的畫法是三角形前面一個圓點;AND門用D表示;OR門用太空船表示————“D 形狀和太空船”不是標準叫法, 只是我喜歡這樣叫而已。

零基礎學習計算機原理:布林邏輯和邏輯閘

前面說的三個操作,是最基本的邏輯操作。除了前面說的三個,另一個有用的布林操作叫“異或”,XOR。

XOR就像普通OR,但有一個區別:如果2個輸入都是true,XOR輸出false;想要XOR輸出true,一個輸入必須是true,另一個必須是false

零基礎學習計算機原理:布林邏輯和邏輯閘

用電晶體實現XOR門有點燒腦子,但可以展示一下怎麼用前面提到的3種門來做XOR門:XOR門有2個輸入,A和 B ,還有1個輸出。

零基礎學習計算機原理:布林邏輯和邏輯閘

## 最後,聊聊抽象

XOR超有用的,我們下次再說它。因為超有用,工程師給了它一個符號,一個 OR 門 + 一個笑臉

零基礎學習計算機原理:布林邏輯和邏輯閘

重要的是,我們現在可以知道怎麼造XOR門了,並且用抽象符號封裝了它。我們完成了又一層抽象,把 XOR 放入“工具箱”了。

後面的課程中,我們可以直接使用它來推導更高階的運算,而不用擔心XOR具體用了幾個門,這幾個門又是怎麼用電晶體拼的,或電子是怎麼流過半導體的。

工程師設計處理器時,很少在電晶體的層面上思考,而是用更大的元件,比如邏輯閘,或者由邏輯閘組成的更大元件,我們以後會講,就算是專業程式設計師也不用考慮邏輯是怎樣在物理層面實現的。

這關鍵的能力,就是抽象,封裝。抽象能力決定一個人的程式設計能力。

我們從電訊號開始,到現在第一次表示資料-真和假-開始有點“計算”的感覺了。

好啦,本期我們實現了布林代數最最重要的三層門。我們下期見。

參考文獻:

1。 楊露斯, 黎煉。 論計算機發展史及展望[J]。 資訊與電腦(理論版), 2010(06):194。

2。 N·M·莫里斯, 楊光輝。 英國標準——二進位制邏輯元件的符號[J]。 煤礦自動化, 1984(02):41

3。 N。A。知乎。布林代數是怎麼出現的?。2017。

4。 阮一峰。布林代數入門。阮一峰部落格。2016

5。 CrashCourse/CrashCourse字幕組。《計算機科學速成課》。youtube。2018