Exklusive Disjunktion

Die exklusive Disjunktion, auch als Kontravalenz, Antivalenz oder ausschließendes Oder bekannt, ist ein logischer Operator, der zwei Aussagen verknüpft und nur dann einen wahren Wert zurückgibt, wenn genau eine der beiden Aussagen wahr ist, aber nicht beide. Sie wird mit dem Symbol ⊕ (manchmal auch ⊻) dargestellt und als „entweder … oder …“ gelesen.

Im Gegensatz zur inklusiven Disjunktion (∨), die auch dann wahr ist, wenn beide Aussagen wahr sind, schließt die exklusive Disjunktion diese Möglichkeit aus. Das heißt, sie ist ausschließlich dann wahr, wenn die beiden Aussagen unterschiedliche Wahrheitswerte haben.

Einige Beispiele für die exklusive Disjunktion sind:

• „Das Licht ist entweder an oder aus“: Eine Lampe kann nicht gleichzeitig an und aus sein. Wenn das eine wahr ist, ist das andere automatisch falsch.
• „Dieses Tier ist entweder ein Hund oder eine Katze“: Wenn das Tier ein Hund ist, kann es keine Katze sein und umgekehrt. Für ein und dasselbe Individuum können nicht beide Möglichkeiten gleichzeitig zutreffen.
• „Der Schlüssel ist entweder in der Schublade oder außerhalb“: Der Schlüssel kann nicht an beiden Orten gleichzeitig sein; er muss sich in genau einem der beiden Zustände befinden.
• Wenn p: „9 ist gerade“ und q: „9 ist eine Primzahl“, dann ist p ⊕ q „die Zahl 9 ist entweder gerade oder eine Primzahl“. Diese Aussage ist falsch, da p und q denselben Wahrheitswert haben, nämlich beide falsch.

Wahrheitstafel

Wie bereits erwähnt, ist die exklusive Disjunktion nur dann wahr, wenn genau eine der beiden Aussagen wahr ist, und falsch, wenn beide wahr oder beide falsch sind. Dieses Verhalten wird in der folgenden Wahrheitstafel dargestellt:

p	q	p ⊕ q
W	W	F
W	F	W
F	W	W
F	F	F

Beispiele zur Veranschaulichung der Wahrheitstafel der exklusiven Disjunktion:

• „Entweder 7 ist ungerade oder 7 ist eine Primzahl“: Beide Aussagen sind wahr (7 ist ungerade und eine Primzahl), daher ist die exklusive Disjunktion falsch.
• „4 ist gerade ⊕ 4 ist eine Primzahl“: Die erste Aussage ist wahr (4 ist gerade) und die zweite ist falsch (4 ist keine Primzahl), daher ist die exklusive Disjunktion wahr.
• „Entweder 9 ist eine Primzahl oder 10 ist positiv“: Die erste Aussage ist falsch und die zweite ist wahr (9 ist keine Primzahl, aber 10 ist positiv), folglich ist die zusammengesetzte Aussage wahr.
• „Entweder 15 ist gerade oder 15 ist eine Primzahl“: Beide Aussagen sind falsch (15 ist weder gerade noch eine Primzahl), daher ist die exklusive Disjunktion falsch.

Eigenschaften

Die exklusive Disjunktion erfüllt eine Reihe von Eigenschaften, die wir im Folgenden betrachten werden.

1) Kommutativität: Die Reihenfolge der Aussagen ändert das Ergebnis nicht.

p ⊕ q ≡ q ⊕ p

2) Assoziativität: Wenn mehr als zwei Aussagen durch eine exklusive Disjunktion verknüpft sind, ändert die Gruppierung das Ergebnis nicht.

(p ⊕ q) ⊕ r ≡ p ⊕ (q ⊕ r)

3) Distributivität über die Konjunktion: Die exklusive Disjunktion ist distributiv über die Konjunktion.

p ∧ (q ⊕ r) ≡ (p ∧ q) ⊕ (p ∧ r)

