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

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

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

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

Множиною істинності виключної диз'юнкції двох суджень є симетричною різницею множин істинності операндів.

Позначення

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

$\oplus _{2}(a,b),~a$ ^ $~b,~a\oplus b,a\oplus _{2}b,a+_{2}b,$ a ≠ b, $a\neq b,(a,b)\oplus _{2},a~XOR~b$

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

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

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

$a\oplus b=(a\land \neg b)\lor (\neg a\land 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)=\lnot (A\leftrightarrow B)$

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

Властивості

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

$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. «Результат істинний (дорівнює 1), якщо A не дорівнює B (A ≠ B)»;
2. «Якщо A не дорівнює B (A ≠ B), то істина (1)».

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

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

1. $A\lor B$ істинне, якщо істинне $~A$ або $~B$, або обидва відразу.
2. $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, як в Jpq.
• Символ диз'юнкції ($\lor$), який змінюється певним чином: з підкресленням (${\underline {\lor }}$) або з точкою вище (${\dot {\vee }}$).
• У деяких мовах програмування, таких як C, C++, C#, Java, Perl, MATLAB і Python, символ циркумфлекс (^) використовується для позначення оператора побітового XOR. Це не використовується поза контекстом програмування, тому що це занадто легко сплутати з іншими видами використання каретки.

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

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

якщо
a =	$~01100101_{2}$
b =	$~00101001_{2}$
тоді
a ^ b =	$~01001100_{2}$

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

В умовах нестачі регістрів оператор XOR може бути використаний обміну значеннями змінних.

Квантові обчислення

У квантових комп'ютерах аналогом операції додавання по модулю 2 є вентиль CNOT.

Див. також

• Додавання
• Бітові операції
• Умовна диз'юнкція
• Диз'юнкція (логіка)

Посилання

• Disjunction Stanford Encyclopedia of Philosophy(англ.)