Vizualizare sursă pentru „Disjuncție exclusivă”

'''Disjuncția exclusivă''', cunoscută și ca '''sau exclusiv''' și notată prin '''XOR''' sau '''EOR''', este o [[operație logică]] asupra doi [[operand|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''.

[[Fișier:XOR gate symbol.jpg|thumb|right|150px|[[Poartă logică]] XOR]]

== 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ție|disjuncția inclusivă]]'', care semnifică faptul că cel puțin una din alternative este adevărată. Alte limbi, precum [[limba latină|latina]], pot avea cuvinte diferite pentru tipuri diferite de "sau".

'''Disjuncția exclusivă''' este o [[operație logică|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.

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

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Disjuncție exclusivă'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p XOR q
|-
| F || F || F
|-
| F || A || A
|-
| A || F || A
|-
| A || A || F
|}
<br />

Pot fi deduse echivalenețele următoare:

: <math>\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}</math>

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 [[adunare|adunării]] [[aritmetică modulară|modulo]] 2, care are următorul tabel de adunare, evident [[izomorfism|izomorf]] cu cel de mai sus:

{| align="center" border="1" cellpadding="8" cellspacing="0" style="background:lightcyan; font-weight:bold; text-align:center; width:45%"
|+ '''Adunare modulo 2'''
|- style="background:paleturquoise"
! style="width:15%" | p
! style="width:15%" | q
! style="width:15%" | p + q
|-
| 0 || 0 || 0
|-
| 0 || 1 || 1
|-
| 1 || 0 || 1
|-
| 1 || 1 || 0
|}
<br />

* Utilizarea simbolului plus are avantajul că toate proprietățile algebrice ordinare ale [[inel (matematică)|inelelor]] și [[câmp (matematică)|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 ''[[sumă directă|suma directă]]'' a structurilor algebrice.
* Un simbol al disjuncției inclusive (∨) care este modificat într-un fel, așa cum este subliniat (<u>∨</u>) sau cu un punct deasupra (<math>\dot\vee</math>).
* În unele [[limbaj de programare|limbaje de programare]], precum [[Limbajul C|C]], [[C++]] și [[Limbajul Java|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 [[Fișier:X-or.svg|20px]].
* În simbologia IEC, un sau exclusiv este marcat prin "=1".

== Expresii echivalente ==

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

: <math>\begin{matrix}
p + q & = & (p \land \lnot q) \lor (\lnot p \land q)
\end{matrix}</math>

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

: <math>\begin{matrix}
p + q & = & \lnot (p \land q) \land (p \lor q)
\end{matrix}</math>

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:

: <math>\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}</math>

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

: <math>\begin{matrix}
p + q & = & \lnot ((p \land q) \lor (\lnot p \land \lnot q))
\end{matrix}</math>

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 [[izomorfism]]ului dintre adunarea [[modulo]] 2 și disjuncția exclusivă, este evident că XOR este o operație [[asociativitate|asociativă]] și [[comutativitate|comutativă]]. De aceea, parantezele pot fi omise pentru operații succesive, iar ordinea termenilor este indiferentă. De exemplu, avem următoarele ecuații:

: <math>\begin{matrix}
p + q & = & q + p \\
\\
(p + q) + r & = & p + (q + r) & = & p + q + r
\end{matrix}</math>

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

: <math>\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}</math>

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

: <math>\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}</math>

== 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țiu vectorial|spațiul vectorial]] <math>(\Z/2\Z)^n</math>.

== Informatică ==

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

* Spune dacă doi biți sunt diferiți.
* Este un [[negație|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 [[eficiență algoritmică|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țea Feistel|rețele Feistel]].

XOR este folosit în [[Redundant array of independent disks|RAID]] 3–6 pentru crearea informației de paritate. De exemplu, RAID poate crea rezerve din octeții <code>10011100</code> și <code>01101100</code> de pe două (sau mai multe) hard drive-uri prin aplicarea operației XOR (<code>11110000</code>) ș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 <code>01101100</code> este pierdut, <code>10011100</code> și <code>11110000</code> 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 [[Interschimbare XOR|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 ==
* [[Conector logic]]
* [[Conjuncție logică]]
* [[Disjuncție logică]]
* [[Egalitate logică]]
* [[Implicație logică]]
* [[NAND logic]]
* [[NOR logic]]
* [[Negație]]
* [[ȘI-NU logic]]

[[Categorie:Logică]]
[[Categorie:Operații binare]]
[[Categorie:Algebră booleană]]
[[Categorie:Logică Boole]]