Alternatywa rozłączna

Alternatywa rozłączna, alternatywa wyłączająca, alternatywa wykluczająca, ekskluzja, różnica symetryczna, suma poprzeczna, suma modulo 2, kontrawalencja, XOR – logiczny funktor zdaniotwórczy (dwuargumentowa funkcja boolowska). W logice matematycznej zapisywana najczęściej jako ${\displaystyle {\underline {\lor }}}$, ${\displaystyle {\dot {\lor }}}$ lub ${\displaystyle \oplus }$. Alternatywa rozłączna zdań ${\displaystyle p\,{\underline {\lor }}\,q}$ jest prawdziwa wtedy, gdy jedno i tylko jedno ze zdań ${\displaystyle p}$oraz ${\displaystyle q}$, jest prawdziwe:

${\displaystyle p\,{\underline {\lor }}\,q\,=\,(p\,\land \neg \,q)\,\lor \,(\neg \,p\,\land \,q)}$ co jest równoznaczne z

${\displaystyle p\,{\underline {\lor }}\,q\,=\,(p\,\lor \,q)\,\land \neg \,(p\,\land \,q)}$

Odpowiada wyrażeniu „albo..., albo...”. Innym oznaczeniem jest ${\displaystyle p\,{\dot {\lor }}\,q}$

Tablica prawdy dla alternatywy rozłącznej

${\displaystyle p}$	${\displaystyle q}$	${\displaystyle p{\underline {\lor }}q}$
0	0	0
0	1	1
1	0	1
1	1	0

gdzie: 1 – zdanie prawdziwe; 0 – zdanie fałszywe

Funkcja XOR dla dowolnej liczby argumentów jest funkcją parzystości, tj. przyjmuje wartość 1, gdy nieparzysta liczba argumentów ma wartość 1; w szczególności dla 2 argumentów XOR przyjmuje wartość 1, gdy dokładnie jeden jej argument ma wartość 1.

Informatyka

W informatyce operację alternatywy rozłącznej stosuje się do par liczb naturalnych wykonując operacje na cyfrach zapisów binarnych tych liczb. Jest to zwykła logiczna alternatywa wykluczająca rozszerzona na ciągi bitów. Wykonuje się ją bit po bicie, na przykład:

7 ^ 5 = (w językach C/C++/C#/Java/JavaScript alternatywę rozłączną oznaczamy za pomocą symbolu ^)

= 0000111₂ ^ 0000101₂ =   (liczby w systemie binarnym)

= 0000010₂ =    (efekt operacji na kolejnych cyfrach)

= 2  (wynik w postaci dziesiętnej).

Sposoby zapisu bramki XOR

• ${\displaystyle (A'B)+(AB')}$
• ${\displaystyle ({\overline {A}}\cdot B)+(A\cdot {\overline {B}})}$ lub ${\displaystyle ({\overline {A}}B)+(A{\overline {B}})}$

Własności

• Operacja XOR jest przemienna:

${\displaystyle p{\underline {\lor }}q=q{\underline {\lor }}p}$

• Operacja XOR jest łączna:

${\displaystyle (p{\underline {\lor }}q){\underline {\lor }}r=p{\underline {\lor }}(q{\underline {\lor }}r)}$

• Istnieje element neutralny; jest nim 0:

${\displaystyle p{\underline {\lor }}0=p}$

• Dla każdego elementu istnieje element odwrotny; jest nim ten sam element:

${\displaystyle p{\underline {\lor }}p=0}$

• ${\displaystyle p{\underline {\lor }}r\neq q{\underline {\lor }}r\Leftrightarrow p\neq q}$

Oznacza to, że alternatywa rozłączna jako działanie dwuargumentowe zadaje na zbiorze, w którym jest określona, strukturę grupy abelowej.

• Ponadto:

  ${\displaystyle p{\underline {\lor }}q=(\lnot p\land q)\lor (p\land \lnot q)}$

  oraz

  ${\displaystyle \lnot (p{\underline {\lor }}q)=(\lnot p\land \lnot q)\lor (p\land q)}$

• Niech ${\displaystyle A\subseteq \mathbb {N} .}$ Wówczas operacja ${\displaystyle d(x,y)=x\operatorname {xor} y}$ wprowadza na zbiorze ${\displaystyle A}$ metrykę.

Przykłady

• Alternatywa rozłączna w zdaniu ${\displaystyle (1+1=3){\underline {\lor }}(3+7=2)}$ jest fałszywa, gdyż wartość logiczna obu zdań to 0 (fałsz), a – jak wynika z tablicy prawdy – w takim przypadku różnica symetryczna jest fałszywa.
• Alternatywa rozłączna w zdaniu ${\displaystyle (2+2=4){\underline {\lor }}(3+1=4)}$ jest fałszywa, ponieważ wartość logiczna zdania zarówno pierwszego, jak i drugiego to 1 (prawda), a – jak wynika z tablicy prawdy – jest ona prawdziwa wtedy, gdy tylko jedno zdanie składowe jest prawdziwe (to znaczy posiada wartość logiczną równą 1).
• Alternatywa rozłączna ${\displaystyle (2+2=4){\underline {\lor }}(3+5=4)}$ jest prawdziwa, jako że tylko jedno zdanie ${\displaystyle (2+2=4)}$ jest prawdziwe, natomiast drugie ${\displaystyle (3+5=4)}$ już nie.

Zobacz też

Zobacz hasła XOR i albo w Wikisłowniku

• dysjunkcja

Przypisy