XOR-Verknüpfung
aus Wikipedia, der freien Enzyklopädie
Eine exklusiv-ODER-Verknüpfung (auch XOR, EOR, Modulo-2 Addition, 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. Als Formelzeichen wird meist der Ausdruck xor oder das Zeichen ⊕ verwendet.
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, "Tom geht zum Einkaufen oder in den Zoo" wird wohl von der Mehrheit der Sprecher als wahr empfunden werden, wenn Tom entweder das eine oder das andere gemacht hat; hat Tom 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- ist die Summe eine gerade Zahl ergibt sich 0, ist sie ungerade 1
XOR-Verknüpfung zweier Bits: 0 ⊕ 0 = 0 0 ⊕ 1 = 1 1 ⊕ 0 = 1 1 ⊕ 1 = 0
Die Umkehrung der XOR-Funktion ist die XNOR-Verknüpfung.
Die XOR-Verknüpfung ist assoziativ und kommutativ.
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
[Bearbeiten] Anwendungsbeispiel in der Kryptografie
Der Klartext 101 wird mit dem Schlüssel 011 XOR-verknüpft und wir erhalten das Ergebnis 110 (erste Zeile). Zum Entschlüsseln wird nun 110 wieder mit dem Schlüssel 011 XOR-verknüpft und wir erhalten wieder unseren Klartext 101 (zweite Zeile).
Die XOR-Verschlüsselung ist die sicherste bekannte Verschlüsselungsmethode – unter der Prämisse, dass der Schlüssel vorher absolut abhörsicher ausgetauscht wurde – und ist damit auch nur theoretisch sicher. Ein Nachteil dieser Methode ist, dass der Schlüssel dann auch mindestens die Länge der zu übertragenden Nachricht haben muss und auch nur einmal verwendet werden kann. Siehe auch: One-Time-Pad
[Bearbeiten] Anwendungsbeispiel im RAID-System
Wir haben zwei Bitfolgen 101 und 011, 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 (011) mit der Parität XOR-verknüpfen (zweite Zeile).
Siehe auch: XOR-Gatter XNOR-Gatter Aussagenlogik
