Сложение по модулю 2

Рис. 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\ne b, (a,b)\oplus_2, a ~XOR~ b$

В таблице символов Юникод есть символ для сложения по модулю 2 (CIRCLED PLUS) — U+2295 (⊕).

Свойства

$a \oplus 0 = a$
$a \oplus a = 0$
$a \oplus b = b \oplus a$
$a \oplus 1 = |\bar a|$
$(a \oplus b) \oplus b = a$
$\bar a \oplus b = a \oplus \bar b =$ a ≡ 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 — зарезервированным словом xor, в языке ассемблера — одноимённой логической командой. При этом сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,

если
a =	$~01100101_2$
b =	$~00101001_2$
то
a ^ 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)

В данной статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из-за отсутствия сносок. Вы можете улучшить статью, внеся более точные указания на источники.