組合邏輯：輸出只看當下的數位積木
從邏輯閘、真值表到加法器、多工器與解碼器，看懂「過目即忘」的電路如何運算。
什麼是組合邏輯：輸出只看當下
數位電路大致分成兩大家族：一種會「記得」過去發生過什麼，另一種「過目即忘」。組合邏輯（combinational logic）屬於後者——它的輸出只由當下這一刻的輸入決定，與之前的歷史毫無關係。
打個比方：一台自動販賣機的找零顯示器，只要你按下的鈕和投入的金額確定了，螢幕上該找多少零錢就唯一確定，不管你昨天買過幾罐飲料。這就是組合邏輯的精神：同樣的輸入，永遠給出同樣的輸出。相對地，會「記得狀態」的電路（如計數器、記憶體）屬於另一個家族——循序邏輯（sequential logic），那是後續主題。
組合邏輯由最基本的邏輯閘（gate）堆疊而成：AND、OR、NOT、XOR 等。它們各自實現一個布林函數，例如兩輸入 AND 閘輸出 $Y = A \cdot B$，只有兩個輸入皆為 1 時輸出才是 1。把這些閘像積木一樣連接起來，就能實現任意複雜的「輸入到輸出」的對應關係。
用真值表與布林代數描述行為
要完整描述一個組合電路，最直接的工具是真值表（truth table）：把所有可能的輸入組合都列出來，並寫下對應的輸出。$n$ 個輸入就有 $2^n$ 種組合。
以一個經典的半加器（half adder）為例，它把兩個一位元的二進位數 $A$、$B$ 相加，輸出「和」$S$ 與「進位」$C$：
| $A$ | $B$ | $S$（和） | $C$（進位） |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
觀察這張表可以「讀」出布林式：和 $S$ 在兩輸入不同時為 1，正是 XOR；進位 $C$ 只在兩輸入皆為 1 時出現，正是 AND：
$$ S = A \oplus B, \qquad C = A \cdot B $$
這就是組合邏輯的工作流程：先定義行為（真值表）→ 再導出布林式 → 最後用邏輯閘實現。
帶數字的小範例：全加器算 1+1+進位
半加器只能加兩個位元，但實際做多位元加法時，每一位還要承接前一位送來的進位。能同時處理三個輸入（$A$、$B$、進位輸入 $C_{in}$）的電路稱為全加器（full adder），輸出為和 $S$ 與進位輸出 $C_{out}$：
$$ S = A \oplus B \oplus C_{in} $$ $$ C_{out} = A\cdot B + C_{in}\cdot(A \oplus B) $$
我們用具體數字驗算：設 $A = 1$、$B = 1$、$C_{in} = 1$（相當於計算 $1+1+1$）。
先算和：
$$ S = 1 \oplus 1 \oplus 1 = (1 \oplus 1) \oplus 1 = 0 \oplus 1 = 1 $$
再算進位：先算 $A \oplus B = 1 \oplus 1 = 0$，於是
$$ C_{out} = (1\cdot 1) + 1\cdot 0 = 1 + 0 = 1 $$
結果是 $C_{out}S = 10_2$，也就是十進位的 $2$——完全正確（$1+1+1=2$）。把多個全加器串起來、讓前一級的 $C_{out}$ 接到下一級的 $C_{in}$，就構成了能加任意位元數的漣波進位加法器（ripple-carry adder），這正是 CPU 算術單元的雛形。
三個明星元件：多工器、解碼器、加法器
組合邏輯有幾個反覆出現的「標準零件」，工程師會直接拿來當積木用。
多工器（multiplexer, MUX）像一個「電子選擇開關」。它有多條資料輸入、一組選擇線，依選擇線的值把其中一條輸入「接通」到輸出。一個 2 對 1 多工器的布林式為：
$$ Y = \overline{S}\cdot D_0 + S\cdot D_1 $$
當選擇線 $S=0$ 時輸出 $D_0$，$S=1$ 時輸出 $D_1$。$n$ 條選擇線可以從 $2^n$ 條輸入中挑一條。資料匯流排、記憶體定址都靠它切換。
解碼器（decoder）做相反的事：把 $n$ 位元的編碼「翻譯」成 $2^n$ 條輸出中唯一被點亮的那一條。例如 2 對 4 解碼器，輸入 $10_2$ 時只有第 2 號輸出為 1，其餘為 0。它常用來做記憶體的位址選擇、七段顯示器的驅動。
加法器前面已經談過，是算術運算的核心。這三者加上比較器、編碼器，幾乎能拼出任何資料處理路徑。
高中 → 大學的銜接
高中與資訊概論課程通常停在「認識邏輯閘」與「畫簡單真值表」。大學的數位邏輯設計會進一步教你化簡：同一個布林函數可以有許多等價的閘級實現，但用的閘越少、層數越淺，電路越省成本、越快。常用工具是卡諾圖（Karnaugh map）與布林代數定理（如狄摩根定律 $\overline{A\cdot B} = \overline{A} + \overline{B}$）。再往上，組合邏輯會與循序邏輯結合，構成完整的數位系統。
深入探討（研究所視角）
把組合邏輯放到嚴謹的理論框架下，第一個關鍵結果是功能完備性（functional completeness）：任何布林函數 $f:\{0,1\}^n \to \{0,1\}$ 都能僅用 $\{\text{AND}, \text{OR}, \text{NOT}\}$ 實現，因為任意函數都可寫成主析取範式（sum of products）——把真值表中所有輸出為 1 的列各寫成一個最小項（minterm）再相或。更強的是，單一閘 NAND 或 NOR 各自即可構成完備集：例如 $\overline{A} = \overline{A\cdot A}$、$A\cdot B = \overline{\overline{A\cdot B}}$，這也是為何 CMOS 製程偏好以 NAND/NOR 為基本單元。
化簡問題本身具有深刻的計算複雜度意涵。尋找最小兩層 SOP 實現等價於覆蓋所有最小項的最少質含項集合，這是一個集合覆蓋問題，屬 NP-hard。卡諾圖只在變數少時可行；工業界改用 Quine–McCluskey 演算法系統地列出所有質含項（prime implicants），再解質含項表。Shannon 展開 $f = x\cdot f_{x=1} + \overline{x}\cdot f_{x=0}$ 則是遞迴分解的理論基礎，也直接導出二元決策圖（Binary Decision Diagram, BDD）這種以圖結構緊湊表示布林函數的資料結構，是現代邏輯合成與形式驗證的支柱。
在物理實現層面，「輸出只看當下輸入」是理想化假設。真實閘有傳播延遲，不同路徑的延遲差會造成競爭與冒險（race and hazard）：輸入變化的瞬間，輸出可能出現短暫的錯誤脈衝（glitch）。靜態冒險可藉由在卡諾圖上加入冗餘的重疊質含項來消除——這說明「邏輯上等價」未必「時序上安全」。此外，組合電路不能含有迴授迴路，否則會退化成不穩定的振盪器或隱含記憶；嚴格而言，一個組合網路對應的是有向無環圖（DAG），其最長路徑（critical path）的延遲決定了整個電路能跑多快的時脈上限——這正是組合邏輯與循序系統時序分析的交會點。