排他的または

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

排他的または
XOR
排他的論理和のベン図
真理値表
論理ゲートXOR ANSI.svg
通常の形式
選言的
接続詞
ゼガルキン多項式
ポストの格子
0-保存はい
1-保存いいえ
単調いいえ
アフィンはい
ベン図

排他的論理和または排他的論理和は、引数が異なる場合にのみ真になる論理演算です(一方が真で、もう一方が偽)。[1]

これは、接頭辞演算子J [2]中置演算子XOR/ ˌɛksˈɔːr /または/ ˈzɔːr /EOREXORによって表さます 、およびXORの否定論理双条件であり、2つの入力が同じである場合にのみtrueを返します。

両方のオペランドが真の場合、「または」の意味があいまいになるため、「排他的論理和」という名前が付けられます。排他的論理和演算子はその場合を除外します。これは、「どちらか一方であるが両方ではない」と考えられることがあります。これは「AまたはBですが、AおよびBではありません」と書くことができます。

結合法則であるため、奇数個の引数が真である場合にのみ真であるn項演算子と見なすことができます。つまり XOR b XOR ...はXOR( ab、...) として扱われる場合があります。

真理値表

XORによって結合された左側の引数。これはバイナリウォルシュ行列です(アダマールコードを参照)。

A XOR B 真理値表は、入力が異なる場合は常にtrueを出力することを示しています。

XOR真理値表
入力 出力
A B
0 0 0
0 1 1
1 0 1
1 1 0
  • 0、false
  • 1、true

同等性、排除、および導入

排他的論理和は、本質的に「どちらか一方を意味しますが、両方もなしも意味しません」。言い換えると、一方が真でもう一方が偽の場合にのみ、ステートメントは真になります。たとえば、2頭の馬がレースをしている場合、2頭のうちの一方がレースに勝ちますが、両方は勝ちません。排他的論理和 また論理積(「論理積」、)、論理和( "論理または"、)、および否定) 次のように:

排他的論理和次のように表現することもできます。

XORのこの表現は、回路またはネットワークを構築するときに役立つ場合があります。これは、XORが1つしかないためです。操作と少数の操作。この身元の証明を以下に示します。

書くと便利な場合があります次のように:

また:

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

排他的論理和は、論理的双条件の否定と同等であり、重要な含意の規則(重要な条件付きは、その前件とその結果の否定の論理和と同等です)と重要な同等性です。

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

否定

ド・モルガンの法則の精神を適用することができます。

現代代数との関係

オペレーター 接続詞)と論理和)は論理システムで非常に役立ちます。次のように、より一般化可能な構造に失敗します。

システムモノイドですが、どちらもグループではありません。これにより、残念ながら、これら2つのシステムを組み合わせて数学的な環などのより大きな構造にすることができなくなります

ただし、排他的論理和を使用するシステム アーベルです演算子の組み合わせ要素の上有名なフィールドを生成します このフィールドは、システムで取得可能な任意のロジックを表すことができますまた、フィールド用の代数解析ツールの武器の追加の利点があります。

より具体的には、0と1を使用すると、論理「AND」演算を上の乗算として解釈できます。および追加としての「XOR」演算

この基底を使用してブールシステムを記述することは、代数正規形と呼ばれます。

自然言語の排他的論理和

論理和は、自然言語でのみ理解されることがよくあります英語では、論理和語「または」は、特に助詞「どちらか」とともに使用される場合、排他的に理解されることがよくあります。以下の英語の例は、通常、メアリーが歌手でも詩人でもないことを意味するものとして会話で理解されます。[3] [4]

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

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

2.メアリーは、歌手または詩人、あるいはその両方です。
3.誰もご飯も豆も食べませんでした。

上記のような例は、包括的セマンティクスに基づいて計算された語用論的 会話の含意としての排他性推論の分析を動機付けました。含意は通常キャンセル可能であり、計算が数量の最大値に依存する場合、下向きの含意のコンテキストでは発生しませんただし、一部の研究者は、排他性を善意の意味論的含意として扱い、それを検証する非古典論理を提案しました。[3]

この英語の「または」の動作は、他の言語でも見られます。ただし、多くの言語には、フランス語のsoit ... soitのように、堅牢に排他的な論理和構造があります。[3]

代替記号

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

  • +、プラス記号。これには、数学的なフィールドの通常の代数的特性のすべてを、さらに苦労することなく使用できるという利点があります。ただし、プラス記号は、一部の記譜法では包括的論理和にも使用されます。排他的論理和は2を法とする加算 対応し、次の加算テーブルがあり、上記のものと明らかに同型であることに注意してください。
     
