今まで2入力固定だと思ってました…よく考えると、3入力以上でも問題ないです。
2入力のXOR
まず2入力の場合。この場合、「どちらかがON、どちらかがOFF」言い換えると「ONになっているものが奇数個」のとき真を出力します。
3入力のXOR
説明するよりも、真偽表を見てもらう方が早いです。
次の表は2入力のXORの真偽表です。
| A | B | OUT |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
このOUTをA'として、A'とCの真偽表が次の表です。
| A' | C | OUT |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 0 | 1 | 1 |
まとめると以下のようになります。
| A | B | C | OUT |
| 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 |
わかりやすいように、出力が真の行を赤色にしてみました。気が付きましたか?そうです。 「真が奇数個入力されたときは真、偶数個のときは偽」 になっています。
考察
2入力のXORは「真となっている個数が奇数個なら真」を返していました。しかし、真偽表をよく見ると、「真を出力したならば、それまでの入力に真は奇数個」とも言えます。
3入力のXORは A1 ^ A2 ^ A3 と表せます。A1 ^ A2 が真ならば、入力に真は1つです。偽ならば0 or 2個です。
そして、これとA3とXORをしてみると、これまたうまいことできていて、真の総数が奇数個(1 or 3個)のときのみ真、偶数個なら偽になります。
N入力のXOR
以上を踏まえると、
A1 ^ A2 ^ A3 ^ … ^ An は「A1, … , An のうち、真となるものが奇数個である」という命題と同値です。
XOR、実におもしろいですね。何かに使えそうです