Exklusiv oder

Das exklusive Oder (XOR) , auch exklusive Disjunktion , exklusive Alternation , logische Nichtäquivalenz oder logische Ungleichheit genannt , ist ein logischer Operator , dessen Negation die logische Bikonditionalaussage ist . Bei zwei Eingaben ist XOR genau dann wahr, wenn sich die Eingaben unterscheiden (eine ist wahr, die andere falsch). Bei mehreren Eingaben ist XOR genau dann wahr, wenn die Anzahl der wahren Eingaben ungerade ist . ^{[ 1 ]}

Die Bezeichnung „exklusives Oder“ rührt daher, dass die Bedeutung von „oder“ mehrdeutig ist, wenn beide Operanden wahr sind. XOR schließt diesen Fall aus. Umgangssprachlich lässt sich XOR beispielsweise so beschreiben: „entweder das eine oder das andere, aber nicht beides“, „entweder das eine oder das andere“ und „A oder B, aber nicht A und B“.

Es wird symbolisiert durch den Präfixoperator ^{[ 2 ] : 16} und durch die Infixoperatoren XOR ( / ˌ ɛ k s ˈ ɔː r / oder / ˈ k s ɔː r / ), EOR , EXOR , , , , ⩛ , , , , und ^. ${\displaystyle J}$${\displaystyle {\dot {\vee }}}$${\displaystyle {\overline {\vee }}}$${\displaystyle {\underline {\vee }}}$${\displaystyle \oplus }$${\displaystyle \nleftrightarrow }$${\displaystyle \not \equiv }$

Die Wahrheitstabelle zeigt , dass die Funktion immer dann „wahr“ ausgibt, wenn sich die Eingaben unterscheiden: ${\displaystyle A\nleftrightarrow B}$

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\nleftrightarrow B}$
F	F	F
F	T	T
T	F	T
T	T	F

Exklusive Disjunktion bedeutet im Wesentlichen „entweder das eine, aber nicht beide und keines von beiden“. Anders ausgedrückt: Die Aussage ist genau dann wahr, wenn eine der beiden Aussagen wahr und die andere falsch ist. Wenn beispielsweise zwei Pferde ein Rennen veranstalten, wird eines der beiden gewinnen, aber nicht beide. Die exklusive Disjunktion , auch als „ oder“ bezeichnet , lässt sich mithilfe der logischen Konjunktion („und“ ), der Disjunktion („oder“ ) und der Negation wie folgt ausdrücken: ${\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}}}$

Die exklusive Disjunktion lässt sich auch folgendermaßen ausdrücken: ${\displaystyle p\nleftrightarrow q}$

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

Diese Darstellung der XOR-Verknüpfung kann beim Aufbau von Schaltungen oder Netzwerken nützlich sein, da sie nur eine Operation und wenige UND - Operationen erfordert. Ein Beweis dieser Identität folgt unten: ${\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}}}$

Manchmal ist es hilfreich, folgendermaßen zu schreiben: ${\displaystyle p\nleftrightarrow q}$

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

oder:

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

Diese Äquivalenz kann hergestellt werden, indem man die De Morganschen Gesetze zweimal auf die vierte Zeile des obigen Beweises anwendet.

Das exklusive Oder ist auch äquivalent zur Negation einer logischen Bikonditionalität , nach den Regeln der materialen Implikation (eine materiale Konditionalität ist äquivalent zur Disjunktion der Negation ihres Antezedens und ihrer Konsequenz) und der materialen Äquivalenz .

Zusammenfassend ergibt sich in mathematischer und ingenieurwissenschaftlicher Notation Folgendes:

${\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}}}$

Wendet man den Geist der De Morganschen Gesetze an , erhält man: $${\displaystyle \neg (p\nleftrightarrow q)\equiv \neg p\nleftrightarrow q\equiv p\nleftrightarrow \neg q.}$$

Obwohl die Operatoren ( Konjunktion ) und ( Disjunktion ) in logischen Systemen sehr nützlich sind, gelingt ihnen eine allgemeinere Struktur in folgender Weise nicht: ${\displaystyle \wedge }$${\displaystyle \lor }$

Die Systeme und sind Monoide , aber keines von beiden ist eine Gruppe . Dies verhindert leider die Kombination dieser beiden Systeme zu größeren Strukturen, wie etwa einem mathematischen Ring . ${\displaystyle (\{T,F\},\wedge )}$${\displaystyle (\{T,F\},\lor )}$

