3値以上の排他的論理和の考え方

本日の内容

論理演算というとORやらANDやらがありますが、その中でも異彩を放つのが排他的論理和であるXOR（あるいはEXOR）です。今回は、その3値以上のXORの考え方についてです。

XOR

XOR/排他的論理和は、論理演算の一種です。具体的には、2値の入力のうち、どちらか片方だけが真（1）のときに真を返すというものになります。

こう聞くと、論理和と同じように聞こえますが、特殊なのは、2値の入力の両方が真だったときです。入力と出力を見てみます。

論理記号

記号としてよく使われるのは⊕あるいは⊻。A XOR Bの場合、A⊕BあるいはA⊻Bと表現されます。今回は、⊕で統一します。

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

これを見てもらったらわかると思いますが、2値の両方が真であった場合も偽となります。これがXORとORの違いです。

排他的論理和のベン図

3値以上の場合

XORは2値の場合、計算が非常に簡単です。しかし、3値になった時に少しややこしいことになります。

では、具体的に見ていきましょう。

A	B	C	A⊕B⊕C
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

3値以上のORやANDが基本的に、2値までと同じ意味を持つのに対して、3値以上のXORはやや説明が面倒です。

ただ、こう考えれば楽です。A⊕B⊕Cは、A⊕BとCの排他的論理和と考えます。

A	B	A⊕B	C	(A⊕B)⊕C
0	0	0	0	0
0	0	0	1	1
0	1	1	0	1
0	1	1	1	0
1	0	1	0	1
1	0	1	1	0
1	1	0	0	0
1	1	0	1	1

こうすればわかりやすいかもしれませんね。

ちなみに、この3値のXORを見ていただければわかるかもしれませんが、A/B/Cと3値入力のうち、真になる入力の個数が奇数個であるときに1を出力していることがおわかりいただけるかもしれません。

そのため、XORはソフトウェアのプログラムにおいては、パリティに用いられることがありますね。

ちなみに3値のXORのベン図は以下の通りとなります。

3値の排他的論理和のベン図

では、これを超える場合はどうでしょうか。実は、XORは性質上、入力値が増えたとしても、真の個数が奇数のときに真を、偶数あるいは0のときに偽を返します。

A	B	C	D	A⊕B	C⊕D	(A⊕B)⊕(C⊕D)	真の個数
0	0	0	0	0	0	0	0
0	0	0	1	0	1	1	1
0	0	1	0	0	1	1	1
0	0	1	1	0	0	0	2
0	1	0	0	1	0	1	1
0	1	0	1	1	1	0	2
0	1	1	0	1	1	0	2
0	1	1	1	1	0	1	3
1	0	0	0	1	0	1	1
1	0	0	1	1	1	0	2
1	0	1	0	1	1	0	2
1	0	1	1	1	0	1	3
1	1	0	0	0	0	0	2
1	1	0	1	0	1	1	3
1	1	1	0	0	1	1	3
1	1	1	1	0	0	0	4

よくよく考えれば、2値入力の場合も、どちらか片方しか真でない時、つまり真が1個の時だけ真を返し、0または2のときは偽でしたね。そういうことです。

〆

電子工学では、3値以上の入力を聞くことはないと思いますが、情報系だともしかしたら聞くかもしれませんね。特に情報理論の分野だと。

XORパリティを使えば、パリティビットを適切に設定するというのは大前提かもしれませんが、誤りビットを検出できるはずです。