以前,この欄でド・モルガンの法則を取り上げました(プログラミングに役立つ 「ド・モルガンの法則」)。今回は,ド・モルガンの続きです。1回ずつ読みきりにしているので,ド・モルガンの続きといっても別の話題です。
ド・モルガンの法則:
NOT (X AND Y) = NOT(X) OR NOT(Y)は,一言で言うと
NOT と AND があれば OR が作れるということです。
さて,以下は,ある日の日経産業新聞をスキャンしたものです(赤線:岩井による)。
フラッシュメモリー欄にNOR型,NAND型とありますが,これらは"OR" や "AND" と響きが似ている感じがします。
実は,
NOR = NOT + ORという意味で,語源は,論理回路の "NAND"と"NOR"です(詳しくは,大容量かつ高速化で普及が進む,「フラッシュメモリー」の原理を探るなどを参照)。
NAND = NOT + AND
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点に尽きます。
2.NAND だけで AND 回路を作ることができる
実際,下記のようにすると作れます。
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 |
時間のある方はやってみてください。暇つぶしのパズル問題になります。