邏輯閘與布林代數：用 0 與 1 打造的數位世界
從 AND、OR、NOT 三個小開關，到會算術的電腦核心
邏輯閘在做什麼
打開任何一台電腦、手機、計算機，把它層層拆開、再拆開，最後你會看到一群只懂兩件事的小開關：有電（1） 和 沒電（0）。數位世界裡沒有「大概」「有點亮」這種模糊地帶，所有資訊都被壓縮成這兩個值。而邏輯閘（logic gate） 就是把這些 0 與 1 拿來做運算的最小單位——它像一個只認得「真」與「假」的守門員，根據輸入決定要不要放行。
最基本的三位主角是 AND（且）、OR（或）、NOT（非）。用日常語言就能直接體會：
- AND：要進機房，需要「門禁卡 而且 指紋」兩者都對，缺一不可。
- OR：要觸發警報，「煙霧感測 或 溫度過高」任一成立就響。
- NOT：把「開」變「關」、把「是」變「否」，做相反的事。
整個數位文明，從加法器、記憶體到 CPU，都是用這幾種小積木堆出來的。
真值表：把規則攤開來看
要精準描述一個邏輯閘的行為，最直接的工具是真值表（truth table）：把所有可能的輸入組合與對應輸出全部列出來。設輸入為 $A$、$B$，輸出為 $Y$。
AND 閘（記作 $Y = A \cdot B$，或直接寫 $AB$）：
| $A$ | $B$ | $Y = A \cdot B$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
只有「兩個都是 1」時輸出才為 1，這跟乘法很像（任何數乘以 0 都是 0）。
OR 閘（記作 $Y = A + B$）：只要有一個是 1，輸出就是 1，唯有 $0+0$ 才得 0。NOT 閘（記作 $Y = \overline{A}$）只有一個輸入：$\overline{0}=1$、$\overline{1}=0$。
實務上還有兩個超好用的組合閘：NAND（$\overline{A \cdot B}$，AND 之後取反）與 NOR（$\overline{A + B}$）。它們之所以重要，是因為光用 NAND 一種閘就能組出所有其他邏輯——這個「萬能性」稍後在研究所段會深入。另一個常見的是 XOR（互斥或），記作 $A \oplus B$，兩輸入「不一樣」時才輸出 1，是加法進位運算的核心。
布林代數：邏輯的數學
把這些運算寫成符號、用代數規則化簡，就是 布林代數（Boolean algebra），由十九世紀數學家 George Boole 奠基。它的變數只能取 $0$ 或 $1$，運算只有「且」「或」「非」三種，卻自成一套嚴謹的代數系統。
幾條最常用的定律（這裡 $+$ 代表 OR、$\cdot$ 代表 AND）：
$$ A + 0 = A, \qquad A \cdot 1 = A $$
$$ A + A = A, \qquad A \cdot A = A \quad (\text{冪等律}) $$
$$ A + \overline{A} = 1, \qquad A \cdot \overline{A} = 0 \quad (\text{互補律}) $$
最有名的則是 De Morgan 定律，它告訴你「取反」如何穿過 AND／OR：
$$ \overline{A \cdot B} = \overline{A} + \overline{B}, \qquad \overline{A + B} = \overline{A} \cdot \overline{B} $$
直覺上：「不是『兩者都對』」等於「至少一個不對」；「不是『至少一個對』」等於「兩者都不對」。這條定律是硬體工程師化簡電路、把 AND/OR 轉成全 NAND 的最重要武器。
動手算一題：化簡一個邏輯式
假設某個控制電路的輸出為
$$ Y = A \cdot B + A \cdot \overline{B} $$
它用了 2 個 AND 閘、1 個 NOT 閘、1 個 OR 閘，共 4 個閘。我們來化簡。
第一步，提出共同因子 $A$（分配律，跟一般代數一樣）：
$$ Y = A \cdot (B + \overline{B}) $$
第二步，套互補律 $B + \overline{B} = 1$：
$$ Y = A \cdot 1 $$
第三步，套 $A \cdot 1 = A$：
$$ Y = A $$
結果令人吃驚：原本 4 個閘的電路，輸出其實就等於 $A$ 本身，完全不需要 $B$！這代表可以直接拿掉所有閘、用一條導線取代。驗算：把 $B=0$ 與 $B=1$ 各代回原式，$A\cdot0+A\cdot1 = 0 + A = A$、$A\cdot1+A\cdot0 = A + 0 = A$，兩種情況都得 $A$，化簡正確。這正是布林代數的價值——更少的閘代表更省電、更便宜、更快。
用閘做加法：半加器
邏輯閘真正動人的地方，是它能「算數學」。考慮兩個 1 位元相加：$0+0=0$、$0+1=1$、$1+0=1$、$1+1=10$（二進位的 2，產生進位）。
我們需要兩個輸出：和（Sum） 與 進位（Carry）。觀察真值表會發現：
$$ \text{Sum} = A \oplus B, \qquad \text{Carry} = A \cdot B $$
也就是一個 XOR 閘加一個 AND 閘，就構成了半加器（half adder）。把多個半加器與全加器串起來，就能做八位元、六十四位元的加法——你手機裡的整數運算，骨子裡就是成千上萬個這種閘的組合。從「兩個小開關」到「會算術的機器」，中間的橋梁正是邏輯閘與布林代數。
深入探討（研究所視角）
布林代數的真正威力，在於它是一套抽象代數結構而非僅僅是真值表的速記。形式上，布林代數是一個六元組 $(B, +, \cdot, \overline{\phantom{x}}, 0, 1)$，滿足交換律、結合律、雙向分配律、互補律與恆等律。最小的非平凡例子是兩元素布林代數 $\mathbb{B} = \{0,1\}$，但同樣的公理也描述集合的聯集／交集／補集——這說明邏輯與集合論共享同一個代數骨架。更深刻地，Stone 表示定理指出：任何布林代數都同構於某個拓撲空間上「既開又閉集合」所成的代數，把純代數對象與拓撲幾何對象一一對應起來。
在工程實務上，核心問題是邏輯極小化：給定一個真值表，如何用最少的閘實現它？任何函數都可寫成標準形式——積之和（SOP） 或 和之積（POS）。例如最小項展開把函數寫成所有使輸出為 1 的輸入組合之 OR：
$$ Y = \sum_i m_i $$
但這通常不是最簡的。卡諾圖（Karnaugh map） 利用相鄰格只差一個變數的特性，以視覺方式合併項；其代數依據正是合併律 $A\cdot B + A\cdot\overline{B} = A$。對變數更多的情況，Quine–McCluskey 演算法提供可程式化的系統解法，但已知通用的邏輯極小化（尋找最小布林電路）屬於 NP-hard，因此實務 EDA 工具多採用啟發式（如 Espresso）。
函數完備性（functional completeness） 是另一個理論支柱：一組運算若能組出所有布林函數，即稱完備。$\{\text{AND}, \text{OR}, \text{NOT}\}$ 顯然完備；而由 De Morgan 定律可知 $\{\text{AND}, \text{NOT}\}$ 與 $\{\text{OR}, \text{NOT}\}$ 也各自完備。最驚人的是 NAND 與 NOR 各自單獨即可完備——例如用 NAND 實現 NOT 只需把兩輸入接在一起：$\overline{A\cdot A} = \overline{A}$，再由 NAND 串接做出 AND 與 OR。這即 Sheffer stroke 的結論，也是為何超大型積體電路（VLSI）常以單一 NAND/NOR 製程大量複製來簡化製造。
再往前延伸，布林函數的複雜度理論直通計算理論的核心：電路複雜度（circuit complexity）研究實現某函數所需的閘數與深度，與 $P$ vs. $NP$ 等開放問題密切相關；而 Shannon 在 1938 年指出開關電路與布林代數的對應，正式把這門十九世紀的純數學，變成了整個數位時代的奠基語言。