Дизъюнкция

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

История

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

Формальное определение дизъюнкции как логической операции появилось в XIX веке в работах Джорджа Буля, который ввёл алгебру логики. В его системе операция, соответствующая дизъюнкции, обозначалась знаком «+» и интерпретировалась как сложение по модулю 2 (исключающее «или»). Позднее, в конце XIX — начале XX века, в работах Готлоба Фреге, Чарльза Пирса и Эрнста Шрёдера, дизъюнкция получила современное обозначение (∨) и была отделена от строгой дизъюнкции. В 1920-х годах американский логик Эмиль Пост предложил систему обозначений, где дизъюнкция обозначается как «∨», что стало стандартом в математической логике.

Виды дизъюнкции

Нестрогая дизъюнкция (логическое «или»)

Нестрогая, или включающая, дизъюнкция (обозначается символом ∨) — операция, результат которой истинен, если истинен хотя бы один из операндов. Она соответствует союзу «или» в русском языке в его неисключающем значении (например: «Я пойду в кино или в театр» — допускается, что человек может пойти и в кино, и в театр). Таблица истинности для двух операндов A и B:

Здесь 0 обозначает ложь, 1 — истину.

Строгая дизъюнкция (исключающее «или»)

Строгая, или исключающая, дизъюнкция (обозначается символом ⊕, ⊻ или XOR) — операция, результат которой истинен тогда и только тогда, когда истинен ровно один из операндов. Она соответствует союзу «либо» в русском языке (например: «Либо я пойду в кино, либо в театр» — подразумевается, что можно выбрать только одно). Таблица истинности для двух операндов:

Строгая дизъюнкция является частным случаем сложения по модулю 2.

Многоместная дизъюнкция

Дизъюнкция может быть обобщена на произвольное число операндов. Для нестрогой дизъюнкции результат истинен, если истинен хотя бы один из операндов. Для строгой дизъюнкции результат истинен, если истинно нечётное количество операндов (то есть 1, 3, 5 и т. д.). В математической логике многоместная дизъюнкция часто обозначается как ⋁ (большая дизъюнкция) или как ∏ (произведение) в контексте булевых функций.

Свойства

Дизъюнкция, как и другие логические операции, обладает рядом формальных свойств, которые описываются аксиомами булевой алгебры:

• Коммутативность: A ∨ B = B ∨ A.
• Ассоциативность: (A ∨ B) ∨ C = A ∨ (B ∨ C).
• Идемпотентность: A ∨ A = A.
• Дистрибутивность относительно конъюнкции: A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C).
• Поглощение: A ∨ (A ∧ B) = A.
• Закон исключённого третьего: A ∨ ¬A = 1 (истина).
• Свойство нуля и единицы: A ∨ 0 = A; A ∨ 1 = 1.

Для строгой дизъюнкции (XOR) характерны иные свойства: она ассоциативна, коммутативна, но не идемпотентна (A ⊕ A = 0). Кроме того, строгая дизъюнкция является обратной операцией к самой себе: A ⊕ B ⊕ B = A.

Обозначения

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

• Математическая логика: ∨ (нестрогая), ⊕ (строгая).
• Булева алгебра: + (нестрогая, но с оговоркой, что 1+1=1), ⊕ (строгая).
• Теория множеств: ∪ (объединение множеств) — аналог нестрогой дизъюнкции.
• Программирование: в языках C, C++, Java, Python и других — || (нестрогая), ^ или xor (строгая).
• Электротехника: символ логического элемента «ИЛИ» (прямоугольник с обозначением ≥1).

Применение

В математике

Дизъюнкция широко используется в математической логике, теории множеств, комбинаторике и теории вероятностей. В теории множеств аналогом нестрогой дизъюнкции является объединение множеств: элемент принадлежит объединению, если он принадлежит хотя бы одному из исходных множеств. В теории вероятностей дизъюнкция соответствует вероятности суммы событий (для несовместных событий — по формуле сложения вероятностей).

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

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

• В условных операторах (if, while) для проверки нескольких условий.
• В битовых операциях (побитовое ИЛИ, XOR) для манипуляции битами.
• В алгоритмах поиска и фильтрации данных.
• В криптографии (например, XOR-шифрование).

В электронике

В цифровой электронике дизъюнкция реализуется с помощью логических элементов «ИЛИ» (OR) и «Исключающее ИЛИ» (XOR). Эти элементы являются базовыми для построения комбинационных схем, сумматоров, дешифраторов и других устройств. Например, полусумматор двоичных чисел строится на основе XOR (для суммы) и AND (для переноса).

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

В языкознании дизъюнкция изучается как один из типов логических союзов. Русский союз «или» может выражать как нестрогую, так и строгую дизъюнкцию в зависимости от контекста. В формальной семантике дизъюнктивные конструкции анализируются с точки зрения истинностных условий и прагматических импликатур.

Связь с другими логическими операциями

Дизъюнкция тесно связана с конъюнкцией (логическим «и») и отрицанием. Через них можно выразить любую булеву функцию. Например, импликация A → B эквивалентна ¬A ∨ B. В классической логике дизъюнкция и конъюнкция образуют двойственную пару: законы де Моргана утверждают, что ¬(A ∨ B) = ¬A ∧ ¬B и ¬(A ∧ B) = ¬A ∨ ¬B.

Критика и альтернативы

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

Источники

• Буль Г. «Исследование законов мысли» (1854).
• Фреге Г. «Основоположения арифметики» (1884).
• Пост Э. «Введение в общую теорию элементарных пропозиций» (1921).
• Мендельсон Э. «Введение в математическую логику» (1964).
• Колмогоров А. Н., Драгалин А. Г. «Введение в математическую логику» (1982).