Das System, das das exklusive Oder verwendet, ist jedoch eine abelsche Gruppe . Die Kombination der Operatoren und über den Elementen ergibt den bekannten zweielementigen Körper . Dieser Körper kann jede mit dem System erzielbare Logik darstellen und bietet zusätzlich den Vorteil, dass er über das gesamte Spektrum der algebraischen Analysemethoden für Körper verfügt. ${\displaystyle (\{T,F\},\oplus )}$${\displaystyle \wedge }$${\displaystyle \oplus }$${\displaystyle \{T,F\}}$${\displaystyle \mathbb {F} _{2}}$${\displaystyle (\land ,\lor )}$

Genauer gesagt, wenn man 0 und 1 miteinander assoziiert, kann man die logische "AND"-Operation als Multiplikation mit und die "XOR"-Operation als Addition mit interpretieren : ${\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}}}$

Die Beschreibung einer Booleschen Funktion als Polynom in , unter Verwendung dieser Basis, wird als algebraische Normalform der Funktion bezeichnet . ^{[ 3 ]}${\displaystyle \mathbb {F} _{2}}$

Disjunktionen werden in natürlichen Sprachen oft ausschließlich verstanden . Im Englischen wird das disjunktive Wort „or“ häufig als ausschließlich verstanden, insbesondere in Verbindung mit dem Partikel „either“. Das folgende englische Beispiel würde im Gespräch normalerweise so verstanden werden, dass Mary nicht gleichzeitig Sängerin und Dichterin ist. ^{[ 4 ] [ 5 ]}

1. Mary ist Sängerin oder Dichterin.

Disjunktion kann jedoch auch inklusiv verstanden werden, sogar in Kombination mit „entweder“. Das erste Beispiel unten zeigt beispielsweise, dass „entweder“ sinnvoll mit der Aussage kombiniert werden kann, dass beide Disjunktionen wahr sind. Das zweite Beispiel zeigt, dass die exklusive Schlussfolgerung in Kontexten mit abwärtsgerichteter Implikation verschwindet . Würde Disjunktion in diesem Beispiel als exklusiv verstanden, bliebe die Möglichkeit offen, dass manche Menschen sowohl Reis als auch Bohnen aßen. ^{[ 4 ]}

2. Mary ist entweder Sängerin oder Dichterin oder beides.

3. Niemand aß Reis oder Bohnen.

Beispiele wie die oben genannten haben Analysen der Exklusivitätsfolgerung als pragmatische Konversationsimplikaturen angeregt , die auf der Grundlage einer inklusiven Semantik berechnet werden . Implikaturen sind typischerweise annullierbar und treten in Kontexten mit abwärtsgerichteten Implikationen nicht auf, wenn ihre Berechnung von der Maxime der Quantität abhängt . Einige Forscher haben Exklusivität jedoch als echte semantische Implikation betrachtet und nichtklassische Logiken vorgeschlagen, die diese bestätigen würden. ^{[ 4 ]}

Dieses Verhalten des englischen „or“ findet sich auch in anderen Sprachen. Viele Sprachen verfügen jedoch über disjunktive Konstruktionen, die strikt exklusiv sind, wie beispielsweise das französische „ soit… soit“ . ^{[ 4 ]}

Das Symbol für die exklusive Disjunktion variiert je nach Anwendungsgebiet und hängt sogar davon ab, welche Eigenschaften im jeweiligen Diskussionskontext hervorgehoben werden. Neben der Abkürzung „XOR“ können auch folgende Symbole verwendet werden:

