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

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

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

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

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

Булева алгебра

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

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

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

Правило: результат дорівнює $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$

Таблиця істинності виглядає таким чином: Шаблон:2-ary truth table Результат застосування виняткової диз'юнкції такий самий, як і від додавання за модулем 2. Тому й саму операцію часто називають додаванням за модулем 2.

Виняткова диз'юнкція є також запереченням еквівалентності, тобто

$(A\oplus B)=\mathrm{\neg }(A\leftrightarrow B)$

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

Властивості

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

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

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

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

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

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

Абелева група

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

$a\oplus 0=a$

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

$a\oplus a=0$

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

Інші властивості

$\begin{array}{ccc}p\oplus 1& =& \mathrm{\neg }p\\ p\oplus \mathrm{\neg }p& =& 1\\ \\ p\oplus q& =& \mathrm{\neg }p\oplus \mathrm{\neg }q\\ \mathrm{\neg }(p\oplus q)& =& \mathrm{\neg }p\oplus q& =& p\oplus \mathrm{\neg }q\\ \\ p\oplus (\mathrm{\neg }p\wedge q)& =& p\vee q\\ p\oplus (p\wedge \mathrm{\neg }q)& =& p\wedge q\\ p\oplus (p\vee q)& =& \mathrm{\neg }p\wedge q\\ \mathrm{\neg }p\oplus (p\vee \mathrm{\neg }q)& =& p\vee q\\ p\wedge (p\oplus \mathrm{\neg }q)& =& p\wedge q\\ p\vee (p\oplus q)& =& p\vee q\end{array}$

Функціональна повнота

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

$\mathrm{\neg }a\equiv a\to (a\oplus a)$

$\mathrm{\neg }a\equiv a\oplus (a\to a)$

$a\vee b\equiv (\mathrm{\neg }a)\to b$

$a\wedge b\equiv \mathrm{\neg }(a\to \mathrm{\neg }b)$

Виняткова диз'юнкція у природних мовах

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

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

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

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

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

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

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

Альтернативні символи

Символ, використовуваний для виняткової диз'юнкції, варіюється від однієї області застосування до іншої. Окрім абревіатури «XOR», можуть траплятися:

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

Додавання за модулем 2

$p$	$q$	$p+q$
0	0	0
0	1	1
1	0	1
1	1	0

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

• Знаком плюс, зміненим певним чином, наприклад, взятим в коло ($\oplus$). Це викликає заперечення: цей же символ вже використовують у математиці для прямої суми алгебраїчних структур.
• Префікс J, як в Jpq.
• Символ диз'юнкції ($\vee$), який певним чином змінюють: із підкресленням ($\underset{\_}{\vee }$) або з точкою вгорі ($\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 Шаблон:Webarchive Stanford Encyclopedia of PhilosophyШаблон:Ref-en