排他的論理和

排他的論理和

排他的論理和
真理値表	${\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-保存	いいえ
単調	いいえ
アフィン	はい
自己双対	いいえ
ヴ t e

排他的論理和、排他的論理和、排他的交替、論理的非同値、または論理的不等号は、否定が論理双条件である論理演算子です。2つの入力がある場合、入力が異なる場合（1つが真で、1つが偽）に限り、XORは真になります。複数の入力がある場合、真の入力の数が奇数の場合に限り、XORは真になります。^[1]

両方のオペランドが true の場合、「または」の意味があいまいになるため、「排他的論理和」という名前が付けられています。XOR では、そのようなケースは除外されます。XOR を非公式に記述する方法としては、「どちらか一方であるが両方ではない」、「どちらか一方」、「A または B であるが、A と B ではない」などがあります。

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

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

排他的選言は、本質的には「どちらか一方であり、両方でもどちらでもない」という意味です。言い換えると、文が真となるのは、一方が真で他方が偽の場合のみです。たとえば、2 頭の馬がレースをしている場合、2 頭のうち 1 頭がレースに勝ちますが、両方が勝つことはありません。排他的選言 は、または とも表記され、次のように論理積(「論理的 and」、)、選言(「論理的 or」、)、および否定( ) で表すことができます。 ${\displaystyle p\nleftrightarrow q}$${\displaystyle p\operatorname {?} q}$${\displaystyle Jpq}$${\displaystyle \wedge }$${\displaystyle \lor }$${\displaystyle \lnot }$

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\lor q)\land \lnot (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 つしかなく、 and演算の数が少ないため、回路やネットワークを構築するときに便利です。この同一性の証明を以下に示します。 ${\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 \lnot (p\nleftrightarrow q)\Leftrightarrow \lnot p\nleftrightarrow q\Leftrightarrow p\nleftrightarrow \lnot q.}$$

演算子 (論理積) と(論理和) は論理システムでは非常に便利ですが、次のように、より一般化可能な構造を実現できません。 ${\displaystyle \wedge }$${\displaystyle \lor }$

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

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

より具体的には、 を0 に、 を1 に関連付けると、論理「AND」演算を の乗算として解釈でき、 「XOR」演算を の加算として解釈できます。 ${\displaystyle F}$${\displaystyle T}$${\displaystyle \mathbb {F} _{2}}$${\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}}}$

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

分離は自然言語では排他的に理解されることが多い。英語では、分離語「または」は、特に助詞「どちらか」と一緒に使用される場合、排他的に理解されることが多い。以下の英語の例は、会話では通常、メアリーが歌手でも詩人でもないことを意味していると理解される。^{[4] [5]}

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

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

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

3. 誰も米も豆も食べませんでした。

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

英語の「または」のこの動作は他の言語にも見られます。しかし、多くの言語には、フランス語のsoit...soitのように、頑強に排他的な選言構文があります。^[4]

排他的論理和に使用される記号は、応用分野によって異なり、特定の議論の文脈で強調される特性によっても異なります。略語「XOR」に加えて、次の記号も使用されることがあります。

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

交換性: はい

関連性: はい

分配性:

排他的論理和はどの二項関数でも分配できません（それ自体でも分配できません）が、論理積は排他的論理和で分配できます。 （論理積と排他的論理和は、体GF(2)の乗算と加算の演算を形成し、任意の体と同様に分配法則に従います。）${\displaystyle C\land (A\oplus B)=(C\land A)\oplus (C\land B)}$

冪等性: いいえ

単調性：なし

真実の保存: いいえ

すべての入力が true の場合、出力は true ではありません。

虚偽の保存: はい

すべての入力が false の場合、出力は false になります。

ウォルシュスペクトル: (2,0,0,−2)

非線形性: 0

関数は線形です。

退縮:

指定された 1 つの入力を他の入力の関数として排他的または逆関数にすることは、反転または自己逆関数です。これを 2 回適用すると、変数入力は変更されません。

true (1) と false (0) にバイナリ値を使用する場合、排他的論理和は2 を法とする加算と まったく同じように機能します。

