Исклучителна дисјункција

Од Википедија, слободна енциклопедија

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

Логичка порта ИЛЛИ
Логичка порта ИЛЛИ

Содржина

[уреди] Дефиниција

Кај многу природни јазици (вклучувајќи го македонскиот), толкувањето на поимот „или“ бара извесна доза на внимателност. Исклучителната дисјункција на два исказа, (p, q), значи дека p е точно или q е точно, но не и двете. На пример, нормалната намера на исказите од типот на „Ќе ги почитуваш правилата или ќе бидеш дисквалификуван“ е да се утврди дека точно само еден од условите може да биде вистинит. Меѓутоа во логиката, значењето на зборот „или“ под основно е вклучителна дисјункција, која значи дека најмалку една од алтернативите е вистинита (точна). латинскиот, јазик како и некои други имаат различни зборови за различните значења на ова „или“.

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

Таблицата на вистинитост за p ИЛЛИ q е следнава:

Таблица на вистинитост: Исклучителна дисјункција
p q p ИЛЛИ q
Слика:nete.png Слика:nete.png Слика:nete.png
Слика:nete.png T T
T Слика:nete.png T
T T Слика:nete.png

Следниве еквиваленти можат да бидат изведени:

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

[уреди] Алтернативни знаци

Знакот за исклучителна дисјункција варира во зависност на неговата употреба, па дури и зависи од својствата кои се нагласуваат во даден котекст или дискусија. Покрај кратенката „ИЛЛИ“, можеме да ги видиме и следниве знаци:

  • Знак плус (+). Ова е математички издржано заради тоа што исклучителната дисјункција соодветствува на собирање модула 2, која ја има следнава таблица на собирање, која е воочливо изоморфична со онаа погоре:
Операциона таблица: Износ Модула 2
p q p + q
0 0 0
0 1 1
1 0 1
1 1 0
  • Уппотребата на знакот плус ја има додатната предност во тоа што сите обични алгебарски својства или прстени и полиња можат да се користат без додатни потешкотии.
  • Знакот плус, кој е модифициран на некој начин, како на пример со заокружување (⊕}. Меѓутоа употребата на овој знак е дискутабилна заради тоа што истиот се поклопува со математичкиот знак за директен износ на алгебарски структури.
  • Знак за вклучителна дисјункција (∨) кој е модифициран на некој начин, како со потцртување ().
  • Знакот Image:xor.png.

[уреди] Еквивалентни изразувања

Исклучителната дисјункција p + q\! може да се изрази како конјункција (∧), дисјункција (∨), и негација (¬) вака:

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

Исклучителната дисјункција p + q\! може исто така да се изрази на следниов начин:

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

Оваа представа на ИЛЛИ може да биде корисна за правење на коло или мрежа, бидејќи има само една ¬ операција и мал број на ∧ и ∨ операции. Доказот на овој идентитет е даден подолу:

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

Понекогаш тоа се користи за пишување на p ИЛЛИ q на следниов начин:

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

Ова еквиваленција може да се воспостави со примена на Де Моргановите закони два пати на четвртата линија на доказот погоре.

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

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


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

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

Овој оддел ги користи следниве знаци:

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

[уреди] Битова операција

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

  • 1 илли 1 = 0
  • 1 илли 0 = 1
  • 1110 илли 1001 = 0111 (ова е исто што и собирање без пренос)