排他的論理和（はいたてきろんりわ）(exclusive or / exclusive disjunction) とは、数理論理学において、与えられた2つの命題のいずれかただ1つのみが真であるときに真となる論理演算である。XOR、EOR、EXOR（エクスオア、エックスオア、エクソア)などと略称される。
演算子は (Unicode: U+22BB ?)、 。誤解のおそれがないときは、XOR、xor、 (Unicode: U+2295 ?)、+、≠ なども使われる。
なお、コンピュータ・プログラミングなど応用数学で、後述するビットごとの排他的論理和 (bitwise exclusive or) を、単に排他的論理和、XORなどと呼ぶことがある。演算子は、XOR、xor、 、^ などが使われる。
目次
1 例
2 性質
2.1 真理値表
3 ビットごとの排他的論理和
4 関連項目
//
「私の身長は156cm以上である」と「私の体重は52kg未満である」の二つの命題の排他的論理和は、これらのうち一方のみが成り立つことであるから、「私は身長156cm以上であり体重が52kg以上である。あるいは、私は身長156cm未満であり体重が52kg未満である。」となる。
なお、2つの命題 A,B について積集合 A ∧ B が空集合であれば、排他的論理和は論理和と同じになる。例えば A = 「私の身長は156cmである」と B = 「私の身長は170cmである」は同時に成立することはない（積集合が空である）ので、(A xor B)は(A ∨ B)と同じく「私の身長は156cmまたは170cmのいずれか一方である」となる。
などと表すことができる。
2を法とする剰余体 での加減算（この体では加算と減算は等しい）は、0を偽、1を真とみなすと、排他的論理和となる。つまり、偶数 (0, 偽) 同士または奇数 (1, 真) 同士を足すと偶数 (0, 偽)、偶数 (0, 偽) と奇数 (1, 真) を足すと奇数 (1, 真) になる。
命題 P命題 QP ? Q
真真偽
真偽真
偽真真
偽偽偽
2進数表現した数値の各ビットに対し、2を法とした剰余体 での加減算（0を偽、1を真とみなした排他的論理和）を求めた結果を、ビットごとの排他的論理和、排他的ビット和、あるいは単に排他的論理和と呼ぶ。
ビットごとの排他的論理和は、2の冪を位数とする有限体 での加減算（この体では加算と減算は等しい）に等しい。なお、 は、位数2の有限体 である。
0（偽）と1（真）に関しては、排他的論理和とビットごとの排他的論理和は等しい。しかし、非0が全て真とみなされる環境や、非0が真に暗黙の型変換される環境では、0と1以外の値に対しても（ビットごとでない）排他的論理和を求めることができ、結果は一般にはビットごとの排他的論理和とは異なるので注意が必要である。
ビットごとの排他的論理和は、ビット演算を行っている場合に、特定のビットだけを反転させるのによく用いられる。ある数値と、その数値のビットを反転させたい部分を 1 にした数値との排他的論理和をとると、指定した部分が反転した数値が得られる: 。
ビットごとの排他的論理和により、多数の入力における偽の個数の奇数・偶数（パリティ）を検出できるため、誤り検出に用いられる。この目的で排他的論理和（論理ゲート）を樹枝状に接続した回路をパリティツリーという。
ビットごとの排他的論理和は特定ビットの反転操作なので、2回繰り返せば元に戻る。つまり 。
これを利用して、 K を鍵とする暗号を作ることができる。平文は 、暗号文は となる。
先の例でいえば、平文 0011(2) が鍵 0110(2) を使って暗号文 0101(2) に変換され、
と、暗号文から鍵を使って平文が復号される。このような暗号をバーナム暗号と呼ぶ。
ただし、鍵の情報量と暗号文の情報量の差だけ平文の情報がもれることから、この暗号が安全であるためには鍵の長さが平文の長さ以上である必要がある。このような暗号をワンタイムパッドと呼ぶ。
排他的論理和と2進数表記法を用いて、石取りゲーム（ニム、三山崩し）の必勝法を導くことができる。
関連項目
真理値
真理値表
ブール代数
ブール論理
ブール関数
ベン図
対称差
選言三段論法
選言肯定
XOR交換アルゴリズム、XOR連結リスト
表・話・編・歴論理演算
AND - OR - NOT - NAND - NOR - XOR - IMP - EQ
カテゴリ: 数理論理学 | 数学に関する記事
更新日時:2008年9月2日(火)23:20
取得日時:2008/10/07 17:33