Искључива дисјункција

Из Википедије, слободне енциклопедије
Venn0110.svg
Венов дијаграм за ~A \oplus B

OR али AND није XOR

Venn 0110 1001.svg
Венов дијаграм за ~A \oplus B \oplus C

Venn 0110 0110.svg ~\oplus~ Venn 0000 1111.svg ~\Leftrightarrow~ Venn 0110 1001.svg

Логички оператор искључива дисјункција, такође позната као искључиво ИЛИ, ексклузивна дисјункција и обележавана као ЕКСИЛИ (енг. XOR) или ⊕, је врста логичке дисјункције над два операнда, чији је резултат тачан само ако један од исказа има вредност тачан.

Другачије речено, искључива дисјункција је логична операција над две логичке вредности, који даје вредност тачан само у случајевима када се вредности операнда разликују.

Табела истинитости[уреди]

Табела истинитости за ~A \oplus B (такође се пише као A\, \mathrm{XOR}\, B или A \neq B) је следећа:

УЛАЗ ИЗЛАЗ
A B A ЕКСИЛИ B
0 0 0
0 1 1
1 0 1
1 1 0

Еквиваленти, елиминација и увођење[уреди]

Следећи еквиваленти могу бити изведени, написани са логичким операторима, у математичкој и инжењерској нотацији:

\begin{matrix}
p \oplus q & = & (p \land \lnot q) & \lor & (\lnot p \land q) & = & p\overline{q} + \overline{p}q \\
\\
      & = & (p \lor q) & \land & (\lnot p \lor \lnot q) & = & (p+q)(\overline{p}+\overline{q}) \\
\\
      & = & (p \lor q) & \land & \lnot (p \land q) & = & (p+q)(\overline{pq})
\end{matrix}

Искључива дисјункција p \oplus q може да се изрази као логичка конјункција (\wedge), дисјункција (\lor) и негација (\lnot) на следећи начин:

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

Искључива дисјункција p \oplus q, такође, може да се изрази на следећи начин:

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

Понекад је корисно да се p \oplus q пише на следећи начин:

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

Алтернативни симболи[уреди]

Симболи за искључиву дисјункцију зависе од његове употребе, и од својства који су истакнути у датом контексту. Поред скраћенице ЕКСИЛИ, било који од следећих симбола се могу користити:

  • Знак плус (+). У математици, искључива дисјункција одговара сабирању по модилу 2, која има следећу табелу сабирања:
Сабирање по модулу 2
p q p + q
0 0 0
0 1 1
1 0 1
1 1 0
  • Употреба знака плус има додатну предност у томе што се алгебраска својства математичког прстена и поља могу користити без додатних потешкоћи.
  • Заокружен знак плус (\oplus).
  • Симбол укључива дисјункција (\lor), промењена на неки начин, као што је подвучено (\underline\lor) и са тачком изнад (\dot\vee).

Својства[уреди]

Овај одељак користи следеће симболе:

\begin{matrix}
0         & = & \mbox{false}     \\
1         & = & \mbox{true}      \\
\lnot p   & = & \mbox{not}\ p    \\
p + q     & = & p\ \mbox{xor}\ q \\
p \land q & = & p\ \mbox{and}\ q \\
p \lor  q & = & p\ \mbox{or} \ q
\end{matrix}

Следеће једначине следе из логичке аксиоме:

\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}

Асоцијативност и комутативности[уреди]

Са изоморфизмичке тачке гледишта између сабирања по модула 2 и искључиве дисјункције, јасно је да је ЕКСИЛИ и асоцијативна и комутативна операција. Тако се заграда може изоставити у узастопним операцијама не правећи разлику у резултату. На пример, имамо следеће једначине:

\begin{matrix}
p + q & = & q + p \\
\\
(p + q) + r & = & p + (q + r) & = & p + q + r
\end{matrix}

Рачунарство[уреди]

Оператори над битовима[уреди]

Искључива дисјункција се често користи у операторима над битовима. Примери:

  • 1 ексили 1 = 0
  • 1 ексили 0 = 1
  • 0 ексили 0 = 0
  • 1110 ексили 1001 = 0111