6 / 63 · 概念

通用邏輯閘：只用 NAND 組成電路

透過構造證明 NAND、NOR 的功能完備性，並驗證 XOR 的中間訊號。

「所有電路」的適用範圍

只用 NAND 就能構成 NOT、AND、OR，任何有限輸入的組合邏輯函數都能用這些運算表示。在這個意義下，NAND 是通用邏輯閘^{通用邏輯閘可僅靠重複使用同一種類的閘來實現任意布林函數。NAND 與 NOR 是典型例子。}，並不表示一個 NAND 也能解決儲存、時脈、配線與電源條件。

\overline a=\operatorname{NAND}(a,a)

ab=\operatorname{NAND}(n,n),\quad n=\operatorname{NAND}(a,b)

a+b=\operatorname{NAND}(\operatorname{NAND}(a,a),\operatorname{NAND}(b,b))

將同一輸入接到 NAND 的兩個端點便得到 NOT。AND 是在 NAND 後再反相^{反相是將 0 變為 1、1 變為 0 的 NOT 運算。公式上方的橫線表示對線下的整個運算式套用 NOT。詳細內容}一次，OR 則運用德摩根定律^{德摩根定律：AND 結果的反相，等於各輸入先反相再做 OR；OR 結果的反相，等於各輸入先反相再做 AND。詳細內容}。NOR 也可合併輸入形成 NOT，並用類似構造證明通用性。

用四個 NAND 組成 XOR

依下列順序定義中間訊號。

n_0=\overline{ab},\quad n_1=\overline{a n_0},\quad n_2=\overline{b n_0},\quad y=\overline{n_1n_2}

a	b	n0	n1	n2	y
0	0	1	1	1	0
0	1	1	1	0	1
1	0	1	0	1	1
1	1	0	1	1	0

以共用中間訊號建立 XOR

第一個 NAND: n0 = NAND(a, b)
中間兩個 NAND: n1 = NAND(a, n0); n2 = NAND(b, n0)
最後一個 NAND: y = NAND(n1, n2)

第二層的兩個 NAND 是並聯的。雖然共有 4 個閘，最長邏輯路徑只有 3 層。在每個閘最大延遲 2 ns 的簡化模型中，最大路徑總和為 6 ns。實際負載與配線造成的差異需另外考慮。

將四個 NAND 的結果與 XOR 比對

XOR · 真值表
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

親自填完表格四列，再與上方 XOR 比較。功能等價是比較所有輸入對應的輸出，並不是宣稱閘數或傳播延遲^{傳播延遲是輸入改變後，輸出穩定至正確值所需的時間。邏輯式是否等價與時間特性是兩個不同問題。詳細內容}相同。

自己試試看

寫出只用 NOR 構成 NOT 與 AND 的算式。AND 結構共有幾個邏輯閘？最長路徑有幾層？

查看解說

NOT a=NOR(a,a)。AND=NOR(NOR(a,a), NOR(b,b))。兩個輸入反相閘加上最後一個 NOR，共 3 個閘；最長路徑為 2 層。