ド・モルガンの法則と論理回路

　以前，この欄でド・モルガンの法則を取り上げました（プログラミングに役立つ 「ド・モルガンの法則」）。今回は，ド・モルガンの続きです。1回ずつ読みきりにしているので，ド・モルガンの続きといっても別の話題です。

　ド・モルガンの法則：

NOT (X AND Y) = NOT(X) OR NOT(Y)

は，一言で言うと

NOT と AND があれば OR が作れる

ということです。

　さて，以下は，ある日の日経産業新聞をスキャンしたものです（赤線：岩井による）。

　フラッシュメモリー欄にNOR型，NAND型とありますが，これらは"OR" や "AND" と響きが似ている感じがします。

　実は，

NOR = NOT + OR
NAND = NOT + AND

という意味で，語源は，論理回路の "NAND"と"NOR"です（詳しくは，大容量かつ高速化で普及が進む，「フラッシュメモリー」の原理を探るなどを参照)。

　ICチップとして販売されている論理回路も，"NAND" や "NOR" の素子がパーツ屋さんで販売されています。

4つのNAND素子が入ったICの例

　というわけで，今回のテーマは，ド･モルガンと論理回路です。

■論理回路の基礎

　まず「1がAから入ってくると0が出力(Out)され，0がAから入ってくると1が出力(Out）される」というものを考えましょう。これを NOT 回路といいます。

NOT 回路

入力	Out
A
0	1
1	0

　次に，「AとBの両方に1が入ってきたときだけ1が出力されて，どちらか一方でも0の場合は，出力も0」というものを考えてみましょう。このような回路を「AND」回路といいます（掛け算のイメージです）。

AND 回路

入力		Out
A	B
0	0	0
	1	0
1	0	0
	1	1

　「AとBのどちらか一方が1だったら1が出力されて，両方とも0の場合は，出力も0」というものも考えてみましょう。これを「OR」回路といいます（足し算のイメージです）。

OR 回路

入力		Out
A	B
0	0	0
	1	1
1	0	1
	1	1

■ NAND回路とは

　NAND 回路は，先に述べたように「NOT + AND」というものです。

NAND 回路

入力		Out
A	B
0	0	1
	1	1
1	0	1
	1	0

　この図の意味は，AND回路の後ろに NOT回路をつないだ（0と1を反転させる）ということです。

=

　NAND回路のメリットは，

1.NAND だけで NOT 回路を作ることができる
2.NAND だけで AND 回路を作ることができる

の2点に尽きます。

　実際，下記のようにすると作れます。

NANDで作ったNOT 回路	NANDで作ったAND回路
NAND回路の入力のAとBを同一の線につなげば実現します。	NAND 回路の先に左で作ったNOT 回路をつなげば実現します。

　で，ド・モルガンの法則に戻ると，

NOT と AND があれば OR が作れる

だったので，上の NAND 回路から OR回路を作れるはずです。

　ド・モルガンの法則で，

NOT(X) OR NOT(Y) = NOT (X AND Y)

なので，入力を A=NOT(X)，B=NOT(Y) とおくと，

A OR B	=	NOT (NOT(A) AND NOT(B))
	=	NOT(A) NAND NOT(B)

となり(論理式で"NAND"という書き方は一般的ではないですが便宜上こう書きました)，これを回路でつなぐと

NANDでORを作った図

が，OR を表すことがわかります。

　実際，

A	NOT(A)	B	NOT(B)	Out =NOT(A) NAND NOT(B)
0	1	0	1	0
		1	0	1
1	0	0	1	1
		1	0	1

　ということで，NOT，AND，OR を 「NAND素子」だけで組むことができました。

　よってNAND素子だけを量産すれば，NOT，AND，ORを作ることができ，つまり任意の論理回路を作ることができることになります。

　よくよく考えてみると，

NOT (A AND B) = A NAND B
NOT (A OR B) = A NOR B

なので，ド・モルガンの法則を見て，NAND/NOR 素子を作ろうと思ったのかもしれません（上述の通り，論理式で"NAND", "NOR" という書き方は一般的ではありません)。

　同じものを量産すれば，規模の経済により安価で安定した品質のものを供給できます。従ってビジネス的にもうまみがあります。

　上記とほぼ同じ方法で，「NOR素子」からNOT，OR，AND を作ることができます。

NOR 回路

入力		Out
A	B
0	0	1
	1	0
1	0	0
	1	0

　時間のある方はやってみてください。暇つぶしのパズル問題になります。