Эксклюзивный или - Exclusive or

Эксклюзивный или
XOR
Диаграмма Венна Exclusive или
Таблица истинности
Логический вентиль XOR ANSI.svg
Нормальные формы
Дизъюнктивный
Конъюнктивный
Полином Жегалкина
Решетки столба
0-сохранение да
1-консервирующий нет
Монотонный нет
Аффинный да
Диаграмма Венна из

Исключительное или или эксклюзивный дизъюнкция является логическая операция , которая выполняется тогда и только тогда , когда ее аргументы отличаются (один, правда, другое ложно).

Он символизирует префиксом оператора J и к инфиксные операторов XOR ( / ˌ ɛ к с ɔːr / или / г ɔːr / ), ПНП , исключающее ИЛИ , , , , , и . Отрицание из XOR является логическим biconditional , что дает истинно тогда и только тогда , когда два входа является одинаковым.

Он получает название «исключающее или», потому что значение «или» неоднозначно, когда оба операнда истинны; исключительный оператор or исключает этот случай. Иногда это воспринимается как «одно или другое, но не то и другое одновременно». Это можно было бы записать как «А или В, но не А и В».

Поскольку он ассоциативен, его можно рассматривать как n -арный оператор, который истинен тогда и только тогда, когда истинно нечетное количество аргументов. То есть, XOR б XOR ... может рассматриваться как XOR ( , Ь , ...).

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

Аргументы слева объединены XOR. Это двоичная матрица Уолша (см. Код Адамара ).

Таблица истинности A XOR B показывает, что он выводит истину всякий раз, когда входные данные различаются:

Таблица истинности XOR
Вход Выход
А B
0 0 0
0 1 1
1 0 1
1 1 0
  • 0, ложь
  • 1, правда

Эквивалентности, исключение и введение

Исключительная дизъюнкция по существу означает «либо одно, но не оба, либо ничего». Другими словами, утверждение истинно тогда и только тогда, когда одно истинно, а другое ложно. Например, если в гонке участвуют две лошади, то выиграет одна из них, но не обе. Исключительная дизъюнкция , также обозначаемая ? или , может быть выражено в терминах логической конъюнкции («логическое и», ), дизъюнкции («логическое или», ) и отрицания ( ) следующим образом:

Исключительная дизъюнкция также может быть выражена следующим образом:

Это представление XOR может быть полезно при построении схемы или сетей, поскольку он имеет только одну операцию и небольшое количество и операции. Доказательство этой идентичности приведено ниже:

Иногда бывает полезно написать так:

или:

Эту эквивалентность можно установить , дважды применяя законы Де Моргана к четвертой строке приведенного выше доказательства.

Исключающее или также эквивалентно отрицанию логического биконусловия по правилам материальной импликации ( материальное условное условие эквивалентно разъединению отрицания его антецедента и его следствия) и материальной эквивалентности .

Таким образом, в математической и инженерной нотации мы имеем:

Отрицание

Дух законов Де Моргана может быть применен, у нас есть:

Отношение к современной алгебре

Хотя операторы ( конъюнкция ) и ( дизъюнкция ) очень полезны в логических системах, они не позволяют получить более обобщаемую структуру следующим образом:

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

Тем не менее, система , использующая исключающее или является абелева группа . Комбинация операторов и элементов over дает хорошо известное поле . Это поле может представлять любую логику, доступную с помощью системы, и имеет дополнительное преимущество арсенала инструментов алгебраического анализа для полей.

Более конкретно, если связать с 0 и с 1, можно интерпретировать логическую операцию «И» как умножение и операцию «исключающее ИЛИ» как сложение :

Использование этого базиса для описания булевой системы называется алгебраической нормальной формой .

Исключительное "или" на естественном языке

Дизъюнкция часто понимается исключительно на естественных языках . В английском языке дизъюнктивное слово «or» часто понимается исключительно, особенно когда оно используется с частицей «либо». Приведенный ниже пример на английском языке обычно понимается в разговоре как подразумевающий, что Мэри не одновременно певица и поэт.

1. Мэри - певица или поэтесса.

Однако дизъюнкцию также можно понимать включительно, даже в сочетании с «либо». Например, первый пример ниже показывает, что «любой» удачно может использоваться в сочетании с прямым утверждением, что оба дизъюнкта истинны. Второй пример показывает, что исключительный вывод исчезает в нисходящих контекстах. Если бы дизъюнкция в этом примере понималась как исключительная, оставалась бы возможность, что некоторые люди ели и рис, и бобы.

