# Исключающее «или»

[править | править код]
Материал из Википедии — свободной энциклопедии
(перенаправлено с «Логическое вычитание»)
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 16 июня 2023 года; проверки требуют 15 правок.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 16 июня 2023 года; проверки требуют 15 правок.
Перейти к навигации Перейти к поиску

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

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

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

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

Инверсией исключающего «или» является эквиваленция.

## Обозначения[править | править код]

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

В Юникоде есть символы для сложения по модулю 2: U+22BB ⊻ xor, U+2295 ⊕ circled plus и U+2A27 ⨧ plus sign with subscript two, U+2A52 ⩒ logical or with dot above, а также символ для суммы по модулю 2: U+2A0A ⨊ modulo two sum.

## Свойства[править | править код]

- a ⊕ 1 = a ¯ {\displaystyle a\oplus 1={\bar {a}}} (отрицание)
- a ⊕ a = 0 {\displaystyle a\oplus a=0} (самообратимость)
- a ⊕ b = b ⊕ a {\displaystyle a\oplus b=b\oplus a} (коммутативность)
- ( a ⊕ b ) ⊕ c = a ⊕ ( b ⊕ c ) {\displaystyle (a\oplus b)\oplus c=a\oplus (b\oplus c)} (ассоциативность)
- ( a ⊕ b ) ⊕ b = a {\displaystyle (a\oplus b)\oplus b=a} (реверсивность[en])
- a ¯ ⊕ b = a ⊕ b ¯ = ( a ≡ b ) {\displaystyle {\bar {a}}\oplus b=a\oplus {\bar {b}}=(a\equiv b)} (сравнения по модулю)
- a ⊕ b = c ; a ⊕ c = b ; {\displaystyle a\oplus b=c;a\oplus c=b;}

## Булева алгебра[править | править код]

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

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

- для бинарного сложения по модулю 2 (применяется в двоичных полусумматорах)[1]:55–61:

a {\displaystyle a} | b {\displaystyle b} | a ⊕ b {\displaystyle a\oplus b}
--- | --- | ---
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

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

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

a {\displaystyle a} | b {\displaystyle b} | c {\displaystyle c} | a ⊕ b ⊕ c {\displaystyle a\oplus b\oplus c}
--- | --- | --- | ---
0 | 0 | 0 | 0
0 | 0 | 1 | 1
0 | 1 | 0 | 1
0 | 1 | 1 | 0
1 | 0 | 0 | 1
1 | 0 | 1 | 0
1 | 1 | 0 | 0
1 | 1 | 1 | 1

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

## Программирование[править | править код]

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

  если

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

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

  то

a ^ b = 01001100 2 {\displaystyle a{\hat {\ }}b=01001100_{2}}

Выполнение операции исключающее «или» для значений логического типа (true, false) производится в разных языках программирования по-разному. Например, в Delphi используется встроенный оператор XOR (пример: условие1 `xor` условие2). В языке C, начиная со стандарта C99, оператор «`^`» над операндами логического типа возвращает результат применения логической операции XOR. В C++ оператор «`^`» для логического типа `bool` возвращает результат согласно описанным правилам, для остальных же типов производится его побитовое применение.

Использование побитового исключающего «или» позволяет поменять местами значения целых переменных без использования дополнительной памяти.

## Криптография[править | править код]

На основе исключающего «или» работает шифр Вернама, также известный как «одноразовый блокнот», обладающий абсолютной криптографической стойкостью. На практике это означает, что если зашифровать исходное сообщение m {\displaystyle m} при помощи одноразового ключа k {\displaystyle k} , так, чтобы длина сообщения и ключа были равны, то по получившемуся в результате шифрования шифротексту c {\displaystyle c} невозможно будет определить значение исходного сообщения без знания ключа.

При этом алгоритм шифрования E {\displaystyle E} представляет из себя только одну операцию – исключающее «или»:

E ( k , m ) = k ⊕ m = c {\displaystyle E(k,m)=k\oplus m=c}

Для дешифровки шифротекста c {\displaystyle c} алгоритмом D {\displaystyle D} исключающее «или» применяют ещё раз:

D ( k , c ) = k ⊕ c = m {\displaystyle D(k,c)=k\oplus c=m}

Важно понимать, что в случае, если попытаться использовать одинаковые ключи для шифрования более чем одного сообщения на основании исключающего «или», то криптографическая стойкость системы будет нарушена.

Помимо одноразового блокнота, операция исключающего «или» получила распространение во многих криптографических системах и алгоритмах включая DES, AES и других.

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

В естественном языке операция «сложение по модулю» эквивалентна двум выражениям:

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 A\lor B} истинно, если истинно A {\displaystyle A} или B {\displaystyle B} , или оба сразу («хотя бы один из двух»).
2. A ⊕ B {\displaystyle A\oplus B} истинно, если истинно A {\displaystyle A} или B {\displaystyle B} , но не оба сразу («только один из двух»).

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

## Квантовые вычисления[править | править код]

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

## Цифровая техника[править | править код]

## См. также[править | править код]

- Идентичность
- Отрицание
- Конъюнкция
- Дизъюнкция
- Эквиваленция
- Импликация
- Обратная импликация
- Штрих Шеффера
- Стрелка Пирса
- Таблица истинности
- Закон тождества

## Примечание[править | править код]

1. ↑ Шило В.Л. Популярные цифровые микросхемы: Справочник.— М.: Радио и связь, 1987. — 352 с. — (Массовая радиобиблиотека. Вып. 1111).

## Внешние ссылки[править | править код]

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

| В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (29 мая 2012)

Источник — https://ru.wikipedia.org/w/index.php?title=Исключающее_«или»&oldid=134718843
Категории:

- Математические операции
- Логические операции
- Двоичная арифметика

Скрытые категории:

- Википедия:Статьи без сносок с мая 2012 года
- Википедия:Статьи без сносок