排他的論理和

出典: フリー百科事典『ウィキペディア（Wikipedia）』

排他的論理和（はいたてきろんりわ）(exclusive or / exclusive disjunction) とは、数理論理学において、与えられた2つの命題のいずれかただ1つのみが真であるときに真となる論理演算である。XOR、EOR、EXOR（エクスオア、エックスオア、エクソア)などと略称される。

演算子は $\veebar$ (Unicode: U+22BB ⊻)、 $\dot\vee$ 。誤解のおそれがないときは、XOR、xor、 $\oplus$ (Unicode: U+2295 ⊕)、+、≠ なども使われる。

なお、コンピュータ・プログラミングなど応用数学で、後述するビットごとの排他的論理和 (bitwise exclusive or) を、単に排他的論理和、XORなどと呼ぶことがある。演算子は、XOR、xor、 $\oplus$ 、^ などが使われる。

[編集] 例

「私の身長は160cm以上である」と「私の体重は60kg未満である」の二つの命題の排他的論理和は、これらのうち一方のみが成り立つことであるから、「私は身長160cm以上であり体重が60kg以上である。あるいは、私は身長160cm未満であり体重が60kg未満である。」となる。

なお、2つの命題 A,B について積集合 A ∧ B が空集合であれば、排他的論理和は論理和と同じくなる。例えば A = 「私の身長は160cmである」と B = 「私の身長は170cmである」は同時に成立することはない（積集合が空である）ので、(A xor B)は(A ∨ B)と同じく「私の身長は160cmまたは170cmのいずれか一方である」となる。

[編集] 性質

排他的論理和は、論理和、論理積、否定を用いて、

$P \veebar Q = (P \land \lnot Q) \lor (\lnot P \land Q)$

$P \veebar Q = (P \lor Q) \land (\lnot P \lor \lnot Q)$

$P \veebar Q = (P \lor Q) \land \lnot (P \land Q)$

などと表すことができる。

2を法とする剰余体 $\mathbb{Z} / [2]$ での加減算（この体では加算と減算は等しい）は、0を偽、1を真とみなすと、排他的論理和となる。つまり、偶数 (0, 偽) 同士または奇数 (1, 真) 同士を足すと偶数 (0, 偽)、偶数 (0, 偽) と奇数 (1, 真) を足すと奇数 (1, 真) になる。

[編集] 真理値表

命題 P	命題 Q	P ⊻ Q
真	真	偽
真	偽	真
偽	真	真
偽	偽	偽

[編集] ビットごとの排他的論理和

2進数表現した数値の各ビットに対し、2を法とした剰余体 $\mathbb{Z} / [2]$ での加減算（0を偽、1を真とみなした排他的論理和）を求めた結果を、ビットごとの排他的論理和、排他的ビット和、あるいは単に排他的論理和と呼ぶ。

ビットごとの排他的論理和は、2の冪を位数とする有限体 $\mathrm{GF}(2^n), n \in \mathbb{N}$ での加減算（この体では加算と減算は等しい）に等しい。なお、 $\mathbb{Z} / [2]$ は、位数2の有限体 $\mathrm{GF}(2)\,$ である。

0（偽）と1（真）に関しては、排他的論理和とビットごとの排他的論理和は等しい。しかし、非0が全て真とみなされる環境や、非0が真に暗黙の型変換される環境では、0と1以外の値に対しても（ビットごとでない）排他的論理和を求めることができ、結果は一般にはビットごとの排他的論理和とは異なるので注意が必要である。

ビットごとの排他的論理和は、ビット演算を行っている場合に、特定のビットだけを反転させるのによく用いられる。ある数値と、その数値のビットを反転させたい部分を 1 にした数値との排他的論理和をとると、指定した部分が反転した数値が得られる:

$0011_{(2)} \oplus 0110_{(2)} = 0101_{(2)}$ 。