NANDがあればなんでもできるその2

この記事はkivantium Advent Calendarの2日目です。

昨日はトランジスタを使ってNANDゲートを作る方法を解説しました。
今日はNANDゲートを使っていろんなゲートを作っていきます。

基本的なゲート

ゲートにはNANDゲートの他にも何種類もあります。

よく使う有名なゲートには記号があります。NANDゲートの記号は

です。
NANDの真理値表を再掲します。

A	B	Q
0	0	1
0	1	1
1	0	1
1	1	0

NOTゲート

NOTゲートは入力が1つ、出力が1つで、入力と出力の値が逆になるようなゲートです。NOTゲートの記号は

です。
真理値表は、

A	Q
0	1
1	0

です。
NOTゲートはNANDゲートを

のようにつなぐと作ることができます。

ANDゲート

ANDゲートは入力が2つ、出力が1つで、2本の入力が両方とも1のときだけ1を出力するようなゲートです。ANDゲートの記号は

です。

真理値表は

A	B	Q
0	0	0
0	1	0
1	0	0
1	1	1

です。これをNANDゲートで表現するには次のようにつなぎます。

そもそもNANDゲートというのはNOT ANDという意味なので、NANDゲートの記号もANDゲートにNOTゲートをつないだ絵になっています（ゲートの入出力に丸をつけるとNOTを表します）。
ここで作ったゲートはNANDゲートにNOTをつないでいるので、ANDに対して2回NOTを行い、結果としてANDができたと解釈することもできます。

ORゲート

ORゲートは入力が2つ、出力が1つで、入力に1が存在したら1を出力するようなゲートです。記号は

です。

真理値表は

A	B	Q
0	0	0
0	1	1
1	0	1
1	1	1

です。これをNANDゲートで表現するには次のようにつなぎます。

完全性の証明

ここまででNANDゲートだけからNOT・AND・ORゲートが作れることを確認しました。
次にどんなゲートでもNOT・AND・ORの組み合わせで作れることを証明します。

まずは記法を準備します。
入力 $A, B$ が与えられた時に $A$ の否定は $\overline{A}$ 、 $A, B$ のANDは $A\bullet B$ 、 $A, B$ のORは $A+B$ のように書くことにします。これらの記法を組み合わせることで、例えばNANDは $\overline{A\bullet B}$ のように書くことができます。

ここで証明したいのは、 $N$ 入力 $M$ 出力の任意のゲートはNOT・AND・ORの組み合わせで書けるということです。
まず、 $N$ 入力 $M$ 出力のゲートは $N$ 入力 $1$ 出力のゲートを $M$ 個並べることで作れるので、NOT・AND・ORだけで $N$ 入力 $1$ 出力の任意のゲートを表現できることを示せば $N$ 入力 $M$ 出力のゲートが作れることが分かります。
（質問があったので図を追加しました）

$N$ 入力 $1$ 出力のゲートがNOT・AND・ORの組み合わせで書けることは数学的帰納法で証明します。

$N=1$ の場合を考えます。1入力1出力のゲートとして考えられる真理値表は、

A	Q
0	0
1	0

と

A	Q
0	0
1	1

と

A	Q
0	1
1	0

と

A	Q
0	1
1	1

の4種類しかありえませんが、それぞれ

$A\bullet \overline{A}$
$A$
$\overline{A}$
$A + \overline{A}$

とすれば作れるので、 $1$ 入力 $1$ 出力のゲートはNOT・AND・ORの組み合わせで書けます。

次に、 $k$ 入力の任意のゲートが全てNOT・AND・ORの組み合わせで書けると仮定します。
このとき、 $k+1$ 入力のゲート $G_{k+1}$ は、入力 $A_{k+1}$ を $0$ に固定すると、 $k$ 入力のあるゲート $G_{0k}$ とみなせます。
また、 $A_{k+1}$ を $1$ に固定したときは $k$ 入力のあるゲート $G_{1k}$ として書けます。このとき、
$G_{k+1} = A_{k+1} \bullet G_{1k} + \overline{A_{k+1}} \bullet G_{0k}$
が成り立ちます。（ $A_{k+1}$ が $1$ のとき後半は常に $0$ なので出力は $G_{1k}$ と一致、 $A_{k+1}$ が $0$ のとき前半は常に $0$ なので出力は $G_{0k}$ と一致する）
$G_{0k}, G_{1k}$ はNOT・AND・ORの組み合わせで書けることが分かっているので、 $G_{k+1}$ もこの3つの組み合わせで書けます。
従って、 $K+1$ 入力 $1$ 出力の任意のゲートが3つの組み合わせで書けることが分かりました。