独占または

排他的論理和

XOR
真理値表	${\displaystyle (0110)}$
論理ゲート
標準形
選言的	${\displaystyle {\overline {x}}\cdot y+x\cdot {\overline {y}}}$
接続詞	${\displaystyle ({\overline {x}}+{\overline {y}})\cdot (x+y)}$
ジェガルキン多項式	${\displaystyle x\oplus y}$
ポストの格子
0保存	はい
1-保存	いいえ
単調	いいえ
アフィン	はい
自己双対	いいえ
v t e

排他的論理和、排他的論理和、排他的選択、論理的非等価性、または論理的不等式は、その否定が論理的双条件である論理演算子です。2 つの入力の場合、XOR は入力が異なる場合(一方が真で、もう一方が偽の場合) に限り真になります。複数の入力の場合、XOR は真の入力の数が奇数の場合に限り真になります。^{[ 1 ]}

「排他的論理和」と呼ばれるのは、両方の演算子が真の場合、「または」の意味が曖昧になるためです。XORは、そのようなケースを除外します。XORを非公式に表現する方法としては、「どちらか一方であるが、両方ではない」、「どちらか一方である」、「AまたはBであるが、AとBの両方ではない」などがあります。

これは接頭辞演算子で表されます${\displaystyle J}$^{[ 2 ] : 16}および中置演算子XOR( / ˌ ɛ k s ˈ ɔː r /または/ ˈ k s ɔː r / )、EOR、EXOR、${\displaystyle {\dot {\vee }}}$、${\displaystyle {\overline {\vee }}}$、${\displaystyle {\underline {\vee }}}$、⩛、${\displaystyle \oplus }$、${\displaystyle \nleftrightarrow }$、${\displaystyle \not \equiv }$、および^。

真理値表${\displaystyle A\nleftrightarrow B}$これは、入力が異なる場合に常にtrueを出力することを示しています。

排他的論理和は基本的に「どちらか一方であるが、両方ではない、またはどちらもではない」という意味です。言い換えれば、その命題は、一方が真で他方が偽である場合に限り真となります。たとえば、2頭の馬がレースをする場合、2頭のうち1頭がレースに勝ちますが、両方が勝つことはありません。排他的論理和は、${\displaystyle p\nleftrightarrow q}$、また、${\displaystyle p\operatorname {?} q}$または${\displaystyle Jpq}$は、論理結合（「論理的かつ」）で表現できます。${\displaystyle \land }$）、論理和（「論理または」、${\displaystyle \vee }$)、および否定(${\displaystyle \neg }$） 次のように：

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\vee q)\land \neg (p\land q)\end{matrix}}}$

排他的論理和${\displaystyle p\nleftrightarrow q}$次のように表現することもできます。

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\land \lnot q)\lor (\lnot p\land q)\end{matrix}}}$

この XOR の表現は、回路やネットワークを構築する際に役立つ可能性があります。なぜなら、それは 1 つしか持たないからです。${\displaystyle \lnot }$操作と少数の${\displaystyle \land }$そして${\displaystyle \lor }$演算。この同一性の証明は以下に示すとおりです。

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\land \lnot q)&\lor &(\lnot p\land q)\\[3pt]&=&((p\land \lnot q)\lor \lnot p)&\land &((p\land \lnot q)\lor q)\\[3pt]&=&((p\lor \lnot p)\land (\lnot q\lor \lnot p))&\land &((p\lor q)\land (\lnot q\lor q))\\[3pt]&=&(\lnot p\lor \lnot q)&\land &(p\lor q)\\[3pt]&=&\lnot (p\land q)&\land &(p\lor q)\end{matrix}}}$

書くことは時に役立つ${\displaystyle p\nleftrightarrow q}$次のように：

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&\lnot ((p\land q)\lor (\lnot p\land \lnot q))\end{matrix}}}$

または：

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\lor q)\land (\lnot p\lor \lnot q)\end{matrix}}}$

この等価性は、上記の証明の4行目にド・モルガンの法則を2回適用することで確立できる。

排他的論理和は、実質含意（実質条件文は、その前件と結果の否定の選言に等しい）と実質等価性の規則により、論理的双条件文の否定にも等しい。

要約すると、数学的および工学的表記では次のようになります。

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\land \lnot q)&\lor &(\lnot p\land q)&=&p{\overline {q}}+{\overline {p}}q\\[3pt]&=&(p\lor q)&\land &(\lnot p\lor \lnot q)&=&(p+q)({\overline {p}}+{\overline {q}})\\[3pt]&=&(p\lor q)&\land &\lnot (p\land q)&=&(p+q)({\overline {pq}})\end{matrix}}}$

ド・モルガンの法則の精神を適用すると、次のようになる。 $${\displaystyle \neg (p\nleftrightarrow q)\equiv \neg p\nleftrightarrow q\equiv p\nleftrightarrow \neg q.}$$

オペレーターは${\displaystyle \wedge }$（接続詞）そして${\displaystyle \lor }$（論理和）は論理システムにおいて非常に有用ですが、次のような方法でより一般化された構造を欠いています。

