Исключительное или или эксклюзивный дизъюнкция является логическая операция , которая выполняется тогда и только тогда , когда ее аргументы отличаются (один, правда, другое ложно). [1]
XOR | |
---|---|
Таблица истинности | |
Логический вентиль | |
Нормальные формы | |
Дизъюнктивный | |
Конъюнктивный | |
Полином Жегалкина | |
Решетки столба | |
0-сохраняющий | да |
1-консервирующий | нет |
Монотонный | нет |
Аффинный | да |
Оно символизирует оператором префикс J [2] и с помощью инфиксные операторов XOR ( / ˌ ɛ к с ɔːr / или / г ɔːr / ), ПНП , исключающее ИЛИ , ⊻ , ⩒ , ⩛ , ⊕ , ↮ и ≢ . Отрицанием из XOR является логическим biconditional , что справедливо тогда и только тогда , когда два входа являются одинаковыми.
Он получает название «исключающее или», потому что значение «или» неоднозначно, когда оба операнда истинны; исключительный оператор or исключает этот случай. Иногда это воспринимается как «одно или другое, но не то и другое одновременно». Это можно было бы записать как «А или В, но не А и В».
Поскольку он ассоциативен, его можно рассматривать как n -арный оператор, который истинен тогда и только тогда, когда истинно нечетное количество аргументов. То есть, XOR б XOR ... может рассматриваться как XOR ( , Ь , ...).
Таблица истинности
Таблица истинности A XOR B показывает, что он выводит истину всякий раз, когда входные данные различаются:
Вход | Выход | |
---|---|---|
А | B | |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
- 0, ложь
- 1, правда
Эквивалентности, исключение и введение
Исключительная дизъюнкция по существу означает «либо одно, но не оба, либо ничего». Другими словами, утверждение истинно тогда и только тогда, когда одно истинно, а другое ложно. Например, если в гонке участвуют две лошади, то выиграет одна из них, но не обе. Исключительная дизъюнкция, также обозначается ⩛ или же , может быть выражено в терминах логической конъюнкции («логическое и»,), дизъюнкция ("логическое ИЛИ ",), а отрицание () следующим образом:
Исключительная дизъюнкция также можно выразить следующим образом:
Такое представление XOR может оказаться полезным при построении схемы или сети, потому что у него есть только один работа и небольшое количество а также операции. Доказательство этой идентичности приводится ниже:
Иногда полезно написать следующим образом:
или же:
Эту эквивалентность можно установить , дважды применяя законы Де Моргана к четвертой строке приведенного выше доказательства.
Исключающее или также эквивалентно отрицанию логического биконусловия по правилам материальной импликации ( материальное условное условие эквивалентно разъединению отрицания его антецедента и его следствия) и материальной эквивалентности .
Таким образом, в математической и инженерной нотации мы имеем:
Отрицание
Дух законов Де Моргана может быть применен, у нас есть:
Отношение к современной алгебре
Хотя операторы ( соединение ) и( дизъюнкция ) очень полезны в логических системах, они нарушают более обобщаемую структуру следующим образом:
Системы а также являются моноидами , но не являются группой . К сожалению, это препятствует объединению этих двух систем в более крупные структуры, такие как математическое кольцо .
Однако система, использующая исключительное или это абелева группа . Комбинация операторов а также над элементами производить известное месторождение . Это поле может представлять любую логику, доступную с помощью системы. и имеет дополнительное преимущество в виде арсенала инструментов алгебраического анализа полей.
В частности, если кто-то ассоциирует с 0 и с 1, можно интерпретировать логическую операцию «И» как умножение на и операция "XOR" как дополнение к :
Использование этого базиса для описания булевой системы называется алгебраической нормальной формой .
Исключительное "или" на естественном языке
Дизъюнкция часто понимается исключительно на естественных языках . В английском языке дизъюнктивное слово «or» часто понимается исключительно, особенно когда оно используется с частицей «либо». Приведенный ниже пример на английском языке обычно понимается в разговоре как подразумевающий, что Мэри не одновременно певица и поэт. [3] [4]
- 1. Мария - певица или поэтесса.
Однако дизъюнкцию также можно понимать включительно, даже в сочетании с «либо». Например, первый пример ниже показывает, что «любой» удачно может использоваться в сочетании с прямым утверждением, что оба дизъюнкта истинны. Второй пример показывает, что исключительный вывод исчезает в нисходящем контексте. Если бы дизъюнкция в этом примере понималась как исключительная, оставалась бы возможность, что некоторые люди ели и рис, и бобы. [3]
- 2. Мэри либо певица, либо поэт, либо и то, и другое.
- 3. Никто не ел ни риса, ни бобов.
Примеры, подобные приведенным выше, мотивировали анализ вывода об исключительности как прагматических речевых импликатур, рассчитанных на основе инклюзивной семантики . Импликатуры обычно отменяются и не возникают в нисходящем контексте, если их расчет зависит от максимума количества . Однако некоторые исследователи рассматривали исключительность как истинное семантическое следствие и предлагали неклассическую логику, которая могла бы ее подтвердить. [3]
Такое поведение английского «или» встречается и в других языках. Однако во многих языках есть дизъюнктивные конструкции, которые строго исключают друг друга, например, французский soit ... soit . [3]
Альтернативные символы
Символ, используемый для исключительной дизъюнкции, варьируется от одной области приложения к другой и даже зависит от свойств, которые подчеркиваются в данном контексте обсуждения. В дополнение к аббревиатуре «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; не используется вне контекста программирования, потому что его слишком легко спутать с другими вариантами использования каретки
- , иногда пишется как
- > <
- > - <
- = 1, в символике IEC
Характеристики
- Коммутативность : да
- Ассоциативность : да
- Распределительность :
- Исключающее или не распределяется по какой-либо двоичной функции (даже самой), а логическая конъюнкция распределяется по исключающей или . (Соединение и исключающее или образуют операции умножения и сложения поля GF (2) , и, как и в любом другом поле, они подчиняются закону распределения.)
- Идемпотентность : нет
- Монотонность : нет
- Сохранение правды: нет
- Когда все входные данные верны, выход неверен.
- Сохранение лжи: да
- Когда все входы ложны, выход ложен.
- Спектр Уолша : (2,0,0, −2)
- Non- линейность : 0
- Функция линейная.
Если для истинного (1) и ложного (0) используются двоичные значения, то исключающее или работает точно так же, как сложение по модулю 2.
Информатика
Побитовая операция
Исключительная дизъюнкция часто используется для побитовых операций. Примеры:
- 1 ИСКЛЮЧАЮЩЕЕ ИЛИ 1 = 0
- 1 ИСКЛЮЧАЮЩЕЕ ИЛИ 0 = 1
- 0 ИСКЛЮЧАЮЩЕЕ ИЛИ 1 = 1
- 0 ИСКЛЮЧАЮЩЕЕ ИЛИ 0 = 0
- 1110 2 XOR1001 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, и непредсказуемость вывода гарантированно будет не хуже, чем у лучшего отдельного источника. [5]
XOR используется в RAID 3–6 для создания информации о четности. Например, RAID может «копировать» байты.10011100 2 и01101100 2 с двух (или более) жестких дисков путем операции XOR только что упомянутых байтов, в результате чего (11110000 2 ) и записать его на другой диск. Согласно этому методу, если один из трех жестких дисков потерян, потерянный байт может быть воссоздан путем операции XOR с байтами оставшихся дисков. Например, если диск, содержащий01101100 2 потеряно,10011100 2 и11110000 2 можно использовать XOR для восстановления потерянного байта. [6]
XOR также используется для обнаружения переполнения в результате двоичной арифметической операции со знаком. Если крайний левый оставшийся бит результата не совпадает с бесконечным числом цифр слева, это означает, что произошло переполнение. Выполнение XOR этих двух битов даст «1», если произойдет переполнение.
XOR может использоваться для обмена двумя числовыми переменными в компьютерах с использованием алгоритма обмена XOR ; однако это считается скорее любопытством и на практике не поощряется.
Связанные списки XOR используют свойства XOR для экономии места для представления структур данных двусвязного списка .
В компьютерной графике методы рисования на основе XOR часто используются для управления такими элементами, как ограничивающие прямоугольники и курсоры в системах без альфа-каналов или плоскостей наложения.
Кодировки
Помимо кодов ASCII, оператор кодируется как U + 22BB ⊻ XOR (HTML ⊻
· &veebar
) иU + 2295 ⊕ CIRCLED PLUS (HTML ⊕
· &CirclePlus, ⊕
), оба в блочных математических операторах .
Смотрите также
- Условие материала • (Парадокс)
- Подтверждение дизъюнкции
- Ampheck
- Булева алгебра (логика)
- Логический домен
- Логическая функция
- Булевозначная функция
- Контролируемые ворота НЕ
- Дизъюнктивный силлогизм
- Логика первого порядка
- Включительно или
- Инволюция
- Список тем по булевой алгебре
- Логический график
- Логическое значение
- Операция
- Бит четности
- Исчисление высказываний
- Правило 90
- Симметричная разница
- Шифр XOR
- Ворота XOR
- Связанный список XOR
Заметки
- ^ Germundsson, Роджер; Вайсштейн, Эрик. «XOR» . MathWorld . Wolfram Research . Проверено 17 июня 2015 года .
- ^ Крейг, Эдвард, изд. (1998), Энциклопедия философии Рутледж , 10 , Тейлор и Фрэнсис, стр. 496, ISBN 9780415073103
- ^ а б в г Алони, Мария (2016), Залта, Эдвард Н. (ред.), "Disjunction" , Стэнфордская энциклопедия философии (изд. Зима 2016 г.), Исследовательская лаборатория метафизики, Стэнфордский университет , получено 2020-09-03
- ^ Дженнингс цитирует многочисленных авторов, утверждающих, что слово «или» имеет исключительный смысл. См. Главу 3, «Первый миф об« Или »»:
Дженнингс, Р. Э. (1994). Генеалогия дизъюнкции . Нью-Йорк: Издательство Оксфордского университета. - ^ Дэвис, Роберт Б. (28 февраля 2002 г.). «Исключающее ИЛИ (XOR) и аппаратные генераторы случайных чисел» (PDF) . Проверено 28 августа 2013 года .
- ^ Нобель, Рикард (26 июля 2011 г.). «Как на самом деле работает RAID 5» . Проверено 23 марта 2017 года .
Внешние ссылки
- Пример использования XOR в криптографии
- Все о XOR
- Доказательства свойств XOR и приложений XOR, CS103: математические основы вычислений, Стэнфордский университет