Exclusieve disjunctie

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen
Venndiagram van de exclusieve disjunctie (rood) van twee verzamelingen

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

Definitie[bewerken | brontekst bewerken]

In het Nederlands en andere talen is het gebruik van het woord of anders dan in de logica. De exclusieve disjunctie van de proposities en betekent of , 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 en wordt gewoonlijk xor genoemd, waarin "xor" staat voor exclusive or, uitgesproken als "eks-or" of "zor". De standaardnotatie is:

Voor twee inputs en is de waarheidstabel van de operator xor:

T T F
T F T
F T T
F F F

Uit deze tabel kan worden afgeleid dat

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[bewerken | brontekst bewerken]

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

  • Het standaardsymbool is , een aangepast -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 (""). Dit symbool wordt gebruikt omdat exclusieve disjunctie correspondeert met optelling modulo 2. Stelt men ONWAAR = 0 en WAAR = 1, dan is A xor B hetzelde als A + B mod 2. De HTML code voor dit symbool is "⊕".
  • een accent ("^"), zoals in de C of Java programmeertalen.

Associativiteit en commutativiteit[bewerken | brontekst bewerken]

Voor meer dan twee ingangen, kan xor toegepast worden op de eerste twee ingangen, en vervolgens kan het resultaat achtervolgens met xor gecombineerd worden met elke volgende ingang:

(A xor B xor C xor D) (((A xor B) xor C) xor D)

Omdat xor associatief is, is de volgorde van de ingangen van geen belang, hetzelfde resultaat wordt bekomen onafhankelijk van de associatie.

De xor-operator is ook commutatief en dus is de volgorde van de operanden van geen belang:

A xor B B xor A

Bitsgewijze bewerking[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

Logische XOR-poort

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 B C D 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[bewerken | brontekst bewerken]