• ${\displaystyle +}$wurde 1847 von George Boole verwendet . ^{[ 6 ]} Obwohl Boole es hauptsächlich auf Klassen anwandte, berücksichtigte er auch den Fall von Aussagen in , und damals war es eine Konjunktion. Darüber hinaus verwendete Boole es ausschließlich. Obwohl diese Verwendung den Zusammenhang zwischen inklusiver Disjunktion (für die heutzutage fast ausschließlich verwendet wird) und exklusiver Disjunktion nicht verdeutlicht und auch zu Verwechslungen mit anderen Verwendungen führen kann, wird sie in einigen klassischen und modernen Lehrbüchern weiterhin beibehalten. ^{[ 7 ] [ 8 ]}${\displaystyle +}$${\displaystyle x,y}$${\displaystyle x+y}$${\displaystyle +}$${\displaystyle \vee }$
• ${\displaystyle {\overline {\vee }}}$wurde von Christine Ladd-Franklin im Jahr 1883 verwendet . ^{[ 9 ]} Streng genommen verwendete Ladd den Begriff, um " ist nicht " oder "Nein ist " auszudrücken, also als Ausschluss, während er implizit die Bedeutung einer exklusiven Disjunktion hat, da der Artikel den Titel "Über die Algebra der Logik" trägt.${\displaystyle A\operatorname {\overline {\vee }} B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle {\overline {\vee }}}$${\displaystyle {\overline {\vee }}}$
• ${\displaystyle \not =}$Der Begriff , der die Negation der Äquivalenz bezeichnet, wurde 1890 von Ernst Schröder verwendet , ^{[ 10 ] : 307} Obwohl die Verwendung von als Äquivalenz bis zu George Boole im Jahr 1847 zurückverfolgt werden kann , ^{[ 6 ]} verwendeten seine Nachfolger, wie Charles Sanders Peirce , Hugh MacColl , Giuseppe Peano und andere, in den 40 Jahren nach Boole nicht wörtlich als Nicht-Äquivalenz, was möglicherweise daran liegt, dass es sich leicht aus Negation und Äquivalenz definieren lässt.${\displaystyle =}$${\displaystyle \not =}$
• ${\displaystyle \circ }$wurde von Giuseppe Peano im Jahr 1894 verwendet : " . Das Zeichen entspricht dem lateinischen aut ; das Zeichen vel . " ^{[ 11 ] : 10} Beachten Sie, dass das lateinische Wort "aut" "ausschließendes Oder" und "vel" "einschließendes Oder" bedeutet und dass Peano es als inklusive Disjunktion verwendet.${\displaystyle a\circ b=a-b\,\cup \,b-a}$${\displaystyle \circ }$${\displaystyle \cup }$${\displaystyle \cup }$
• ${\displaystyle \vee \vee }$wurde 1936 von Izrail Solomonovich Gradshtein (Израиль Соломонович Градштейн) verwendet. ^{[ 12 ] : 76}
• ${\displaystyle \oplus }$wurde 1938 von Claude Shannon verwendet . ^{[ 13 ]} Shannon entlehnte das Symbol als exklusive Disjunktion von Edward Vermilye Huntington im Jahr 1904. ^{[ 14 ]} Huntington wiederum entlehnte das Symbol 1890 von Gottfried Wilhelm Leibniz (das genaue Entstehungsdatum ist nicht bekannt, aber es wurde mit ziemlicher Sicherheit nach 1685 verfasst; 1890 ist das Veröffentlichungsjahr). ^{[ 15 ]} Sowohl Huntington im Jahr 1904 als auch Leibniz im Jahr 1890 verwendeten das Symbol als algebraische Operation. Darüber hinaus nutzte Huntington das Symbol 1904 auch als inklusive Disjunktion (logische Summe) und 1933 erneut als inklusive Disjunktion. ^{[ 16 ]}${\displaystyle +}$
• ${\displaystyle \not \equiv }$, das auch die Negation der Äquivalenz bezeichnet, wurde 1944 von Alonzo Church verwendet . ^{[ 17 ]}
• ${\displaystyle J}$(als Präfixoperator , ) wurde 1949 von Józef Maria Bocheński verwendet . ^{[ 2 ] : 16} Jemand ^{[ 18 ]} könnte fälschlicherweise annehmen, dass Jan Łukasiewicz als Erster den Operator für die exklusive Disjunktion verwendet hat (dieser Irrtum scheint weit verbreitet zu sein), obwohl Łukasiewicz ihn weder 1929 ^{[ 19 ]} noch in anderen Arbeiten verwendete. Tatsächlich führte Bocheński 1949 ein System polnischer Notation ein, das alle 16 binären Konnektive der klassischen Logik benennt. Dieses System ist eine kompatible Erweiterung der Notation von Łukasiewicz aus dem Jahr 1929, und in dem der Operator für die exklusive Disjunktion erstmals auftauchte. Bocheńskis Verwendung von als exklusive Disjunktion hat keine Beziehung zum polnischen "alternatywa rozłączna" von "exklusivem oder" und ist ein Zufall, zu dem die Tabelle auf Seite 16 des Buches von 1949 führt.${\displaystyle J\phi \psi }$${\displaystyle J}$${\displaystyle J}$${\displaystyle J}$
• ^Das Caret-Zeichen wird in verschiedenen Programmiersprachen verwendet, um den bitweisen Exklusiv-Oder-Operator zu bezeichnen, angefangen mit C ^{[ 20 ]} und einschließlich C++ , C# , D , Java , Perl , Ruby , PHP , Python und Rust .
• Die symmetrische Differenz zweier Mengen und , die als deren elementweises exklusives Oder interpretiert werden kann, wurde unterschiedlich als , , oder bezeichnet . ^{[ 21 ]}${\displaystyle S}$${\displaystyle T}$${\displaystyle S\ominus T}$${\displaystyle S\mathop {\triangledown } T}$${\displaystyle S\mathop {\vartriangle } T}$

