排他的論理和のソースを表示

{{Redirect3|XOR|論理演算|論理回路|XORゲート}}
[[ファイル:Venn-Diagram-XOR.png|thumb|ベン図による排他的論理和<math>P \veebar Q</math>]]
'''排他的論理和'''（はいたてきろんりわ、{{Lang-en-short|exclusive or / exclusive disjunction}}）とは、[[ブール論理]]や[[古典論理]]、[[ビット演算]]などにおいて、2つの入力のどちらか片方が真でもう片方が偽の時には結果が真となり、両方とも真あるいは両方とも偽の時は偽となる演算（[[論理演算]]）である。'''XOR'''、'''EOR'''、'''EX-OR'''（エクスオア、エックスオア、エクソア）などと略称される。

== 表記法 ==
中置演算子のある体系では、中置演算子を利用した[[中置記法]]により表記されることが多い。[[演算 (数学)|演算子]]は <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> と書くことが多い。

=== プログラミング言語 ===
記号を使った中置演算子としては <code>^</code> や <code>@</code> などが使われることが多く、キーワードが演算子になるような言語では <code>XOR</code> や <code>xor</code> などが使われることが多い。[[真理値]]の排他的論理和の演算子としては<ref>[[ビット演算]]の排他的論理和には専用の演算が必要である（Haskellでは<code>xor</code>という関数）。</ref>同値の否定の[[関係演算子|比較演算子]]がその意味のため、専用の演算子を持たないこともある（[[Haskell]]など）。
:<code>z = x ^ y;</code>
:<code>z = x xor y;</code>
Haskellでは、
:<code>z = x /= y</code>
ここで<code>/=</code>の型は<code>(/=) :: Eq a => a -> a -> Bool</code>、意味はC言語などの<code>!=</code>と同じである。

IEC 60617の[[XORゲート#記号|XORゲートの記号]]では、<code>=1</code>が排他的論理和を意味するものとして使われている。

[[File:XOR IEC.svg]]

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

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

{{See also|対称差}}

== 性質 ==
排他的論理和は、[[論理和]]、[[論理積]]、[[否定]]を用いて、
:<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>
などと表すことができる。

; 真理値表
{| border=1 cellpadding=2 cellspacing=0 style="margin-left:40px"
|- style="background-color:#ccc"
! 命題 ''P'' !! 命題 ''Q'' !! ''P ⊻ Q''
|- align="center"
| {{yes2|真}}|| {{yes2|真}}|| {{no2|'''偽'''}}
|- align="center"
| {{yes2|真}}|| {{no2|偽}}|| {{yes2|'''真'''}}
|- align="center"
| {{no2|偽}}|| {{yes2|真}}|| {{yes2|'''真'''}}
|- align="center"
| {{no2|偽}}|| {{no2|偽}}|| {{no2|'''偽'''}}
|}

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

== ビットごとの排他的論理和 ==
[[二進法|2進数]]表現した数値の各[[ビット]]に対し、0 を偽、1 を真とみなして排他的論理和を求めた結果を、'''ビットごとの排他的論理和'''、'''排他的ビット和'''、または単に'''排他的論理和'''と呼ぶ。
{| border=1 cellpadding=2 cellspacing=0 style="margin-left:3em;"
! ⊕ !! 0 !! 1
|- align="center"
! 0
| {{no2|0}} || {{yes2|1}}
|- align="center"
! 1
| {{yes2|1}} || {{no2|0}}
|}

    &nbsp;&nbsp; ''P'' = 0011
    &nbsp;&nbsp; ''K'' = 0110
   ''P'' ⊕ ''K'' = 0101

ビットごとの排他的論理和は、[[位取り記数法|桁上がり]]を無視した2進数の加算の結果と等しい。つまり、ビットごとの排他的論理和は、2 の[[冪乗|冪]]を位数とする[[有限体]] <math>\mathrm{GF}(2^n)</math><!--, n \in \mathbb{N}--> での加減算（この体では加算と減算は等しい）に等しい。（なお、2を法とする剰余体 <math>\mathbb{Z} / [2]</math> は、位数2の有限体 <math>\mathrm{GF}(2)</math> である。）

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

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

=== ビット演算 ===
ビットごとの排他的論理和は、コンピュータ上で[[ビット演算]]を行っている場合に、特定のビットだけを反転させるのによく用いられる。ある数値と、その数値のビットを反転させたい部分を 1 にした数値との排他的論理和をとると、指定した部分が反転した数値が得られる:
:<math>0011_{(2)} \oplus 0110_{(2)} = 0101_{(2)}</math>

多くの[[プロセッサ]]で、レジスタをゼロにする場合に、直接ゼロをレジスタへ転送するより、自分自身とのXORをとってゼロとするほうが有利な場合がある。
:<math>X \oplus X = 0</math>
主に以下の条件が成立する場合、[[言語プロセッサ|言語処理系]]が[[最適化_(情報工学)|最適化]]の一環としてXORを用いる。
* 即値のゼロを省略することにより、コードサイズが削減できる。
* 処理がレジスタと[[演算装置#ALU|ALU]]のみで完結するので、サイクル数や消費電力が削減できる。
* XOR演算による[[フラグ_(コンピュータ)|フラグ]]変化がその後の処理に不利な影響を残さない。

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

ビットごとの排他的論理和は特定ビットの反転操作なので、2回繰り返せば元に戻る。つまり
:<math>(P \oplus K) \oplus K = P</math>
これは、[[結合法則]]によって、次のとおりに証明できる。
:<math>(P \oplus K) \oplus K = 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>
[[バーナム暗号]]は、この性質を利用した暗号である。一般に鍵交換問題があることから、短い鍵を元にした何らかの数列を使うことも多いが、[[ワンタイムパッド]]によるバーナム暗号には原文と同じ長さの鍵（そのような大量の情報量をもつものは、もはや運用上は「鍵」とはいえないが）が必要である。[[情報理論的安全性|解読が絶対に不可能]]（理論的に、どのような解読結果も同様に確からしいものになってしまう）という意味では最強の暗号であるが、暗号の利用は運用の面も含めて総合的に判断しなければならないものであり、鍵の事前共有とその秘匿に必要な多大なコストが大きな難点である。

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

== 注・出典 ==
<references/>

== 関連項目 ==
*[[真理値]]
*[[真理値表]]
*[[ブール代数]]
*[[ブール論理]]
*[[ブール関数]]
*[[ベン図]]
*[[対称差]]
*[[選言三段論法]]
*[[選言肯定]]
*[[XOR交換アルゴリズム]]、[[XOR連結リスト]]
*[[マスク (情報工学)]]

{{論理演算}}
{{Common logical symbols}}
{{Normdaten}}
{{DEFAULTSORT:はいたてきろんりわ}}
[[Category:論理結合子]]
[[Category:デジタル回路]]
[[Category:二分法]]
[[Category:数学に関する記事]]