Disjuncţie exclusivă

De la Wikipedia, enciclopedia liberă

Dezvoltare

Unul sau mai mulţi wikipedişti lucrează în acest moment la extinderea acestui articol.

Din această cauză este posibil să existe deficienţe în formatare sau conţinut. Vă rugăm să nu faceţi modificări în timp ce este afişat acest anunţ. În schimb puteţi face sugestii în pagina de discuţii a articolului.

Dacă vedeţi în istoricul articolului că a trecut mai mult de o săptămână de la ultima editare, puteţi şterge acest anunţ şi modifica articolul.

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.

[modifică] Asociativitate şi commutativitate

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}

[modifică] 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}

[modifică] 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 (\Z/2\Z)^n.