Alternatywa wykluczająca

Alternatywa wykluczająca (inne używane nazwy: alternatywa rozłączna, różnica symetryczna, suma poprzeczna, suma modulo 2, kontrawalencja, XOR, exclusive or, EOR) – logiczny funktor zdaniotwórczy (dwuargumentowa funkcja boolowska) . Różnica symetryczna zdań $p \underline\or q$ jest prawdziwa wtedy i tylko wtedy, gdy dokładnie jedno ze zdań $p, q$ jest prawdziwe:

$p \underline\or q = (p \and \neg q) \or (\neg p \and q)$

Odpowiada wyrażeniu „albo ... albo ...”. Innym oznaczeniem jest $p \dot\or q$ .

Tablica prawdy dla alternatywy wykluczającej:
$p \!$	$q \!$	$p \underline\or q \!$
0	0	0
0	1	1
1	0	1
1	1	0

gdzie:

1 – zdanie prawdziwe

0 – fałszywe

Przy użyciu funkcji XOR dla więcej niż dwóch argumentów wynik jest prawdziwy, gdy nieparzysta liczba argumentów jest prawdą.

Informatyka [edytuj]

W informatyce operację alternatywy wykluczającej 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. Np.:

7 ^ 5 = (w językach C/C++/Java alternatywę wykluczającą oznaczamy za pomocą symbolu ^)

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

= 0000010₂ = (efekt operacji na kolejnych cyfrach)

= 2 (wynik w postaci dziesiętnej)

Własności [edytuj]

Operacja XOR jest przemienna:

$p \dot\or q = q \dot\or p$

Operacja XOR jest łączna:

$(p \dot\or q) \dot\or r = p \dot\or (q \dot\or r)$

Istnieje element neutralny; jest nim 0:

$p \dot\or 0 = p$

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

$p \dot\or p = 0$

$p \dot\or r \neq q \dot\or r \Leftrightarrow p \neq q$

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

Ponadto:

$p \dot\or q = (\lnot p\and q) \or (p\and\lnot q)$

oraz

$\lnot(p \dot\or q) = (\lnot p\and\lnot q) \or (p\and q)$

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

Przykłady [edytuj]

Alternatywa wykluczająca w zdaniu $(1+1=3) \underline\or (3+7=2)$ jest fałszywa, ponieważ wartość logiczna obu zdań to 0 (fałsz), a jak wynika z tablicy prawdy w takim przypadku różnica symetryczna jest fałszywa.
Alternatywa wykluczająca w zdaniu $(2+2=4) \underline\or (3+1=4)$ jest fałszywa, gdyż wartość logiczna zdania 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 (tj. posiada wartość logiczną równą 1).
Alternatywa wykluczająca $(2+2=4) \underline\or (3+5=4)$ jest prawdziwa, gdyż tylko jedno zdanie ( $2+2=4$ ) jest prawdziwe, z kolei drugie ( $3+5=4$ ) już nie.