• BPnet
  • ビジネス
  • IT
  • テクノロジー
  • 医療
  • 建設・不動産
  • TRENDY
  • WOMAN
  • ショッピング
  • 転職
  • ナショジオ
  • 日経電子版
  • PR

  • PR

  • PR

  • PR

  • PR

岩井 慶一郎のIT的数学入門

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

2008/03/21 ITpro

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

 ド・モルガンの法則:

NOT (X AND Y) = NOT(X) OR NOT(Y)
は,一言で言うと
NOT と AND があれば OR が作れる
ということです。

 さて,以下は,ある日の日経産業新聞をスキャンしたものです(赤線:岩井による)。

NAND と NOR

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

 実は,

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

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

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

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

■論理回路の基礎

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

NOT 回路

入力 Out NOT回路
A
01
10

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

AND 回路

入力OutAND回路
AB
000
10
100
11

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

OR 回路

入力OutOR回路
AB
000
11
101
11

■ NAND回路とは

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

NAND 回路

入力OutNAND回路
AB
001
11
101
10

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

NAND回路 = AND+NOT回路

 NAND回路のメリットは,

1.NAND だけで NOT 回路を作ることができる
2.NAND だけで AND 回路を作ることができる
の2点に尽きます。

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

NANDで作ったNOT 回路NANDで作ったAND回路
NANDからNOTNANDから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を作った図
NANDからORを作る

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

 実際,

ANOT(A)BNOT(B)Out
=NOT(A) NAND NOT(B)
01010
101
10011
101

 ということで,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 回路

入力OutNAND回路
AB
001
10
100
10

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

あなたにお薦め

連載新着

連載目次を見る

今のおすすめ記事

  • 【記者の眼】

    日本人SEが外資系ITに大量流出、これでいいのか?

     日本ハムの二刀流こと、大谷翔平選手のメジャー移籍が話題になっている。23歳という年齢は早すぎる気もするが、メジャーを熱望しながらプロ野球界にとどまった経緯を考えれば、当然の流れといえそうだ。もはや「なぜお前もメジャーに行くのか?」と嘆くよりも、大舞台での雄姿を早く見たいのではないだろうか。

ITpro SPECIALPR

What’s New!

経営

アプリケーション/DB/ミドルウエア

クラウド

運用管理

設計/開発

サーバー/ストレージ

クライアント/OA機器

ネットワーク/通信サービス

セキュリティ

もっと見る