Disjuncție exclusivă

Disjuncția exclusivă, cunoscută și ca sau exclusiv și notată prin XOR sau EOR, este o operație logică asupra doi operanzi din care rezultă o valoare logică de adevărat dacă și numai dacă unul dintre operanzi, dar nu amândoi, are valoarea adevărat.

Definiție

În multe limbaje naturale, printre care și limba română, interpretarea cuvântului "sau" necesită un anumit grad de atenție. Disjuncția exclusivă a două perechi de propoziții, (p, q), înseamnă că p este adevărată sau q este adevărată, dar nu ambele. De exemplu, intenția normală a frazei "Poți urma regulile sau poți fi descalificat" este să arate faptul că numai una din condiții este adevărată. Spre deosebire, în logică înțelesul cuvântului "sau" este disjuncția inclusivă, care semnifică faptul că cel puțin una din alternative este adevărată. Alte limbi, precum latina, pot avea cuvinte diferite pentru tipuri diferite de "sau".

Disjuncția exclusivă este o operație asupra două valori logice, de obicei valorile a două propoziții, care produce o valoare de adevărat dacă numai unul dintre operanzi este adevărat.

Tabelul de adevăr al lui p XOR q (scris și p + q, p ⊕ q, sau p ≠ q) este următorul:

**Disjuncție exclusivă**
p	q	p XOR q
F	F	F
F	A	A
A	F	A
A	A	F

Pot fi deduse echivalenețele următoare:

{\begin{matrix}p+q&=&(p\land \lnot q)&\lor &(\lnot p\land q)\\\\&=&(p\lor q)&\land &(\lnot p\lor \lnot q)\\\\&=&(p\lor q)&\land &\lnot (p\land q)\end{matrix}}

Operația XOR generalizată sau n-ară este adevărată atunci când numărul de biți 1 este impar.

Simboluri alternative

Simbolul utilizat pentru disjuncția exclusivă variază de la un câmp de aplicare la altul, și depinde chiar și de proprietățile evidențiate într-un anumit context de discuție. Pe lângă abrevierea "XOR", oricare dintre simbolurile următoare pot fi întâlnite:

un semn plus (+). Acesta are sens matematic, deoarece disjuncția exclusivă corespunde adunării modulo 2, care are următorul tabel de adunare, evident izomorf cu cel de mai sus:

**Adunare modulo 2**
p	q	p + q
0	0	0
0	1	1
1	0	1
1	1	0

Utilizarea simbolului plus are avantajul că toate proprietățile algebrice ordinare ale inelelor și câmpurilor matematice pot fi folosite fără alte adăugiri. Dar semnul plus este folosit și pentru disjuncția inclusivă în unele sisteme de notație.
Un semn plus care este modificat într-un fel, așa cum este încercuit (⊕). Acest mod de folosire respectă faptul că același simbol plus se folosește în matematică pentru suma directă a structurilor algebrice.
Un simbol al disjuncției inclusive (∨) care este modificat într-un fel, așa cum este subliniat (∨) sau cu un punct deasupra ( ${\dot {\vee }}$ ).
În unele limbaje de programare, precum C, C++ și Java, se folosește simbolul ^ pentru operația XOR. Acesta nu este folosit în afara limbajelor de programare, deoarece poate fi ușor de confundat cu alte sensuri atribuite lui.
Simbolul .
În simbologia IEC, un sau exclusiv este marcat prin "=1".

Expresii echivalente

Disjuncția exclusivă $p+q\!$ poate fi exprimată în funcție de conjuncție (∧), disjuncție (∨) sau negație (¬) după cum urmează:

{\begin{matrix}p+q&=&(p\land \lnot q)\lor (\lnot p\land q)\end{matrix}}

Disjuncția exclusivă $p+q\!$ poate fi de asemenea exprimată în felul următor:

{\begin{matrix}p+q&=&\lnot (p\land q)\land (p\lor q)\end{matrix}}

Reprezentarea lui XOR poate fi utilă atunci când se construiește un circuit sau o rețea, deoarece conține o singură operație ¬ și un număr mic de operații ∧ și ∨. Demonstrația acestei identități este scrisă mai jos:

{\begin{matrix}p+q&=&(p\land \lnot q)&\lor &(\lnot p\land q)\\&=&((p\land \lnot q)\lor \lnot p)&\land &((p\land \lnot q)\lor q)\\&=&((p\lor \lnot p)\land (\lnot q\lor \lnot p))&\land &((p\lor q)\land (\lnot q\lor q))\\&=&(\lnot p\lor \lnot q)&\land &(p\lor q)\\&=&\lnot (p\land q)&\land &(p\lor q)\end{matrix}}

Uneori este folositor să se scrie p XOR q sub forma următoare:

