Исключающее или , исключительная дизъюнкция , исключительное чередование , логическая неэквивалентность или логическое неравенство — это логический оператор , отрицание которого является логическим двуусловием . При двух входных данных операция XOR является истиной тогда и только тогда, когда входные данные различаются (один — истина, другой — ложь). При наличии нескольких входных данных операция XOR является истинной тогда и только тогда, когда количество истинных входных данных нечетно . [1]
Он получил название «исключающее или», потому что значение «или» неоднозначно, когда оба операнда истинны. XOR исключает этот случай. Некоторыми неформальными способами описания XOR являются «один или другой, но не оба», «либо тот, либо другой» и «A или B, но не A и B».
Он символизируется префиксным оператором [2] : 16 и инфиксными операторами XOR ( / ˌ ɛ k s ˈ ɔː r / , / ˌ ɛ k s ˈ ɔː / , / ˈ k s ɔː r / или / ˈ k s ɔː / ), EOR , EXOR , , , , ⩛ , , , и .
Определение
Каждая строка этой двоичной матрицы Уолша представляет собой таблицу истинности вариативного XOR аргументов, показанных слева. Например, строка AB соответствует 2-круговой диаграмме Венна, а строка ABC - диаграмме Венна с 3 кругами, показанной выше. (Как и на диаграммах Венна, белый цвет — ложь, а красный — истина.)
Таблица истинности показывает , что она выводит true всякий раз , когда входные данные различаются:
Эквиваленты, исключение и введение
Исключительная дизъюнкция по сути означает «либо одно, но не оба и не ничего». Другими словами, утверждение истинно тогда и только тогда, когда одно истинно, а другое ложно. Например, если соревнуются две лошади, то победит одна из них, но не обе. Исключительная дизъюнкция , также обозначаемая или , может быть выражена через логическую конъюнкцию («логическое и», ), дизъюнкцию («логическое или», ) и отрицание ( ) следующим образом:
Исключительную дизъюнкцию можно также выразить следующим образом:
Такое представление XOR может оказаться полезным при построении схемы или сети, поскольку оно имеет только одну операцию и небольшое количество операций and . Доказательство этой идентичности приведено ниже:
Иногда полезно написать так:
или:
Эту эквивалентность можно установить, дважды применив законы Де Моргана к четвертой строке приведенного выше доказательства.
Вкратце, мы имеем в математических и инженерных обозначениях:
Отрицание оператора
Можно применить дух законов Де Моргана:
Отношение к современной алгебре
Хотя операторы ( конъюнкция ) и ( дизъюнкция ) очень полезны в логических системах, они не позволяют создать более обобщаемую структуру следующим образом:
Системы и являются моноидами , но ни одна из них не является группой . К сожалению, это препятствует объединению этих двух систем в более крупные структуры, такие как математическое кольцо .
Однако система, использующая исключительную или, является абелевой группой . Комбинация операторов и надэлементов создает хорошо известное двухэлементное поле . Это поле может представлять любую логику, доступную с помощью системы, и имеет дополнительное преимущество, заключающееся в арсенале инструментов алгебраического анализа полей.
Более конкретно, если кто-то ассоциирует с 0 и с 1, можно интерпретировать логическую операцию «И» как умножение , а операцию «ИСКЛЮЧАЮЩЕЕ ИЛИ» как сложение :
Дизъюнкция часто понимается исключительно в естественных языках . В английском языке разделительное слово «или» часто понимается исключительно, особенно когда оно употребляется с частицей «либо». Приведенный ниже английский пример в разговоре обычно понимается как подразумевающий, что Мэри не является одновременно певицей и поэтессой. [4] [5]
1. Мэри – певица или поэтесса.
Однако дизъюнкцию можно понимать и включительно, даже в сочетании с «либо». Например, первый пример ниже показывает, что «либо» можно удачно использовать в сочетании с прямым утверждением, что оба дизъюнкта истинны. Второй пример показывает, что исключительный вывод исчезает в нисходящих влекущих контекстах. Если бы в этом примере дизъюнкция понималась как исключающая, это оставило бы открытой возможность того, что некоторые люди ели и рис, и бобы. [4]
2. Мэри либо певица, либо поэтесса, либо и то, и другое.
3. Никто не ел ни риса, ни фасоли.
Примеры, подобные приведенным выше, мотивировали анализ вывода об исключительности как прагматических разговорных импликатур , рассчитанных на основе инклюзивной семантики . Импликатуры обычно отменяемы и не возникают в нисходящих контекстах, если их расчет зависит от Максимы Количества . Однако некоторые исследователи рассматривали исключительность как добросовестное семантическое следствие и предлагали неклассическую логику, которая могла бы ее подтвердить. [4]
Такое поведение английского «или» встречается и в других языках. Однако во многих языках есть дизъюнктивные конструкции, которые являются строго исключающими, например, во французском языке soit... soit . [4]
Альтернативные символы
Символ, используемый для исключительной дизъюнкции, варьируется от одной области применения к другой и даже зависит от свойств, подчеркиваемых в данном контексте обсуждения. Помимо аббревиатуры «XOR», также может встречаться любой из следующих символов:
был использован Джорджем Булем в 1847 году. [6] Хотя Буль использовал в основном классы, он также рассматривал случаи, когда предложения в , и в то время являются связками. Более того, Буль использовал его исключительно. Хотя такое использование не показывает связи между инклюзивной дизъюнкцией (которая в настоящее время почти постоянно используется) и исключительной дизъюнкцией, а также может вызвать путаницу с другими ее использованиями, в некоторых классических и современных учебниках все еще сохраняется такое использование. [7] [8]
было использовано Кристиной Лэдд-Франклин в 1883 году. [9] Строго говоря, Лэдд использовал для выражения « есть-не » или «нет есть », т. е. использовался как исключение, при этом имплицитно имело значение исключительной дизъюнкции, поскольку статья озаглавлена как «Об алгебре логики».
, обозначающий отрицание эквивалентности , был использован Эрнстом Шредером в 1890 году, [10] : 307 Хотя использование термина эквивалентность можно отнести к Джорджу Булю в 1847 году, [6] в течение 40 лет после Буля, его последователи, такие как как Чарльз Сандерс Пирс , Хью Макколл , Джузеппе Пеано и т. д., не использовали термин «неэквивалентность» буквально, что, возможно, связано с тем, что его можно было легко определить через отрицание и эквивалентность.
был использован Джузеппе Пеано в 1894 году: « Знак соответствует латинскому aut ; знак vel ». [11] : 10 Обратите внимание, что латинское слово «aut» означает «исключающее или», а «vel» означает «включающее или», и что Пеано использует его как включающую дизъюнкцию.
использовался Израилом Соломоновичем Градштейном (Izrail Solomonovich Gradstein) в 1936 году. [12] : 76
использовался Клодом Шенноном в 1938 году. [13] Шеннон позаимствовал этот символ как исключительную дизъюнкцию у Эдварда Вермили Хантингтона в 1904 году . [14] Хантингтон заимствовал символ у Готфрида Вильгельма Лейбница в 1890 году (исходная дата точно не известна, но почти наверняка оно написано после 1685 года, а время публикации — 1890 год). [15] Хотя и Хантингтон в 1904 году, и Лейбниц в 1890 году использовали символ как алгебраическую операцию. Более того, Хантингтон в 1904 году использовал этот символ и как инклюзивную дизъюнкцию (логическую сумму), а в 1933 году — как инклюзивную дизъюнкцию. [16]
, также обозначающий отрицание эквивалентности , был использован Алонзо Чёрчем в 1944 году. [17]
(как префиксный оператор , ) был использован Юзефом Марией Боченским в 1949 году. [2] : 16 Кто-то [18] может ошибиться, что именно Ян Лукасевич первым использовал для исключающей дизъюнкции (похоже, что ошибка широко распространена) , тогда как ни в 1929 г. [19], ни в других работах Лукасевич такого не использовал. Фактически, в 1949 году Боченский ввел систему польской записи , в которой названы все 16 бинарных связок классической логики, которая является совместимым расширением системы обозначений Лукасевича 1929 года и в которой впервые появилась исключительная дизъюнкция. Использование Боченским слова «исключительная дизъюнкция» не имеет никакого отношения к польскому «alternatywa rozłączna», означающему «исключительное или», и является случайностью, которую см. в таблице на странице 16 книги 1949 года.
^, каретка , использовалась в нескольких языках программирования для обозначения побитового исключающего оператора or, начиная с C [20] , а также включая C++ , C# , D , Java , Perl , Ruby , PHP и Python .
Симметричная разность двух множеств и , которую можно интерпретировать как их поэлементное исключение или, по-разному обозначалась как , или . [21]
Исключающее or не распространяется ни на одну бинарную функцию (даже на саму себя), но логическое соединение распространяется на исключающее или . (Соединение и исключение или образуют операции умножения и сложения поля GF (2) и, как и в любом поле, они подчиняются закону распределения.)
Исключающая или с одним указанным входным сигналом, как функция другого входного сигнала, является инволюционной или самообратной функцией; применение его дважды оставляет ввод переменной неизменным.
Если используются двоичные значения для true (1) и false (0), то исключающее или работает точно так же, как сложение по модулю 2.
Как отмечалось выше, поскольку исключающая дизъюнкция идентична сложению по модулю 2, побитовая исключающая дизъюнкция двух n -битных строк идентична стандартному вектору сложения в векторном пространстве .
В информатике исключительная дизъюнкция имеет несколько применений:
Он сообщает, являются ли два бита неравными.
Это необязательный бит-флиппер (решающий вход выбирает, инвертировать ли входные данные).
В некоторых компьютерных архитектурах более эффективно хранить ноль в регистре путем выполнения операции XOR над самим собой (биты, подвергнутые операции XOR сами по себе, всегда равны нулю), чем загружать и сохранять нулевое значение.
В криптографии XOR иногда используется как простая самообратная функция смешивания, например, в одноразовых блокнотах или сетевых системах Фейстеля . [ нужна цитация ] XOR также широко используется в блочных шифрах, таких как AES (Rijndael) или Serpent, а также в реализации блочных шифров (CBC, CFB, OFB или CTR).
Аналогично, XOR можно использовать при создании пулов энтропии для аппаратных генераторов случайных чисел . Операция XOR сохраняет случайность, а это означает, что случайный бит, подвергнутый операции XOR с неслучайным битом, приведет к получению случайного бита. Несколько источников потенциально случайных данных можно объединить с помощью XOR, и непредсказуемость выходных данных гарантированно будет не хуже, чем у лучшего отдельного источника. [22]
XOR используется в RAID 3–6 для создания информации о четности. Например, RAID может «резервировать» байты 10011100 2 и 01101100 2 с двух (или более) жестких дисков путем XOR только что упомянутых байтов, в результате чего получается ( 11110000 2 ) и записи его на другой диск. Согласно этому методу, если какой-либо из трех жестких дисков утерян, потерянный байт можно воссоздать путем операции XOR байтов с оставшихся дисков. Например, если диск, содержащий 01101100 2 , потерян, 10011100 2 и 11110000 2 можно выполнить с помощью операции XOR для восстановления потерянного байта. [23]
XOR также используется для обнаружения переполнения в результате знаковой двоичной арифметической операции. Если самый левый оставшийся бит результата не совпадает с бесконечным числом цифр слева, это означает, что произошло переполнение. Если произойдет переполнение, операция XOR этих двух битов даст «1».
XOR можно использовать для замены двух числовых переменных в компьютерах с использованием алгоритма замены XOR ; однако это считается скорее диковинкой и не поощряется на практике.
\nleftrightarrowВ уценке на основе LaTeX ( ) она также называется «не стрелка влево-вправо» ( ) . Помимо кодов ASCII, оператор кодируется как U+22BB ⊻ XOR ( ⊻ ) и U+2295 ⊕ CIRCLED PLUS ( ⊕, ⊕ ), оба в блочных математических операторах .
^ Аб Боченски, JM (1949). Précis de logique mathématique (PDF) (на французском языке). Нидерланды: Ф.Г. Крундер, Буссум, Пайс-Бас.Переведено как Боченский, Ю.М. (1959). Краткое изложение математической логики . Перевод Берда, О. Дордрехт, Голландия: Издательство D. Reidel Publishing Company. дои : 10.1007/978-94-017-0592-9. ISBN 978-90-481-8329-6.
^ abcd Алони, Мария (2016). «Дизъюнкция». В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии (изд. Зима 2016 г.). Лаборатория метафизических исследований Стэнфордского университета . Проверено 3 сентября 2020 г.
↑ Дженнингс цитирует многочисленных авторов, утверждающих, что слово «или» имеет исключительный смысл. См. главу 3 «Первый миф об «или»: Дженнингс Р.Э. (1994). Генеалогия дизъюнкции . Нью-Йорк: Издательство Оксфордского университета.
^ Аб Буль, Г. (1847). Математический анализ логики как очерк дедуктивного рассуждения. Кембридж/Лондон: Макмиллан, Барклай и Макмиллан/Джордж Белл. п. 17.
^ Эндертон, Х. (2001) [1972]. Математическое введение в логику (2-е изд.). Сан-Диего, Нью-Йорк, Бостон, Лондон, Торонто, Сидней и Токио: научно-технологическая компания Harcourt. п. 51.
^ Раутенберг, В. (2010) [2006]. Краткое введение в математическую логику (3-е изд.). Нью-Йорк, Дордрехт, Гейдельберг и Лондон: Springer. п. 3.
^ Лэдд, Кристина (1883). «Об алгебре логики». В Пирсе, CS (ред.). Исследования в области логики, проводимые членами Университета Джонса Хопкинса . Бостон: Литтл, Браун и компания. стр. 17–71.
^ Шредер, Э. (1890). Vorlesungen über die Algebra der Logik (Exakte Logik), Erster Band (на немецком языке). Лейпциг: Druck und Verlag BG Teubner.Перепечатано Thoemmes Press в 2000 году.
^ Пеано, Г. (1894). Математические обозначения логики. Введение в математические формулы . Турин: Фрателли Боккна. Перепечатано в Peano, G. (1958). Опера Scelte, Том II. Рома: Edizioni Cremonese. стр. 123–176.
^ ГРАДШТЕЙН, И. С. (1959) [1936]. ПРЯМАЯ И ОБРАТНАЯ ТЕОРЕМЫ: ЭЛЕМЕНТЫ АЛГЕБРЫ ЛОГИКИ (3-е изд.). МОСКВА: ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ФИЗИКА-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ.В переводе Градштейн И.С. (1963). Прямые и обратные теоремы: элементы символической логики . Перевод Боддингтона, Т. Оксфорда, Лондон, Нью-Йорк и Париж: Pergamon Press.
^ Шеннон, CE (1938). «Символический анализ релейных и коммутационных схем» (PDF) . Труды Американского института инженеров-электриков . 57 (12): 713–723. дои : 10.1109/T-AIEE.1938.5057767. hdl : 1721.1/11173 . S2CID 51638483.
^ Хантингтон, EV (1904). «Наборы независимых постулатов алгебры логики». Труды Американского математического общества . 5 (3): 288–309. дои : 10.1090/S0002-9947-1904-1500675-4.
^ Лейбниц, GW (1890) [16??/17??]. Герхардт, CI (ред.). Die philosophischen Schriften, Siebter Band (на немецком языке). Берлин: Вайдманн. п. 237 . Проверено 7 июля 2023 г.
^ Хантингтон, Э.В. (1933). «Новые наборы независимых постулатов алгебры логики, с особым упором на Principia Mathematica Уайтхеда и Рассела». Труды Американского математического общества . 35 (1): 274–304.
^ Черч, А. (1996) [1944]. Введение в математическую логику . Нью-Джерси: Издательство Принстонского университета. п. 37.
^ Лукасевич, Ян (1929). Elementy logiki matematycznej [ Элементы математической логики ] (на польском языке) (1-е изд.). Варшава, Польша: Państwowe Wydawnictwo Naukowe .