排他的論理和

排他的論理和
https://ja.wikipedia.org/wiki/%E6%8E%92%E4%BB%96%E7%9A%84%E8%AB%96%E7%90%86%E5%92%8C

　※　今日は、こんな所で…。

『出典: フリー百科事典『ウィキペディア（Wikipedia）』
曖昧さ回避「XOR」は論理演算について説明しているこの項目へ転送されています。論理回路については「XORゲート」をご覧ください。

ベン図による排他的論理和 P ⊻ Q P\veebar Q

排他的論理和（はいたてきろんりわ、英: exclusive or / exclusive disjunction）とは、ブール論理や古典論理、ビット演算などにおいて、2つの入力のどちらか片方が真でもう片方が偽の時には結果が真となり、両方とも真あるいは両方とも偽の時は偽となる演算（論理演算）である。XOR、EOR、EX-OR（エクスオア、エックスオア、エクソア）などと略称される。

表記法

中置演算子のある体系では、中置演算子を利用した中置記法により表記されることが多い。

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

論理学などでは ⊻ \veebar を使用して P ⊻ Q P\veebar Q と書くことが多く、論理回路などでは ⊕ \oplus を使用して A ⊕ B A \oplus B と書くことが多い。

プログラミング言語

記号を使った中置演算子としては ^ や @ などが使われることが多く、キーワードが演算子になるような言語では 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のいずれか一方である」となる。

「対称差」も参照

性質

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

P ⊻ Q = ( P ∧ ¬ Q ) ∨ ( ¬ P ∧ Q ) P\veebar Q=(P\land \lnot Q)\lor (\lnot P\land Q)

P ⊻ Q = ( P ∨ Q ) ∧ ( ¬ P ∨ ¬ Q ) P\veebar Q=(P\lor Q)\land (\lnot P\lor \lnot Q)

P ⊻ Q = ( P ∨ Q ) ∧ ¬ ( P ∧ Q ) P\veebar Q=(P\lor Q)\land \lnot (P\land Q)

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

真理値表

命題 P 命題 Q P ⊻ Q

真真偽
真偽真
偽真真
偽偽偽

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

ビットごとの排他的論理和

2進数表現した数値の各ビットに対し、0 を偽、1 を真とみなして排他的論理和を求めた結果を、ビットごとの排他的論理和、排他的ビット和、または単に排他的論理和と呼ぶ。
⊕ 0 1
0 0 1
1 1 0

  P = 0011
  K = 0110

P ⊕ K = 0101

ビットごとの排他的論理和は、桁上がりを無視した2進数の加算の結果と等しい。

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

1 桁の2進数の排他的論理和は、半加算器の一部である。

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

ビット演算

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

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

多くのプロセッサで、レジスタをゼロにする場合に、直接ゼロをレジスタへ転送するより、自分自身とのXORをとってゼロとするほうが有利な場合がある。

X ⊕ X = 0 {\displaystyle X\oplus X=0}

主に以下の条件が成立する場合、言語処理系が最適化の一環としてXORを用いる。

即値のゼロを省略することにより、コードサイズが削減できる。
処理がレジスタとALUのみで完結するので、サイクル数や消費電力が削減できる。
XOR演算によるフラグ変化がその後の処理に不利な影響を残さない。

ビットごとの排他的論理和によって、多数の入力における偽の個数の奇数・偶数（パリティ）が検出できるので、誤り検出に用いられる。この目的で排他的論理和（論理ゲート）を樹枝状に接続した回路をパリティツリーという。

ビットごとの排他的論理和は特定ビットの反転操作なので、2回繰り返せば元に戻る。つまり

( P ⊕ K ) ⊕ K = P (P\oplus K)\oplus K=P

これは、結合法則によって、次のとおりに証明できる。

( P ⊕ K ) ⊕ K = P ⊕ ( K ⊕ K ) = P {\displaystyle (P\oplus K)\oplus K=P\oplus (K\oplus K)=P}

この性質は便利であって、さまざまな応用がある。単純なものでは、（現代では有用性はほとんどないが）2個のレジスタの内容を他の資源を使わず交換できる「XOR交換アルゴリズム」があり、データ構造では「XOR連結リスト」がある。
暗号

K K を鍵とする暗号に使うこともできる。平文を P P とすると、 P ⊕ K P\oplus K を暗号文とすることができる。

先の例でいえば、平文 0011 ( 2 ) 0011_{{(2)}} が鍵 0110 ( 2 ) 0110_{{(2)}} を使って暗号文 0101 ( 2 ) 0101_{{(2)}} に変換され、次のとおり同一の鍵を使って暗号文から平文に復号できる。

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

バーナム暗号は、この性質を利用した暗号である。一般に鍵交換問題があることから、短い鍵を元にした何らかの数列を使うことも多いが、ワンタイムパッドによるバーナム暗号には原文と同じ長さの鍵（そのような大量の情報量をもつものは、もはや運用上は「鍵」とはいえないが）が必要である。解読が絶対に不可能（理論的に、どのような解読結果も同様に確からしいものになってしまう）という意味では最強の暗号であるが、暗号の利用は運用の面も含めて総合的に判断しなければならないものであり、鍵の事前共有とその秘匿に必要な多大なコストが大きな難点である。
その他

排他的論理和と2進数表記を用いて、三つ山崩し（ニム）の必勝法を導くことができる。

排他的論理和

共有: