Эксклюзивный или

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Неподтвержденные материалы могут быть оспорены и удалены. Найти источники:  «Эксклюзив или» – новости  · газеты  · книги  · ученый  · JSTOR ( май 2013 г. ) ( Узнайте, как и когда удалять это сообщение )

Эксклюзивный или

XOR
Таблица истинности	${\displaystyle (0110)}$
Логический вентиль
Нормальные формы
Дизъюнктивный	${\displaystyle {\overline {x}}\cdot y+x\cdot {\overline {y}}}$
Соединительный	${\displaystyle ({\overline {x}}+{\overline {y}})\cdot (x+y)}$
Полином Жегалкина	${\displaystyle x\oplus y}$
Решетки Поста
0-сохраняющий	да
1-сохраняющий	нет
Монотонный	нет
Аффинный	да
Самодвойственный	нет
в т е

Логические связки
НЕТ ${\displaystyle \neg A,-A,{\overline {A}},\sim A}$ И ${\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}$ НЕ-И ${\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}$ OR ${\displaystyle A\lor B,A+B,A\mid B,A\parallel B}$ NOR ${\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}$ XNOR ${\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}$ └ equivalent ${\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}$ XOR ${\displaystyle A{\underline {\lor }}B,A\oplus B}$ └nonequivalent ${\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}$ implies ${\displaystyle A\Rightarrow B,A\supset B,A\rightarrow B}$ nonimplication (NIMPLY) ${\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}$ converse ${\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}$ converse nonimplication ${\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}$
Related concepts
Propositional calculus Predicate logic Boolean algebra Truth table Truth function Boolean function Functional completeness Scope (logic)
Applications
Digital logic Programming languages Mathematical logic Philosophy of logic
Category
v t e

Исключающее или , исключающая дизъюнкция , исключающее чередование , логическая неэквивалентность или логическое неравенство — это логический оператор , отрицание которого является логическим биусловием . С двумя входами XOR истинен тогда и только тогда, когда входы различаются (один истинен, один ложен). С несколькими входами XOR истинен тогда и только тогда, когда число истинных входов нечетно . [ ^1]

Он получил название «исключающее или», потому что значение «или» неоднозначно, когда оба операнда истинны. XOR исключает этот случай. Некоторые неформальные способы описания XOR — «один или другой, но не оба», «либо один, либо другой» и «A или B, но не A и B».

Он обозначается префиксным оператором ^{[2] : 16} и инфиксными операторами XOR ( / ˌ ɛ k s ˈ ɔː r / , / ˌ ɛ k s ˈ ɔː / , / ˈ k s ɔː r / или / ˈ k s ɔː / ), EOR , EXOR , , , , ⩛ , , , и .${\displaystyle J}$ ${\displaystyle {\dot {\vee }}}$${\displaystyle {\overline {\vee }}}$${\displaystyle {\underline {\vee }}}$${\displaystyle \oplus }$${\displaystyle \nleftrightarrow }$${\displaystyle \not \equiv }$

Таблица истинности показывает , что она выводит значение true всякий раз, когда входные данные различаются:${\displaystyle A\oplus B}$

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\oplus B}$
Ф	Ф	Ф
Ф	Т	Т
Т	Ф	Т
Т	Т	Ф

Исключительная дизъюнкция по сути означает «либо одно, но не оба, ни ни одно». Другими словами, утверждение истинно тогда и только тогда, когда одно из них истинно, а другое ложно. Например, если скачут две лошади, то одна из них выиграет гонку, но не обе. Исключительная дизъюнкция , также обозначаемая как или , может быть выражена в терминах логической конъюнкции («логическое и», ), дизъюнкции («логическое или», ) и отрицания ( ) следующим образом:${\displaystyle p\nleftrightarrow q}$${\displaystyle p\operatorname {?} q}$${\displaystyle Jpq}$${\displaystyle \wedge }$${\displaystyle \lor }$${\displaystyle \lnot }$

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\lor q)\land \lnot (p\land q)\end{matrix}}}$

Исключающую дизъюнкцию можно также выразить следующим образом:${\displaystyle p\nleftrightarrow q}$

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\land \lnot q)\lor (\lnot p\land q)\end{matrix}}}$

