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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Сложение по модулю 2
Исключающее ИЛИ
Элемент Исключающее ИЛИ (100).png
Основная информация
Классы
T0
T1
M
L
S
 Да   Нет   Нет   Да   Нет 
ДНФ \overline{x} \cdot y + x \cdot \overline{y}
КНФ ( \overline{x} + \overline{y} ) \cdot ( x + y )
Полином Жегалкина x \oplus y
Таблица истинности (0110)


Рис. 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 ().

Свойства[править | править вики-текст]

Булева алгебра[править | править вики-текст]

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

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

~a ~b ~a \oplus b
~0 ~0 ~0
~0 ~1 ~1
~1 ~0 ~1
~1 ~1 ~0
Правило: результат равен ~0, если оба операнда равны; во всех остальных случаях результат равен ~1.
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 \wedge 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.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]