Эксклюзивный или - Exclusive or

эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью от добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: "Эксклюзивный или"  – Новости  · газеты  · книги  · ученый  · 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 scriptstyle A oplus B oplus C}$

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

это символизированный оператором префикса J^[2] и по инфикс операторы XOR (/ˌɛksˈɔːr/ или /ˈzɔːr/), EOR, EXOR, ⊻, ⩒, ⩛, ⊕, ↮, и ≢. В отрицание XOR является логическая двусмысленность, который возвращает истину, только если два входа совпадают.

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

В более общем плане XOR истинно только тогда, когда истинно нечетное количество входов. Цепочка XOR -а XOR б XOR c XOR d (и так далее) - истинно, если нечетное количество входов истинно, и ложно, если четное количество входов истинно.

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

Аргументы слева объединены XOR. Это двоичный Матрица Уолша (ср. Код Адамара ).

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

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

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

Исключительная дизъюнкция по существу означает «либо одно, но не оба, либо ничего». Другими словами, утверждение верно если и только если одно верно, а другое ложно. Например, если участвуют две лошади, то одна из них выиграет скачку, но не обе. Исключительная дизъюнкция ${ displaystyle p oplus q}$, также обозначается ${ displaystyle p}$ ⩛ ${ displaystyle q}$ или ${ displaystyle operatorname {J} pq}$, можно выразить через логическое соединение ("логическое и", ${ Displaystyle клин}$), дизъюнкция ("логическое или", ${ 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 клин}$ и ${ 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}}}$

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

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

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

${ 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 клин}$ (соединение ) и ${ displaystyle lor}$ (дизъюнкция ) очень полезны в логических системах, они нарушают более обобщаемую структуру следующим образом:

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

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

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

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

Эксклюзивное "или" на английском языке

Оксфордский словарь английского языка объясняет «либо ... либо» следующим образом:

Основная функция либои т. д., чтобы подчеркнуть полное безразличие из двух (или более) предметов или курсов ...; но второстепенная функция - подчеркнуть взаимную исключительность = одного из двух, но не обоих одновременно.^[3]

Исключающее-или явно заявляет «одно или другое, но не ни то, ни другое». Однако соответствие отображения между формальными Булево операторы и конъюнкции естественного языка далеки от простых или взаимно однозначных, и десятилетиями изучались в лингвистика и аналитическая философия.^{[нужна цитата ]}

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

В английском языке конструкция «либо ... или» обычно используется для обозначения исключающего или, а «или» обычно используется для включения.^{[сомнительный – обсудить]} Но в испанском языке слово «o» (или) может использоваться в форме «п о q"(включительно) или форма" o п о q"(исключительный). Некоторые могут утверждать, что любой двоичный или другой н-арный исключающее "или" истинно тогда и только тогда, когда оно имеет нечетное количество истинных входов (это, однако, не единственное разумное определение; например, цифровые вентили xor с несколькими входами обычно не используют это определение), и что там не является союзом в английском языке, который обладает этим общим свойством. Например, Барретт и Стеннер утверждают в статье 1971 года «Миф об исключительном» или'"(Mind, 80 (317), 116–121), что ни один автор не представил пример английского or-предложения, которое кажется ложным, потому что оба его ввода истинны, и отмахивается от or-предложений, таких как« The light лампочка либо включена, либо выключена "как отражение конкретных фактов о мире, а не природы слова" или ". Тем не менее,"парадокс парикмахера «… Все в городе бреются сами или бреются у парикмахера, который бреет парикмахера? - не было бы парадоксальным, если бы« или »не могло быть исключительным (хотя пурист мог бы сказать, что в формулировке парадокса требуется« либо » ).

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

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

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

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

• ${ displaystyle oplus}$, измененный знак плюса; этот символ также используется в математике для обозначения прямая сумма алгебраических структур
• J, как в Jpq
• Инклюзивный символ дизъюнкции (${ displaystyle lor}$), который каким-либо образом изменен, например
  • ${ displaystyle { underline { lor}}}$
  • ${ displaystyle { dot { vee}}}$
• ^, то каретка, используется в нескольких языки программирования, такие как C, C ++, C #, D, Ява, Perl, Рубин, 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 (А oplus B)}$	${ displaystyle ~~~ oplus ~~~}$	${ displaystyle ~ C}$
	${ displaystyle ~~~ oplus ~~~}$		${ displaystyle Leftrightarrow}$		${ displaystyle Leftrightarrow}$		${ displaystyle ~~~ oplus ~~~}$

Распределительность:

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

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

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

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

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

Информатика

Традиционное символическое представление XOR логический вентиль

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

Нимбер дополнение - это Эксклюзивный или из неотрицательные целые числа в двоичный представление. Это тоже векторное сложение в ${ Displaystyle ( mathbb {Z} / 2 mathbb {Z}) ^ {4}}$.

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

• 1 исключающее ИЛИ 1 = 0
• 1 исключающее ИЛИ 0 = 1
• 0 исключающее ИЛИ 1 = 1
• 0 исключающее ИЛИ 0 = 0
• 11102 XOR 10012 = 01112 (это эквивалентно сложению без нести )

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

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

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

В логических схемах простой сумматор можно сделать с Ворота XOR для сложения чисел и серии логических элементов И, ИЛИ и НЕ для создания вывода переноса.

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

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

Эксклюзивный или иногда используется как простая функция микширования в криптография, например, с одноразовый блокнот или Сеть Фейстеля системы.^{[нужна цитата ]}

Exclusive-or также широко используется в блочных шифрах, таких как AES (Rijndael) или Serpent, и в реализации блочного шифра (CBC, CFB, OFB или CTR).

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

XOR используется в RAID 3–6 для создания информации о четности. Например, RAID может «копировать» байты. 100111002 и 011011002 с двух (или более) жестких дисков путем операции XOR только что упомянутых байтов, в результате чего (111100002) и записать его на другой диск. Согласно этому методу, если один из трех жестких дисков потерян, потерянный байт может быть воссоздан путем операции XOR с байтами оставшихся дисков. Например, если диск, содержащий 011011002 потерян, 100111002 и 111100002 можно выполнить XOR для восстановления потерянного байта.^[6]

XOR также используется для обнаружения переполнения в результате двоичной арифметической операции со знаком. Если крайний левый оставшийся бит результата не совпадает с бесконечным числом цифр слева, это означает, что произошло переполнение. Выполнение операции XOR для этих двух битов даст «1» в случае переполнения.

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

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

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

Кодировки

Помимо кодов ASCII, оператор кодируется в U + 22BB ⊻ XOR (HTML⊻ · & veebar;) и U + 2295 ⊕ ОБРАТНЫЙ ПЛЮС (HTML⊕ · & CirclePlus ;, & oplus;), оба в блоке математические операторы.

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

Заметки

внешние ссылки

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