Сложение по модулю 2 | |
---|---|
Исключающее ИЛИ, XOR | |
Диаграмма Венна | |
Таблица истинности | |
Логический вентиль |
|
Нормальные формы | |
Дизъюнктивная | |
Конъюнктивная | |
Полином Жегалкина | |
Принадлежность предполным классам | |
Сохраняет 0 | Да |
Сохраняет 1 | Нет |
Монотонна | Нет |
Линейна | Да |
Самодвойственна | Нет |
Сложе́ние по мо́дулю 2 (исключа́ющее «ИЛИ», XOR, строгая дизъюнкция, поразрядное дополнение, побитовый комплемент, инвертирование по маске, жегалкинское сложение, логическое вычитание, логи́ческая неравнозна́чность) — булева функция, а также логическая и битовая операция. В случае двух переменных результат выполнения операции истинен тогда и только тогда, когда один из аргументов истинен, а второй — ложен. Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов, равных 1, составляющих текущий набор, — нечётное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.
Сложение по модулю 2 следует отличать от простого сложения, которое соответствует обыкновенному неисключающему «или» (логической дизъюнкции).
В теории множеств сложению по модулю 2 соответствует операция симметричной разности двух множеств.
Запись может быть префиксной («польская запись») — знак операции ставится перед операндами, инфиксной — знак операции ставится между операндами и постфиксной — знак операции ставится после операндов. При числе операндов более 2 префиксная и постфиксная записи экономичнее инфиксной записи. Чаще всего встречаются следующие варианты записи:
^
a ≠ b,
В таблице символов Юникод есть символы для сложения по модулю 2: XOR — U+22BB (⊻), CIRCLED PLUS — U+2295 (⊕) и PLUS SIGN WITH SUCSCRIPT TWO — U+2A27 (⨧), а также символ для суммы по модулю 2: MODULO TWO SUM — U+2A0A (⨊).
В булевой алгебре сложение по модулю 2 — это функция двух, трёх и более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества . Результат также принадлежит множеству . Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений может использоваться любая другая пара подходящих символов, например или или «ложь», «истина», но при этом необходимо доопределять старшинство, например, .
Таблицы истинности:
0 | 0 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 0 |
Правило: результат равен , если оба операнда равны; во всех остальных случаях результат равен .
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, Python и т. д. битовая операция поразрядного дополнения обозначается символом «^», в языках Паскаль, Delphi, Ada, Visual Basic — зарезервированным словом xor, в языке ассемблера — одноимённой логической командой. При этом сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,
Выполнение операции исключающее «или» для значений логического типа (true, false) производится в разных языках программирования по-разному. Например, в Delphi используется встроенный оператор XOR (пример: условие1 xor условие2). В языке C, начиная со стандарта C99, оператор «^» над операндами логического типа возвращает результат применения логической операции XOR. В С++ оператор «^» для логического типа bool возвращает результат согласно описанным правилам, для остальных же типов производится его побитовое применение.
В естественном языке операция «сложение по модулю» эквивалентна двум выражениям:
Часто указывают на сходство между сложением по модулю 2 и конструкцией «либо … либо …» в естественном языке. Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как , а «ложь» как .
Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам, и обе имеют сходство с союзом «или» в повседневной речи. Сравните правила для этих операций:
Операция исключает последний вариант («оба сразу») и по этой причине называется исключающим «ИЛИ». Операция включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ». Неоднозначность естественного языка заключается в том, что союз «или» может применяться в обоих случаях.
В квантовых компьютерах аналог операции сложения по модулю 2 — вентиль CNOT.
В этой статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из-за отсутствия сносок. |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .