Сложение по модулю 2

Исключающее ИЛИ

Основная информация

T₀	T₁	M	L	S
Да	Нет	Нет	Да	Нет

ДНФ

<math>\overline{x} \cdot y + x \cdot \overline{y}</math>

КНФ

<math>( \overline{x} + \overline{y} ) \cdot ( x + y )</math>

Полином Жегалкина

<math>x \oplus y </math>

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

Сложе́ние по мо́дулю 2 (логи́ческая неравнозна́чность, исключа́ющее «ИЛИ», строгая дизъюнкция, XOR, поразрядное дополнение, побитовый комплемент, жегалкинское сложение) — булева функция, а также логическая и битовая операция. В случае двух переменных результат выполнения операции является истинным тогда и только тогда, когда один из аргументов является истинным, а второй ложным. Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов равных 1, составляющих текущий набор — нечетное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.

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

В теории множеств сложению по модулю 2 соответствует операция симметричной разности двух множеств.

в префиксной записи: <math>max(a, b) - min(a, b)</math>.

Обозначения

Запись может быть префиксной («польская запись») — знак операции ставится перед операндами, инфиксной — знак операции ставится между операндами и постфиксной — знак операции ставится после операндов. При числе операндов более 2-х префиксная и постфиксная записи экономичнее инфиксной записи. Чаще всего встречаются следующие варианты записи:
<math>\oplus_2(a,b), ~a</math> ^ <math>b, ~a \oplus b, a \oplus_2 b, a +_2 b, </math> a ≠ b, <math>a\ne b, (a,b)\oplus_2, a ~XOR~ b</math>

В таблице символов Юникод есть символ для сложения по модулю 2 (CIRCLED PLUS) — U+2295 (⊕).

Свойства

<math>a \oplus 0 = a</math> (идемпотентность)
<math>a \oplus 1 = \bar a</math> (отрицание)
<math>a \oplus a = 0</math>
<math>a \oplus b = b \oplus a</math> (коммутативность)
<math>( a \oplus b ) \oplus c = a \oplus ( b \oplus c )</math> (ассоциативность)
<math>( a \oplus b ) \oplus b = a</math>
<math>\bar a \oplus b = a \oplus \bar b = (a \equiv b)</math> (сравнения по модулю)

Булева алгебра

В булевой алгебре сложение по модулю 2 — это функция двух, трёх и более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества <math>\{0, 1\}</math>. Результат также принадлежит множеству <math>\{0, 1\}</math>. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений <math>0, 1</math> может использоваться любая другая пара подходящих символов, например <math>false, true</math> или <math>F, T</math> или «ложь», «истина», но при этом необходимо доопределять старшинство, например, <math>true > false</math>.

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

для бинарного сложения по модулю 2 (применяется в двоичных полусумматорах):

<math>a</math>	<math>b</math>	<math>a \oplus b</math>
<math>0</math>	<math>0</math>	<math>0</math>
<math>0</math>	<math>1</math>	<math>1</math>
<math>1</math>	<math>0</math>	<math>1</math>
<math>1</math>	<math>1</math>	<math>0</math>

Правило: результат равен <math>0</math>, если оба операнда равны; во всех остальных случаях результат равен <math>1</math>.

для тернарного сложения по модулю 2 (применяется в двоичных полных сумматорах):

X	Y	Z	⊕(X,Y,Z)
0	0	0	0
1	0	0	1
0	1	0	1
1	1	0	0
0	0	1	1
1	0	1	0
0	1	1	0
1	1	1	1

Правило: результат равен <math>0</math>, если нет операндов, равных <math>1</math>, либо их чётное количество.

Программирование

В языках C/C++, Java, C#, Ruby, PHP, JavaScript, Python и т. д. битовая операция поразрядного дополнения обозначается символом «^», в языках Паскаль, Delphi, Ada, Visual Basic — зарезервированным словом xor, в языке ассемблера — одноимённой логической командой. При этом сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,

если

то

Выполнение операции исключающее «или» для значений логического типа (true, false) производится в разных языках программирования по-разному. Например, в Delphi используется встроенный оператор XOR (пример: условие1 xor условие2). В языке C, начиная со стандарта C99, оператор «^» над операндами логического типа возвращает результат применения логической операции XOR. В С++ оператор «^» для логического типа bool возвращает результат согласно описанным правилам, для остальных же типов производится его побитовое применение.

