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

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

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

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

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

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

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

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

**Таблица на вистинитост: Исклучителна дисјункција**
p	q	p ИЛЛИ q

	T	T
T		T
T	T

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

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

Уппотребата на знакот плус ја има додатната предност во тоа што сите обични алгебарски својства или прстени и полиња можат да се користат без додатни потешкотии.
Знакот плус, кој е модифициран на некој начин, како на пример со заокружување (⊕}. Меѓутоа употребата на овој знак е дискутабилна заради тоа што истиот се поклопува со математичкиот знак за директен износ на алгебарски структури.
Знак за вклучителна дисјункција (∨) кој е модифициран на некој начин, како со потцртување (∨).
Знакот .

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

Исклучителната дисјункција $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}$