布林邏輯與邏輯閘：從一盞樓梯燈到整台電腦
AND、OR、NOT、XOR、真值表與邏輯閘如何長出算術，以及為何 NAND 一種閘就能建構整個數位世界
電燈開關藏著一整座電腦城市
想像你站在一個房間裡，牆上有兩個開關控制同一盞燈：樓梯上下兩端各一個。你在樓下打開燈，上樓後再用另一個開關把它關掉。這種「樓梯燈」的設計，其實就是一個活生生的邏輯運算：燈亮或不亮，取決於兩個開關狀態的某種「組合規則」。
把「開關打開」記作 1、「關閉」記作 0，把「燈亮」記作 1、「燈滅」記作 0，這盞樓梯燈的行為就能寫成一張對照表。而這正是數位電腦最底層的祕密：再龐大的程式、再華麗的遊戲畫面、再聰明的 AI 模型，最終都被翻譯成數以億計的 0 與 1，再交給一群只懂得「真」與「假」的微小電路去處理。這些電路的運算規則，就是布林邏輯(Boolean logic)；實現這些規則的硬體元件，就是邏輯閘(logic gate)。
這篇文章，我們從一盞燈出發，一路走到能做加法的電路，最後看看為什麼一種叫 NAND 的閘，足以建構出整台電腦。
布林代數：只有兩個值的世界
布林邏輯得名於十九世紀數學家喬治・布爾(George Boole)。它的核心極為簡單：每個變數只能取兩個值，習慣上寫成 0 與 1，或對應到「假(false)」與「真(true)」。在這個世界裡，運算不是加減乘除，而是邏輯運算。
最基本的三個運算是 AND、OR、NOT，加上常用的 XOR，構成我們日常推理的形式化版本。它們各自對應一個很直覺的中文意義：
- AND（且）：兩者都為真，結果才為真。像「要帶傘 而且 要穿外套，我才出門」。
- OR（或）：只要其中一個為真，結果就為真。像「下雨 或 颳風，我就待在家」。
- NOT（非）：把真假反過來。「不是晴天」。
- XOR（互斥或）：兩者不同時為真，相同時為假。前面樓梯燈的例子正是 XOR：只有一個開關被切換，燈才會改變狀態。
我們常用符號表示這些運算：AND 寫成 $A \cdot B$ 或 $A \land B$，OR 寫成 $A + B$ 或 $A \lor B$，NOT 寫成 $\overline{A}$ 或 $\lnot A$，XOR 寫成 $A \oplus B$。
要注意，這裡的 $+$ 不是算術加法。在布林代數裡 $1 + 1 = 1$（OR 的結果），而不是 2。這是初學者最常踩的坑：布林的符號借用了算術外型，意義卻完全不同。
真值表：把規則攤開來看
要精確定義一個邏輯運算，最可靠的方法是把所有可能的輸入組合與對應輸出全部列出來，這張表叫真值表(truth table)。對兩個輸入而言，總共有 $2^2 = 4$ 種組合：
| A | B | A AND B | A OR B | A XOR B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
NOT 只有一個輸入，所以它的真值表只有兩列：
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
真值表的價值在於它毫無歧義。當你不確定某個複雜邏輯式到底在算什麼，把所有輸入列出來逐一計算，答案一目了然。對於 $n$ 個輸入，真值表會有 $2^n$ 列，這也預示了一個重要事實：輸入越多，可能性呈指數成長。
邏輯閘：讓電路執行邏輯
布林運算是抽象規則，邏輯閘則是把規則做成硬體的實體電路。每個邏輯閘接收一或多個電壓訊號（高電壓代表 1、低電壓代表 0），輸出一個訊號。工程界用標準符號繪製這些閘：
AND 閘 OR 閘 NOT 閘（反相器）
A ─┐ A ─┐ A ─▷○─ Y
╲D─ Y ╲)─ Y （三角形後接小圓圈）
B ─┘ B ─┘
實務上有六個常見的閘。除了 AND、OR、NOT、XOR，還有兩個「加了否定」的版本：
- NAND（NOT-AND）：先 AND 再 NOT，即 $\overline{A \cdot B}$。
- NOR（NOT-OR）：先 OR 再 NOT，即 $\overline{A + B}$。
它們的符號就是在對應閘的輸出端多畫一個小圓圈（代表反相）。NAND 與 NOR 看似只是配角，後面我們會看到它們其實是整個數位世界的基石。
De Morgan 定律：否定的分配規則
當邏輯式裡同時出現否定與 AND／OR，常需要化簡或改寫。最重要的工具是 De Morgan 定律：
$$\overline{A \cdot B} = \overline{A} + \overline{B}$$
$$\overline{A + B} = \overline{A} \cdot \overline{B}$$
用白話說：「不是（A 且 B）」等於「不是 A 或不是 B」；「不是（A 或 B）」等於「不是 A 且不是 B」。否定一個括號時，要把裡面的 AND 換成 OR、OR 換成 AND，並把每一項各自否定。
舉個生活例子：「不是（你帶了傘 而且 帶了外套）」，意思就是「你沒帶傘 或 沒帶外套」——只要少了任一樣就成立。
我們可以用真值表驗證第一條定律：
| A | B | A·B | $\overline{A \cdot B}$ | $\overline{A}$ | $\overline{B}$ | $\overline{A}+\overline{B}$ |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
第四欄與第七欄完全相同，定律成立。De Morgan 定律不只是數學趣味，它在硬體設計中極為關鍵：它讓我們能把任何用 AND／OR／NOT 寫成的電路，改寫成只用 NAND 或只用 NOR 的形式。
從邏輯到算術：半加器與全加器
布林邏輯最動人的地方，是它能直接做出算術。電腦怎麼用「真假」做加法？我們從二進位最基本的單位加法看起。
兩個一位元(bit)相加，有四種情況：
0 + 0 = 0 （和 0，進位 0）
0 + 1 = 1 （和 1，進位 0）
1 + 0 = 1 （和 1，進位 0）
1 + 1 = 10 （和 0，進位 1）
注意最後一行：$1+1$ 在二進位是 $10$，也就是「和(sum)為 0、進位(carry)為 1」。我們需要兩個輸出：和、進位。觀察規律：
- 和 的真值表，恰好就是 A XOR B。
- 進位 的真值表，恰好就是 A AND B。
把這兩個閘組合起來，就得到半加器(half adder)：
A ──┬──────[XOR]──── Sum（和）
│ ┌──┘
B ──┼───┤
│ └──[AND]──── Carry（進位）
└───────┘
半加器只能加兩個位元，但真正的加法需要處理「來自前一位的進位」。例如十進位 $19 + 5$，個位 $9+5$ 要進位到十位。能同時接收「進位輸入」的電路叫全加器(full adder)：它有三個輸入（A、B、進位輸入 $C_{in}$），兩個輸出（和 Sum、進位輸出 $C_{out}$）。全加器可以用兩個半加器加一個 OR 閘構成。
把 $n$ 個全加器串接起來——前一個的進位輸出接到下一個的進位輸入——就成了能處理 $n$ 位元加法的「漣波進位加法器(ripple-carry adder)」。這就是電腦做整數加法的硬體雛形。從幾個只懂真假的小閘，竟長出了算術，這正是計算之美。
動手看一個例子
讓我們親手化簡一個邏輯式，並驗證它。考慮這個式子：
$$Y = \overline{\overline{A} \cdot \overline{B}}$$
它看起來有點嚇人（雙重否定加 AND），但用 De Morgan 定律，把外層否定分配進去：
$$Y = \overline{\overline{A}} + \overline{\overline{B}} = A + B$$
雙重否定互相抵消，最後竟然就是單純的 $A + B$（OR）！也就是說，「對兩個輸入各取反、AND、再取反」等於「OR」。我們用真值表驗證：
| A | B | $\overline{A}$ | $\overline{B}$ | $\overline{A}\cdot\overline{B}$ | $Y=\overline{\overline{A}\cdot\overline{B}}$ | A+B |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
最後兩欄完全一致，化簡正確。我們也可以用程式把任意邏輯式的真值表列印出來，驗證自己的推導：
def half_adder(a, b):
"""半加器：回傳 (和, 進位)"""
s = a ^ b # XOR -> 和
c = a & b # AND -> 進位
return s, c
# 列印半加器真值表
print(" A B | Sum Carry")
for a in (0, 1):
for b in (0, 1):
s, c = half_adder(a, b)
print(f" {a} {b} | {s} {c}")
執行結果：
A B | Sum Carry
0 0 | 0 0
0 1 | 1 0
1 0 | 1 0
1 1 | 0 1
Python 內建的位元運算子 ^（XOR）、&（AND）、|（OR）、~（NOT）讓我們能直接在程式裡玩布林邏輯。注意 ~ 在 Python 是對整數做按位反相，會牽涉負數補數表示，初學時用單一位元建議改寫成 1 - a 來表達 NOT 較不易混淆。
重點回顧
- 布林邏輯的變數只有 0 與 1 兩個值，基本運算是 AND（且）、OR（或）、NOT（非）、XOR（互斥或）；要小心 $1+1=1$，布林的 $+$ 不是算術加法。
- 真值表把所有 $2^n$ 種輸入組合與輸出攤開列出，是定義與驗證邏輯式最可靠的方法。
- 邏輯閘是把布林運算實作成電路的硬體；常見六種為 AND、OR、NOT、NAND、NOR、XOR，輸出端的小圓圈代表反相。
- De Morgan 定律 $\overline{A\cdot B}=\overline{A}+\overline{B}$ 與 $\overline{A+B}=\overline{A}\cdot\overline{B}$，是化簡與改寫邏輯式的核心工具。
- 半加器（XOR 算和、AND 算進位）與全加器（多了進位輸入）展示了邏輯如何長出算術，串接後即成多位元加法器。
深入探討（研究所視角）
前面我們用了 AND、OR、NOT 等多種閘，但一個深刻的問題是：最少需要幾種閘，就能建構出任意邏輯電路？ 答案出人意料——只要一種就夠了，那就是 NAND（NOR 也行）。NAND 被稱為通用閘(universal gate)，因為任何布林函數都能僅用 NAND 閘實現。
要證明這點，只需展示 NAND 能合成出 AND、OR、NOT 這組「函數完備(functionally complete)」的基底。回憶 NAND 的定義 $\text{NAND}(A,B)=\overline{A\cdot B}$：
- NOT：兩個輸入接同一訊號。$\text{NAND}(A,A)=\overline{A\cdot A}=\overline{A}$。
- AND：先 NAND 再 NOT。$\overline{\text{NAND}(A,B)}=\overline{\overline{A\cdot B}}=A\cdot B$；而 NOT 又能用 NAND 做，所以 AND 需兩個 NAND。
- OR：對兩輸入先各自取 NOT（各一個 NAND），再 NAND。由 De Morgan，$\text{NAND}(\overline{A},\overline{B})=\overline{\overline{A}\cdot\overline{B}}=A+B$，共三個 NAND。
既然 AND、OR、NOT 都能用 NAND 合成，而這三者已知函數完備，NAND 自然也函數完備。這在工程上意義重大：晶圓廠只要把製程針對單一種 NAND 閘高度優化，就能拼出整顆 CPU，降低設計與製造複雜度。CMOS 製程裡 NAND 的電晶體實作也比 AND（NAND 再串一級反相器）更省、更快。
第二個研究所關注的核心是邏輯化簡(logic minimization)。同一個布林函數可以有無數種等價寫法，但化簡後的式子能用更少的閘、更低的延遲、更省的功耗實現。化簡的代數工具就是布林代數的公理：交換律、結合律、分配律、吸收律 $A+A\cdot B=A$、互補律 $A+\overline{A}=1$ 等，配合 De Morgan 定律反覆改寫。
但手動代數化簡容易出錯且難以保證最優。經典的系統化方法是卡諾圖(Karnaugh map, K-map)：把真值表按格雷碼(Gray code)排列成二維方格，相鄰格只差一個變數，藉由「圈出相鄰的 1」消去變數，得到最簡的積項之和(sum of products)。卡諾圖在變數少（約 4~6 個）時直觀好用；變數一多便不可行，此時改用 Quine–McCluskey 演算法做表格式化簡。
值得指出的是，邏輯化簡的一般問題在計算複雜度上是困難的：求最小的邏輯式等價於電路最小化問題，屬於 $\Sigma_2^p$（多項式階層第二層）的難題，沒有已知的多項式時間最優演算法。因此實務 EDA(電子設計自動化)工具大多採用啟發式(heuristic)，如 Espresso 邏輯最小化器，在可接受時間內求得「夠好」而非「絕對最優」的解。
往更廣處連結：布林函數構成了命題邏輯(propositional logic)的語意基礎，判定一個布林式是否存在使其為真的賦值，就是著名的布林可滿足性問題(SAT)——史上第一個被證明為 NP-complete 的問題（Cook–Levin 定理）。從這個角度看，我們手上這些 AND、OR、NOT 小閘，一端連著實體的矽晶電路，另一端連著計算理論最深的難題之一。從一盞樓梯燈到 P 對 NP，布林邏輯始終是那條貫穿其間的主線。