Связь с естественным языком

В естественном языке операция «сложение по модулю» эквивалентна двум выражениям:

«результат истинен (равен 1), если A не равно B (A≠B)»;
«если A не равно B (A≠B), то истина (1)».

Часто указывают на сходство между сложением по модулю 2 и конструкцией «либо … либо …» в естественном языке. Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как <math>1</math>, а «ложь» как <math>0</math>.

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

<math>A \lor B</math> истинно, если истинно <math>A</math> или <math>B</math>, или оба сразу ("хотя бы один из двух").
<math>A \oplus B</math> истинно, если истинно <math>A</math> или <math>B</math>, но не оба сразу ("только один из двух").

Операция <math>\oplus</math> исключает последний вариант («оба сразу») и по этой причине называется исключающим «ИЛИ». Операция <math>\lor</math> включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ». Неоднозначность естественного языка заключается в том, что союз «или» может применяться в обоих случаях.

Квантовые вычисления

В квантовых компьютерах аналогом операции сложения по модулю 2 является вентиль CNOT.

См. также

Напишите отзыв о статье "Сложение по модулю 2"

Ссылки

[alglib.sources.ru/articles/logic.php#xor Алгебра логики и цифровые компьютеры: Функция сложения по модулю 2 (xor)]

Отрывок, характеризующий Сложение по модулю 2

– Ну что ж, коли не боишься.
– Луиза Ивановна, можно мне? – спросила Соня.
Играли ли в колечко, в веревочку или рублик, разговаривали ли, как теперь, Николай не отходил от Сони и совсем новыми глазами смотрел на нее. Ему казалось, что он нынче только в первый раз, благодаря этим пробочным усам, вполне узнал ее. Соня действительно этот вечер была весела, оживлена и хороша, какой никогда еще не видал ее Николай.
«Так вот она какая, а я то дурак!» думал он, глядя на ее блестящие глаза и счастливую, восторженную, из под усов делающую ямочки на щеках, улыбку, которой он не видал прежде.
– Я ничего не боюсь, – сказала Соня. – Можно сейчас? – Она встала. Соне рассказали, где амбар, как ей молча стоять и слушать, и подали ей шубку. Она накинула ее себе на голову и взглянула на Николая.
«Что за прелесть эта девочка!» подумал он. «И об чем я думал до сих пор!»
Соня вышла в коридор, чтобы итти в амбар. Николай поспешно пошел на парадное крыльцо, говоря, что ему жарко. Действительно в доме было душно от столпившегося народа.
На дворе был тот же неподвижный холод, тот же месяц, только было еще светлее. Свет был так силен и звезд на снеге было так много, что на небо не хотелось смотреть, и настоящих звезд было незаметно. На небе было черно и скучно, на земле было весело.
«Дурак я, дурак! Чего ждал до сих пор?» подумал Николай и, сбежав на крыльцо, он обошел угол дома по той тропинке, которая вела к заднему крыльцу. Он знал, что здесь пойдет Соня. На половине дороги стояли сложенные сажени дров, на них был снег, от них падала тень; через них и с боку их, переплетаясь, падали тени старых голых лип на снег и дорожку. Дорожка вела к амбару. Рубленная стена амбара и крыша, покрытая снегом, как высеченная из какого то драгоценного камня, блестели в месячном свете. В саду треснуло дерево, и опять всё совершенно затихло. Грудь, казалось, дышала не воздухом, а какой то вечно молодой силой и радостью.
С девичьего крыльца застучали ноги по ступенькам, скрыпнуло звонко на последней, на которую был нанесен снег, и голос старой девушки сказал:
– Прямо, прямо, вот по дорожке, барышня. Только не оглядываться.
– Я не боюсь, – отвечал голос Сони, и по дорожке, по направлению к Николаю, завизжали, засвистели в тоненьких башмачках ножки Сони.
Соня шла закутавшись в шубку. Она была уже в двух шагах, когда увидала его; она увидала его тоже не таким, каким она знала и какого всегда немножко боялась. Он был в женском платье со спутанными волосами и с счастливой и новой для Сони улыбкой. Соня быстро подбежала к нему.
«Совсем другая, и всё та же», думал Николай, глядя на ее лицо, всё освещенное лунным светом. Он продел руки под шубку, прикрывавшую ее голову, обнял, прижал к себе и поцеловал в губы, над которыми были усы и от которых пахло жженой пробкой. Соня в самую середину губ поцеловала его и, выпростав маленькие руки, с обеих сторон взяла его за щеки.
– Соня!… Nicolas!… – только сказали они. Они подбежали к амбару и вернулись назад каждый с своего крыльца.

Когда все поехали назад от Пелагеи Даниловны, Наташа, всегда всё видевшая и замечавшая, устроила так размещение, что Луиза Ивановна и она сели в сани с Диммлером, а Соня села с Николаем и девушками.
Николай, уже не перегоняясь, ровно ехал в обратный путь, и всё вглядываясь в этом странном, лунном свете в Соню, отыскивал при этом всё переменяющем свете, из под бровей и усов свою ту прежнюю и теперешнюю Соню, с которой он решил уже никогда не разлучаться. Он вглядывался, и когда узнавал всё ту же и другую и вспоминал, слышав этот запах пробки, смешанный с чувством поцелуя, он полной грудью вдыхал в себя морозный воздух и, глядя на уходящую землю и блестящее небо, он чувствовал себя опять в волшебном царстве.
– Соня, тебе хорошо? – изредка спрашивал он.
– Да, – отвечала Соня. – А тебе ?
На середине дороги Николай дал подержать лошадей кучеру, на минутку подбежал к саням Наташи и стал на отвод.
– Наташа, – сказал он ей шопотом по французски, – знаешь, я решился насчет Сони.
– Ты ей сказал? – спросила Наташа, вся вдруг просияв от радости.
– Ах, какая ты странная с этими усами и бровями, Наташа! Ты рада?
– Я так рада, так рада! Я уж сердилась на тебя. Я тебе не говорила, но ты дурно с ней поступал. Это такое сердце, Nicolas. Как я рада! Я бываю гадкая, но мне совестно было быть одной счастливой без Сони, – продолжала Наташа. – Теперь я так рада, ну, беги к ней.
– Нет, постой, ах какая ты смешная! – сказал Николай, всё всматриваясь в нее, и в сестре тоже находя что то новое, необыкновенное и обворожительно нежное, чего он прежде не видал в ней. – Наташа, что то волшебное. А?
– Да, – отвечала она, – ты прекрасно сделал.
«Если б я прежде видел ее такою, какою она теперь, – думал Николай, – я бы давно спросил, что сделать и сделал бы всё, что бы она ни велела, и всё бы было хорошо».
– Так ты рада, и я хорошо сделал?
– Ах, так хорошо! Я недавно с мамашей поссорилась за это. Мама сказала, что она тебя ловит. Как это можно говорить? Я с мама чуть не побранилась. И никому никогда не позволю ничего дурного про нее сказать и подумать, потому что в ней одно хорошее.
– Так хорошо? – сказал Николай, еще раз высматривая выражение лица сестры, чтобы узнать, правда ли это, и, скрыпя сапогами, он соскочил с отвода и побежал к своим саням. Всё тот же счастливый, улыбающийся черкес, с усиками и блестящими глазами, смотревший из под собольего капора, сидел там, и этот черкес был Соня, и эта Соня была наверное его будущая, счастливая и любящая жена.
Приехав домой и рассказав матери о том, как они провели время у Мелюковых, барышни ушли к себе. Раздевшись, но не стирая пробочных усов, они долго сидели, разговаривая о своем счастьи. Они говорили о том, как они будут жить замужем, как их мужья будут дружны и как они будут счастливы.
На Наташином столе стояли еще с вечера приготовленные Дуняшей зеркала. – Только когда всё это будет? Я боюсь, что никогда… Это было бы слишком хорошо! – сказала Наташа вставая и подходя к зеркалам.
– Садись, Наташа, может быть ты увидишь его, – сказала Соня. Наташа зажгла свечи и села. – Какого то с усами вижу, – сказала Наташа, видевшая свое лицо.
– Не надо смеяться, барышня, – сказала Дуняша.
Наташа нашла с помощью Сони и горничной положение зеркалу; лицо ее приняло серьезное выражение, и она замолкла. Долго она сидела, глядя на ряд уходящих свечей в зеркалах, предполагая (соображаясь с слышанными рассказами) то, что она увидит гроб, то, что увидит его, князя Андрея, в этом последнем, сливающемся, смутном квадрате. Но как ни готова она была принять малейшее пятно за образ человека или гроба, она ничего не видала. Она часто стала мигать и отошла от зеркала.