Строгая дизъюнкция

Строгая дизъюнкция (от лат. disjunctio — разобщение, различие; также исключающее «или», логическое сложение по модулю 2, XOR) — это логическая операция, которая соединяет два высказывания (простых суждения) в одно сложное, истинное только в том случае, когда ровно одно из исходных высказываний истинно, а другое ложно. В отличие от нестрогой (слабой) дизъюнкции, допускающей одновременную истинность обоих компонентов, строгая дизъюнкция исключает такую возможность. В естественном языке ей соответствует союз «либо… либо…», употреблённый в разделительном смысле (например: «Либо он пойдёт в кино, либо останется дома»).

История

Понятие строгой дизъюнкции восходит к античной логике. Аристотель в трактате «Об истолковании» различал два типа разделительных суждений: «или… или…» в смысле «одно из двух, но не оба» (строгое) и «или… или…» в смысле «по крайней мере одно из двух» (нестрогое). Однако в классической силлогистике строгая дизъюнкция не получила формального развития, так как Аристотель и его последователи (перипатетики) рассматривали её как частный случай нестрогой.

В средневековой схоластике (Пётр Испанский, Уильям Оккам) разделительные суждения анализировались в рамках учения о суппозициях (подстановках). Оккам, в частности, указывал, что высказывание вида «S есть P или Q» может быть истинным либо в случае, когда S есть P, либо когда S есть Q, но не одновременно.

Формализация строгой дизъюнкции как бинарной логической операции произошла в XIX веке в работах Джорджа Буля, который ввёл операцию «исключающее ИЛИ» (XOR) как сложение по модулю 2 в своей алгебре логики. В 1854 году в книге «Исследование законов мышления» Буль показал, что эта операция соответствует арифметическому сложению без переноса (mod 2). В XX веке, с развитием математической логики и теории множеств, строгая дизъюнкция стала стандартным элементом пропозициональной логики, а также нашла применение в теории цифровых схем (логический элемент «Исключающее ИЛИ»).

Обозначение и символика

В различных логических и математических системах строгая дизъюнкция обозначается по-разному:

• ⊻ (знак «исключающее ИЛИ» в логике высказываний);
• ⊕ (символ сложения по модулю 2, распространён в теории чисел и криптографии);
• XOR (от англ. eXclusive OR — исключающее ИЛИ);
• ≠ (в некоторых контекстах, как знак неравенства, если рассматривать истинность как 1, а ложь как 0);
• + (в булевой алгебре, где сложение понимается как сложение по модулю 2).

В русскоязычной логической литературе чаще всего используется символ ⊻ или ⊕.

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

Строгая дизъюнкция двух высказываний A и B (обозначается A ⊻ B) принимает значение «истина» (1) тогда и только тогда, когда значения A и B различны. Если A и B оба истинны или оба ложны, результат — «ложь» (0).

Свойства

Строгая дизъюнкция обладает рядом формальных свойств, отличающих её от нестрогой дизъюнкции (∨) и конъюнкции (∧):

• Коммутативность: A ⊻ B = B ⊻ A (порядок операндов не влияет на результат).
• Ассоциативность: (A ⊻ B) ⊻ C = A ⊻ (B ⊻ C). Это свойство позволяет записывать строгую дизъюнкцию трёх и более высказываний без скобок, однако интерпретация многоместной XOR (чётность числа истинных операндов) требует осторожности.
• Дистрибутивность относительно конъюнкции: A ⊻ (B ∧ C) = (A ⊻ B) ∧ (A ⊻ C) — не выполняется в общем случае. Вместо этого действует дистрибутивность конъюнкции относительно XOR: A ∧ (B ⊻ C) = (A ∧ B) ⊻ (A ∧ C).
• Идемпотентность: A ⊻ A = 0 (ложь). Повторение одного и того же высказывания даёт ложь.
• Поглощение: A ⊻ 0 = A; A ⊻ 1 = ¬A (отрицание A).
• Связь с отрицанием: A ⊻ B = ¬(A ↔ B) (строгая дизъюнкция эквивалентна отрицанию эквивалентности). Также A ⊻ B = (A ∨ B) ∧ ¬(A ∧ B).

