排他的論理和
排他的論理和（はいたてきろんりわ、英: exclusive or / exclusive disjunction）とは、ブール論理や古典論理、ビット演算などにおいて、2つの入力のどちらか片方が真でもう片方が偽の時には結果が真となり、両方とも真あるいは両方とも偽の時は偽となる演算（論理演算）である。XOR、EOR、EX-OR（エクスオア、エックスオア、エクソア）などと略称される。
Contents
表記法
中置演算子のある体系では、中置演算子を利用した中置記法により表記されることが多い。演算子は [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]
多くのプロセッサで、レジスタをゼロクリアする場合に、直接ゼロを書き込むより、自分自身とのXORをとってゼロとするほうが（コードサイズや速度などで）有利な場合がある。
ビットごとの排他的論理和により、多数の入力における偽の個数の奇数・偶数（パリティ）を検出できるため、誤り検出に用いられる。この目的で排他的論理和（論理ゲート）を樹枝状に接続した回路をパリティツリーという。
ビットごとの排他的論理和は特定ビットの反転操作なので、2回繰り返せば元に戻る。つまり
- [math](P \oplus K) \oplus K = P[/math]
この性質は便利であり、さまざまな応用がある。単純なものでは、（現代では有用性はほとんど無いが）2個のレジスタの内容をテンポラリな資源を使わず交換できる「XOR交換アルゴリズム」といったものから、データ構造では「XOR連結リスト」などがある。
他には、[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進数表記法を用いて、石取りゲーム（ニム、三山崩し）の必勝法を導くことができる。