システム${\displaystyle (\{T,F\},\wedge )}$そして${\displaystyle (\{T,F\},\lor )}$これらはモノイドですが、どちらも群ではありません。残念ながら、このため、これら2つのシステムを組み合わせて、数学的な環のようなより大きな構造を作成することはできません。

しかし、排他的または${\displaystyle (\{T,F\},\oplus )}$はアーベル群です。演算子の組み合わせ${\displaystyle \wedge }$そして${\displaystyle \oplus }$要素の上に${\displaystyle \{T,F\}}$よく知られている2要素場を生成する${\displaystyle \mathbb {F} _{2}}$このフィールドは、システムで取得可能なあらゆるロジックを表すことができます。${\displaystyle (\land ,\lor )}$さらに、体に関する代数解析ツールの豊富なツール群を利用できるという利点もある。

より具体的には、${\displaystyle F}$0と${\displaystyle T}$1 の場合、論理「AND」演算は乗算として解釈できます。${\displaystyle \mathbb {F} _{2}}$そして「XOR」演算は加算として${\displaystyle \mathbb {F} _{2}}$:

${\displaystyle {\begin{matrix}r=p\land q&\Leftrightarrow &r=p\cdot q{\pmod {2}}\\[3pt]r=p\oplus q&\Leftrightarrow &r=p+q{\pmod {2}}\\\end{matrix}}}$

ブール関数を多項式として記述すると、${\displaystyle \mathbb {F} _{2}}$この基底を用いると、関数の代数的標準形と呼ばれる。^{[ 3 ]}

自然言語では、選言はしばしば排他的に理解される。英語では、選言語「or」は、特に助詞「either」と一緒に使われる場合、しばしば排他的に理解される。以下の英語の例は、通常、会話ではメアリーが歌手であり詩人でもあるわけではないことを示唆していると理解される。^{[ 4 ] [ 5 ]}

1. メアリーは歌手か詩人だ。

しかし、選言は「どちらか一方」と組み合わせた場合でも、包括的に理解することもできます。たとえば、以下の最初の例は、「どちらか一方」が両方の選言が真であるという明確な記述と組み合わせて適切に使用できることを示しています。2番目の例は、下方含意の文脈では排他的推論が消滅することを示しています。この例で選言が排他的に理解された場合、一部の人々が米と豆の両方を食べる可能性が残されます。^{[ 4 ]}

2. メアリーは歌手か詩人か、あるいはその両方である。

3. 誰も米も豆も食べなかった。

上記のような例は、排他性推論を、包括的な意味論に基づいて計算される実用的な会話的含意として分析する動機付けとなっている。含意は通常取り消し可能であり、その計算が量の公理に依存する場合、下方含意の文脈では生じない。しかし、一部の研究者は排他性を正真正銘の意味的含意として扱い、それを検証する非古典的論理を提案している。^{[ 4 ]}

英語の「or」のこの振る舞いは他の言語でも見られます。しかし、多くの言語にはフランス語のsoit... soitのように、排他的な選言構文があります。^{[ 4 ]}

排他的論理和を表す記号は、応用分野によって異なり、議論の文脈で強調される特性によっても異なります。「XOR」という略語の他に、以下の記号が用いられることもあります。

