Эта статья требует дополнительных ссылок для проверки . ( май 2013 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) |
XOR | |
---|---|
Таблица истинности | |
Логический вентиль | |
Нормальные формы | |
Дизъюнктивный | |
Конъюнктивный | |
Полином Жегалкина | |
Решетки столба | |
0-сохраняющий | да |
1-консервирующий | нет |
Монотонный | нет |
Аффинный | да |
Исключительное или или эксклюзивный дизъюнкция является логическая операция , которая выполняется тогда и только тогда , когда ее аргументы отличаются (один, правда, другое ложно). [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 может быть полезно при построении схемы или сетей, поскольку он имеет только одну операцию и небольшое количество и операции. Доказательство этой идентичности приводится ниже:
Иногда бывает полезно написать так:
или же:
Эту эквивалентность можно установить , дважды применяя законы Де Моргана к четвертой строке приведенного выше доказательства.
Исключающее или также эквивалентно отрицанию логического биконусловия по правилам материальной импликации ( материальное условное условие эквивалентно разъединению отрицания его антецедента и его следствия) и материальной эквивалентности .
Таким образом, в математической и инженерной нотации мы имеем:
Отношение к современной алгебре
Хотя операторы ( конъюнкция ) и ( дизъюнкция ) очень полезны в логических системах, они не позволяют получить более обобщаемую структуру следующим образом:
Системы и являются моноидами , но ни одна из них не является группой . К сожалению, это препятствует объединению этих двух систем в более крупные структуры, такие как математическое кольцо .
Тем не менее, система , использующая исключающее или является абелева группа . Комбинация операторов и элементов over дает хорошо известное поле . Это поле может представлять любую логику, доступную с помощью системы, и имеет дополнительное преимущество арсенала инструментов алгебраического анализа для полей. F 2 {\displaystyle F_{2}}
Более конкретно, если связать с 0 и с 1, можно интерпретировать логическую операцию «И» как умножение и операцию «исключающее ИЛИ» как сложение :
Использование этого базиса для описания булевой системы называется алгебраической нормальной формой .
Исключительное "или" на естественном языке
Дизъюнкция часто понимается исключительно на естественных языках . В английском языке дизъюнктивное слово «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 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, и непредсказуемость вывода гарантированно будет не хуже, чем у лучшего отдельного источника. [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 ⊻
· ⊻
) и U + 2295 ⊕ CIRCLED PLUS (HTML · ), оба в блочных математических операторах . ⊕
⊕, ⊕
Смотрите также
- Условие материала • (Парадокс)
- Подтверждение дизъюнкции
- Ampheck
- Булева алгебра (логика)
- Логический домен
- Логическая функция
- Булевозначная функция
- Контролируемые ворота НЕ
- Дизъюнктивный силлогизм
- Логика первого порядка
- Включительно или
- Инволюция
- Список тем по булевой алгебре
- Логический график
- Логическое значение
- Операция
- Бит четности
- Исчисление высказываний
- Правило 90
- Симметричная разница
- Шифр XOR
- Ворота XOR
- Связанный список XOR
Заметки
- ^ Germundsson, Роджер; Вайсштейн, Эрик. «XOR» . MathWorld . Wolfram Research . Проверено 17 июня 2015 года .
- ^ Крейг, Эдвард, изд. (1998), Энциклопедия философии Рутледж , 10 , Тейлор и Фрэнсис, стр. 496, ISBN 9780415073103
- ^ a b c d Алони, Мария (2016), Залта, Эдвард Н. (ред.), "Disjunction" , Стэнфордская энциклопедия философии (изд. зима 2016 г.), Исследовательская лаборатория метафизики, Стэнфордский университет , получено 2020-09- 03
- ^ Дженнингс цитирует многочисленных авторов, утверждающих, что слово «или» имеет исключительный смысл. См. Главу 3, «Первый миф об« Или »»: Jennings, RE (1994). Генеалогия дизъюнкции . Нью-Йорк: Издательство Оксфордского университета.
- ↑ Дэвис, Роберт Б. (28 февраля 2002 г.). «Исключающее ИЛИ (XOR) и аппаратные генераторы случайных чисел» (PDF) . Проверено 28 августа 2013 года .
- ↑ Нобель, Рикард (26 июля 2011 г.). «Как на самом деле работает RAID 5» . Проверено 23 марта 2017 года .
Внешние ссылки
Викискладе есть медиафайлы по теме исключительной дизъюнкции . |
Поищите эксклюзивный или или XOR в Викисловаре, бесплатном словаре. |
- Пример использования XOR в криптографии
- Все о XOR
- Доказательства свойств XOR и приложений XOR, CS103: математические основы вычислений, Стэнфордский университет