WikiSort.ru - Не сортированное

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

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

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

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

в префиксной записи

${\displaystyle max(a,b)-min(a,b)}$ .

Обозначения

Запись может быть префиксной («польская запись») — знак операции ставится перед операндами, инфиксной — знак операции ставится между операндами и постфиксной — знак операции ставится после операндов. При числе операндов более 2 префиксная и постфиксная записи экономичнее инфиксной записи. Чаще всего встречаются следующие варианты записи:
${\displaystyle \oplus _{2}(a,b),~a}$ ^ ${\displaystyle b,~a\oplus b,a\oplus _{2}b,a+_{2}b,}$ a ≠ b, ${\displaystyle a\neq b,(a,b)\oplus _{2},a~XOR~b}$

В таблице символов Юникод есть символы для сложения по модулю 2: XOR — U+22BB (⊻), CIRCLED PLUS — U+2295 (⊕) и PLUS SIGN WITH SUCSCRIPT TWO — U+2A27 (⨧), а также символ для суммы по модулю 2: MODULO TWO SUM — U+2A0A (⨊).

Свойства

• ${\displaystyle a\oplus 0=a}$ (идемпотентность)
• ${\displaystyle a\oplus 1={\bar {a}}}$ (отрицание)
• ${\displaystyle a\oplus a=0}$
• ${\displaystyle a\oplus b=b\oplus a}$ (коммутативность)
• ${\displaystyle (a\oplus b)\oplus c=a\oplus (b\oplus c)}$ (ассоциативность)
• ${\displaystyle (a\oplus b)\oplus b=a}$
• ${\displaystyle {\bar {a}}\oplus b=a\oplus {\bar {b}}=(a\equiv b)}$ (сравнения по модулю)

Булева алгебра

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

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

• для бинарного сложения по модулю 2 (применяется в двоичных полусумматорах):

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle a\oplus b}$
0	0	0
1	0	1
0	1	1
1	1	0

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

• для тернарного сложения по модулю 2 (применяется в двоичных полных сумматорах):

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle c}$	${\displaystyle a\oplus b\oplus c}$
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

Правило: результат равен ${\displaystyle 0}$ , если нет операндов, равных ${\displaystyle 1}$ , либо их чётное количество.

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

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

если

${\displaystyle a=01100101_{2}}$

${\displaystyle b=00101001_{2}}$

то

${\displaystyle 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, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как ${\displaystyle 1}$ , а «ложь» как ${\displaystyle 0}$ .

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

1. ${\displaystyle A\lor B}$ истинно, если истинно ${\displaystyle A}$ или ${\displaystyle B}$ , или оба сразу ("хотя бы один из двух").
2. ${\displaystyle A\oplus B}$ истинно, если истинно ${\displaystyle A}$ или ${\displaystyle B}$ , но не оба сразу ("только один из двух").

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

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

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

Ссылки

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

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