Kommutativität : ja

${\displaystyle A\oplus B}$	${\displaystyle \Leftrightarrow }$	${\displaystyle B\oplus A}$
	${\displaystyle \Leftrightarrow }$

Assoziativität : ja

${\displaystyle ~A}$	${\displaystyle ~~~\oplus ~~~}$	${\displaystyle (B\oplus C)}$	${\displaystyle \Leftrightarrow }$			${\displaystyle (A\oplus B)}$	${\displaystyle ~~~\oplus ~~~}$	${\displaystyle ~C}$
	${\displaystyle ~~~\oplus ~~~}$		${\displaystyle \Leftrightarrow }$		${\displaystyle \Leftrightarrow }$		${\displaystyle ~~~\oplus ~~~}$

Distributivität :

Das exklusive Oder distributivgesetz distributiv über keine binäre Funktion (nicht einmal über sich selbst), die logische Konjunktion hingegen schon . (Konjunktion und exklusives Oder bilden die Multiplikations- und Additionsoperationen eines Körpers GF(2) , und wie in jedem Körper gehorchen sie dem Distributivgesetz.)${\displaystyle C\land (A\oplus B)=(C\land A)\oplus (C\land B)}$

Idempotenz : nein

${\displaystyle ~A~}$	${\displaystyle ~\oplus ~}$	${\displaystyle ~A~}$	${\displaystyle \Leftrightarrow }$	${\displaystyle ~0~}$	${\displaystyle \nLeftrightarrow }$	${\displaystyle ~A~}$
	${\displaystyle ~\oplus ~}$		${\displaystyle \Leftrightarrow }$		${\displaystyle \nLeftrightarrow }$

Monotonie : nein

${\displaystyle A\rightarrow B}$	${\displaystyle \nRightarrow }$			${\displaystyle (A\oplus C)}$	${\displaystyle \rightarrow }$	${\displaystyle (B\oplus C)}$
	${\displaystyle \nRightarrow }$		${\displaystyle \Leftrightarrow }$		${\displaystyle \rightarrow }$

Wahrheitserhaltend: nein

Wenn alle Eingaben wahr sind, ist die Ausgabe nicht wahr.

${\displaystyle A\land B}$	${\displaystyle \nRightarrow }$	${\displaystyle A\oplus B}$
	${\displaystyle \nRightarrow }$

Falschheitserhaltend: ja

Wenn alle Eingaben falsch sind, ist die Ausgabe falsch.

${\displaystyle A\oplus B}$	${\displaystyle \Rightarrow }$	${\displaystyle A\lor B}$
	${\displaystyle \Rightarrow }$

Walsh-Spektrum : (2,0,0,−2)

Nichtlinearität : 0

Die Funktion ist linear.

Involution:

Exklusiv oder mit einem festgelegten Eingang als Funktion des anderen Eingangs ist eine Involution oder selbstinverse Funktion; die zweimalige Anwendung lässt den variablen Eingang unverändert.

${\displaystyle ~A\oplus B~}$	${\displaystyle ~\oplus ~}$	${\displaystyle ~B~}$	${\displaystyle \Leftrightarrow }$	${\displaystyle ~A~}$
	${\displaystyle ~\oplus ~}$		${\displaystyle \Leftrightarrow }$

Bei Verwendung von Binärwerten für wahr (1) und falsch (0) funktioniert das exklusive Oder genau wie die Addition modulo 2.

Die exklusive Disjunktion wird häufig für bitweise Operationen verwendet. Beispiele:

• 1 XOR 1 = 0
• 1 XOR 0 = 1
• 0 XOR 1 = 1
• 0 XOR 0 = 0
• 1110 2 XOR 1001 2 = 0111 2 (dies entspricht einer Addition ohne Übertrag )

Wie bereits erwähnt, ist die exklusive Disjunktion identisch mit der Addition modulo 2. Daher ist die bitweise exklusive Disjunktion zweier n- Bit-Zeichenketten identisch mit der Standardvektoraddition im Vektorraum . ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$

In der Informatik hat die exklusive Disjunktion verschiedene Anwendungsgebiete:

