半加算回路はAND・OR・NOTだけで表現できた。 では、この3種類の回路をすべて用意しなければならないのだろうか。

実は、ANDとNOTを組み合わせたNAND回路だけでもAND・OR・NOTをすべて構成できる。 つまり、半加算回路も理論上はNANDだけで作れる。

本記事では、AND・OR・NOTをNANDで表現したうえで、5個のNANDによる半加算回路を構成する。

NANDによる表現

NANDとは、AかつBを否定するものである。 つまり、

$$ A\mathbin{\mathrm{NAND}}B=\lnot(A\land B) $$

である。

NOTのNAND表現

これを用いて、NOTを考える。

NOTは1つだけ入力を持つ単項演算である。 しかし、NANDは2つの入力を持つ。

どうするか。 同じ入力を2回入れちゃえばよいのだ。

\(A\land A\)とは要するにAであり、 それを否定すれば、単なる否定と同じである。

よって、

$$ \lnot A=A\mathbin{\mathrm{NAND}}A $$

ORのNAND表現

次に、ORはどうすればよいか。

否定によるORとANDの相互変換であるド・モルガンの法則と、 二重否定が使えるかもしれない。

$$ \begin{aligned} A\lor B &=\lnot\lnot(A\lor B)\\ &=\lnot(\lnot A\land\lnot B)\\ &=(\lnot A)\mathbin{\mathrm{NAND}}(\lnot B)\\ &=(A\mathbin{\mathrm{NAND}}A) \mathbin{\mathrm{NAND}}(B\mathbin{\mathrm{NAND}}B) \end{aligned} $$

ANDのNAND表現

同様にANDも行けそうだ。 二重否定をうまく使えるかも。

$$ \begin{aligned} A\land B &=\lnot\lnot(A\land B)\\ &=\lnot(A\mathbin{\mathrm{NAND}}B)\\ &=(A\mathbin{\mathrm{NAND}}B) \mathbin{\mathrm{NAND}}(A\mathbin{\mathrm{NAND}}B) \end{aligned} $$

NANDだけで半加算回路を表現してみる

以上で、NANDによるNOT OR ANDの表現を得た。 これを用いて、半加算回路を表現することができる。

$$ C=(A\mathbin{\mathrm{NAND}}B) \mathbin{\mathrm{NAND}}(A\mathbin{\mathrm{NAND}}B) $$

Sはかなり複雑になる。 そこで、天下り的ではあるが、

$$ \begin{aligned} S &=({A\mathbin{\mathrm{NAND}}(A\mathbin{\mathrm{NAND}}B)}) \\ &\mathbin{\mathrm{NAND}} ({B\mathbin{\mathrm{NAND}}(A\mathbin{\mathrm{NAND}}B)}) \end{aligned} $$

と書けることが分かっているとして話を進めたい。

この天下りの式によると、5個のNAND回路があればよいと分かる。

ここで、途中結果を変数を置くことで簡素に表現する。

$$ D=A\mathbin{\mathrm{NAND}}B $$

すると、

$$ \begin{aligned} C&=D\mathbin{\mathrm{NAND}}D\\ S&=(A\mathbin{\mathrm{NAND}}D) \mathbin{\mathrm{NAND}}(B\mathbin{\mathrm{NAND}}D) \end{aligned} $$

となる。

さらに、

$$ \begin{aligned} E&=A\mathbin{\mathrm{NAND}}D\\ F&=B\mathbin{\mathrm{NAND}}D \end{aligned} $$

とおくと、

$$ S=E\mathbin{\mathrm{NAND}}F $$

よって、半加算回路は以下のようにNANDで表現できる。

  flowchart LR
    A((A))
    B((B))

    D["D = A NAND B"]
    E["E = A NAND D"]
    F["F = B NAND D"]
    C["C = D NAND D"]
    S["S = E NAND F"]

    A --> D
    B --> D

    A --> E
    D --> E

    B --> F
    D --> F

    D --> C
    D --> C

    E --> S
    F --> S

因みに、天下りの式が本当にXORになっているかを検算すると、

$$ \begin{aligned} E &=A\mathbin{\mathrm{NAND}}(A\mathbin{\mathrm{NAND}}B)\\ &=A\mathbin{\mathrm{NAND}}\lnot(A\land B)\\ &=\lnot{A\land(\lnot A\lor\lnot B)}\\ &=\lnot{(A\land\lnot A)\lor(A\land\lnot B)}\\ &=\lnot(A\land\lnot B)\\ &=\lnot A\lor B \end{aligned} $$

$$ \begin{aligned} F &=B\mathbin{\mathrm{NAND}}(A\mathbin{\mathrm{NAND}}B)\\ &=B\mathbin{\mathrm{NAND}}\lnot(A\land B)\\ &=\lnot{B\land(\lnot A\lor\lnot B)}\\ &=\lnot{(B\land\lnot A)\lor(B\land\lnot B)}\\ &=\lnot(B\land\lnot A)\\ &=\lnot B\lor A \end{aligned} $$

であり、ド・モルガンの法則を用いると、

$$ \begin{aligned} S &=E\mathbin{\mathrm{NAND}}F\\ &=\lnot{(\lnot A\lor B)\land(A\lor\lnot B)}\\ &=(A\land\lnot B)\lor(\lnot A\land B)\\ &=A\oplus B \end{aligned} $$

となり、排他的論理和と一致している。