Это представление XOR может оказаться полезным при построении схемы или сети, поскольку оно имеет только одну операцию и небольшое количество операций и . Доказательство этой идентичности приведено ниже:${\displaystyle \lnot }$${\displaystyle \land }$${\displaystyle \lor }$

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\land \lnot q)&\lor &(\lnot p\land q)\\[3pt]&=&((p\land \lnot q)\lor \lnot p)&\land &((p\land \lnot q)\lor q)\\[3pt]&=&((p\lor \lnot p)\land (\lnot q\lor \lnot p))&\land &((p\lor q)\land (\lnot q\lor q))\\[3pt]&=&(\lnot p\lor \lnot q)&\land &(p\lor q)\\[3pt]&=&\lnot (p\land q)&\land &(p\lor q)\end{matrix}}}$

Иногда полезно писать следующим образом:${\displaystyle p\nleftrightarrow q}$

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&\lnot ((p\land q)\lor (\lnot p\land \lnot q))\end{matrix}}}$

или:

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\lor q)\land (\lnot p\lor \lnot q)\end{matrix}}}$

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

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

Подводя итог, мы имеем в математической и инженерной нотации:

${\displaystyle {\begin{matrix}p\nleftrightarrow q&=&(p\land \lnot q)&\lor &(\lnot p\land q)&=&p{\overline {q}}+{\overline {p}}q\\[3pt]&=&(p\lor q)&\land &(\lnot p\lor \lnot q)&=&(p+q)({\overline {p}}+{\overline {q}})\\[3pt]&=&(p\lor q)&\land &\lnot (p\land q)&=&(p+q)({\overline {pq}})\end{matrix}}}$

Применяя дух законов Де Моргана , получаем:$${\displaystyle \lnot (p\nleftrightarrow q)\Leftrightarrow \lnot p\nleftrightarrow q\Leftrightarrow p\nleftrightarrow \lnot q.}$$

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

Системы и являются моноидами , но ни одна из них не является группой . К сожалению, это препятствует объединению этих двух систем в более крупные структуры, такие как математическое кольцо .${\displaystyle (\{T,F\},\wedge )}$${\displaystyle (\{T,F\},\lor )}$

Однако система, использующая исключающее или, является абелевой группой . Сочетание операторов и над элементами создает хорошо известное двухэлементное поле . Это поле может представлять любую логику, доступную с помощью системы , и имеет дополнительное преимущество в виде арсенала инструментов алгебраического анализа для полей.${\displaystyle (\{T,F\},\oplus )}$ ${\displaystyle \wedge }$${\displaystyle \oplus }$${\displaystyle \{T,F\}}$${\displaystyle \mathbb {F} _{2}}$${\displaystyle (\land ,\lor )}$

Более конкретно, если сопоставить 0 и 1, то можно интерпретировать логическую операцию «И» как умножение , а операцию «ИСКЛЮЧАЮЩЕЕ ИЛИ» — как сложение :${\displaystyle F}$${\displaystyle T}$${\displaystyle \mathbb {F} _{2}}$${\displaystyle \mathbb {F} _{2}}$

${\displaystyle {\begin{matrix}r=p\land q&\Leftrightarrow &r=p\cdot q{\pmod {2}}\\[3pt]r=p\oplus q&\Leftrightarrow &r=p+q{\pmod {2}}\\\end{matrix}}}$

Описание булевой функции как полинома от с использованием этого базиса называется алгебраической нормальной формой функции . ^[3]${\displaystyle \mathbb {F} _{2}}$

Дизъюнкция часто понимается исключительно в естественных языках . В английском языке разделительное слово "or" часто понимается исключительно, особенно когда используется с частицей "either". Английский пример ниже обычно понимается в разговоре как подразумевающий, что Мэри не является одновременно певицей и поэтессой. ^{[4] [5]}

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

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

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

3. Никто не ел ни риса, ни бобов.

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

Такое поведение английского "or" также встречается в других языках. Однако во многих языках есть дизъюнктивные конструкции, которые являются строго исключающими, например, французский soit... soit . ^[4]

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