2. Мэри либо певица, либо поэт, либо и то, и другое.
3. Никто не ел ни риса, ни бобов.

Примеры, подобные приведенным выше, мотивировали анализ вывода об исключительности как прагматических разговорных импликатур, рассчитанных на основе инклюзивной семантики . Импликатуры обычно отменяются и не возникают в нисходящем контексте, если их расчет зависит от максимума количества . Однако некоторые исследователи рассматривали исключительность как истинное семантическое следствие и предлагали неклассическую логику, которая могла бы ее подтвердить.

Такое поведение английского «или» встречается и в других языках. Однако во многих языках есть дизъюнктивные конструкции, которые строго исключают друг друга, например, французский soit ... soit .

Альтернативные символы

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

  • +, знак плюс, преимущество которого состоит в том, что все обычные алгебраические свойства математических колец и полей можно использовать без лишних слов; но знак плюс также используется для инклюзивной дизъюнкции в некоторых системах обозначений; обратите внимание, что исключительная дизъюнкция соответствует сложению по модулю 2, которое имеет следующую таблицу сложения, явно изоморфную приведенной выше:
     
0 0 0
0 1 1
1 0 1
1 1 0
  • , модифицированный знак плюса; этот символ также используется в математике для прямой суммы алгебраических структур
  • J, как в J pq
  • Инклюзивный символ дизъюнкции ( ), который каким-либо образом модифицируется, например
  • ^, каретка , используемая в нескольких языках программирования , таких как C , C ++ , C # , D , Java , Perl , Ruby , PHP и Python , обозначающая побитовый оператор XOR; не используется вне контекста программирования, потому что его слишком легко спутать с другими вариантами использования каретки
  • X-or.svg, иногда пишется как
    • > <
    • > - <
  • = 1, в символике IEC

Характеристики

Коммутативность : да
        
Venn0110.svg          Venn0110.svg
Ассоциативность : да
        
Венн 0101 0101.svg Венн 0011 1100.svg          Венн 0110 1001.svg          Венн 0110 0110.svg Венн 0000 1111.svg
Распределительность :
Исключающее или не распределяется по какой-либо двоичной функции (даже самой), а логическая конъюнкция распределяется по исключающей или . (Соединение и исключающее или образуют операции умножения и сложения поля GF (2) , и, как и в любом другом поле, они подчиняются закону распределения.)
Идемпотентность : нет
                 
Venn01.svg Venn01.svg          Venn00.svg          Venn01.svg
Монотонность : нет
        
Венн 1011 1011.svg          Венн 1011 1101.svg          Venn 0101 1010.svg Венн 0011 1100.svg
Сохранение правды: нет
Когда все входные данные верны, выход неверен.
        
Venn0001.svg          Venn0110.svg
Сохранение лжи: да
Когда все входы ложны, выход ложен.
        
Venn0110.svg          Venn0111.svg
Спектр Уолша : (2,0,0, −2)
Non- линейность : 0
Функция линейная.

Если для истинного (1) и ложного (0) используются двоичные значения, то исключающее или работает точно так же, как сложение по модулю 2.

Информатика

Традиционное символическое представление логического элемента XOR

Побитовая операция

Nimber дополнение является эксклюзивным или из целых неотрицательных чисел в двоичном представлении. Это тоже векторное сложение в .

Исключительная дизъюнкция часто используется для побитовых операций. Примеры:

  • 1 ИСКЛЮЧАЮЩЕЕ ИЛИ 1 = 0
  • 1 ИСКЛЮЧАЮЩЕЕ ИЛИ 0 = 1
  • 0 ИСКЛЮЧАЮЩЕЕ ИЛИ 1 = 1
  • 0 исключающее ИЛИ 0 = 0
  • 1110 2 XOR 1001 2 = 0111 2 (это эквивалентно сложению без переноса )

Как отмечалось выше, поскольку исключительная дизъюнкция идентична сложению по модулю 2, побитовая исключительная дизъюнкция двух n- битных строк идентична стандартному вектору сложения в векторном пространстве .

В информатике исключительная дизъюнкция имеет несколько применений:

  • Он сообщает, являются ли два бита неравными.
  • Это необязательный бит-флиппер (решающий ввод выбирает, инвертировать ли ввод данных).
  • Он сообщает, существует ли нечетное количество 1 битов ( истинно, если истинно нечетное число переменных).

