Виключна диз'юнкція
Виключна диз'юнкція, також операція XOR (від англ. eXclusive OR), додавання за модулем два — логічна та бітова операція, що приймає значення «істина» тоді і лише тоді коли значення «істина» має рівно один з її операндів. Виключна диз'юнкція є запереченням логічної еквівалентності. У випадку двох змінних результат виконання операції є істинним тоді і тільки тоді, коли лише один з аргументів є істинним. Для функції трьох і більше змінних результат виконання операції буде істинним тільки тоді, коли аргументів рівних 1 на заданому наборі буде непарна кількість. Така операція природним чином виникає в кільці відрахувань по модулю 2, звідки і походить назва операції.
Додавання за модулем 2 слід відрізняти від простого додавання булевих операндів, яке відповідає звичайному логічному «або», тобто логічній диз'юнкції.
Множиною істинності виключної диз'юнкції двох суджень є симетричною різницею множин істинності операндів.
ПозначенняРедагувати
Запис може бути префіксний («польський запис») — знак операції ставиться перед операндами, інфіксний — знак операції ставиться між операндами і постфіксний — знак операції ставиться після операндів. При числі операндів більше двох префіксний та постфіксний запис економніше інфіксного запису. Найчастіше зустрічаються наступні варіанти запису:
^ a ≠ b,
У таблиці символів Юнікод є символ для додавання за модулем 2 (CIRCLED PLUS) — U +2295 ( ⊕ ).
Виключну диз'юнкцію деколи задають через інші логічні операції, наприклад:
Булева алгебраРедагувати
У булевій алгебрі додавання за модулем 2 — це функція двох, трьох і більше змінних (вони ж — операнди, вони ж — аргументи функції). Змінні можуть приймати значення з множин . Результат також належить множині . Обчислення результату проводиться по простому правилу, або по таблиці істинності. Замість значень може використовуватися будь-яка інша пара підходящих символів, наприклад або або «хибність», «істина», але при цьому необхідно довизначити старшинство, наприклад, .
Таблиці істинності:
- Для бінарного додавання за модулем 2 (застосовується в двійкових напівсуматорах):
- Правило: результат дорівнює , якщо обидва операнди рівні; у всіх інших випадках результат дорівнює .
- Для тернарного додавання за модулем 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), якщо A не дорівнює B (A ≠ B)»;
- «Якщо A не дорівнює B (A ≠ B), то істина (1)».
Часто вказують на схожість між додаванням за модулем 2 і конструкцією «або …, або …» в природній мові. Складене твердження «або A, або B» вважається істинним, коли істинне або A, або B, але не обидва відразу, інакше складене твердження хибне. Це в точності відповідає визначенню операції в булевій алгебрі, якщо «істину» позначати як , а «хибність» як .
Цю операцію нерідко порівнюють з диз'юнкцією, тому що вони дуже схожі за властивостями, і обидві мають схожість зі сполучником «або» у повсякденній мові. Порівняйте правила для цих операцій:
- істинне, якщо істинне або , або обидва відразу.
- істинне, якщо істинне або , але не обидва відразу.
Операція виключає останній варіант («обидва відразу») і з цієї причини називається виключне «АБО». Операція включає останній варіант («обидва відразу») і з цієї причини іноді називається включне «АБО». Неоднозначність природної мови полягає в тому, що сполучник «або» може застосовуватися в обох випадках.
Альтернативні символиРедагувати
Символ, використовуваний для виключної диз'юнкції варіюється від однієї області застосування до іншої. На додаток до абревіатури «XOR» можуть використовуватися:
- Знак плюс (+). Це має сенс, тому що математично виключній диз'юнкції відповідає додавання по модулю 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(англ.)