STAGE 5
XOR
「違う」を見分ける
🎯 ミッション
XOR の意味と真理値表を説明できるようになろう。XOR を使う・XOR を AND/OR/NOT で作る・2ビットの数の一致を判定する、の3つの課題を解き、確認クイズに全問正解すれば合格。
未達成

ねこ博士
STAGE3 で、「コーヒーまたは紅茶」の「または」は、ふつう「どちらか一方だけ」という意味だ、という話をしたね。今日はその「どちらか一方だけ」のゲートを作る。家の階段の電灯を思い出してほしい。1階と2階の両方にスイッチがあるよね。

うさ美
あります。1階で点けて、2階で消せる。どちらのスイッチを動かしても、電灯の状態が切り替わります。

ねこ博士
2つのスイッチの向きを A、B(それぞれ 0 か 1)として、電灯が点く組み合わせを表にしてみよう。最初、両方 0 のとき消えているとする。

うさ美
00 で消えている。どちらか1つを動かすと点くから、01 と 10 は点灯。そこからもう片方も動かすと切り替わって消えるので、11 は消灯。点くのは「A と B が違うとき」です。
| A | B | OR | XOR |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 |

ねこ博士
この「2つの入力が違うときだけ 1」のゲートを XOR(エックスオア)と呼ぶ。exclusive OR(排他的な OR)を縮めた名前で、日本語では排他的論理和という。「排他的」は「ほかを締め出す」という意味。両方 1 の場合を締め出した OR、ということだね。

ねこ博士
では、XOR が無いときに、AND・OR・NOT から作れるかを考えよう。OR と XOR の表を見比べると、違うのはどの行かな。

うさ美
11 の行だけです。OR は 1、XOR は 0。それ以外の3行は同じ。

ねこ博士
そう。だから「OR だけれど、11 の行だけは 0 にしたい」。11 の行でだけ 1 になるゲートは何だった?

うさ美
AND です。……その反対の NOT AND は、11 の行でだけ 0 で、ほかは 1。

ねこ博士
その2つ、OR の出力と NOT AND の出力を、どう組み合わせればいい?

うさ美
OR が 1 で、しかも NOT AND も 1 のときだけ 1 にしたいから、AND でまとめます。11 の行は NOT AND が 0 なので消える。00 の行は OR が 0 なので消える。残るのは 01 と 10。
A XOR B = ( A OR B ) AND NOT ( A AND B )
「少なくとも1つは 1」かつ「両方 1 ではない」=「ちょうど1つだけ 1」
使う部品:OR 1個、AND 2個、NOT 1個

うさ美
「ちょうど1つだけ」なら、別の言い方もできませんか。「A だけが 1」または「B だけが 1」。

ねこ博士
できるね。「A だけが 1」はどう書ける?

うさ美
A AND (NOT B)。「B だけが 1」は (NOT A) AND B。その2つの OR です。
A XOR B = ( A AND (NOT B) ) OR ( (NOT A) AND B )
こちらは NOT 2個、AND 2個、OR 1個。同じ働きでも、組み方は1通りではない

ねこ博士
XOR は「違うかどうか」の判定器だから、反対の NOT XOR は「同じかどうか」の判定器になる。これを使うと、2つの数が等しいかを調べられる。数 A を2ビット A1 A0、数 B を B1 B0 で表すとき、A と B が等しいのはどんなときかな。

うさ美
上の桁どうしが同じで、かつ、下の桁どうしも同じとき。だから「NOT (A1 XOR B1)」と「NOT (A0 XOR B0)」の AND です。
等しい EQ = NOT ( A1 XOR B1 ) AND NOT ( A0 XOR B0 )
ビット数が増えても、桁ごとに「同じか」を調べて全部を AND でまとめればよい

ねこ博士
CPU は「この2つの値は等しいか」をしょっちゅう調べている。プログラムの「もし x が 5 なら」という判断は、最後はこの回路で答えが出るんだ。

ねこ博士
最後に、XOR が大活躍する場面を1つ見せておこう。2進数の1桁どうしの足し算を、4通り全部書いてごらん。

うさ美
0+0=0、0+1=1、1+0=1、1+1 は2だから、2進数では 10 です。

ねこ博士
その答えの1の位だけを並べると?

うさ美
0、1、1、0。……XOR の表と同じです。そして 1+1 のときだけ、上の位に 1 が出てくる。これは AND の表と同じ。

ねこ博士
そう。足し算の1の位は XOR、繰り上がりは AND で作れる。足し算の回路は、ここまでの部品で組めるということだ。それは STAGE7 で組み立てる。その前に次のステージで、すべての部品をたった1種類から作る話をしよう。
確認クイズ
Q1. XOR の出力が 1 になるのは?
正解! XOR は「ちょうど1つだけ 1」。両方 1 の行を締め出した OR、と覚えてもよい。
Q2. 階段の電灯で、両方のスイッチが 1 のとき電灯が消えているのはなぜ?
正解! どちらのスイッチを動かしても状態が反転する。00 から2回反転すると元の「消灯」。これがちょうど XOR の性質。
Q3. 2進数の1桁どうしの足し算で、答えの「1の位」と同じ真理値表を持つゲートは?
正解! 0+0=0、0+1=1、1+0=1、1+1=10。1の位は 0,1,1,0 で XOR と同じ。繰り上がり(0,0,0,1)は AND と同じ。