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

Материал из Википедии — свободной энциклопедии

Сложе́ние по модулю 2 — логическая операция, по своему применению максимально приближенная к грамматической конструкции "либо ... либо ...". Синонимы: исключа́ющее "ИЛИ", XOR.

Это бинарная инфиксная операция, то есть, она имеет два операнда и ставится между ними. Чаще всего встречаются следующие варианты записи:
$~a$ ^ $~b, ~a \oplus b, a \oplus_2 b, a + b, a +_2 b, a ~XOR~ b$ .

[править] Булева алгебра

В булевой алгебре сложение по модулю 2 - это функция двух переменных (они же - операнды операции). Переменные могут принимать значения из множества $~\{0, 1\}$ . Результат также принадлежит множеству $~\{0, 1\}$ . Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений $~0, 1$ может использоваться любая другая пара подходящих символов, например $~false, true$ или $~F, T$ или "ложь", "истина".

Правило: результат равен $~0$ , если оба операнда равны; во всех остальных случаях результат равен $~1$ .

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

$~a$	$~b$	$~a \oplus b$
$~0$	$~0$	$~0$
$~0$	$~1$	$~1$
$~1$	$~0$	$~1$
$~1$	$~1$	$~0$

[править] Программирование

В компьютерных языках сложение по модулю 2 используется сравнительно редко. В языках C/C++ (а также Java, C#, PHP, JavaScript и т.д.) эта операция обозначается символом "^" и выполняется для всех битов левого и правого операнда попарно. Например,

если
a =	$~01100101_2$
b =	$~00101001_2$
то
a ^ b =	$~01001100_2$

Выполнение операции XOR для значений логического типа (true, false) производится операцией "!=". Например, если необходимо проверить, что выполняется одно из двух условий, но не оба, можно записать эту проверку так: if (condition1 != condition2) ..., где condition1 и condition2 - значения логического типа.

[править] Связь с естественным языком

Часто указывают на сходство между сложением по модулю 2 и конструкцией "либо ... либо ..." в естественном языке. Составное утверждение "либо A, либо B" считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если "истину" обозначать как $1$ , а "ложь" как $0$ .

Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам, и обе имеют сходство с союзом "или" в повседневной речи. Сравните правила для этих операций:

$A \lor B$ истинно, если истинно $~A$ или $~B$ , или оба сразу.
$A \oplus B$ истинно, если истинно $~A$ или $~B$ , но не оба сразу.

Операция $\oplus$ исключает последний вариант ("оба сразу") и по этой причине называется исключающим "ИЛИ". Операция $\lor$ включает последний вариант ("оба сразу") и по этой причине иногда называется включающим "ИЛИ". Неоднозначность естественного языка заключается в том, что союз "или" может применяться в обоих случаях.