Виключна диз'юнкція

Рис. 1 Графік побітового виключає «або»

Виключна диз'юнкція (також операція XOR, додавання за модулем два) — логічна операція, що приймає значення «істина» тоді і тільки тоді коли значення «істина» має рівно один з її операндів. Виключна диз'юнкція є логічною і бітовою операцією, а також запереченням логічної еквівалентності. У випадку двох змінних результат виконання операції є істинним тоді і тільки тоді, коли лише один з аргументів є істинним. Для функції трьох і більше змінних результат виконання операції буде істинним тільки тоді, коли аргументів рівних 1 на заданому наборі буде непарна кількість. Така операція природним чином виникає в кільці відрахувань по модулю 2, звідки і походить назва операції.

Додавання за модулем 2 слід відрізняти від простого додавання, яке відповідає звичайному логічному "або", тобто логічній диз'юнкції.

Позначення [ред.]

Запис може бути префіксний («польський запис») - знак операції ставиться перед операндами, інфіксний - знак операції ставиться між операндами і постфіксний - знак операції ставиться після операндів. При числі операндів більше двох префіксний та постфіксний запис економніше інфіксного запису. Найчастіше зустрічаються наступні варіанти запису:

$\oplus_2(a,b), ~a$ ^ $~b, ~a \oplus b, a \oplus_2 b, a +_2 b,$ a ≠ b, $a\ne b, (a,b)\oplus_2, a ~XOR~ b$

У таблиці символів Юнікод є символ для додавання за модулем 2 (CIRCLED PLUS) - U +2295 ( ⊕ ).

Виключну диз'юнкцію деколи задають через інші логічні операції, наприклад:

$a \oplus b = \neg (a \leftrightarrow b)$

$a \oplus b = (a \and \neg b) \or (\neg a \and b)$

Булева алгебра [ред.]

У булевій алгебрі додавання за модулем 2 - це функція двох, трьох і більше змінних (вони ж - операнди, вони ж - аргументи функції). Змінні можуть приймати значення з множин $~\{0, 1\}$ . Результат також належить множині $~\{0, 1\}$ . Обчислення результату проводиться по простому правилу, або по таблиці істинності. Замість значень $~0, 1$ може використовуватися будь-яка інша пара підходящих символів, наприклад $~false, true$ або $~F, T$ або «хибність», «істина», але при цьому необхідно довизначити старшинство, наприклад, $~true > false$ .

Таблиці істинності:

Для бінарного додавання за модулем 2 (застосовується в двійкових напівсуматорахах):

$~a$	$~b$	$~a \oplus b$
$~0$	$~0$	$~0$
$~0$	$~1$	$~1$
$~1$	$~0$	$~1$
$~1$	$~1$	$~0$

Правило: результат дорівнює $~0$ , якщо обидва операнди рівні; у всіх інших випадках результат дорівнює $~1$ .

Для тернарного додавання за модулем 2 (застосовується в двійкових повних суматорів):

X	Y	Z	⊕(X,Y,Z)
0	0	0	0
1	0	0	1
0	1	0	1
1	1	0	0
0	0	1	1
1	0	1	0
0	1	1	0
1	1	1	1

Визначення [ред.]

Діаграма Венна для операції $A \oplus B$

Таблиця істинності виглядає таким чином:

$~A$	$~B$	$A \oplus B$
хибність	хибність	хибність
хибність	істина	істина
істина	хибність	істина
істина	істина	хибність

Результат застосування виключної диз'юнкції такий самий як і від додавання за модулем 2. Тому і саму операцію часто називають додаванням за модулем 2.

Відповідною операцією в теорії множин є симетрична різниця множин.

Властивості [ред.]

асоціативність

$a \oplus (b \oplus c) \equiv (a \oplus b) \oplus c$

комутативність

$a \oplus b \equiv b \oplus a$

дистрибутивність

$a \land (b \oplus c) \equiv (a \land b) \oplus (a \land c)$

Абелева група [ред.]

елемент 0 є нейтральним:

$a \oplus 0 = a$

кожен елемент є обернений сам до себе:

$a \oplus a = 0$

Таким чином $(\{1, 0\}, \oplus)$ є абелевою групою. Разом із операцією $\wedge$ також утворюється поле Галуа $F_2$ .

Інші властивості [ред.]

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