• Es zeigt an, ob zwei Bits ungleich sind.
• Es handelt sich um einen steuerbaren Bit-Flipper (der Steuereingang bestimmt, ob die Eingangsdaten invertiert werden sollen oder nicht).
• Es gibt an, ob eine ungerade Anzahl von 1-Bits vorhanden ist ( ist genau dann wahr, wenn eine ungerade Anzahl der Variablen wahr ist), was dem Paritätsbit entspricht, das von einer Paritätsfunktion zurückgegeben wird .${\displaystyle A\oplus B\oplus C\oplus D\oplus E}$

In logischen Schaltungen kann ein einfacher Addierer mit einem XOR-Gatter zur Addition der Zahlen und einer Reihe von AND-, OR- und NOT-Gattern zur Erzeugung des Übertragsausgangs realisiert werden .

Bei einigen Computerarchitekturen ist es effizienter, eine Null in einem Register zu speichern, indem man das Register mit sich selbst per XOR verknüpft (Bits, die mit sich selbst per XOR verknüpft werden, sind immer null), als den Wert Null zu laden und zu speichern.

In der Kryptographie wird XOR mitunter als einfache, selbstinverse Mischfunktion verwendet, beispielsweise in One-Time-Pad- oder Feistel- Netzwerksystemen. XOR findet auch breite Anwendung in Blockchiffren wie AES (Rijndael) oder Serpent sowie in deren Implementierungen (CBC, CFB, OFB oder CTR).

Bei einfachen schwellenwertaktivierten künstlichen neuronalen Netzen erfordert die Modellierung der XOR-Funktion eine zweite Schicht, da XOR keine linear trennbare Funktion ist.

XOR kann analog dazu zur Erzeugung von Entropiepools für Hardware-Zufallszahlengeneratoren verwendet werden . Die XOR-Operation erhält die Zufälligkeit, d. h., die XOR-Verknüpfung eines Zufallsbits mit einem nicht-zufälligen Bit ergibt wieder ein Zufallsbit. Mehrere Quellen potenziell zufälliger Daten können mittels XOR kombiniert werden, und die Unvorhersagbarkeit des Ergebnisses ist garantiert mindestens so gut wie die der besten einzelnen Quelle. ^{[ 22 ]}

XOR wird in RAID 3–6 zur Erzeugung von Paritätsinformationen verwendet . Beispielsweise kann RAID die Bytes 100111002 und 011011002 von zwei (oder mehr) Festplatten sichern, indem die genannten Bytes per XOR verknüpft werden. Das Ergebnis ist ( 111100002 ) . Dieses Byte wird dann auf eine andere Festplatte geschrieben. Fällt eine der drei Festplatten aus, kann das verlorene Byte durch XOR-Verknüpfung von Bytes der verbleibenden Festplatten wiederhergestellt werden. Geht beispielsweise die Festplatte mit dem Byte 011011002 verloren , können 100111002 und 111100002 per XOR verknüpft werden , um das verlorene Byte wiederherzustellen. ^{[ 23 ]}

Die XOR-Verknüpfung dient auch dazu, einen Überlauf im Ergebnis einer binären Rechenoperation mit Vorzeichen zu erkennen. Stimmt das linke Bit des Ergebnisses nicht mit der unendlichen Anzahl der Ziffern links davon überein, so ist ein Überlauf aufgetreten. Die XOR-Verknüpfung dieser beiden Bits ergibt im Falle eines Überlaufs eine „1“.

XOR kann verwendet werden, um zwei numerische Variablen in Computern mithilfe des XOR-Swap-Algorithmus zu vertauschen ; dies wird jedoch eher als Kuriosität betrachtet und in der Praxis nicht empfohlen.

XOR-verkettete Listen nutzen die Eigenschaften von XOR, um Speicherplatz bei der Darstellung von doppelt verketteten Listendatenstrukturen zu sparen.

In der Computergrafik werden häufig XOR-basierte Zeichenmethoden verwendet, um Elemente wie Begrenzungsrahmen und Cursor auf Systemen ohne Alphakanäle oder Überlagerungsebenen zu verwalten.

\nleftrightarrowIn LaTeX -basiertem Markdown wird es auch als „nicht Links-Rechts-Pfeil“ ( ) bezeichnet . Neben den ASCII-Codes ist der Operator auch als U+22BB ⊻ XOR ( ⊻ ) und U+2295 ⊕ CIRCLED PLUS ( ⊕, ⊕ ) kodiert, beides Blockoperatoren . ${\displaystyle \nleftrightarrow }$

• Alles über XOR
• Beweise der XOR-Eigenschaften und Anwendungen von XOR, CS103: Mathematische Grundlagen des Rechnens, Stanford University