kivantium活動日記

プログラムを使っていろいろやります

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}として書けます。このとき、
 {\displaystyle 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つの組み合わせで書けることが分かりました。

以上より数学的帰納法を用いてNOT・AND・ORだけであらゆるゲートが表現できることが証明できました。

NANDゲートを使ってNOT・AND・ORが作れるので、NANDだけであらゆるゲートが表現できることも分かります。

ここまでで出てきた回路は出力は入力の情報だけで決定することができるという性質を持ちます。
このような回路を組み合わせ回路といいます。

これとは逆に内部状態が出力に影響して、入力だけでは出力が決定しない回路を順序回路といいます。

今日の記事で我々は任意のゲートを作る能力を手に入れましたが、効率的な回路を作れるかどうかはまた別の問題です。次回はより複雑な組み合わせ回路をつくる方法について書きます。