STAGE 4
ド・モルガンの法則
部品を入れ替える
🎯 ミッション
ド・モルガンの法則がなぜ成り立つかを、真理値表で説明できるようになろう。AND を NOT+OR で、OR を NOT+AND で作る2つの課題を解き、確認クイズに全問正解すれば合格。
未達成

ねこ博士
今日は少し意地悪な問題から始めよう。手元に NOT と OR はたくさんあるのに、AND が1つもない。それでも「A かつ B」の回路を作れるだろうか。

うさ美
OR は「1つでもあれば1」で、AND は「全部そろったら1」。性格が逆っぽいので、OR から AND を作れる気がしません。

ねこ博士
正面からだと難しいね。そこで、向きを変えて考えよう。AND の出力が 0 になるのは、どんなときかな。

うさ美
真理値表で AND が 0 なのは、00、01、10 の3行です。共通しているのは……A か B の少なくとも1つが 0 のとき。

ねこ博士
では、「A が 0」を、NOT を使って言い直すと?

うさ美
NOT A が 1、です。同じように「B が 0」は「NOT B が 1」。

ねこ博士
すると、「A か B の少なくとも1つが 0」は、どう言い換えられる?

うさ美
「NOT A が 1」または「NOT B が 1」……「少なくとも1つ」は OR だから、NOT A OR NOT B が 1、ということですか?

ねこ博士
その通り。ここまでで分かったことを式にすると、「AND が 0 のときに 1 になるもの」が作れた。
A AND B が 0 ⇔ A か B の少なくとも1つが 0 ⇔ (NOT A) OR (NOT B) が 1
つまり (NOT A) OR (NOT B) は、A AND B の「反対」になっている

うさ美
欲しいのは AND そのものだから……反対の反対にすればいい。前のステージで、NOT を2回通すと元に戻るとやったので、最後に NOT をもう1つ付けます。

ねこ博士
そう。こうなる。
A AND B = NOT ( (NOT A) OR (NOT B) )
使う部品:NOT が3個、OR が1個。AND は使わない

ねこ博士
本当に正しいかは、4行全部を計算して確かめるのが確実だ。真理値表に途中の列を足していくよ。
| A | B | NOT A | NOT B | (NOT A) OR (NOT B) | その NOT | A AND B |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |

うさ美
最後の2列が4行とも一致しています。

ねこ博士
いまの関係は、19世紀イギリスの数学者オーガスタス・ド・モルガンの名前をとって、ド・モルガンの法則と呼ばれている。ふつうは、両辺に NOT をかけた形で書くことが多い。
ド・モルガンの法則(その1):NOT ( A AND B ) = (NOT A) OR (NOT B)
ド・モルガンの法則(その2):NOT ( A OR B ) = (NOT A) AND (NOT B)

うさ美
その2のほうも、同じ考え方で確かめられますか?

ねこ博士
やってごらん。今度は OR が 0 になるのはどんなときかを考えるといい。

うさ美
OR が 0 になるのは 00 の行だけ、つまり A も B も 0 のとき。「A が 0 かつ B が 0」は「NOT A が 1 かつ NOT B が 1」だから、(NOT A) AND (NOT B) が 1。これが「OR が 0」と同じなので、NOT(A OR B) = (NOT A) AND (NOT B)。その1と同じ形になりました。

ねこ博士
そう。AND と OR を入れ替えて、全部に NOT を付けると、もう一方になる。だから、OR が無くても NOT と AND から OR を作れる。
A OR B = NOT ( (NOT A) AND (NOT B) )

うさ美
ふだんの言葉にも当てはまりますか?

ねこ博士
当てはまるよ。「明日は雨でも風でもない」という文は、「雨が降る OR 風が吹く」の否定だね。法則その2によれば、それは何と同じかな。

うさ美
「雨が降らない」かつ「風が吹かない」。たしかに同じ意味です。逆に「雨が降って、しかも風も吹く、ということはない」は、その1で「雨が降らない、または、風が吹かない」。どちらか片方は外れている、という意味ですね。

ねこ博士
そう。否定すると「かつ」と「または」が入れ替わる。文章を読み違えやすいところだから、プログラムを書くときにも役に立つ。

うさ美
でも、AND があるなら最初から AND を使えばいいのに、どうして作り直すんですか?

ねこ博士
理由は2つある。1つは、工場で作るときに、部品の種類が少ないほど作りやすく、検査もしやすいこと。もう1つは、ゲートの種類によってトランジスタの数が違うから、同じ働きをもっと少ない部品で作れる組み方を探したいこと。今日の考え方を進めると、たった1種類のゲートだけで全部を作ることができる。それが STAGE6 の話だ。その前に、次はもう1つの大事なゲートを作っておこう。
確認クイズ
Q1. NOT ( A OR B ) と同じものは?
正解! ド・モルガンの法則その2。OR が 0 になるのは A も B も 0 のときだけなので、その反対は「NOT A かつ NOT B」。
Q2. 「宿題が終わった、かつ、部屋を片付けた」が成り立たない、と同じ意味の文は?
正解! NOT(A AND B)=(NOT A) OR (NOT B)。どちらか片方でも欠けていれば「両方そろった」は成り立たない。
Q3. NOT と OR だけで AND を作るとき、必要な NOT の数は?
正解! A と B をそれぞれ反転するのに2個、OR の出力をもう一度反転するのに1個。NOT((NOT A) OR (NOT B))。