{\begin{matrix}p+q&=&\lnot ((p\land q)\lor (\lnot p\land \lnot q))\end{matrix}}

Se poate ajunge la această echivalență aplicând Legile lui De Morgan de două ori la a patra linie a demonstrației de mai sus.

Asociativitate și comutativitate

Din perspectiva izomorfismului dintre adunarea modulo 2 și disjuncția exclusivă, este evident că XOR este o operație asociativă și comutativă. De aceea, parantezele pot fi omise pentru operații succesive, iar ordinea termenilor este indiferentă. De exemplu, avem următoarele ecuații:

{\begin{matrix}p+q&=&q+p\\\\(p+q)+r&=&p+(q+r)&=&p+q+r\end{matrix}}

Proprietăți

Această secțiune folosește următoarele simboluri:

{\begin{matrix}0&=&{\mbox{fals}}\\1&=&{\mbox{adevarat}}\\\lnot p&=&{\mbox{non}}\ p\\p+q&=&p\ {\mbox{xor}}\ q\\p\land q&=&p\ {\mbox{si}}\ q\\p\lor q&=&p\ {\mbox{sau}}\ q\end{matrix}}

Ecuațiile următoare derivă din axiomele logice:

{\begin{matrix}p+0&=&p\\p+1&=&\lnot p\\p+p&=&0\\p+\lnot p&=&1\\\\p+q&=&q+p\\p+q+p&=&q\\p+(q+r)&=&(p+q)+r\\p+q&=&\lnot p+\lnot q\\\lnot (p+q)&=&\lnot p+q&=&p+\lnot q\\\\p+(\lnot p\land q)&=&p\lor q\\p+(p\land \lnot q)&=&p\land q\\p+(p\lor q)&=&\lnot p\land q\\\lnot p+(p\lor \lnot q)&=&p\lor q\\p\land (p+\lnot q)&=&p\land q\\p\lor (p+q)&=&p\lor q\end{matrix}}

Operații pe biți

Disjuncția exclusivă este des utilizată pentru operații pe biți. Exemple:

1 xor 1 = 0
1 xor 0 = 1
1110 xor 1001 = 0111 (aceasta este echivalentă cu adunarea fără transport)

Așa cum s-a notat mai sus, deoarece disjuncția exclusivă este echivalentă cu adunarea modulo 2, disjuncția exclusivă pe biți a două șiruri de n biți este identică cu adunarea vectorilor în spațiul vectorial $(\mathbb {Z} /2\mathbb {Z} )^{n}$ .

Informatică

În informatică, disjuncția exclusivă are mai multe utilizări:

Spune dacă doi biți sunt diferiți.
Este un schimbător de biți opțional.
Spune dacă există un număr impar de biți 1 (A ⊕ B ⊕ C ⊕ D ⊕ E este adevărat dacă și numai dacă există un număr impar de variabile care sunt adevărate).

În circuitele logice, un sumator simplu poate fi construit cu o poartă XOR pentru a aduna numerele și o serie de porți AND, OR și NOT pentru a crea transportul.

În unele arhitecturi de calculatoare, este mai eficient să se memoreze un zero într-un registru prin aplicarea operației XOR asupra registrului cu el însuși (operația XOR aplicată unui bit cu el însuși dă întotdeauna zero) decât încărcarea și memorarea valorii zero. În rețelele neuronale simple cu prag activat, modelarea funcției 'xor' necesită un al doilea strat, deoarece 'xor' nu este o funcție liniar separabilă.

Disjuncția exclusivă este folosită uneori ca o funcție de amestecare simplă în criptografie, de exemplu, în sisteme cu rețele Feistel.

XOR este folosit în RAID 3–6 pentru crearea informației de paritate. De exemplu, RAID poate crea rezerve din octeții 10011100 și 01101100 de pe două (sau mai multe) hard drive-uri prin aplicarea operației XOR (11110000) și scrierea rezultatului pe alt hard drive. În acest fel, dacă unul dintre hard-uri se defectează, octetul pierdut poate fi recreat aplicând XOR pe octeții din celelalte hard-uri. Dacă hard-ul conținând 01101100 este pierdut, 10011100 și 11110000 pot fi supuse lui XOR pentru a recupera octetul pierdut.

XOR este de asemenea folosit pentru detectarea depășirilor în rezultatul operațiilor aritmetice binare cu semn. Dacă bitul cel mai din stânga care este reținut nu este același cu infinitatea de numere de la stânga, înseamnă că a avut loc o depășire. Aplicarea XOR asupra celor doi biți dă "one" dacă este depășire.

XOR poate fi folosit pentru interschimbarea a două variabile numerice, utilizând Algoritmul interschimbării XOR; totuși, acesta este considerat ca fiind doar o curiozitate și nu este recomandat a se folosi în practică.

Vezi și