4) Neutrales Element: Eine Kontradiktion (eine immer falsche Aussage, F) wirkt als neutrales Element oder Identität.

p ⊕ F ≡ p

5) Inverses oder selbstnegierendes Element: Jede Aussage ist ihr eigenes Inverses.

p ⊕ p ≡ F

6) Beziehung zur Negation: Die Negation eines der beiden Operanden ist äquivalent zur Negation des gesamten Ausdrucks.

p ⊕ ¬q ≡ ¬(p ⊕ q)

¬p ⊕ q ≡ ¬(p ⊕ q)

7) Kürzungsregel: Wenn p ⊕ q ≡ p ⊕ r, dann kann p „gekürzt“ werden, woraus folgt, dass q ≡ r. 

8) Äquivalenzen zu anderen Operatoren: Die exklusive Disjunktion kann auf verschiedene Weisen durch die Basisoperatoren (∧, ∨, ¬) ausgedrückt werden:

p ⊕ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q)

(Dies ist die Definition selbst: „p und nicht q, oder nicht p und q“)

p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q)

(„Das eine oder das andere, aber nicht beide“)

Die exklusive Disjunktion ist die Negation des Bikonditionals: Während p ↔ q wahr ist, wenn p und q denselben Wahrheitswert haben, ist p ⊕ q wahr, wenn sie unterschiedliche Werte haben.

p ⊕ q ≡ ¬(p ↔ q)

Exklusive Disjunktion in der Mengenlehre

In der Mengenlehre hat die exklusive Disjunktion ihr direktes Äquivalent in der symmetrischen Differenz: eine Operation, die zwei Mengen zu einer neuen Menge kombiniert, welche die Elemente enthält, die zu genau einer der beiden Mengen gehören, aber nicht zu beiden.

Beispiele

• Gegeben seien A = {1, 2, 3} und B = {2, 3, 4}. Ihre symmetrische Differenz ist A Δ B = {1, 4}. Die Elemente 2 und 3, die zu beiden Mengen gehören, werden vom Ergebnis ausgeschlossen.
• Wenn C = {a, e, i} und D = {e, o, u}, dann ist C Δ D = {a, i, o, u}. Nur der Vokal „e“ wird ausgeschlossen, da er in beiden Mengen vorkommt.

Eigenschaften der symmetrischen Differenz:

• Kommutativität: A Δ B = B Δ A
• Assoziativität: (A Δ B) Δ C = A Δ (B Δ C)
• Distributivität der Schnittmenge: A ∩ (B Δ C) = (A ∩ B) Δ (A ∩ C)
• Neutrales Element: A Δ ∅ = A (∅ ist die leere Menge).
• Selbstinversivität: A Δ A = ∅
• Beziehung zu Vereinigung und Schnittmenge: A Δ B = (A ∪ B) \ (A ∩ B)

Exklusive Disjunktion in logischen Schaltungen

In der Digitalelektronik wird die exklusive Disjunktion physisch durch das XOR-Gatter implementiert. Diese Komponente empfängt zwei Eingangssignale und erzeugt einen Ausgang, der dem Verhalten des Operators ⊕ entspricht.

Das XOR-Gatter gibt den Wert 1 (wahr) nur dann aus, wenn seine Eingänge unterschiedlich sind, und 0 (falsch), wenn beide Eingänge gleich sind. Diese Eigenschaft macht es grundlegend für Operationen, bei denen die Erkennung von Unterschieden entscheidend ist.

Eingang A	Eingang B	Ausgang (A XOR B)
0	0	0
0	1	1
1	0	1
1	1	0

In der Programmierung ist die exklusive Disjunktion in mehreren Sprachen direkt durch den Operator „^“ vertreten. Dieses Symbol wird konsistent in Sprachen wie C, C++, Java und Python verwendet, um die XOR-Operation zwischen zwei booleschen Werten oder Bits durchzuführen. Zum Beispiel gibt der Ausdruck „a ^ b“ nur dann wahr zurück, wenn die Werte von „a“ und „b“ unterschiedlich sind.