Cdtrjyty

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

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

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

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

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

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

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

Обозначения |

Запись может быть префиксной («польская запись») — знак операции ставится перед операндами, инфиксной — знак операции ставится между операндами и постфиксной — знак операции ставится после операндов. При числе операндов более 2 префиксная и постфиксная записи экономичнее инфиксной записи. Чаще всего встречаются следующие варианты записи:
⊕2(a,b), a{displaystyle oplus _{2}(a,b),~a} ^ b, a⊕b,a⊕2b,a+2b,{displaystyle b,~aoplus b,aoplus _{2}b,a+_{2}b,} a ≠ b, a≠b,(a,b)⊕2,a XOR b{displaystyle aneq 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 (⨊).

Свойства |

• 
  a⊕0=a{displaystyle aoplus 0=a} (идемпотентность)


• 
  a⊕1=a¯{displaystyle aoplus 1={bar {a}}} (отрицание)


• a⊕a=0{displaystyle aoplus a=0}


• 
  a⊕b=b⊕a{displaystyle aoplus b=boplus a} (коммутативность)


• 
  (a⊕b)⊕c=a⊕(b⊕c){displaystyle (aoplus b)oplus c=aoplus (boplus c)} (ассоциативность)


• (a⊕b)⊕b=a{displaystyle (aoplus b)oplus b=a}


• 
  a¯⊕b=a⊕b¯=(a≡b){displaystyle {bar {a}}oplus b=aoplus {bar {b}}=(aequiv b)} (сравнения по модулю)

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

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

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

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

a{displaystyle a}	b{displaystyle b}	a⊕b{displaystyle aoplus b}
0	0	0
1	0	1
0	1	1
1	1	0

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

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

a{displaystyle a}	b{displaystyle b}	c{displaystyle c}	a⊕b⊕c{displaystyle aoplus boplus 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

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

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

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

если

a=011001012{displaystyle a=01100101_{2}}

b=001010012{displaystyle b=00101001_{2}}

то

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

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

1. 
   A∨B{displaystyle Alor B} истинно, если истинно A{displaystyle A} или B{displaystyle B}, или оба сразу ("хотя бы один из двух").


2. 
   A⊕B{displaystyle Aoplus B} истинно, если истинно A{displaystyle A} или B{displaystyle B}, но не оба сразу ("только один из двух").

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

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

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

Ссылки |

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

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