為什麼 $\XOR$, $\XNOR$, $\AND$ 與 $\OR$ 不是通用邏輯閘？

有學過一點程式的人應該對邏輯運算 $\AND$, $\OR$, $\NOT$ 都不陌生，許多程式還有支援 $\XOR$。其中 $\AND$, $\OR$, $\XOR$ 可視為從 $\{0,1\}^2 = \{(0,0),(0,1),(1,0), (1,1)\}$ 打到 $\{0,1\}$ 的函數。比如 $\AND$ 的定義就是 $$\AND(0,0)=0,\ \AND(0,1)=0,\ \AND(1,0)=0,\ \AND(1,1)=1。$$ 類似地，$\OR$ 在 $(0,0),(0,1),(1,0),(1,1)$ 上的取值依序為 $0,1,1,1$，$\XOR$ 為 $0,1,1,0$。 而 $\NOT$ 是從 $\{0,1\}$ 打到 $\{0,1\}$ 的函數，其作用為 $\NOT(0)=1$, $\NOT(1)=0$。 我們可以把這些運算想成一個一個閘門，稱為「邏輯閘」，變數流進閘門，再流出作用後的值。比如 $\AND$ 可以畫成像下面這樣：

其中 $A,B$ 是輸入，分別都可為 $0$ 或 $1$，而 $C=\AND(A,B)$ 是輸出。下面我們稱這種輸入兩個值得出一個值的邏輯閘為「二進一出」。如果是 $\NOT$，那就只有「一進一出」。除了上面提到的幾個邏輯閘，另外還有三個常用的二進一出邏輯閘：$\NAND$, $\NOR$, $\XNOR$，它們分別為 $\AND$, $\OR$ 與 $\XOR$ 的「否定」，等同於做完 $\AND$, $\OR$, $\XOR$ 後再做 $\NOT$。請注意，我們用一個正方形（或長方形）裡面寫 $\AND$, $\OR$, $\XOR$… 表示要執行哪個運算，這只是方便。其實這些常用的邏輯閘都有自己的慣用圖示，網路上很容易搜尋到，這裡就不貼出來了。

我們可以用許多邏輯閘組成「邏輯電路」，比如下面是一個「純粹使用 $\XOR$」所組成的邏輯電路：

所謂用邏輯閘「組成」電路，這個「組成」的規則為何我想無需過度描述，看圖例就很容易理解。但有兩件默認可以做的事，在許多資料中常常沒有講明（我指的是理想情形，現實中想必會有更多限制），一個是可以在某些地方直接加入 $0$ 或 $1$ 參與運算，另外一個就是可以進行「複製」，比如上圖中一開始 $A$ 就先複製成兩份，其中一個走下面那條路與 $B$ 進行了 $\XOR$ 之後，所得出來的值又複製成三份往後走。

像上面這樣，我們可以用邏輯閘組成各式各樣的邏輯電路，一般來說當然也不用侷限於「只用一種邏輯閘」這樣的規則。另外，雖然上圖的例子總地來看仍然是二進一出：輸入 $A,B$，輸出 $f(A,B)$，不過顯然我們也可以隨意地構造出「$m$ 進 $n$ 出」的電路。有一個定理是說：我們可以用開頭所提到的那些常用邏輯閘來實現任意從 $\{0,1\}^m$ 打到 $\{0,1\}^n$ 的函數。這證明雖然不深奧，但也不是三兩句話可以解決，這裡我們就不去管它。

接著要解釋「通用邏輯閘」。一個邏輯閘被稱為通用邏輯閘，意思是只要使用這種邏輯閘就可以實現所有其他的邏輯閘（也因此只要用它就能實現所有從 $\{0,1\}^m$ 打到 $\{0,1\}^n$ 的函數）。何謂「實現其他的邏輯閘」？比如上面圖示的那個 $f(A,B)$，如果它代入 $(A,B)=(0,0),(0,1),(1,0),(1,1)$ 所得到的輸出值都與 $\AND$ 一樣，那我們就成功地「只用 $\XOR$ 實現 $\AND$」了。（這可能嗎？你可以自己代代看，不過很快我們就會回答這個問題。）又比如不難看出 $\XOR(1,A)=\NOT(A)$，或者 $\NAND(A,A) = \NOT(A)$，所以 $\XOR$ 與 $\NAND$ 都可以用來實現 $\NOT$。

所以，有誰是通用邏輯閘嗎？當然我們可以先排除 $\NOT$，這傢伙是一進一出，變不出什麼花樣。所以重點在於那些常用的二進一出邏輯閘，有沒有人是通用邏輯閘。確實是有的，一個"眾所周知"的事實是：

$\NAND$ 與 $\NOR$ 是通用邏輯閘，而 $\XOR$, $\AND$, $\OR$, $\XNOR$ 都不是。