• ${\displaystyle +}$был использован Джорджем Булем в 1847 году. ^[6] Хотя Буль использовал его в основном на классах, он также рассматривал случай, когда предложения в , и в то время является связкой. Более того, Буль использовал его исключительно. Хотя такое использование не показывает связь между инклюзивной дизъюнкцией (для которой почти постоянно используется в настоящее время) и исключающей дизъюнкцией, а также может вызывать путаницу с другими его использованиями, некоторые классические и современные учебники все еще сохраняют такое использование. ^{[7] [8]}${\displaystyle +}$${\displaystyle x,y}$${\displaystyle x+y}$${\displaystyle +}$${\displaystyle \vee }$
• ${\displaystyle {\overline {\vee }}}$был использован Кристиной Лэдд-Франклин в 1883 году. ^[9] Строго говоря, Лэдд использовал его для выражения « is-not » или «No is », т. е. использовал в качестве исключений, хотя неявно имеет значение исключающей дизъюнкции, поскольку статья озаглавлена ​​как «Об алгебре логики».${\displaystyle A\operatorname {\overline {\vee }} B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle {\overline {\vee }}}$${\displaystyle {\overline {\vee }}}$
• ${\displaystyle \not =}$, обозначающее отрицание эквивалентности , использовал Эрнст Шредер в 1890 году, ^{[10] : 307} Хотя использование как эквивалентности можно отнести к Джорджу Булю в 1847 году, ^[6] в течение 40 лет после Буля его последователи, такие как Чарльз Сандерс Пирс , Хью Макколл , Джузеппе Пеано и т. д., не использовали как неэквивалентность буквально, возможно, потому, что ее можно было легко определить через отрицание и эквивалентность.${\displaystyle =}$${\displaystyle \not =}$
• ${\displaystyle \circ }$был использован Джузеппе Пеано в 1894 году: " . Знак соответствует латинскому aut ; знак vel ." ^{[11] : 10} Обратите внимание, что латинское слово "aut" означает "исключающее или", а "vel" означает "включающее или", и Пеано использовал это как включающую дизъюнкцию.${\displaystyle a\circ b=a-b\,\cup \,b-a}$${\displaystyle \circ }$${\displaystyle \cup }$${\displaystyle \cup }$
• ${\displaystyle \vee \vee }$использовался Израилом Соломоновичем Градштейном (Izrail Solomonovich Gradstein) в 1936 году. ^{[12] : 76}
• ${\displaystyle \oplus }$был использован Клодом Шенноном в 1938 году. ^[13] Шеннон заимствовал символ как исключающую дизъюнкцию у Эдварда Вермилье Хантингтона в 1904 году. ^[14] Хантингтон заимствовал символ у Готфрида Вильгельма Лейбница в 1890 году (первоначальная дата точно не известна, но почти наверняка он написан после 1685 года; и 1890 год - это время публикации). ^[15] В то время как Хантингтон в 1904 году и Лейбниц в 1890 году использовали символ как алгебраическую операцию. Кроме того, Хантингтон в 1904 году использовал символ как инклюзивную дизъюнкцию (логическую сумму), а в 1933 году использовал как инклюзивную дизъюнкцию. ^[16]${\displaystyle +}$
• ${\displaystyle \not \equiv }$, также обозначающий отрицание эквивалентности , был использован Алонзо Чёрчем в 1944 году. ^[17]
• ${\displaystyle J}$(как префиксный оператор , ) был использован Юзефом Марией Бохеньским в 1949 году. ^{[2] : 16} Кто-то ^[18] может ошибочно принять, что именно Ян Лукасевич первым использовал для исключающей дизъюнкции (кажется, эта ошибка широко распространена), в то время как ни в 1929 году ^[19], ни в других работах Лукасевич не использовал такого использования. Фактически, в 1949 году Бохеньский ввел систему польской нотации , которая называет все 16 бинарных связок классической логики, которая является совместимым расширением нотации Лукасевича 1929 года, и в которой для исключающей дизъюнкции впервые появилось. Использование Бохеньским термина «исключающая дизъюнкция» не имеет никакого отношения к польскому «alternatywa rozłączna» — «исключающее или» и является случайностью, см. таблицу на стр. 16 книги 1949 года.${\displaystyle J\phi \psi }$${\displaystyle J}$${\displaystyle J}$${\displaystyle J}$
• ^, знак вставки , использовался в нескольких языках программирования для обозначения побитового исключающего оператора ИЛИ, начиная с языка C ^[20] , а также включая C++ , C# , D , Java , Perl , Ruby , PHP и Python .
• Симметричная разность двух множеств и , которую можно интерпретировать как их поэлементное исключающее или, по-разному обозначается как , , или . ^[21]${\displaystyle S}$${\displaystyle T}$${\displaystyle S\ominus T}$${\displaystyle S\mathop {\triangledown } T}$${\displaystyle S\mathop {\vartriangle } T}$

Коммутативность : да

${\displaystyle A\oplus B}$	${\displaystyle \Leftrightarrow }$	${\displaystyle B\oplus A}$
	${\displaystyle \Leftrightarrow }$

Ассоциативность : да

