重點 只有 AND+OR 無法表達「否定」,不構成功能完備集 (functionally complete)。
問有沒有『否定能力』:NOR、NAND 本身即完備;少了 NOT 且無 NAND/NOR 就不行。
逐選項分析
A✕
NOR 本身即為 universal gate,單用 NOR 就能組出 AND/OR/NOT,再加 NOT 當然完備。
B✕
NOR 與 NAND 各自都是 universal gate,任一個即可組出所有邏輯功能,兩者合起來更不用說。
C✕
NAND 本身即 universal gate,可組出 AND/OR/NOT,加上 NOT 亦為完備集合。
D✓ 正確
AND 與 OR 皆為單調 (monotonic) 函數,無論怎麼組合都無法產生「反相」效果,缺少 NOT,無法構成功能完備集。
功能完備 (Functionally Complete) 集合判斷
| 組合 | 是否完備 | 關鍵理由 |
|---|
| {NAND} | ✅ | 單一 universal gate |
| {NOR} | ✅ | 單一 universal gate |
| {AND, OR, NOT} | ✅ | 布林代數基本集 |
| {AND, OR} | ❌ | 缺 NOT,無法反相 |
| {XOR, AND} | ✅ | 可推出 NOT |
考生常直覺「AND+OR 就是布林基本運算」而誤選完備。事實上布林三要素為 AND、OR、NOT,缺 NOT 則任何輸入全 0 時輸出必為 0,無法實現所有布林函數。