0 0 0
0 1 1
1 0 1
1 1 0
  • 、変更されたプラス記号。この記号は、数学でも代数的構造の直和に使用されます
  • JJpqのように
  • 包括的論理和記号()など、何らかの方法で変更されたもの
  • ^caret 、 CC ++C#DJavaPerlRubyPHPPythonなどのいくつかのプログラミング言語で使用され、ビット単位のXOR演算子を示します。キャレットの他の使用法と混同されやすいため、プログラミングコンテキスト以外では使用されません
  • X-or.svg、時々次のように書かれます
    • > <
    • >-<
  • = 1、IECシンボル体系で

プロパティ

可換性:はい
        
Venn0110.svg          Venn0110.svg
結合性:はい
        
ヴェン01010101.svg Venn 0011 1100.svg          ヴェン01101001.svg          ヴェン01100110.svg Venn 0000 1111.svg
分配法則
排他的論理和は任意のバイナリ関数(それ自体でさえも)に分散しませんが、論理積は排他的論理和に分散します。(論理積と排他的論理和、またはフィールド GF(2)の乗算と加算の演算を形成し、他のフィールドと同様に、分配法則に従います。)
べき等:いいえ
                 
Venn01.svg Venn01.svg          Venn00.svg          Venn01.svg
単調性:いいえ
        
ヴェン10111011.svg          ヴェン10111101.svg          ヴェン01011010.svg Venn 0011 1100.svg
真実を保存する:いいえ
すべての入力が真の場合、出力は真ではありません。
        
Venn0001.svg          Venn0110.svg
虚偽の保存:はい
すべての入力がfalseの場合、出力はfalseです。
        
Venn0110.svg          Venn0111.svg
ウォルシュスペクトル:(2,0,0、−2)
非線形:0
関数は線形です。

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

コンピュータサイエンス

ビット演算

ニンバー加算は、バイナリ表現の排他または非負の整数です。これは、のベクトル加算でもあります

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

  • 1 XOR 1 = 0
  • 1 XOR 0 = 1
  • 0 XOR 1 = 1
  • 0 XOR 0 = 0
  • 1110 2 XOR 1001 2 = 0111 2 (これはキャリーなしの加算と同等です

上記のように、排他的論理和は2を法とする加算と同一であるため、2つのnビット文字列のビット単位の排他的論理和はベクトル空間での加算の標準ベクトルと同一です。

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

  • 2ビットが等しくないかどうかを示します。
  • これはオプションのビットフリッパーです(決定入力はデータ入力を反転するかどうかを選択します)。
  • 1ビットの奇数があるかどうかを示します(奇数の変数が真である場合にのみ真です)。

論理回路では、数値を加算するためのXORゲートと、キャリー出力を作成するための一連のAND、OR、およびNOTゲートを使用して 単純な加算器を作成できます。

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

単純なしきい値でアクティブ化されるニューラルネットワークでは、XORは線形分離可能関数ではないため、XOR関数のモデリングには2番目の層が必要です。

排他的論理和-または、暗号化の単純なミキシング機能として使用されることもあります。たとえば、ワンタイムパッドFeistelネットワークシステムで使用されます。[要出典]

排他的論理和-または、AES(Rijndael)やSerpentなどのブロック暗号やブロック暗号の実装(CBC、CFB、OFB、CTR)でも頻繁に使用されます。

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

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

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

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

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

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

エンコーディング

ラテックスベースのマークダウン(\ nleftrightarrow)では「左右矢印ではない」(\ nleftrightarrow)とも呼ばれます)。ASCIIコードとは別に、演算子はU +22BB⊻XOR HTML )およびU + 2295⊕CIRCLEDPLUS HTML )で、両方ともブロック数学演算子でエンコードされます。 &#8891;  &veebar; &#8853;  &CirclePlus;, &oplus;

も参照してください

ノート

  1. ^ Germundsson、Roger; ワイスタイン、エリック。「XOR」MathWorldWolframResearch 2015年6月17日取得
  2. ^ クレイグ、エドワード、編 (1998)、哲学のRoutledge百科事典、vol。10、テイラーアンドフランシス、p。496、ISBN 9780415073103
  3. ^ a b c d Aloni、Maria(2016)、"Disjunction"、in Zalta、Edward N.(ed。)、The Stanford Encyclopedia of Philosophy(Winter 2016 ed。)、Metaphysics Research Lab、Stanford University 、Retrieved 2020-09 -03
  4. ^ Jenningsは、「または」という言葉には排他的な意味があると言っている多くの著者を引用しています。第3章「「または」の最初の神話」: Jennings、RE(1994)を参照してください。論理和の系譜ニューヨーク:オックスフォード大学出版局。
  5. ^ Davies、Robert B(2002年2月28日)。「排他的論理和(XOR)およびハードウェア乱数ジェネレーター」(PDF)2013年8月28日取得
  6. ^ ノーベル、リッカード(2011年7月26日)。「RAID5が実際にどのように機能するか」2017年3月23日取得

外部リンク