${\displaystyle ~A}$	${\displaystyle ~~~\oplus ~~~}$	${\displaystyle (B\oplus C)}$	${\displaystyle \Leftrightarrow }$			${\displaystyle (A\oplus B)}$	${\displaystyle ~~~\oplus ~~~}$	${\displaystyle ~C}$
	${\displaystyle ~~~\oplus ~~~}$		${\displaystyle \Leftrightarrow }$		${\displaystyle \Leftrightarrow }$		${\displaystyle ~~~\oplus ~~~}$

Распределяемость :

Исключающее ИЛИ не распространяется ни на одну двоичную функцию (даже на само себя), но логическая конъюнкция распространяется на исключающее ИЛИ . (Конъюнкция и исключающее ИЛИ образуют операции умножения и сложения поля GF (2) , и как в любом поле они подчиняются распределительному закону.)${\displaystyle C\land (A\oplus B)=(C\land A)\oplus (C\land B)}$

Идемпотентность : нет

${\displaystyle ~A~}$	${\displaystyle ~\oplus ~}$	${\displaystyle ~A~}$	${\displaystyle \Leftrightarrow }$	${\displaystyle ~0~}$	${\displaystyle \nLeftrightarrow }$	${\displaystyle ~A~}$
	${\displaystyle ~\oplus ~}$		${\displaystyle \Leftrightarrow }$		${\displaystyle \nLeftrightarrow }$

Монотонность : нет

${\displaystyle A\rightarrow B}$	${\displaystyle \nRightarrow }$			${\displaystyle (A\oplus C)}$	${\displaystyle \rightarrow }$	${\displaystyle (B\oplus C)}$
	${\displaystyle \nRightarrow }$		${\displaystyle \Leftrightarrow }$		${\displaystyle \rightarrow }$

Сохранение истины: нет

Когда все входные данные истинны, выходные данные не истинны.

${\displaystyle A\land B}$	${\displaystyle \nRightarrow }$	${\displaystyle A\oplus B}$
	${\displaystyle \nRightarrow }$

Сохранение лжи: да

Если все входные данные ложны, то и выходной сигнал ложный.

${\displaystyle A\oplus B}$	${\displaystyle \Rightarrow }$	${\displaystyle A\lor B}$
	${\displaystyle \Rightarrow }$

Спектр Уолша : (2,0,0,−2)

Нелинейность : 0

Функция линейна.

Инволюция:

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

${\displaystyle ~A\oplus B~}$	${\displaystyle ~\oplus ~}$	${\displaystyle ~B~}$	${\displaystyle \Leftrightarrow }$	${\displaystyle ~A~}$
	${\displaystyle ~\oplus ~}$		${\displaystyle \Leftrightarrow }$

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

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

• 1 XOR 1 = 0
• 1 XOR 0 = 1
• 0 XOR 1 = 1
• 0 XOR 0 = 0
• 1110 2 XOR 1001 2 = 0111 2 (это эквивалентно сложению без переноса )

Как отмечено выше, поскольку исключающая дизъюнкция идентична сложению по модулю 2, побитовая исключающая дизъюнкция двух n -битных строк идентична стандартному вектору сложения в векторном пространстве .${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$

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

• Он сообщает, являются ли два бита неравными.
• Это управляемый бит-флиппер (управляющий вход выбирает, инвертировать или нет входные данные).
• Он сообщает, существует ли нечетное число единичных битов ( истинно тогда и только тогда, когда нечетное число переменных имеет значение true), что равно биту четности, возвращаемому функцией четности .${\displaystyle A\oplus B\oplus C\oplus D\oplus E}$

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

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

В криптографии XOR иногда используется как простая, самообратная функция смешивания, например, в одноразовых шифрблокнотах или сетевых системах Фейстеля . ^{[ требуется ссылка ]} XOR также широко используется в блочных шифрах, таких как AES (Rijndael) или Serpent, а также в реализациях блочных шифров (CBC, CFB, OFB или CTR).

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

Аналогично, 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 ; однако это скорее считается курьёзом и не поощряется на практике.

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

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

\nleftrightarrowВ разметке на основе LaTeX ( ) он также называется "стрелка не влево-вправо" ( ). Помимо кодов ASCII, оператор кодируется как U+22BB ⊻ XOR ( ⊻ ) и U+2295 ⊕ CIRCLED PLUS ( ⊕, ⊕ ), оба в блочных математических операторах .${\displaystyle \nleftrightarrow }$

На Викискладе есть медиафайлы по теме Исключительная дизъюнкция .

Найдите значение оператора «исключающее ИЛИ»  или «XOR» в Викисловаре, бесплатном словаре.

• Все о XOR
• Доказательства свойств XOR и применения XOR, CS103: Математические основы вычислений, Стэнфордский университет