Exclusieve disjunctie
Uit Wikipedia, de vrije encyclopedie
De exclusieve disjunctie (symbool xor) is een logische operator die resulteert in waar als één van de operanden, maar niet allebei, waar is.
Inhoud |
[bewerk] Definitie
In het Nederlands en andere talen is het gebruik van het woord of anders dan in de logica. De exclusieve disjunctie van proposities A en B betekent A of B, maar niet allebei, zoals in "je kunt je mond houden of de klas uit gaan". 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 één, en slechts één van de operandi WAAR is. De exclusieve disjunctie van propositie A en B wordt gewoonlijk A xor B genoemd, waar "xor" voor "exclusive or" staat en wordt uitgesproken als "eks-or" of "zor".
Voor twee inputs A en B is de waarheidstabel van de operator :
| A | B | A xor B |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | F |
Uit deze tabel kan worden afgeleid dat
- (A xor B) ⇔ (A and not B) or (not A en B) ⇔ (A or B) en (not A or not B) ⇔ (A or B) en not (A and 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.
[bewerk] Symbolen
In de literatuur worden verschillende wiskundige symbolen gebruikt voor exclusieve disjunctie. Naast de afkorting "xor" worden ook volgende notaties gebruikt:
- een plusteken ("+") of een aangepast plusteken, zoals een plusteken in een cirkel ("
"). Dit symbool wordt gebruikt omdat exclusieve disjunctie correspondeert met optelling modulo 2. Daarbij is 0+0 = 1+1 = 0, en 0+1 = 1+0 = 1, men bekomt dit door te stellen dat VALS = 0 en WAAR = 1. De HTML code voor dit symbool is "⊕". - een aangepast "v" symbool, bijvoorbeeld door onderlijnen : "∨". Dit wordt gebruikt omdat exclusieve disjunctie verwant is met gewone inclusieve disjunctie, wat meestal met een gewoon v-symbool ("∨") wordt weergegeven.
- een accent ("^"), zoals in de C of Java programmeertalen.
Eveneens worden verschillende tekstuele notaties gebruikt, zoals "EOR" (wat een alternatieve afkorting is als "xor") en "orr" (analoog aan iff, waaraan het tegengesteld is).
[bewerk] Definitie d.m.v. symbolen
Met bovenstaande symbolen kan met XOR schrijven als:
A ∨ B = (A ∧ !B) ∨ (!A ∧ B) (dit is de definitie)
Na uitwerking leidt men af dat XOR ook kan geschreven worden als:
A ∨ B = !(A ∧ B) ∧ (A ∨ B)
Deze voorstelling van XOR is zeer krachtig, omdat het enkele één negatiebewerking (!) en een klein aantal ∧ en ∨ bewerkingen vergt. Dit is erg praktisch wanneer men een circuit of netwerk wil opbouwen dat de XOR-bewerking implementeert.
Bewijs: A ∨ B = (A ∧ !B) ∨ (!A ∧ B)
= {(A ∧ !B) ∨ !A} ∧ {(A ∧ !B) ∨ B}
= {(A ∨ !A) ∧ (!B ∨ !A)} ∧ {(A ∨ B) ∧ (!B ∧ B)}
= {!A ∨ !B} ∧ {A ∨ B}
= !(A ∧ B) ∧ (A ∨ B)
[bewerk] Associativiteit en commutativiteit
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
[bewerk] Bitsgewijze bewerking
Exclusieve disjunctie wordt vaak gebruikt in bitsgewijze bewerkingen. Bijvoorbeeld:
- 1 xor 1 = 0
- 1 xor 0 = 1
- 1110 xor 1001 = 0111
[bewerk] In computerwetenschappen
In computerwetenschappen wordt exclusieve disjunctie meestal 'exclusieve of' of 'xor' genoemd. Het kent verschillende toepassingen:
- Het geeft aan of twee bits gelijk 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 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 netwerksystemen.
