Exclusieve disjunctie

De exclusieve disjunctie (symbool xor) is een logische operator die resulteert in waar als een van de operanden waar is, maar ze niet allebei waar zijn. Het wordt, bij verzamelingen die corresponderen met het waar zijn van een operand, ook het symmetrisch verschil genoemd.

Definitie

In het Nederlands en andere talen is het gebruik van het woord of anders dan in de logica. De exclusieve disjunctie van de proposities $A$ en $B$ betekent $A$ of $B$ , maar niet allebei, zoals in "iemand kan spreken of zwijgen". In de logica betekent het woord 'of' meestal de andere, inclusieve disjunctie.

Formeler is exclusieve disjunctie een logische operator. De operatie levert het resultaat WAAR op als een, en slechts een van de operandi WAAR is. De exclusieve disjunctie van de proposities $A$ en $B$ wordt gewoonlijk $A$ xor $B$ genoemd, waarin "xor" staat voor exclusive or, uitgesproken als "eks-or" of "zor". De standaardnotatie is:

A\mathop {\underline {\lor }} B

Voor twee inputs $A$ en $B$ is de waarheidstabel van de operator xor:

$A$	$B$	$A\mathop {\underline {\lor }} B$
T	T	F
T	F	T
F	T	T
F	F	F

Uit deze tabel kan worden afgeleid dat

A\mathop {\underline {\lor }} B\Longleftrightarrow (A\land \neg B)\lor (\neg A\land B)\Longleftrightarrow (A\lor B)\land (\neg A\lor \neg B)\Longleftrightarrow (A\lor B)\land \neg (A\land B)

In het algemeen hangt het resultaat van xor af van het aantal WAAR operanden, als er een oneven aantal WAAR operanden is dan zal het resultaat WAAR zijn, anders zal het VALS zijn.

Symbolen

In de literatuur worden verschillende wiskundige symbolen gebruikt voor exclusieve disjunctie. Naast de afkorting "xor" worden ook volgende notaties gebruikt:

Het standaardsymbool is ${\underline {\lor }}$ , een aangepast $\lor$ -symbool. Dit wordt gebruikt omdat exclusieve disjunctie verwant is met gewone inclusieve disjunctie.
Een plusteken ("+") of een aangepast plusteken, zoals een plusteken in een cirkel (" $\oplus$ "). Dit symbool wordt gebruikt omdat exclusieve disjunctie correspondeert met optelling modulo 2. Stelt men ONWAAR = 0 en WAAR = 1, dan is A xor B hetzelfde als A + B mod 2. De HTML code voor dit symbool is "⊕".
een accent ("^"), zoals in de C of Java programmeertalen.

Commutativiteit en associativiteit

Exclusieve disjunctie is commutatief:

A\ \mathrm {xor} \ B=B\ \mathrm {xor} \ A

en ook associatief:

(A\ \mathrm {xor} \ B)\ \mathrm {xor} \ C=A\ \mathrm {xor} \ (B\ \mathrm {xor} \ C)

Voor meer dan twee operandi kan xor toegepast worden op de eerste twee en vervolgens kan het resultaat achtereenvolgens gecombineerd worden met elke volgende operand. Vanwege de commutativiteit is de volgorde van combineren van geen belang.

((A\ \mathrm {xor} \ B)\ \mathrm {xor} \ C)\ \mathrm {xor} \ D=A\ \mathrm {xor} \ B\ \mathrm {xor} \ C\ \mathrm {xor} \ D

De combinatie

A_{1}\ \mathrm {xor} \ldots \ \mathrm {xor} \ A_{n}

is WAAR, als een oneven aantal van de operandi $A_{i}$ WAAR is.

Bitsgewijze bewerking

In principe is de 'exclusieve disjunctie' dus niet anders dan de ongelijkheidsoperatie voor 'Boolese' variabelen - wat de operatie populair maakt is dat veel computers bitsgewijze exclusieve disjunctie ondersteunen - waar WAAR gerepresenteerd als 1 ondersteld wordt. Bijvoorbeeld:

1 xor 1 = 0
1 xor 0 = 1
1110 xor 1001 = 0111

In computerwetenschappen

In computerwetenschappen wordt exclusieve disjunctie meestal 'exclusieve of' of 'xor' genoemd. Het kent verschillende toepassingen:

Het geeft aan of twee bits ongelijk zijn.
Het is een gestuurde bit-flipper: de beslissende ingang geeft aan of de data van de andere ingang al dan niet moet geïnverteerd worden.
Het geeft aan of een sequentie een oneven aantal 1 bits bevat, immers A ${\underline {\lor }}$ B ${\underline {\lor }}$ C ${\underline {\lor }}$ D ${\underline {\lor }}$ E is WAAR als en slechts als een even aantal van de variabelen WAAR is.

Op sommige computerarchitecturen is het efficiënter om een 0 op te slaan in een register door de bestaande registerwaarde te 'xor-en' met zichzelf (de xor bewerking van bits met zichzelf levert altijd 0), in plaats van het laden en opslaan van een nulwaarde. Omdat xor logisch gezien complexer is dan 'or' en 'and', vereist het neurale netwerk een extra laag bewerkingen.

Exclusieve-of wordt soms gebruikt als een eenvoudige mengfunctie in cryptografie, bijvoorbeeld bij one-time-pad of Feistel-systemen (bvb. DES, AES).

Zie ook