Виключна диз'юнкція

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Рис. 1 Графік побітового виключного «або»

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

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

Множиною істинності виключної диз'юнкції двох суджень є симетричною різницею множин істинності операндів.

Позначення[ред.ред. код]

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


\oplus_2(a,b),  ~a ^ ~b,  ~a \oplus b,  a \oplus_2 b,  a +_2 b,  a ≠ b, a\ne b,  (a,b)\oplus_2,  a ~XOR~ b

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

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

a \oplus b = \neg (a \leftrightarrow b)
a \oplus b = (a \and \neg b) \or (\neg a \and b)

Булева алгебра[ред.ред. код]

У булевій алгебрі додавання за модулем 2 — це функція двох, трьох і більше змінних (вони ж — операнди, вони ж — аргументи функції). Змінні можуть приймати значення з множин ~\{0, 1\}. Результат також належить множині ~\{0, 1\}. Обчислення результату проводиться по простому правилу, або по таблиці істинності. Замість значень ~0, 1 може використовуватися будь-яка інша пара підходящих символів, наприклад ~false, true або ~F, T або «хибність», «істина», але при цьому необхідно довизначити старшинство, наприклад, ~true > false.

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

~a ~b ~a \oplus b
~0 ~0 ~0
~0 ~1 ~1
~1 ~0 ~1
~1 ~1 ~0
Правило: результат дорівнює ~0, якщо обидва операнди рівні; у всіх інших випадках результат дорівнює ~1.
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

Визначення[ред.ред. код]

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

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

~A ~B A \oplus B
хибність хибність хибність
хибність істина істина
істина хибність істина
істина істина хибність

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

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

(A \oplus B) = \lnot (A \leftrightarrow  B)

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

Властивості[ред.ред. код]

a \oplus (b \oplus c) \equiv (a \oplus b) \oplus c
a \oplus  b \equiv b \oplus a
a \land (b \oplus c) \equiv (a \land b) \oplus (a \land c)

Абелева група[ред.ред. код]

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

Таким чином (\{1, 0\}, \oplus) є абелевою групою. Разом із операцією \wedge також утворюється поле Галуа F_2.

Інші властивості[ред.ред. код]

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

Функціональна повнота[ред.ред. код]

Множина операцій \{ \oplus, \to \} є функціонально повною:

 \lnot a \equiv a \to (a \oplus a)
 \lnot a \equiv  a \oplus (a \to a)
 a \lor b \equiv (\lnot a) \rightarrow b
 a \land b \equiv \lnot (a \rightarrow \lnot b)

Виключна диз'юнкція в природніх мовах[ред.ред. код]

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

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

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

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

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

  1. A \lor B істинне, якщо істинне ~A або ~B, або обидва відразу.
  2. A \oplus B істинне, якщо істинне ~A або ~B, але не обидва відразу.

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

Альтернативні символи[ред.ред. код]

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

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

Виключна диз'юнкція у програмуванні[ред.ред. код]

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

якщо
a = ~01100101_2
b = ~00101001_2
тоді
a ^ b = ~01001100_2

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

Квантові обчислення[ред.ред. код]

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]

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