Disjuncţie exclusivă

De la Wikipedia, enciclopedia liberă

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.

Poartă logică XOR

[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 folsoeş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".

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