XOR-Verknüpfung

Eine exklusiv-ODER-Verknüpfung (auch XOR, EOR, Antivalenz oder Kontravalenz) ist ein Begriff aus der Aussagenlogik. Die Gesamtaussage ist dann wahr, wenn entweder die erste Aussage oder die zweite Aussage wahr ist, aber nicht beide.

Im Deutschen entspricht die Formulierung "Entweder A oder B" am besten dem Ausdruck "A XOR B", also der XOR-Verknüpfung der Aussagen A und B. Generell dürfte oder jedoch immer als XOR interpretiert werden; die Aussage, "Xaver geht zum Einkaufen oder in den Zoo" wird wohl von der Mehrheit der Sprecher als wahr empfunden werden, wenn Xaver entweder das eine oder das andere gemacht hat; hat Xaver jedoch beides gemacht, wird man üblicherweise annehmen, die Aussage sei falsch gewesen, obwohl diese Aussage im Sinne der Aussagenlogik wahr ist.

Praktisch entspricht dies der Addition zweier Bits modulo 2.

XOR-Verknüpung zweier Bits:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

Der Vorteil der XOR-Verknüpfung ist, dass sie umkehrbar (symmetrisch) ist. Dies wird u.a. in der Kryptographie (dadurch kann beim Verschlüsseln die gleiche Funktion verwendet werden, wie beim Entschlüsseln) und beim RAID-System ausgenutzt:

101 XOR 011 = 110
110 XOR 011 = 101
110 XOR 101 = 011

Anwendungsbeispiel in der Kryptografie

Der Klartext 101 wird mit dem Schlüssel 11 XOR-verknüpft und wir erhalten das Ergebnis 110 (erste Zeile). Zum Entschlüsseln wird nun 110 wieder mit dem Schlüssel 11 XOR-verknüpft und wir erhalten wieder unseren Klartext 101 (zweite Zeile).

Anwendungsbeispiel im RAID-System

Wir haben zwei Bitfolgen 101 und 11, aus denen mittels XOR-Verknüpfung die Parität gebildet wird: 110 (erste Zeile). Geht nun die erste Bitfolge (101) verloren, so können wir sie wiederherstellen, indem wir die zweite Bitfolge (11) mit der Parität XOR-verknüpfen (zweite Zeile).

Siehe auch: XOR-Gatter Aussagenlogik