Отличие от нестрогой дизъюнкции

Основное различие между строгой и нестрогой дизъюнкцией заключается в допустимости одновременной истинности обеих частей.

В русском языке контекст часто не позволяет однозначно определить, какая дизъюнкция имеется в виду. Например, высказывание «К зачёту допускаются студенты, сдавшие экзамен или имеющие уважительную причину» обычно понимается как нестрогая дизъюнкция (допускаются оба случая). Высказывание «Либо ты сдашь экзамен, либо будешь отчислен» — как строгая (одновременное выполнение невозможно).

Применение

В математике и логике

Строгая дизъюнкция используется в теории множеств для обозначения симметрической разности: A △ B = { x | x ∈ A ⊻ x ∈ B }. В арифметике операция XOR соответствует сложению по модулю 2, что лежит в основе двоичной арифметики и кодов с обнаружением ошибок (например, контрольные суммы).

В цифровой электронике

Логический элемент «Исключающее ИЛИ» (XOR) — один из базовых элементов цифровых схем. Он реализует функцию строгой дизъюнкции. Применяется в:

• Сумматорах: полусумматор использует XOR для вычисления суммы двух одноразрядных двоичных чисел.
• Схемах сравнения: XOR позволяет определить, равны ли два бита (если результат 0 — равны, если 1 — не равны).
• Генераторах псевдослучайных чисел: на основе XOR строятся регистры сдвига с линейной обратной связью (LFSR).
• Криптографии: XOR является основной операцией в симметричных шифрах (например, в шифре Вернама) и в алгоритмах блочного шифрования (AES, DES).

В программировании

В языках программирования строгая дизъюнкция обычно реализуется оператором ^ (в C, C++, Java, C#, Python) или ключевым словом xor (в Pascal, Delphi, SQL). Используется для:

• Побитовых операций: x ^ y — побитовое исключающее ИЛИ.
• Логических операций: в некоторых языках (например, в Python) ^ работает как логический XOR для булевых значений.
• Проверки чётности: (x ^ y) & 1 возвращает 1, если количество единиц в двоичном представлении суммы нечётно.
• Обмена значениями переменных без временной переменной: a ^= b; b ^= a; a ^= b; (для целых чисел).

В лингвистике

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

Критика и ограничения

В классической логике строгая дизъюнкция часто рассматривается как производная операция, выражаемая через отрицание, конъюнкцию и нестрогую дизъюнкцию: A ⊻ B = (A ∨ B) ∧ ¬(A ∧ B). Это делает её несамостоятельной с точки зрения аксиоматизации пропозициональной логики. В некоторых неклассических логиках (например, в интуиционистской логике) строгая дизъюнкция не является базовой операцией, так как её определение требует использования закона исключённого третьего.

В естественном языке граница между строгой и нестрогой дизъюнкцией размыта. Например, высказывание «Ты придёшь на вечеринку или останешься дома» может быть интерпретировано как строгая дизъюнкция (невозможно быть одновременно в двух местах) или как нестрогая (возможно, человек сначала придёт, а потом уйдёт). Контекст и интонация играют решающую роль.

Источники

1. Аристотель. «Об истолковании» (лат. De Interpretatione), гл. 7–9.
2. Буль Дж. «Исследование законов мышления» (1854), гл. II–III.
3. Гильберт Д., Аккерман В. «Основы теоретической логики» (рус. пер. 1947), § 2.
4. Мендельсон Э. «Введение в математическую логику» (рус. пер. 1976), гл. 1.
5. Тарский А. «Введение в логику и методологию дедуктивных наук» (рус. пер. 1948), § 14.
6. Харрис Д., Харрис С. «Цифровая схемотехника и архитектура компьютера» (рус. пер. 2016), гл. 2.