排他的論理和はビット演算によく使用されます。例:

• 1 排他的論理和 1 = 0
• 1 排他的論理和 0 = 1
• 0 排他的論理和 1 = 1
• 0 排他的論理和 0 = 0
• 1110 2 XOR 1001 2 = 0111 2 (これは繰り上がりなしの加算に相当します)

上で述べたように、排他的論理和は 2 を法とする加算と同じであるため、2 つのnビット文字列のビットごとの排他的論理和は、ベクトル空間 における加算の標準ベクトルと同じになります。 ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$

コンピュータ サイエンスでは、排他的論理和にはいくつかの用途があります。

• 2 つのビットが等しくないかどうかを判断します。
• これは制御可能なビットフリッパーです (制御入力によって、データ入力を反転するかどうかが選択されます)。
• これは、1 ビットが奇数個あるかどうかを示します( は、変数の数が奇数個の場合にのみ真になります)。これは、パリティ関数によって返されるパリティ ビットに等しくなります。${\displaystyle A\oplus B\oplus C\oplus D\oplus E}$

論理回路では、数値を加算するXOR ゲートと、桁上げ出力を作成する一連の AND、OR、NOT ゲートを使用して、 単純な加算器を作成できます。

一部のコンピュータ アーキテクチャでは、値 0 をロードして格納するよりも、レジスタを自身と XOR してレジスタにゼロを格納する方が効率的です (自身と XOR されたビットは常にゼロになります)。

暗号化では、XOR は、ワンタイム パッドやFeistel ネットワークシステムなどの単純な自己逆混合関数として使用されることがあります。 ^{[引用が必要]} XOR は、AES (Rijndael) や Serpent などのブロック暗号や、ブロック暗号の実装 (CBC、CFB、OFB、CTR) でも頻繁に使用されます。

単純な閾値活性化人工ニューラル ネットワークでは、XOR は線形に分離可能な関数ではないため、XOR 関数をモデル化するには 2 番目のレイヤーが必要です。

同様に、XORはハードウェア乱数ジェネレータのエントロピープールの生成にも使用できます。XOR演算はランダム性を保持します。つまり、ランダムビットを非ランダムビットとXOR演算すると、ランダムビットが生成されます。XORを使用すると、ランダムな可能性のある複数のデータソースを組み合わせることができ、出力の予測不可能性は、少なくとも個々のソースの最良のものと同等であることが保証されます。^[22]

XOR はRAID 3～6 でパリティ情報を作成するために使用されます。たとえば、RAID は 2 台 (またはそれ以上) のハード ドライブからバイト10011100 2と01101100 2を「バックアップ」できます。これは、前述のバイトを XOR して ( 11110000 2 ) を作成し、それを別のドライブに書き込むことによって行います。この方法では、3 台のハード ドライブのいずれかが失われた場合、残りのドライブのバイトを XOR することで失われたバイトを再作成できます。たとえば、01101100 2 を含むドライブが失われた場合、10011100 2と11110000 2を XOR して失われたバイトを回復できます。^[23]

XOR は、符号付き 2 進算術演算の結果のオーバーフローを検出するためにも使用されます。結果の左端の保持ビットが左側の無限桁数と同じでない場合は、オーバーフローが発生したことを意味します。オーバーフローが発生した場合、これら 2 つのビットを XOR すると「1」になります。

XOR は、XOR スワップ アルゴリズムを使用してコンピューター内の 2 つの数値変数を交換するために使用できます。ただし、これはむしろ好奇心によるものであり、実際には推奨されていません。

XOR リンク リストは、二重にリンクされたリストのデータ構造を表すためのスペースを節約するために XOR プロパティを活用します。

コンピュータ グラフィックスでは、アルファ チャネルやオーバーレイ プレーンのないシステム上の境界ボックスやカーソルなどの項目を管理するために、XOR ベースの描画方法がよく使用されます。

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

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

無料辞書の Wiktionary で、排他的論理和 またはXOR を調べてください。

• XOR について
• XOR 特性の証明と XOR の応用、CS103: コンピューティングの数学的基礎、スタンフォード大学