• ${\displaystyle +}$1847年にジョージ・ブールによって使用された。 ^{[ 6 ]}ブールは${\displaystyle +}$主に授業について、彼はまた、${\displaystyle x,y}$は命題である${\displaystyle x+y}$当時${\displaystyle +}$は結合子です。さらに、ブールはそれを専ら使用しました。このような使用法は、包括的選言（そのため）との関係を示していませんが、${\displaystyle \vee }$（現在ではほぼ固定的に使用されている）と排他的論理和であり、他の用法との混同を招く可能性もあるが、古典的および現代の教科書の中には、依然としてそのような用法を維持しているものもある。^{[ 7 ] [ 8 ]}
• ${\displaystyle {\overline {\vee }}}$1883年にクリスティン・ラッド＝フランクリンによって使用された。 ^{[ 9 ]}厳密に言えば、ラッドは${\displaystyle A\operatorname {\overline {\vee }} B}$「${\displaystyle A}$ではない${\displaystyle B}$「または「いいえ」${\displaystyle A}$は${\displaystyle B}$つまり、${\displaystyle {\overline {\vee }}}$除外として、暗黙のうちに${\displaystyle {\overline {\vee }}}$この記事のタイトルが「論理の代数について」であるため、排他的論理和の意味を持つ。
• ${\displaystyle \not =}$同値性の否定を表す は、1890 年にエルンスト・シュレーダーによって使用されました。 ^{[ 10 ] : 307}の使用は${\displaystyle =}$等価性は1847年のジョージ・ブールに遡ることができるが^{[ 6 ]} 、ブールの後の40年間、チャールズ・サンダース・パース、ヒュー・マッコール、ジュゼッペ・ペアノなどの彼の後継者たちは等価性を使用しなかった。${\displaystyle \not =}$文字通り非等価性として定義されるのは、おそらく否定と等価性から容易に定義できるからだろう。
• ${\displaystyle \circ }$1894年にジュゼッペ・ペアノによって使用された：「${\displaystyle a\circ b=a-b\,\cup \,b-a}$看板${\displaystyle \circ }$ラテン語のautに対応する。${\displaystyle \cup }$velに。^{[ 11 ] : 10}ラテン語の「aut」は「排他的または」を意味し、「vel」は「包含的または」を意味することに注意してください。また、Peano は、${\displaystyle \cup }$包括的な選言として。
• ${\displaystyle \vee \vee }$1936 年にイズライル・ソロモノヴィチ・グラドシュテイン (Израиль Соломонович Градлытейн) によって使用されました。^{[ 12 ] : 76}
• ${\displaystyle \oplus }$1938年にクロード・シャノンによって使用された。^{[ 13 ]}シャノンは1904年にエドワード・ヴァーミリイ・ハンティントンから排他的論理和としてこの記号を借用した。 ^{[ 14 ]}ハンティントンは1890年にゴットフリート・ヴィルヘルム・ライプニッツからこの記号を借用した（元の日付は明確には分かっていないが、ほぼ間違いなく1685年以降に書かれ、1890年は出版された年である）。^{[ 15 ]} 1904年のハンティントンと1890年のライプニッツはどちらも代数演算としてこの記号を使用した。さらに、1904年のハンティントンは包括的論理和（論理和）としてもこの記号を使用し、1933年には${\displaystyle +}$包括的選言として。^{[ 16 ]}
• ${\displaystyle \not \equiv }$同値性の否定も表すこの表現は、 1944年にアロンゾ・チャーチによって使用された。 ^{[ 17 ]}
• ${\displaystyle J}$（接頭辞演算子として、${\displaystyle J\phi \psi }$）は、 1949年にJózef Maria Bocheńskiによって使用されました。^{[ 2 ]： 16}誰か^{[ 18 ]}は、最初に使用したのがJan Łukasiewiczであると誤解しているかもしれません。${\displaystyle J}$排他的論理和については（この間違いは広く広まっているようだが）、1929年^{[ 19 ]}でも他の著作でも、ウカシェヴィチはそのような使い方をしていない。実際、1949年にボチェンスキーは、古典論理の16個の二項結合子すべてに名前を付けるポーランド記法を導入したが、これは1929年のウカシェヴィチの記法と互換性のある拡張であり、${\displaystyle J}$排他的論理和が初めて登場したのは、ボチェンスキーによる使用法である。${\displaystyle J}$排他的論理和は、ポーランド語の「alternatywa rozłączna」（排他的または）とは何の関係もなく、偶然の一致である。これについては、1949年の書籍の16ページの表を参照のこと。
• ^キャレットは、C [ ^{20 ]を}皮切りに、 C++、C#、D、Java、Perl、Ruby、PHP、Python、Rustなど、いくつかのプログラミング言語でビットごとの排他的論理和演算子を表すために使用されてきました。
• 2つの集合の対称差${\displaystyle S}$そして${\displaystyle T}$これは、要素ごとの排他的または、と解釈される可能性があり、次のように様々に表記されてきました。${\displaystyle S\ominus T}$、${\displaystyle S\mathop {\triangledown } T}$、 または${\displaystyle S\mathop {\vartriangle } T}$[ ^{21 ]​}

可換性：あり

連想性：あり

分配性：

排他的論理和は、いかなる二項関数（それ自体でさえも）に対しても分配法則を満たさないが、論理積は排他的論理和に対して分配法則を満たす。${\displaystyle C\land (A\oplus B)=(C\land A)\oplus (C\land B)}$（論理積と排他的論理和は、体GF(2)の乗算と加算演算を構成し、他の体と同様に分配法則に従います。）

冪等性：なし

単調性：なし

真実保持：いいえ

すべての入力が真の場合、出力は真ではない。

虚偽性を維持する：はい

すべての入力が偽の場合、出力も偽となる。

ウォルシュスペクトル：（2,0,0,−2）

非線形性：0

この関数は線形である。

退化：

排他的、または一方の入力が他方の入力の関数となる関数は、対合関数または自己逆関数です。この関数を2回適用しても、入力変数は変化しません。

真（1）と偽（0）に二進数を使用する場合、排他的論理和は、 2を法とする加算とまったく同じように機能します。

LaTeXベースのマークダウンでは「左右矢印ではない」( \nleftrightarrow)とも呼ばれます(${\displaystyle \nleftrightarrow }$) ASCII コードとは別に、演算子はブロック数学演算子のU+22BB ⊻ XOR ( & veebar; )とU+2295 ⊕ CIRCLED PLUS ( & CirclePlus;, & oplus; )にエンコードされています。

ウィキメディア・コモンズには排他的論理和に関連するメディアがあります。

無料辞書であるWiktionaryで「排他的論理和（exclusive or）  」または「XOR」を調べてみてください。

• XORについて
• XORの性質の証明とXORの応用、CS103：計算機科学の数学的基礎、スタンフォード大学