Learning Objectives
- 說明布林值只有「真／假」兩種，並對應到電路的 1 與 0
- 寫出 AND、OR、NOT、XOR、NAND、NOR 的真值表
- 把一句判斷規則寫成布林運算式，列出它的真值表
- 用笛摩根定律改寫運算式，說明 NAND 為什麼稱為萬用閘
電腦怎麼做「判斷」
手機解鎖的規則是「指紋對了，或密碼對了」；宿舍門禁是「有學生證，而且在開放時間內」。 這些規則的每個條件只有兩種答案：是，或否。
前幾課看過，電腦裡的資料全部是 0 和 1。這一課要回答：只有 0 和 1，電腦怎麼做出判斷？ 答案是一套只處理「是／否」的代數，加上把這套代數做成電路的元件：邏輯閘（logic gate）。
| 生活裡的說法 | 布林值 | 電路裡 |
|---|---|---|
| 是、真（true） | 1 | 高電壓（有電） |
| 否、假（false） | 0 | 低電壓（沒電） |
布林代數與三個基本運算
英國數學家布爾（George Boole）在 1847 年的《邏輯的數學分析》與 1854 年的《思維規律》中， 把邏輯推理寫成代數：變數只有真與假兩種值，用運算把它們組合起來。這套方法後來稱為布林代數（Boolean algebra）。
將近一百年後，夏農（Claude Shannon）在 1937 年的 MIT 碩士論文（1938 年發表）中指出： 用繼電器、開關組成的電路，可以用布林代數來分析與設計。從此，「設計電路」可以先在紙上用代數算，數位電路的設計就建立在這個基礎上。
布林代數有三個基本運算：
| 運算 | 意思 | 生活例子 | 什麼時候是 1 |
|---|---|---|---|
| AND（且） | 兩個條件都要成立 | 有學生證 且 在開放時間 | 兩個輸入都是 1 |
| OR（或） | 至少一個成立 | 指紋對 或 密碼對 | 至少一個輸入是 1 |
| NOT（非） | 相反 | 不是假日 | 輸入是 0 |
把所有可能的輸入列出來，寫出每一種輸入的結果，這張表叫真值表（truth table）。 兩個輸入各有 0、1 兩種值，所以有 2 × 2 = 4 列；三個輸入就有 2³ = 8 列。
XOR、NAND、NOR 與電路符號
除了三個基本運算，電路裡還常用三種由它們組合出來的閘：
| 閘 | 運算式 | 什麼時候輸出 1 | 常見用途 |
|---|---|---|---|
| XOR（互斥或） | A ⊕ B | 兩個輸入不一樣 | 樓梯兩端的開關控制同一盞燈、加法的個位數（下一課） |
| NAND | (A · B)′ | AND 的相反：除了兩個都是 1，其他都輸出 1 | 最常用來製造晶片的基本單元 |
| NOR | (A + B)′ | OR 的相反：兩個都是 0 才輸出 1 | 「全部都沒有發生」的偵測 |
書寫時，AND 常寫成乘號 A · B、OR 寫成加號 A + B、NOT 在變數右上加一撇 A′（或在上方畫一條橫線）。 電路圖的符號：AND 是半圓形（D 字形），OR 是尖頭的弧形，NOT 是三角形，輸出端的小圓圈表示「再反相一次」， 所以 NAND＝AND 加小圓圈、NOR＝OR 加小圓圈。
真正的邏輯閘是用電晶體做的：電晶體像一個用電壓控制的開關，幾個電晶體串聯或並聯，就能做出一個閘。 一顆處理器裡有非常大量的電晶體，組成數不清的邏輯閘。
把一條規則寫成運算式，列出真值表
門禁規則「有學生證，而且（在開放時間或是管理員）」寫成 card & (hours | admin)。程式用三層迴圈把三個條件的 8 種組合都試一次。在 Python 裡 & 對 0 和 1 做 AND、| 做 OR。看上方三個變數怎麼一列一列變化，再對照輸出：哪幾列會開門？
想一想：真值表與運算式
下面這段程式會印出什麼？（& 是 AND，| 是 OR，1 - C 是 NOT C）
A, B, C = 1, 0, 1
print((A & B) | (1 - C))
樓梯有上下兩個開關控制同一盞燈：不管燈現在亮不亮，撥任何一個開關，燈都會改變狀態。這盞燈的電路是哪一種閘？
一個電路有 4 個輸入，它的完整真值表有幾列？
布林代數的規則與笛摩根定律
布林代數有一些和一般代數很像的規則，可以用來化簡運算式（也就是讓電路用更少的閘）：
| 規則 | AND 的寫法 | OR 的寫法 |
|---|---|---|
| 交換律 | A · B ＝ B · A | A + B ＝ B + A |
| 和 0、1 運算 | A · 1 ＝ A，A · 0 ＝ 0 | A + 0 ＝ A，A + 1 ＝ 1 |
| 和自己運算 | A · A ＝ A | A + A ＝ A |
| 和自己的相反運算 | A · A′ ＝ 0 | A + A′ ＝ 1 |
| 分配律 | A · (B + C) ＝ A · B + A · C | A + B · C ＝ (A + B) · (A + C) |
最常用的是笛摩根定律（De Morgan's laws），以英國數學家笛摩根（Augustus De Morgan）命名：
NOT (A AND B) ＝ (NOT A) OR (NOT B)
NOT (A OR B) ＝ (NOT A) AND (NOT B)
用生活的話說：「不是兩個都有」等於「至少缺一個」；「兩個都沒有」等於「沒有 A 而且沒有 B」。 下面的程式把四種輸入都代進去，確認兩邊永遠相等。
用程式驗證笛摩根定律
在只有 0 和 1 的情況下，NOT x 可以寫成 1 - x。程式對 A、B 的四種組合分別算出等號左邊與右邊，再用 == 比較。看 left 和 right 是不是每一列都一樣。
NAND 是萬用閘
只用 NAND 一種閘，就能做出 NOT、AND、OR，因此能做出任何邏輯電路。這種性質叫功能完備（functionally complete）， NAND 因此稱為萬用閘（universal gate）；NOR 也有同樣的性質。
| 想做的閘 | 只用 NAND 的做法 |
|---|---|
| NOT A | 把 A 同時接到 NAND 的兩個輸入：(A · A)′ ＝ A′ |
| A AND B | NAND 之後再接一個「當成 NOT 用的 NAND」 |
| A OR B | 先把 A、B 各自反相，再接 NAND：(A′ · B′)′ ＝ A + B（笛摩根定律） |
這個性質在 1913 年由謝弗（Henry M. Sheffer）發表；美國哲學家皮爾士（Charles S. Peirce）在 1880 年左右的手稿中已經注意到，但當時沒有發表。 對晶片製造來說，整顆晶片大量重複同一種單元比較容易製造與最佳化，這是 NAND 常用的原因之一。
下面的練習是「填空題」：電路的其他部分已經接好，你要選一個閘放進「?」，讓整個電路符合目標真值表。
想一想：化簡與萬用閘
依笛摩根定律，NOT (A OR B) 等於下列哪一個？
把同一個訊號 A 同時接到 NAND 閘的兩個輸入，輸出是什麼？
運算式 A + A′ · B（A OR ((NOT A) AND B)）化簡後等於哪一個？可以用真值表檢查。
重點整理
- 布林值只有真（1）與假（0），在電路裡對應高電壓與低電壓；布林代數由布爾提出，夏農把它用在開關電路的設計上。
- 三個基本運算：AND（兩個都是 1）、OR（至少一個是 1）、NOT（相反）。由它們組合出 XOR（不一樣才是 1）、NAND、NOR。
- 真值表列出所有輸入組合的結果，n 個輸入有 2ⁿ 列。任何「是／否」的判斷規則都能寫成運算式，再列出真值表。
- 笛摩根定律：NOT (A AND B)＝(NOT A) OR (NOT B)，NOT (A OR B)＝(NOT A) AND (NOT B)。
- 只用 NAND（或只用 NOR）就能做出所有邏輯電路，因此稱為萬用閘。
下一課：把邏輯閘組合起來，做出一個會算加法的電路。想在程式裡練習 and、or、not，可以接著上 Python 軌的條件判斷。