Исключающее «или»

Сложение по модулю 2
Исключающее ИЛИ
Таблица истинности	$(0110)$
Нормальные формы
Дизъюнктивная	${\overline {x}}\cdot y+x\cdot {\overline {y}}$
Конъюнктивная	$({\overline {x}}+{\overline {y}})\cdot (x+y)$
Полином Жегалкина	$x\oplus y$

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

Сложе́ние по мо́дулю 2 (логи́ческое сложе́ние, исключа́ющее «ИЛИ», строгая дизъюнкция, XOR, поразрядное дополнение, побитовый комплемент, жегалкинское сложение) — булева функция, а также логическая и битовая операция. В случае 2-х переменных результат выполнения операции является истинным тогда и только тогда, когда лишь один из аргументов является истинным. Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов равных 1, составляющих текущий набор — нечетное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.

Сложение по модулю 2 следует отличать от простого сложения, которое соответствует обыкновенному неисключающему «или» (логической дизъюнкции).

В теории множеств сложению по модулю 2 соответствует операция симметричной разности двух множеств.

Обозначения

ПР Запись может быть префиксной («польская запись») — знак операции ставится перед операндами, инфиксной — знак операции ста­вит­ся между операндами и постфиксной — знак операции ставится после операндов. При числе операндов более 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 0=a$ (идемпотентность)
• $a\oplus 1={\bar {a}}$ (отрицание)
• $a\oplus a=0$
• $a\oplus b=b\oplus a$ (коммутативность)
• $(a\oplus b)\oplus c=a\oplus (b\oplus c)$ (асссоциативность)
• $(a\oplus b)\oplus b=a$
• ${\bar {a}}\oplus b=a\oplus {\bar {b}}=a\equiv 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

Программирование

В языках C/C++ (а также Java, C#, Ruby, PHP, JavaScript и т. д.) битовая операция поразрядного дополнения обозначается символом «^», в языках Паскаль, Delphi, Ada, Visual Basic — зарезервированным словом xor, в языке ассемблера — одноимённой логической командой. При этом сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,

если

$a=01100101_{2}$

$b=00101001_{2}$

то

$a{\hat {\ }}b=01001100_{2}$

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

Связь с естественным языком

В естественном языке операция «сложение по модулю» эквивалентна двум выражениям:

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$ включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ». Неоднозначность естественного языка заключается в том, что союз «или» может применяться в обоих случаях.

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

В квантовых компьютерах аналогом операции сложения по модулю 2 является вентиль CNOT.

См. также

• Тернарное сложение по модулю 2
• Деление по модулю
• Алгоритм обмена при помощи исключающего ИЛИ

Ссылки

• Алгебра логики и цифровые компьютеры: Функция сложения по модулю 2 (xor)