Disjuncţie exclusivă

De la Wikipedia, enciclopedia liberă

Salt la: Navigare, căutare

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.

Poartă logică XOR

Cuprins

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

[modifică] 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 discjuncţ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 Image:xor.png.
  • În simbologia IEC, un sau exclusiv este marcat prin "=1".

[modifică] 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) & \and & ((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.

[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.

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

[modifică] Vezi şi

Adus de la http://ro.wikipedia.org/wiki/Disjunc%C5%A3ie_exclusiv%C4%83
Unelte personale