Αποκλειστική διάζευξη

Στην μαθηματική λογική, η αποκλειστική διάζευξη είναι ο λογικός τελεστής που δίνει αποτέλεσμα αληθές αν και μόνο αν ακριβώς ένας από τους όρους στους οποίους ενεργεί είναι αληθής.

Για να δηλώσουν αποκλειστική διάζευξη χρησιμοποιούνται τα σύμβολα XOR και ${\displaystyle \oplus }$. Η αποκλειστική διάζευξη μπορεί να γραφεί με χρήση μόνο των λογικών τελεστών σύζευξη (ή "ένωση" ή "λογική άθροιση") ${\displaystyle \wedge }$, διάζευξη ${\displaystyle \lor }$, και άρνηση ${\displaystyle \neg }$ ως εξής:^{[1]:147-148[2]:21[3]:17}

${\displaystyle {\begin{matrix}p\oplus q&=&(p\land \lnot q)\lor (\lnot p\land q)\end{matrix}}}$

Πίνακας αλήθειας

Παρακάτω δίνεται ο πίνακας αλήθειας της πρότασης ${\displaystyle p\oplus q}$:^[4]:11[5]:18

${\displaystyle p}$	${\displaystyle q}$	${\displaystyle \oplus }$
0	0	0
0	1	1
1	0	1
1	1	0

όπου 0 αντιστοιχεί στην τιμή ψευδής και 1 στην τιμή αληθής.

Ιδιότητες

Η αποκλειστική διάζευξη ικανοποιεί τις παρακάτω ιδιότητες:^{[1]: 147-148 [6]:24}

• Ικανοποιεί την ${\displaystyle x\oplus x=0}$.

Απόδειξη

Προκύπτει από την πρώτη και την τελευταία γραμμή του πίνακα ορισμού.

• Ικανοποιεί την ${\displaystyle x\oplus 1=\neg x}$.

Απόδειξη

Προκύπτει από την δεύτερη και την τελευταία γραμμή του πίνακα ορισμού.

• Ικανοποιεί την αντιμεταθετική ιδιότητα ${\displaystyle x\oplus y=y\oplus x}$.

Απόδειξη

Όταν ${\displaystyle x=y}$ τότε ${\displaystyle x\oplus y=y\oplus x=0}$. Όταν ${\displaystyle x\neq y}$ τότε ${\displaystyle x\oplus y=y\oplus x=1}$.

• Ικανοποιεί την προσεταιριστική ιδιότητα ${\displaystyle (x\oplus y)\oplus z=x\oplus (y\oplus z)}$ και γι' αυτό οι παρενθέσεις συνήθως παραλείπονται.

Απόδειξη

${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x\oplus (y\oplus z)}$ ${\displaystyle (x\oplus y)\oplus z}$ 0 0 0 ${\displaystyle 0\oplus 0=0}$ ${\displaystyle 0\oplus 0=0}$ 0 0 1 ${\displaystyle 0\oplus 1=1}$ ${\displaystyle 0\oplus 1=1}$ 0 1 0 ${\displaystyle 1\oplus 0=1}$ ${\displaystyle 0\oplus 1=1}$ 0 1 1 ${\displaystyle 1\oplus 1=0}$ ${\displaystyle 0\oplus 0=0}$ 1 0 0 ${\displaystyle 1\oplus 0=1}$ ${\displaystyle 1\oplus 0=1}$ 1 0 1 ${\displaystyle 1\oplus 1=0}$ ${\displaystyle 1\oplus 1=0}$ 1 1 0 ${\displaystyle 0\oplus 0=0}$ ${\displaystyle 1\oplus 1=0}$ 1 1 1 ${\displaystyle 1\oplus 0=1}$ ${\displaystyle 0\oplus 1=1}$

• Η διάζευξη και η σύζευξη δεν μπορούν να υλοποιηθούν με την χρήση μόνο τελεστών αποκλειστικής διάζευξης.^[7]:199

Γενικεύσεις

Η αποκλειστική διάζευξη ${\displaystyle n}$ εισόδων ${\displaystyle x_{1},\ldots ,x_{n}}$ ορίζεται ως ${\displaystyle x_{1}\oplus x_{2}\oplus \ldots \oplus x_{n}}$ και είναι ισοδύναμη με την συνάρτηση^{[1]: 148 [6]: 25}

${\displaystyle s(x_{1},\ldots ,x_{n})={\begin{cases}1&{\text{αν υπάρχει μονός αριθμός 1 μεταξύ των }}x_{1},\ldots ,x_{n}\\0&{\text{διαφορετικά}}.\end{cases}}}$

Δείτε επίσης

• Λογική διάζευξη
• Λογική σύζευξη
• Άλγεβρα Μπουλ