⚡ 論理回路CPUクエスト
STAGE 4 ― ド・モルガンの法則 ―
クリア 0 / 10
🧭 地図
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行全部を計算して確かめるのが確実だ。真理値表に途中の列を足していくよ。
ABNOT ANOT B(NOT A) OR (NOT B)その NOTA AND B
0011100
0110100
1001100
1100011
うさ美
最後の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 ) と同じものは?

Q2. 「宿題が終わった、かつ、部屋を片付けた」が成り立たない、と同じ意味の文は?

Q3. NOT と OR だけで AND を作るとき、必要な NOT の数は?