Виняткова диз'юнкція, також операція XOR (від англ. eXclusive OR), додавання за модулем два — логічна та бітова операція, що набуває значення «істина» тоді й лише тоді, коли значення «істина» має суто один з її операндів. Виняткова диз'юнкція є запереченням логічної еквівалентності. У випадку двох змінних результат виконання операції є істинним тоді й тільки тоді, якщо лише один з аргументів є істинним. Для функції трьох і більше змінних результат виконання операції буде істинним тільки тоді, коли аргументів, рівних 1, на заданому наборі буде непарна кількість. Така операція природним чином виникає в кільці лишків за модулем 2, звідки й походить назва операції.

Рис. 1 Графік побітового виняткового «або»

Додавання за модулем 2 слід відрізняти від простого додавання булевих операндів, яке відповідає звичайному логічному «або», тобто логічній диз'юнкції.

Відповідною операцією в теорії множин є симетрична різниця множин істинності операндів.

ПозначенняРедагувати

Запис може бути префіксний («польський запис») — знак операції ставиться перед операндами, інфіксний — знак операції ставиться між операндами і постфіксний — знак операції ставиться після операндів. За кількості операндів більше двох префіксний та постфіксний запис економніші за інфіксний. Найчастіше трапляються такі варіанти запису:


  ^   a ≠ b,  

У таблиці символів Юнікод є символ для додавання за модулем 2 (CIRCLED PLUS) — U +2295 ( ).

Виняткову диз'юнкцію деколи задають через інші логічні операції, наприклад:

 
 

Булева алгебраРедагувати

У булевій алгебрі додавання за модулем 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

ВизначенняРедагувати

 
Діаграма Венна для операції  

Таблиця істинності виглядає таким чином:

     
хибність хибність хибність
хибність істина істина
істина хибність істина
істина істина хибність

Результат застосування виняткової диз'юнкції такий самий, як і від додавання за модулем 2. Тому й саму операцію часто називають додаванням за модулем 2.

Виняткова диз'юнкція є також запереченням еквівалентності, тобто

 

Відповідною операцією в теорії множин є симетрична різниця множин.

ВластивостіРедагувати

 
 
 

Абелева групаРедагувати

  • елемент 0 є нейтральним:
 
  • кожен елемент є обернений сам до себе:
 

Таким чином   є абелевою групою. Разом із операцією   також утворюється поле Галуа  .

Інші властивостіРедагувати

 

Функціональна повнотаРедагувати

Множина операцій   є функціонально повною:

 
 
 
 

Виняткова диз'юнкція у природних мовахРедагувати

Виняткові диз'юнкції найкраще відповідає український вислів «або …, або …». Твердження або А, або В є справедливим, коли справедливе А чи В, але не обоє водночас.

У природній мові операція «складання за модулем» еквівалентна двом виразам:

  1. «Результат істинний (дорівнює 1), якщо A не дорівнює B (A ≠ B)»;
  2. «Якщо A не дорівнює B (A ≠ B), то істина (1)».

На схожість між додаванням за модулем 2 і конструкцією «або …, або …» в природній мові часто вказують. Це точно відповідає визначенню операції в булевій алгебрі, якщо «істину» позначати як  , а «хибність» як  .

Цю операцію нерідко порівнюють із диз'юнкцією, тому що вони дуже схожі за властивостями, і обидві мають схожість зі сполучником «або» у повсякденній мові. Порівняйте правила для цих операцій:

  1.   істинне, якщо істинне   або  , або обидва відразу.
  2.   істинне, якщо істинне   або  , але не обидва відразу.

Операція   не допускає останнього варіанту («обидва відразу»); саме тому її називають винятковим, ексклюзивним «АБО». Операція   допускає останній варіант («обидва відразу»), тож іноді її називають звичним, інклюзивним «АБО». Неоднозначність природної мови полягає в тому, що сполучник «або» застосовують в обох випадках.

Альтернативні символиРедагувати

Символ, використовуваний для виняткової диз'юнкції, варіюється від однієї області застосування до іншої. Окрім абревіатури «XOR», можуть траплятися:

  • Знак плюс (+). Це має сенс, тому що математично винятковій диз'юнкції відповідає додавання за модулем 2, яке має наступну таблицю:
Додавання за модулем 2
     
0 0 0
0 1 1
1 0 1
1 1 0
Використання знаку «плюс» має додаткову перевагу, бо всі звичайні алгебраїчні властивості математичного кільця і поля можна використати без зайвого клопоту. Тим не менш, знак плюс використовують також для ексклюзивної диз'юнкції у деяких позначеннях систем.
  • Знаком плюс, зміненим певним чином, наприклад, взятим в коло ( ). Це викликає заперечення: цей же символ вже використовують у математиці для прямої суми алгебраїчних структур.
  • Префікс J, як в Jpq.
  • Символ диз'юнкції ( ), який певним чином змінюють: із підкресленням ( ) або з точкою вгорі ( ).
  • У деяких мовах програмування, таких як C, C++, C#, Java, Perl, MATLAB і Python, символ циркумфлекс (^) використовують для позначення оператора побітового XOR. Його не використовують поза контекстом програмування, бо в цьому разі його можна зрозуміти хибно.

Виняткова диз'юнкція у програмуванніРедагувати

У мовах C/C++ (а також Java, C#, Ruby, PHP, JavaScript, Swift) цю операцію позначають символом «^»; у мовах Паскаль, Delphi, Ада — зарезервованим словом XOR. Додавання виконується побітово для двох операндів. Наприклад,

якщо
a =  
b =  
тоді
a ^ b =  

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

За нестачі регістрів оператор XOR можна використати для обміну значеннями змінних.

Квантові обчисленняРедагувати

У квантових комп'ютерах аналогом операції додавання за модулем 2 є вентиль CNOT.

Див. такожРедагувати

ПосиланняРедагувати

  • Disjunction Stanford Encyclopedia of Philosophy(англ.)