Learning Objectives
- 用 0 和 1 描述開關與燈的關係，寫出真值表
- 依 NOT、AND、OR 的順序計算布林式
- 用窮舉所有輸入的方式判斷兩個布林式是否相等
- 從真值表寫出最小項相加的布林式，並接成電路驗證
一盞樓梯燈，兩個開關
樓梯間的燈通常有兩個開關，樓下一個、樓上一個。你在樓下開燈，走到樓上關燈；不管另一個開關現在扳在哪裡，扳任何一個，燈都會跟著變。
這個行為要怎麼精確描述？用「上」「下」「亮」「暗」寫句子很快就會繞在一起，改用 0 和 1 就清楚了。把開關位置記成 A、B，把燈記成 Y，假設兩個開關都在 0 的時候燈是暗的，所有情況只有四種：
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
這張表叫做真值表（truth table）：列出輸入的每一種組合，以及對應的輸出。它把「扳任何一個燈都會變」這句話變成可以逐列檢查的東西：從任何一列出發，只改 A 或只改 B，Y 都會翻轉。
n 個輸入有 2ⁿ 種組合，所以真值表有 2ⁿ 列。2 個輸入 4 列，3 個輸入 8 列，10 個輸入就有 1024 列。列數增加得很快，這也是後面的課要學化簡與模組化的原因。
AND、OR、NOT 與計算順序
只處理 0 和 1 的代數叫做布林代數（Boolean algebra），基本運算只有三種：
| 運算 | 寫法 | 讀作 | 結果是 1 的時候 |
|---|---|---|---|
| NOT | A′ | A 的反相 | A 是 0 |
| AND | A·B | A 而且 B | 兩個都是 1 |
| OR | A + B | A 或 B | 至少一個是 1 |
要留意 + 和 · 看起來像加法與乘法，但這裡只有 0 和 1：1 + 1 = 1，不是 2。OR 只回答「有沒有至少一個是 1」。
計算順序也和四則運算相似：括號最先，接著 NOT，再來 AND，最後 OR。以 A＝0、B＝1、C＝0 計算 A + B·C′：
C′ = 1
B·C′ = 1·1 = 1
A + B·C′ = 0 + 1 = 1
加上括號結果就可能不同。同樣的輸入，(A + B)·C 是 (0 + 1)·0 = 0。反相符號的範圍也要看清楚：(A·B)′ 是先 AND 再反相，A′·B′ 是先各自反相再 AND，這兩個不相等，等一下會親手驗證。
基本定律：不用背，窮舉就能證明
布林式可以像代數一樣改寫，改寫的依據是這些定律：
| 定律 | 第一種形式 | 第二種形式 |
|---|---|---|
| 交換律 | A·B = B·A | A + B = B + A |
| 結合律 | (A·B)·C = A·(B·C) | (A + B) + C = A + (B + C) |
| 分配律 | A·(B + C) = A·B + A·C | A + B·C = (A + B)·(A + C) |
| 吸收律 | A·(A + B) = A | A + A·B = A |
| 笛摩根定律 | (A·B)′ = A′ + B′ | (A + B)′ = A′·B′ |
第二種分配律在一般算術裡是錯的，在布林代數裡卻成立；吸收律也很不像一般代數。這些定律不必硬背，因為布林代數有一個很大的好處：變數的值只有兩種，所以兩個式子相不相等可以直接窮舉。把每一種輸入代進去算，每一列都相同就是相等；只要有一列不同就是不相等。
這種證明方式在一般代數做不到（x 有無限多種可能），在布林代數裡卻是有限的工作。不過要記得代價：列數是 2ⁿ，變數一多就試不完。
用程式窮舉驗證定律
程式裡的 & 是 AND、| 是 OR，都是對 0 和 1 運算。留意前半段 assert 全部通過，後半段找到的是一個長得很像定律的式子的反例。
從真值表寫出布林式
設計電路時，常常是先知道「什麼情況下要輸出 1」，也就是先有真值表，再求式子。方法很機械：
- 找出 Y 是 1 的每一列。
- 每一列寫成一個乘積：值是 1 的變數直接寫，值是 0 的變數加反相。這個乘積只有在這一列才等於 1，叫做最小項（minterm）。
- 全部用 OR 加起來。
樓梯燈的 Y 在 A＝0、B＝1 和 A＝1、B＝0 是 1，所以：
A＝0、B＝1 → A′·B
A＝1、B＝0 → A·B′
Y = A′·B + A·B′
為什麼這樣一定對？每個最小項只在自己那一列是 1，OR 起來之後，Y 剛好在這些列是 1，其他列全部是 0。所以任何真值表都能寫成布林式，也就都能接成只用 AND、OR、NOT 的電路。這種「乘積相加」的形式簡稱 SOP（sum of products）。
這個式子常常不是最短的。最短的寫法要等到第 3 課的卡諾圖。
用程式從真值表產生式子
下面的程式照著剛才的三個步驟走，最後把式子代回每一列檢查。看 parts 怎麼一個變數一個變數長出來。
從邏輯學走進電路
布林代數的名字來自英國數學家 George Boole。他在 1847 年的《The Mathematical Analysis of Logic》與 1854 年的《The Laws of Thought》裡，用代數的方法處理邏輯推論。當時它是邏輯學的工具，和電路沒有關係。
把它接上電路的是 Claude Shannon。他在 MIT 的碩士論文《A Symbolic Analysis of Relay and Switching Circuits》（1937 年完成，1938 年刊登在 AIEE 的期刊）指出：繼電器開關的串聯與並聯，可以用布林代數來描述與化簡。開關串聯是 AND，兩個都接通電流才過得去；並聯是 OR，有一個接通就過得去。
這件事的實際意義是：設計開關電路不再只能靠經驗與試接，可以先用代數算出來。現在的晶片用電晶體取代了繼電器，這個想法一直沿用到今天。
確認一下
A＝1、B＝0、C＝0，A + B·C 和 (A + B)·C 分別是多少？
一個電路有 6 個輸入，要完整檢查它的功能，真值表有幾列？
要判斷 A + A·B 和 A 是否相等，下面哪一個作法足以證明？
真值表只有 A＝0、B＝1 與 A＝1、B＝1 兩列的 Y 是 1。依最小項相加寫出來的式子是？
走廊有三個開關，要求扳任何一個燈都會變。把三個開關都扳到 1，再和全部是 0 的時候（燈暗）比較，燈是亮還是暗？
重點整理
- 布林代數只有 0 和 1，基本運算是 NOT、AND、OR，計算順序是括號、NOT、AND、OR；1 + 1 = 1。
- 真值表列出輸入的所有組合，n 個輸入有 2ⁿ 列。
- 因為值只有兩種，兩個布林式是否相等可以窮舉判斷；一列不同就是不相等。笛摩根定律告訴你反相進到括號裡時，AND 和 OR 要互換。
- 把 Y＝1 的列寫成最小項再相加，任何真值表都能變成布林式。同一個真值表可以有很多種電路。
下一課把這些運算變成實際的邏輯閘，並且看看為什麼只要一種閘就夠了。