В логических схемах можно сделать простой сумматор с вентилем XOR для сложения чисел и серией вентилей AND, OR и NOT для создания вывода переноса.

На некоторых компьютерных архитектурах более эффективно хранить ноль в регистре, выполняя операцию XOR с регистром с самим собой (биты, объединенные с помощью XOR с самими собой, всегда равны нулю) вместо загрузки и сохранения нулевого значения.

В простых нейронных сетях , активируемых порогом , для моделирования функции XOR требуется второй уровень, поскольку функция XOR не является линейно разделимой функцией.

Exclusive-or иногда используется как простая функция смешивания в криптографии , например, с одноразовым блокнотом или сетевыми системами Фейстеля .

Exclusive-or также широко используется в блочных шифрах, таких как AES (Rijndael) или Serpent, и в реализации блочного шифра (CBC, CFB, OFB или CTR).

Точно так же XOR можно использовать при создании пулов энтропии для аппаратных генераторов случайных чисел . Операция XOR сохраняет случайность, что означает, что случайный бит, обработанный XOR с неслучайным битом, приведет к случайному биту. Несколько источников потенциально случайных данных могут быть объединены с помощью XOR, и непредсказуемость вывода гарантированно будет не хуже, чем у наилучшего отдельного источника.

XOR используется в RAID 3–6 для создания информации о четности. Например, RAID может « выполнить резервное копирование» байтов 10011100 2 и 01101100 2 с двух (или более) жестких дисков, выполняя операцию « исключающее ИЛИ» только что упомянутых байтов, в результате чего получается ( 11110000 2 ) и записывается на другой диск. Согласно этому методу, если один из трех жестких дисков потерян, потерянный байт может быть воссоздан путем операции XOR с байтами оставшихся дисков. Например, если диск, содержащий 01101100 2 , потерян, 10011100 2 и 11110000 2 могут быть подвергнуты операции XOR для восстановления потерянного байта.

XOR также используется для обнаружения переполнения в результате двоичной арифметической операции со знаком. Если крайний левый оставшийся бит результата не совпадает с бесконечным числом цифр слева, это означает, что произошло переполнение. Выполнение XOR этих двух битов даст «1», если произойдет переполнение.

XOR можно использовать для замены двух числовых переменных в компьютерах с помощью алгоритма обмена XOR ; однако это считается скорее любопытством и на практике не поощряется.

Связанные списки XOR используют свойства XOR для экономии места для представления структур данных двусвязного списка .

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

Кодировки

Это также называется «стрелкой не влево-вправо» (\ nleftrightarrow) в уценке на основе латекса ( ). Помимо кодов ASCII, оператор кодируется как U + 22BBXOR (HTML  · ) и U + 2295CIRCLED PLUS (HTML  · ), оба в блочных математических операторах . &#8891;  &veebar; &#8853;  &CirclePlus;, &oplus;

Смотрите также

Примечания

  1. ^ Germundsson, Роджер; Вайсштейн, Эрик. «XOR» . MathWorld . Wolfram Research . Проверено 17 июня 2015 года .
  2. ^ Крейг, Эдвард, изд. (1998), Энциклопедия философии Рутледж , 10 , Тейлор и Фрэнсис, стр. 496, ISBN 9780415073103
  3. ^ a b c d Алони, Мария (2016), Залта, Эдвард Н. (ред.), "Disjunction" , Стэнфордская энциклопедия философии (изд. зима 2016 г.), Исследовательская лаборатория метафизики, Стэнфордский университет , получено 2020-09- 03
  4. ^ Дженнингс цитирует многочисленных авторов, утверждающих, что слово «или» имеет исключительный смысл. См. Главу 3, «Первый миф об« Или »»:
    Jennings, RE (1994). Генеалогия дизъюнкции . Нью-Йорк: Издательство Оксфордского университета.
  5. Дэвис, Роберт Б. (28 февраля 2002 г.). «Исключающее ИЛИ (XOR) и аппаратные генераторы случайных чисел» (PDF) . Проверено 28 августа 2013 года .
  6. Нобель, Рикард (26 июля 2011 г.). «Как на самом деле работает RAID 5» . Проверено 23 марта 2017 года .

внешние ссылки