排他的論理和
テンプレート:Redirect3テンプレート:Redirect
排他的論理和（はいたてきろんりわ，exclusive or / exclusive disjunction) とは、ブール論理や古典論理などにおいて、与えられた2つの命題のいずれかただ1つのみが真であるときに真となる論理演算である。 XOR、EOR、EX-OR（エクスオア、エックスオア、エクソア)などと略称される。 なお、コンピュータ・プログラミングなど応用数学では、後述するビットごとの排他的論理和（bitwise exclusive or）を、単に排他的論理和、EX-ORなどと呼ぶことがある。
表記法
排他的論理和（EX-OR） は、中置記法により表記される。 演算子は <math>\veebar</math> (Unicode: U+22BB ⊻)、 <math>\dot\vee</math> 。誤解のおそれがないときは、XOR、xor、 <math>\oplus</math> (Unicode: U+2295 ⊕)、+、≠ なども使われる。
論理学
<math>\veebar</math>を使用して <math>P \veebar Q</math> と書く。
電子工学
<math>\oplus</math> 記号を使用して <math>A \oplus B</math> と書く。論理回路のページも参照。
プログラミング言語
ビット毎の排他的論理和の演算子は、XOR、xor、 ^ などが使われる。
- z = x ^ y;
- z = x xor y;
のように使用される。
例
「私の身長は160cm以上である」と「私の体重は52kg未満である」の二つの命題の排他的論理和は、これらのうち一方のみが成り立つことであるから、「私は身長160cm以上であり体重が52kg以上である。あるいは、私は身長160cm未満であり体重が52kg未満である。」となる。
なお、2つの命題 A,B について積集合 A ∧ B が空集合であれば、排他的論理和は論理和と同じになる。例えば A = 「私の身長は160cmである」と B = 「私の身長は170cmである」は同時に成立することはない（積集合が空である）ので、（A xor B）は（A ∨ B）と同じく「私の身長は160cmまたは170cmのいずれか一方である」となる。
性質
- <math>P \veebar Q = (P \land \lnot Q) \lor (\lnot P \land Q)</math>
- <math>P \veebar Q = (P \lor Q) \land (\lnot P \lor \lnot Q)</math>
- <math>P \veebar Q = (P \lor Q) \land \lnot (P \land Q)</math>
などと表すことができる。
2を法とする剰余体 <math>\mathbb{Z} / [2]</math> での加減算（この体では加算と減算は等しい）は、0を偽、1を真とみなすと、排他的論理和となる。つまり、偶数 (0, 偽) 同士または奇数 (1, 真) 同士を足すと偶数 (0, 偽)、偶数 (0, 偽) と奇数 (1, 真) を足すと奇数 (1, 真) になる。
真理値表
| 命題 P | 命題 Q | P ⊻ Q |
|---|---|---|
| 真 | 真 | 偽 |
| 真 | 偽 | 真 |
| 偽 | 真 | 真 |
| 偽 | 偽 | 偽 |
ビットごとの排他的論理和
2進数表現した数値の各ビットに対し、2を法とした剰余体 <math>\mathbb{Z} / [2]</math> での加減算（0を偽、1を真とみなした排他的論理和）を求めた結果を、ビットごとの排他的論理和、排他的ビット和、あるいは単に排他的論理和と呼ぶ。
ビットごとの排他的論理和は、2の冪を位数とする有限体 <math>\mathrm{GF}(2^n), n \in \mathbb{N}</math> での加減算（この体では加算と減算は等しい）に等しい。なお、<math>\mathbb{Z} / [2]</math> は、位数2の有限体 <math>\mathrm{GF}(2)\,</math> である。
0（偽）と1（真）に関しては、排他的論理和とビットごとの排他的論理和は等しい。しかし、非0が全て真とみなされる環境や、非0が真に暗黙の型変換される環境では、0と1以外の値に対しても（ビットごとでない）排他的論理和を求めることができ、結果は一般にはビットごとの排他的論理和とは異なるので注意が必要である。
ビットごとの排他的論理和は、ビット演算を行っている場合に、特定のビットだけを反転させるのによく用いられる。ある数値と、その数値のビットを反転させたい部分を 1 にした数値との排他的論理和をとると、指定した部分が反転した数値が得られる:
- <math>0011_{(2)} \oplus 0110_{(2)} = 0101_{(2)}</math> 。
また、x86などのCPUでは、レジスタをゼロクリアする場合に、直接ゼロを書き込むより、自分自身とのXORをとってゼロとするほうが（コードサイズや速度などで）有利な場合がある。
ビットごとの排他的論理和により、多数の入力における偽の個数の奇数・偶数（パリティ）を検出できるため、誤り検出に用いられる。この目的で排他的論理和（論理ゲート）を樹枝状に接続した回路をパリティツリーという。
ビットごとの排他的論理和は特定ビットの反転操作なので、2回繰り返せば元に戻る。つまり
- <math>(P \oplus K) \oplus K = P</math> 。
これを利用して、 <math>K</math> を鍵とする暗号を作ることができる。平文は <math>P\,</math> 、暗号文は <math>P \oplus K</math> となる。
先の例でいえば、平文 <math>0011_{(2)}</math> が鍵 <math>0110_{(2)}</math> を使って暗号文 <math>0101_{(2)}</math> に変換され、
- <math>0101_{(2)} \oplus 0110_{(2)} = 0011_{(2)}</math>
と、暗号文から鍵を使って平文が復号される。このような暗号をバーナム暗号と呼ぶ。
ただし、鍵の情報量と暗号文の情報量の差だけ平文の情報がもれることから、この暗号が安全であるためには鍵の長さが平文の長さ以上である必要がある。このような暗号をワンタイムパッドと呼ぶ。
排他的論理和と2進数表記法を用いて、石取りゲーム（ニム、三山崩し）の必勝法を導くことができる。
