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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Эксклюзивное ИЛИ »  -  новости  · газеты  · книги  · ученый  · 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-консервирующий	нет
Монотонный	нет
Аффинный	да
v т е

Диаграмма Венна из${\ displaystyle \ scriptstyle A \ oplus B \ oplus C}$

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

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

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

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

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

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

• 0, ложь
• 1, правда

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

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

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

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

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

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

${\displaystyle {\begin{matrix}p\oplus 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\oplus q}$

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

или же:

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

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

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

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

${\displaystyle {\begin{matrix}p\oplus 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 \wedge }$${\displaystyle \lor }$

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

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

Более конкретно, если связать с 0 и с 1, можно интерпретировать логическую операцию «И» как умножение и операцию «исключающее ИЛИ» как сложение :${\displaystyle F}$${\displaystyle T}$${\displaystyle F_{2}}$${\displaystyle 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}}}$

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

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

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

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

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

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

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

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

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

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

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

• +, знак плюс, преимущество которого состоит в том, что все обычные алгебраические свойства математических колец и полей можно использовать без лишних слов; но знак плюс также используется для инклюзивной дизъюнкции в некоторых системах счисления; обратите внимание, что исключительная дизъюнкция соответствует сложению по модулю 2, которое имеет следующую таблицу сложения, явно изоморфную приведенной выше:

${\displaystyle p}$	${\displaystyle q}$	${\displaystyle p+q}$
0	0	0
0	1	1
1	0	1
1	1	0

• ${\displaystyle \oplus }$, измененный знак плюса; этот символ также используется в математике для прямой суммы алгебраических структур
• J, как в J pq
• Инклюзивный символ дизъюнкции ( ), который каким-либо образом модифицируется, например${\displaystyle \lor }$
  • ${\displaystyle {\underline {\lor }}}$
  • ${\displaystyle {\dot {\vee }}}$
• ^, каретка , используемая в нескольких языках программирования , таких как C , C ++ , C # , D , Java , Perl , Ruby , PHP и Python , обозначающая побитовый оператор XOR; не используется вне контекста программирования, потому что его слишком легко спутать с другими вариантами использования каретки
• , иногда пишется как
  • > <
  • > - <
• = 1, в символике IEC

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

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

${\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)

Non- линейность : 0

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

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

Информатика

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

Nimber дополнение является эксклюзивным или из целых неотрицательных чисел в двоичном представлении. Это тоже векторное сложение в .${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{4}}$

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

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

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

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

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

В логических схемах можно сделать простой сумматор с вентилем 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 с двух (или более) жестких дисков, выполняя операцию « исключающее ИЛИ» только что упомянутых байтов, в результате чего получается ( 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  · ), оба в блочных математических операторах . ⊕  ⊕, ⊕

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

Примечания

внешняя ссылка

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

Поищите эксклюзивный или  или XOR в Викисловаре, бесплатном словаре.

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