要證明 $\NAND$ 與 $\NOR$ 是通用邏輯閘很單純，只要直接展示給你看它們怎麼生出其他的邏輯閘就行了。這可以參考 Wikipedia 的 Logic gate 裡面的 Universal logic gates 的部分。當然那些構造方式都是非常聰明的，要從無到有想出來並不容易，但一旦造出來了就很容易明白。像這樣，你問一件事可不可能，我直接做出來給你看，那就是可能了，這種構造性證明很容易理解。相對來說，很少看到有人清楚地解釋為什麼 $\XOR$, $\AND$, $\OR$, $\XNOR$ 不是通用邏輯閘。以 $\XOR$ 為例，為什麼它不通用？這表示至少存在一種邏輯閘無法用 $\XOR$ 構造出來。這種「某事情不可能」的證明，通常就比較不直覺。因為你做不到，未必是不可能，也許只是努力還不夠。而且用邏輯閘構造邏輯電路的方式有無限多種，所以也無法使用窮舉法。必須想出某種「道理」，從根本上來否定我們要問的事情的可能性才行。一個常用的手法就是想辦法證明「所有使用這種邏輯閘構造出來的邏輯電路都一定滿足某種性質」，而這個「性質」就自然地給出了一個限制。對於 $\XOR$ 不是通用邏輯閘這件事，我第一次聽到的時候就聽說是要觀察「$0$ 與 $1$ 的數量的奇偶性」這件事，但這具體到底是什麼意思我一直搞不清楚，直到看到這個討論才終於明白。主要就是因為 $\XOR$ 有下述性質：

若 $a_1,a_2,a_3,a_4$ 四個數中有偶數個 $0$，偶數個 $1$，且 $b_1,b_2,b_3,b_4$ 亦然，則 $\XOR(a_1,b_1),\XOR(a_2,b_2),\XOR(a_3,b_3),\XOR(a_4,b_4)$ 中同樣有偶數個 $0$，偶數個 $1$。

這個性質可以直接檢查，這裡就不詳細討論（是否有什麼比較聰明的檢查方式我也沒細想，反正最慘就是把所有可能的情形都列出來）。從這個性質出發，我們即可推論出：「任何一個純粹由 $\XOR$ 所組成的二進一出邏輯電路 $f(A,B)$，都會滿足 $f(0,0)$, $f(0,1)$, $f(1,0)$, $f(1,1)$ 四個數中有偶數個 $0$，偶數個 $1$。」事實上，在這樣的電路中的「任何一處」，都會滿足下述的性質：

把 $(A,B)=(0,0),(0,1),(1,0),(1,1)$ 四種輸入在該處所對應的數值記作 $x_1,x_2,x_3,x_4$，則 $x_1\sim x_4$ 這四個數中有偶數個 $0$，偶數個 $1$。

為什麼會這樣？我們不做太形式化的證明，用「觀察」應該就可以充分地說服自己。首先讓我們把上述性質稱為「（在該處）保持偶數」，然後我們再重貼一次前面那個電路圖：

現在讓我們來好好觀察一下。一開始上面的 $1$ 與 $A$ 通過 $\XOR$ 之後的值，是否「保持偶數」？是的，因為對應 $(A,B)=(0,0),(0,1),(1,0),(1,1)$，得到的值為 $\XOR(1,0)=1$, $\XOR(1,0)=1$, $\XOR(1,1)=0$, $\XOR(1,1)=0$（請注意上面對「保持偶數」的描述！雖然這一步只有 $1$ 與 $A$ 交互作用，但還是要把 $(A,B)$ 的所有可能都一起看）。類似這樣，接著再觀察，下面 $A$ 與 $B$ 經過 $\XOR$ 產生的值，是否也「保持偶數」？然後，如果在電路的某處有「保持偶數」，往後走，遇到另一個「保持偶數」的地方來的值，進行 $\XOR$，是否仍然「保持偶數」？思考一下，會發現這些問題的答案都是「是」。這樣一路到最後，輸出的 $f(A,B)$ 自然也「保持偶數」。這就限制了 $f(A,B)$ 的可能性，比如說，它就不可能是 $\AND$。

使用上面這個聰明的論證方式，我們也可以證明 $\XNOR$ 不是通用邏輯閘，但對於 $\AND$ 與 $\OR$ 就行不通了，因為它們並沒有「保持偶數」的特性。那為什麼它們不通用呢？$\NAND$ 與 $\NOR$ 不過就是它們的相反，卻是通用的，乍看之下這真的有點奇妙。事實上，$\AND$ 與 $\OR$ 不是通用邏輯閘，都有更簡單（知道了就很簡單，不知道時根本想不到）的看法。對於單純使用 $\AND$ 構造的二進一出電路，只要注意到下面這件事即可：無論構造的電路如何複雜，輸入值 $A,B$ 中只要有一個是 $0$，最終輸出結果必為 $0$。而對於單純使用 $\OR$ 構造的電路則正相反：輸入值只要有一個人是 $1$，最終結果必為 $1$。這樣的特性顯然使得 $\AND$ 與 $\OR$ 不可能是通用邏輯閘。這樣，我們就把全部的問題都解決了。