Mixing
排他的論理和
ベン図による排他的論理和P⊻Q{displaystyle Pveebar Q}
排他的論理和（はいたてきろんりわ、英: exclusive or / exclusive disjunction）とは、ブール論理や古典論理、ビット演算などにおいて、2つの入力のどちらか片方が真でもう片方が偽の時には結果が真となり、両方とも真あるいは両方とも偽の時は偽となる演算（論理演算）である。XOR、EOR、EX-OR（エクスオア、エックスオア、エクソア）などと略称される。
目次
1 表記法
1.1 プログラミング言語
2 例
3 性質
3.1 真理値表
4 ビットごとの排他的論理和
5 関連項目
表記法
中置演算子のある体系では、中置演算子を利用した中置記法により表記されることが多い。演算子は ⊻{displaystyle veebar }
論理学などでは ⊻{displaystyle veebar }
プログラミング言語
記号を使った中置演算子としては ^ や @ などが使われることが多く、キーワードが演算子になるような言語では 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){displaystyle Pveebar Q=(Pland lnot Q)lor (lnot Pland Q)}
- P⊻Q=(P∨Q)∧(¬P∨¬Q){displaystyle Pveebar Q=(Plor Q)land (lnot Plor lnot Q)}
- P⊻Q=(P∨Q)∧¬(P∧Q){displaystyle Pveebar Q=(Plor Q)land lnot (Pland Q)}
などと表すことができる。
2を法とする剰余体 Z/[2]{displaystyle mathbb {Z} /[2]}![{mathbb {Z}}/[2]](https://wikimedia.org/api/rest_v1/media/math/render/svg/716f29dd6f4027abef803cd813ca8c62efb2c897)
これは、二進数の計算を考えるとき、半加算器の一部である。
真理値表
| 命題 P | 命題 Q | P ⊻ Q |
|---|---|---|
| 真 | 真 | 偽 |
| 真 | 偽 | 真 |
| 偽 | 真 | 真 |
| 偽 | 偽 | 偽 |
ビットごとの排他的論理和
2進数表現した数値の各ビットに対し、2を法とした剰余体 Z/[2]{displaystyle mathbb {Z} /[2]}
ビットごとの排他的論理和は、2の冪を位数とする有限体 GF(2n),n∈N{displaystyle mathrm {GF} (2^{n}),nin mathbb {N} }
0（偽）と1（真）に関しては、排他的論理和とビットごとの排他的論理和は等しい。しかし、非0が全て真とみなされる環境や、非0が真に暗黙の型変換される環境では、0と1以外の値に対しても（ビットごとでない）排他的論理和を求めることができ、結果は一般にはビットごとの排他的論理和とは異なるので注意が必要である。
ビットごとの排他的論理和は、ビット演算を行っている場合に、特定のビットだけを反転させるのによく用いられる。ある数値と、その数値のビットを反転させたい部分を 1 にした数値との排他的論理和をとると、指定した部分が反転した数値が得られる:
- 0011(2)⊕0110(2)=0101(2){displaystyle 0011_{(2)}oplus 0110_{(2)}=0101_{(2)}}
多くのプロセッサで、レジスタをゼロクリアする場合に、直接ゼロを書き込むより、自分自身とのXORをとってゼロとするほうが（コードサイズや速度などで）有利な場合がある。
ビットごとの排他的論理和により、多数の入力における偽の個数の奇数・偶数（パリティ）を検出できるため、誤り検出に用いられる。この目的で排他的論理和（論理ゲート）を樹枝状に接続した回路をパリティツリーという。
ビットごとの排他的論理和は特定ビットの反転操作なので、2回繰り返せば元に戻る。つまり
- (P⊕K)⊕K=P{displaystyle (Poplus K)oplus K=P}
この性質は便利であり、さまざまな応用がある。単純なものでは、（現代では有用性はほとんど無いが）2個のレジスタの内容をテンポラリな資源を使わず交換できる「XOR交換アルゴリズム」といったものから、データ構造では「XOR連結リスト」などがある。
他には、K{displaystyle K}
先の例でいえば、平文 0011(2){displaystyle 0011_{(2)}}
- 0101(2)⊕0110(2)=0011(2){displaystyle 0101_{(2)}oplus 0110_{(2)}=0011_{(2)}}
と、暗号文から鍵を使って平文が復号される。このような暗号をバーナム暗号と呼ぶ。一般に鍵交換問題があることから、短い鍵を元にした何らかの数列を使うことも多いが、ワンタイムパッドによるバーナム暗号には原文と同じ長さの鍵（そのような大量の情報量を持つものは、もはや運用上は「鍵」とは言えないが）が必要である。「解読」が絶対に不可能（理論的に、どのような解読結果も同様に確からしいものになってしまう）という意味では「最強」の暗号だが、暗号の強度は運用の観点なども含め総合的に判断しなければならないものであり、「鍵」の事前共有とその秘匿に必要な多大なコストが大きな難点である。
排他的論理和と2進数表記法を用いて、石取りゲーム（ニム、三山崩し）の必勝法を導くことができる。
関連項目
- 真理値
- 真理値表
- ブール代数
- ブール論理
- ブール関数
- ベン図
- 対称差
- 選言三段論法
- 選言肯定
XOR交換アルゴリズム、XOR連結リスト
- マスク (情報工学)
| ||||||||||||||