Функціональна повнота [ред.]

Множина операцій $\{ \oplus, \to \}$ є функціонально повною:

$\lnot a \equiv a \to (a \oplus a)$

$\lnot a \equiv a \oplus (a \to a)$

$a \lor b \equiv (\lnot a) \rightarrow b$

$a \land b \equiv \lnot (a \rightarrow \lnot b)$

Виключна диз'юнкція в природніх мовах [ред.]

Виключна диз'юнкція найближче відповідає українському «або …, або … ». Твердження або А, або В є справедливим коли справедливе А чи В, але не обоє одночасно.

У природній мові операція «складання по модулю» еквівалентна двом виразами:

«Результат істинний (дорівнює 1), якщо A не дорівнює B (A ≠ B)»;
«Якщо A не дорівнює B (A ≠ B), то істина (1)».

Часто вказують на схожість між додаванням за модулем 2 і конструкцією «або ..., або ...» в природній мові. Складене твердження «або A, або B» вважається істинним, коли істинне або A, або B, але не обидва відразу, інакше складене твердження хибне. Це в точності відповідає визначенню операції в булевій алгебрі, якщо «істину» позначати як $1$ , а «брехня» як $0$ .

Цю операцію нерідко порівнюють з диз'юнкцією тому, що вони дуже схожі за властивостями, і обидві мають схожість з союзом «або» у повсякденній мові. Порівняйте правила для цих операцій:

$A \lor B$ істинне, якщо істинне $~A$ або $~B$ , або обидва відразу.
$A \oplus B$ істинне, якщо істинне $~A$ або $~B$ , але не обидва відразу.

Операція $\oplus$ виключає останній варіант («обидва відразу») і з цієї причини називається виключне «АБО». Операція $\lor$ включає останній варіант («обидва відразу») і з цієї причини іноді називається включне «АБО». Неоднозначність природної мови полягає в тому, що союз «або» може застосовуватися в обох випадках.

Альтернативні символи [ред.]

Символ, використовуваний виключно для диз'юнкції варіюється від однієї області застосування до іншої. На додаток до абревіатури "XOR", будь-який з наступних символів можуть також розглядатися:

Знак плюс (+). Це має сенс, тому що математично ексклюзивні диз'юнкції відповідає модулю 2, який має наступну таблицю Крім того, ясно ізоморфними на один вище:

**Додавання за модулем 2**
$p$	$q$	$p + q$
0	0	0
0	1	1
1	0	1
1	1	0

Використання знаку плюс має додаткову перевагу, що всі звичайні алгебраїчні властивості математичного кільця і поля можуть бути використані без зайвого клопоту. Тим не менш, знак плюс використовується також для ексклюзивної диз'юнкції в деяких позначеннях систем.
Знаком плюс, зміненого в деякому роді ( $\oplus$ ). Це використання стикається із запереченням, що цей же символ вже використовується в математиці пряма сума алгебраїчних структур.
Префікс J, як і в J' PQ.
Включно символ диз'юнкції ( $\lor$ ), який змінюється певним чином: з підкресленням ( $\underline\lor$ ) або з точкою вище ( $\dot\vee$ ).
У деяких мовах програмування, таких як C, C++, C #, Java, Perl, MATLAB і Python, курсор (^) використовується для позначення оператор побітового XOR. Це не використовується поза контекстом програмування, тому що це занадто легко сплутати з іншими видами використання каретки.

Виключна диз'юнкція у програмуванні [ред.]

В мовах C/C++ (а також Java, C#, Ruby, PHP, JavaScript ) дана операція позначається символом «^», в мовах Паскаль, Delphi, Ада - зарезервованим словом XOR. Додавання виконується побітово для двох операндів. Наприклад,

якщо
a =	$~01100101_2$
b =	$~00101001_2$
тоді
a ^ b =	$~01001100_2$

Виконання операції виключне«або» для значень логічного типу (true, false) проводиться в різних мовах програмування по-різному. Наприклад, в Delphi використовується вбудований оператор XOR (приклад: умова1 xor умова2). У мові C, починаючи зі стандарту C99, оператор «^» над операндами логічного типу повертає результат застосування логічної операції XOR. У С++ оператор «^» для логічного типу bool повертає результат згідно з описаними правилами, для інших же типів виробляється його побітове застосування.