Исключающее ИЛИ (XOR / Строгая дизъюнкция): таблица истинности и свойства
В информатике и дискретной математике строгая дизъюнкция (также известная как Исключающее ИЛИ или XOR от англ. eXclusive OR) — это логическая операция, которая выдает истину только в том случае, если значения операндов различны.
В отличие от обычной дизъюнкции (логического ИЛИ), которая допускает истинность обоих высказываний одновременно, строгая дизъюнкция ставит жесткое условие: «либо одно, либо другое, но ни в коем случае не оба вместе».
Также эту операцию часто называют «сложением по модулю 2». В программировании XOR играет огромную роль — он применяется для генерации случайных чисел, проверки четности битов и в криптографии (шифровании данных).
Обозначения исключающего ИЛИ
Для обозначения этой операции в различных сферах используются разные символы. Для двух операндов $A$ и $B$ она может записываться так:
- $A \oplus B$ (классическое математическое обозначение — плюс в кружочке);
- $A \not\equiv B$ (знак неэквивалентности, подчеркивающий, что операнды не должны быть равны);
A XOR B(в языках программирования Pascal, SQL);A ^ B(побитовый XOR в языках C, C++, Java, C#, Python, JavaScript).
Пример из реальной жизни
Лучший пример исключающего ИЛИ — это ситуация жесткого выбора.
Представьте, что вы купили комплексный обед в ресторане, и официант говорит: «В качестве напитка вы можете выбрать чай ($A$) ИЛИ кофе ($B$)».
- Если вы возьмете только чай ($A=1, B=0$) $\rightarrow$ правило соблюдено (Итог = 1).
- Если вы возьмете только кофе ($A=0, B=1$) $\rightarrow$ правило соблюдено (Итог = 1).
- Если вы попытаетесь взять и чай, и кофе ($A=1, B=1$) $\rightarrow$ официант вам откажет (Итог = 0).
- Если вы откажетесь от всего ($A=0, B=0$) $\rightarrow$ условие выбора напитка не выполнено (Итог = 0).
Таблица истинности для XOR
Таблица истинности наглядно показывает, что результат равен 1 только тогда, когда на входе есть ровно одна единица (операнды разные). Если операнды одинаковые (оба нули или обе единицы), результат равен нулю.
Для двух переменных ($A \oplus B$)
| $A$ | $B$ | $A \oplus B$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Для трех переменных ($A \oplus B \oplus C$)
При работе с тремя и более переменными XOR работает как индикатор нечетности. Результат будет равен 1 тогда и только тогда, когда количество единиц на входе — нечетное (одна или три).
| $A$ | $B$ | $C$ | $A \oplus B \oplus C$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
(Воспользуйтесь нашим интерактивным калькулятором, чтобы автоматически построить таблицу истинности для любого количества переменных!)
Основные свойства и законы XOR
Исключающее ИЛИ обладает рядом уникальных и очень полезных математических свойств:
1. Коммутативность (переместительный закон): От перемены мест операндов результат не меняется.
$$A \oplus B = B \oplus A$$
2. Ассоциативность (сочетательный закон):
$$(A \oplus B) \oplus C = A \oplus (B \oplus C)$$
3. Взаимодействие с нулем (нейтральный элемент): XOR с нулем не меняет исходное значение.
$$A \oplus 0 = A$$
4. Взаимодействие с единицей (инверсия): XOR с единицей работает как логическое отрицание (НЕ).
$$A \oplus 1 = \neg A$$
5. Самообратимость (идемпотентность): XOR элемента с самим собой всегда дает ноль. Это свойство используется в программировании для быстрого обнуления регистров памяти (x ^ x = 0).
$$A \oplus A = 0$$
6. Выражение через базовые операции: Строгую дизъюнкцию можно выразить через базовые И, ИЛИ и НЕ:
$$A \oplus B = (A \lor B) \land \neg(A \land B)$$
Или в другой форме:
$$A \oplus B = (A \land \neg B) \lor (\neg A \land B)$$
Попробуйте покликать кнопки в нашем интерактивном тренажере ниже, чтобы на практике запомнить логику работы Исключающего ИЛИ!