Alternatywa rozłączna
Alternatywa rozłączna, znana również jako alternatywa wyłączająca, ekskluzja, alternatywa wykluczająca, różnica symetryczna, suma poprzeczna, suma modulo 2, kontrawalencja, XOR, to logiczny funktor zdaniotwórczy (dwuargumentowa funkcja boolowska). W notacji logiki matematycznej jest zazwyczaj zapisywana jako
∨
_
{\displaystyle {\underline {\lor }},}
lub
⊕
{\displaystyle \oplus .}
Alternatywa rozłączna dla zdań
p
∨
_
q
{\displaystyle p{\underline {\lor }}q}
jest prawdziwa wówczas, gdy jedno, i tylko jedno z zdań
p
,
q
{\displaystyle p,q}
jest prawdziwe:
p
∨
_
q
=(
p
∧
¬
q
)
∨
(
¬
p
∧
q
)
,
{\displaystyle p{\underline {\lor }}q=(p\land \neg q)\lor (\neg p\land q),}
co jest równoznaczne z
p
∨
_
q
=(
p
∨
q
)
∧
¬
(
p
∧
q
)
.
{\displaystyle p{\underline {\lor }}q=(p\lor q)\land \neg (p\land q).}
Jest to wyrażenie odpowiadające „albo…, albo…”. Innym symbolem dla tej operacji jest
p
∨
˙
q
.
{\displaystyle p{\dot {\lor }}q.}
Wartości logiczne przyjmują następujące znaczenia: 1 – zdanie prawdziwe; 0 – zdanie fałszywe.
W przypadku użycia funkcji XOR dla większej liczby argumentów, wynik jest prawdziwy, gdy liczba prawdziwych argumentów jest nieparzysta.
Informatyka
W dziedzinie informatyki operację alternatywy rozłącznej wykorzystuje się dla par liczb naturalnych, wykonując operacje na cyfrach zapisów binarnych tych liczb. Jest to rozszerzenie zwykłej logicznej alternatywy wykluczającej na ciągi bitów. Operacja ta wykonywana jest bit po bicie, na przykład:
7 ^ 5 = (w językach C/C++/C#/Java/JavaScript alternatywę rozłączną oznaczamy za pomocą symbolu ^)
= 00001112 ^ 00001012 = (liczby w systemie binarnym)
= 00000102 = (efekt operacji na kolejnych cyfrach)
= 2 (wynik w postaci dziesiętnej).
Sposoby zapisu bramki XOR
(
A
′
B
)
+
(
A
B
′
)
{\displaystyle (A’B)+(AB’)}
(
A
¯
⋅
B
)
+
(
A
⋅
B
¯
)
{\displaystyle ({\overline {A}}\cdot B)+(A\cdot {\overline {B}})}
lub
(
A
¯
B
)
+
(
A
B
¯
)
{\displaystyle ({\overline {A}}B)+(A{\overline {B}})}
== Własności ==
Operacja XOR jest przemienna:
p
∨
_
q
=
q
∨
_
p
{\displaystyle p{\underline {\lor }}q=q{\underline {\lor }}p}
Operacja XOR jest łączna:
(
p
∨
_
q
)
∨
_
r
=
p
∨
_
(
q
∨
_
r
)
{\displaystyle (p{\underline {\lor }}q){\underline {\lor }}r=p{\underline {\lor }}(q{\underline {\lor }}r)}
Istnieje element neutralny; jest nim 0:
p
∨
_
0
=
p
{\displaystyle p{\underline {\lor }}0=p}
Dla każdego elementu istnieje element odwrotny; jest nim ten sam element:
p
∨
_
p
=
0
{\displaystyle p{\underline {\lor }}p=0}
p
∨
_
r
≠
q
∨
_
r
⇔
p
≠
q
{\displaystyle p{\underline {\lor }}r\neq q{\underline {\lor }}r\Leftrightarrow p\neq q}
Oznacza to, że alternatywa rozłączna, jako operacja dwuargumentowa, tworzy na zbiorze, w którym jest określona, strukturę grupy abelowej.
Ponadto:
p
∨
_
q
=
(
¬
p
∧
q
)
∨
(
p
∧
¬
q
)
{\displaystyle p{\underline {\lor }}q=(\lnot p\land q)\lor (p\land \lnot q)}
oraz
¬
(
p
∨
_
q
)
=
(
¬
p
∧
¬
q
)
∨
(
p
∧
q
)
{\displaystyle \lnot (p{\underline {\lor }}q)=(\lnot p\land \lnot q)\lor (p\land q)}
Niech
A
⊆
N
.
{\displaystyle A\subseteq \mathbb {N} .}
Wówczas operacja
d
(
x
,
y
)
=
x
xor
y
{\displaystyle d(x,y)=x\operatorname {xor} y}
wprowadza na zbiorze
A
{\displaystyle A}
metrykę.
Przykłady
Alternatywa rozłączna w zdaniu
(
1
+
1
=
3
)
∨
_
(
3
+
7
=
2
)
{\displaystyle (1+1=3){\underline {\lor }}(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 rozłączna w zdaniu
(
2
+
2
=
4
)
∨
_
(
3
+
1
=
4
)
{\displaystyle (2+2=4){\underline {\lor }}(3+1=4)}
jest fałszywa, ponieważ wartość logiczna obu zdań wynosi 1 (prawda), a – jak wynika z tablicy prawdy – jest ona prawdziwa tylko wtedy, gdy jedno z zdań składowych jest prawdziwe (tzn. ma wartość logiczną równą 1).
Alternatywa rozłączna
(
2
+
2
=
4
)
∨
_
(
3
+
5
=
4
)
{\displaystyle (2+2=4){\underline {\lor }}(3+5=4)}
jest prawdziwa, ponieważ tylko jedno zdanie
(
2
+
2
=
4
)
{\displaystyle (2+2=4)}
jest prawdziwe, natomiast drugie
(
3
+
5
=
4
)
{\displaystyle (3+5=4)}
już nie.
Zobacz też
dysjunkcja
