Законы де Моргана

Пара логических эквивалентностей

Законы Де Моргана, представленные диаграммами Венна . В каждом случае результирующий набор представляет собой набор всех точек любого оттенка синего цвета.

В пропозициональной логике и булевой алгебре законы Де Моргана ^{[1] [2] [3],} также известные как теорема Де Моргана ^[4] , представляют собой пару правил преобразования, которые оба являются допустимыми правилами вывода . Они названы в честь Августа Де Моргана , британского математика 19-го века. Правила позволяют выражать конъюнкции и дизъюнкции исключительно в терминах друг друга через отрицание .

Правила можно выразить на английском языке следующим образом:

• Отрицание «А и В» то же самое, что «не А или не В».
• Отрицание «А или В» то же самое, что «не А и не В».

или

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

или

• не (А или В) = (не А) и (не В)
• не (А и В) = (не А) или (не В)

где «A или B» — это « включающее или », означающее по крайней мере одно из A или B, а не « исключающее или », означающее ровно одно из A или B.

Эквивалентность ¬φ ∨ ¬ψ и ¬(φ ∧ ψ) отображена в этой таблице истинности. ^[5]

Закон де Моргана с операцией вычитания множеств

Другая форма закона Де Моргана выглядит следующим образом.

${\displaystyle A-(B\cup C)=(A-B)\cap (A-C),}$

${\displaystyle A-(B\cap C)=(A-B)\cup (A-C).}$

Применение правил включает упрощение логических выражений в компьютерных программах и цифровых схемах. Законы де Моргана являются примером более общей концепции математической дуальности .

Формальная запись

Правило отрицания конъюнкции можно записать в секвенциальной записи:

${\displaystyle {\begin{aligned}\neg (P\land Q)&\vdash (\neg P\lor \neg Q),{\text{and}}\\(\neg P\lor \neg Q)&\vdash \neg (P\land Q).\end{aligned}}}$

Отрицание правила дизъюнкции можно записать так:

${\displaystyle {\begin{aligned}\neg (P\lor Q)&\vdash (\neg P\land \neg Q),{\text{and}}\\(\neg P\land \neg Q)&\vdash \neg (P\lor Q).\end{aligned}}}$

В форме правила : отрицание союза

${\displaystyle {\frac {\neg (P\land Q)}{\therefore \neg P\lor \neg Q}}\qquad {\frac {\neg P\lor \neg Q}{\therefore \neg (P\land Q)}}}$

и отрицание дизъюнкции

${\displaystyle {\frac {\neg (P\lor Q)}{\therefore \neg P\land \neg Q}}\qquad {\frac {\neg P\land \neg Q}{\therefore \neg (P\lor Q)}}}$

и выражены как истинностно-функциональные тавтологии или теоремы пропозициональной логики:

${\displaystyle {\begin{aligned}\neg (P\land Q)&\leftrightarrow (\neg P\lor \neg Q),\\\neg (P\lor Q)&\leftrightarrow (\neg P\land \neg Q).\\\end{aligned}}}$

где и — предложения, выраженные в некоторой формальной системе. ${\displaystyle P}$ ${\displaystyle Q}$

Обобщенные законы Де Моргана обеспечивают эквивалентность для отрицания конъюнкции или дизъюнкции, включающей несколько терминов.
Для набора предложений обобщенные законы Де Моргана следующие: ${\displaystyle P_{1},P_{2},\dots ,P_{n}}$

${\displaystyle {\begin{aligned}\lnot (P_{1}\land P_{2}\land \dots \land P_{n})\leftrightarrow \lnot P_{1}\lor \lnot P_{2}\lor \ldots \lor \lnot P_{n}\\\lnot (P_{1}\lor P_{2}\lor \dots \lor P_{n})\leftrightarrow \lnot P_{1}\land \lnot P_{2}\land \ldots \land \lnot P_{n}\end{aligned}}}$

Эти законы обобщают первоначальные законы Де Моргана для отрицания конъюнкций и дизъюнкций.

Форма замены

Законы Де Моргана обычно показаны в компактной форме выше, с отрицанием выхода слева и отрицанием входов справа. Более ясная форма для подстановки может быть сформулирована как:

${\displaystyle {\begin{aligned}(P\land Q)&\Longleftrightarrow \neg (\neg P\lor \neg Q),\\(P\lor Q)&\Longleftrightarrow \neg (\neg P\land \neg Q).\end{aligned}}}$

Это подчеркивает необходимость инвертировать как входы, так и выходы, а также менять оператор при выполнении подстановки.

Теория множеств

В теории множеств это часто определяется как «взаимообмен объединения и пересечения при дополнении» ^[6] , что формально можно выразить как:

${\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}}$

где:

• ${\displaystyle {\overline {A}}}$является отрицанием , при этом верхняя черта пишется над терминами, которые нужно отрицать, ${\displaystyle A}$
• ${\displaystyle \cap }$— оператор пересечения (И),
• ${\displaystyle \cup }$— оператор объединения (ИЛИ).

Объединения и пересечения любого количества множеств

Обобщенная форма —

${\displaystyle {\begin{aligned}{\overline {\bigcap _{i\in I}A_{i}}}&\equiv \bigcup _{i\in I}{\overline {A_{i}}},\\{\overline {\bigcup _{i\in I}A_{i}}}&\equiv \bigcap _{i\in I}{\overline {A_{i}}},\end{aligned}}}$

где I — некоторое, возможно счетное или несчетное бесконечное, индексное множество.

В системе обозначений законы Де Моргана можно запомнить, используя мнемонический прием «перерыв строки, смена знака» ^{[7] .}

Булева алгебра

Аналогично в булевой алгебре этот закон можно формально выразить так:

${\displaystyle {\begin{aligned}{\overline {A\land B}}&={\overline {A}}\lor {\overline {B}},\\{\overline {A\lor B}}&={\overline {A}}\land {\overline {B}},\end{aligned}}}$

где:

• ${\displaystyle {\overline {A}}}$является отрицанием , при этом верхняя черта пишется над терминами, которые нужно отрицать, ${\displaystyle A}$
• ${\displaystyle \land }$— оператор логического соединения (И),
• ${\displaystyle \lor }$— оператор логической дизъюнкции (ИЛИ).

что можно обобщить до

${\displaystyle {\begin{aligned}{\overline {A_{1}\land A_{2}\land \ldots \land A_{n}}}={\overline {A_{1}}}\lor {\overline {A_{2}}}\lor \ldots \lor {\overline {A_{n}}},\\{\overline {A_{1}\lor A_{2}\lor \ldots \lor A_{n}}}={\overline {A_{1}}}\land {\overline {A_{2}}}\land \ldots \land {\overline {A_{n}}}.\end{aligned}}}$

Инженерное дело

В электротехнике и вычислительной технике законы де Моргана обычно записываются так:

${\displaystyle {\overline {(A\cdot B)}}\equiv ({\overline {A}}+{\overline {B}})}$

и

${\displaystyle {\overline {(A+B)}}\equiv ({\overline {A}}\cdot {\overline {B}}),}$

где:

• ${\displaystyle \cdot }$это логическое И,
• ${\displaystyle +}$это логическое ИЛИ,
• черта сверху — это логическое НЕ того, что находится под чертой.

Поиск текста

Законы де Моргана обычно применяются к поиску текста с использованием булевых операторов AND, OR и NOT. Рассмотрим набор документов, содержащих слова «кошки» и «собаки». Законы де Моргана гласят, что эти два поиска вернут один и тот же набор документов:

Поиск A: НЕ (кошки ИЛИ собаки)

Поиск B: (НЕ кошки) И (НЕ собаки)

Корпус документов, содержащих «кошки» или «собаки», можно представить четырьмя документами:

Документ 1: Содержит только слово «кошки».

Документ 2: Содержит только «собак».

Документ 3: Содержит как «кошек», так и «собак».

Документ 4: Не содержит ни «кошек», ни «собак».

Чтобы оценить Поиск А, очевидно, что поиск «(кошки ИЛИ собаки)» попадет в Документы 1, 2 и 3. Таким образом, отрицание этого поиска (то есть Поиск А) попадет во все остальное, то есть в Документ 4.

При оценке поиска B поиск «(НЕ кошки)» выдаст результаты по документам, не содержащим слово «кошки», то есть по документам 2 и 4. Аналогично поиск «(НЕ собаки)» выдаст результаты по документам 1 и 4. Применение оператора AND к этим двум поискам (то есть по поиску B) выдаст результаты по документам, которые являются общими для этих двух поисков, то есть по документу 4.

Аналогичную оценку можно применить, чтобы показать, что следующие два поиска вернут документы 1, 2 и 4:

Поиск C: НЕ (кошки И собаки),

Поиск D: (НЕ кошки) ИЛИ (НЕ собаки).

История

Законы названы в честь Августа Де Моргана (1806–1871), ^[8] который ввел формальную версию законов в классическую пропозициональную логику . Формулировка Де Моргана находилась под влиянием алгебраизации логики, предпринятой Джорджем Булем , которая позже закрепила притязания Де Моргана на открытие. Тем не менее, похожее наблюдение было сделано Аристотелем и было известно греческим и средневековым логикам. ^[9] Например, в 14 веке Уильям Оккам записал слова, которые получались при прочтении законов. ^[10] Жан Буридан в своей книге Summulae de Dialectica также описывает правила преобразования, которые следуют линиям законов Де Моргана. ^[11] Тем не менее, Де Моргану приписывают заслугу за формулировку законов в терминах современной формальной логики и включение их в язык логики. Законы Де Моргана можно легко доказать, и они могут даже показаться тривиальными. ^[12] Тем не менее, эти законы полезны для принятия обоснованных выводов в доказательствах и дедуктивных аргументах.

Доказательство для булевой алгебры

Теорему де Моргана можно применить к отрицанию дизъюнкции или отрицанию конъюнкции во всей формуле или ее части.

Отрицание дизъюнкции

В случае его применения к дизъюнкции рассмотрим следующее утверждение: «ложно, что хотя бы одно из утверждений A или B истинно», которое записывается как:

${\displaystyle \neg (A\lor B).}$

Поскольку установлено, что ни A, ни B не являются истинными, то из этого следует, что как A, так и B не являются истинными, что можно записать непосредственно как:

${\displaystyle (\neg A)\wedge (\neg B).}$

Если бы A или B были истинны, то дизъюнкция A и B была бы истинной, делая ее отрицание ложным. Представленное на английском языке, это следует логике, что «поскольку две вещи обе ложны, также ложно, что любая из них истинна».

Работая в противоположном направлении, второе выражение утверждает, что A ложно, а B ложно (или, что эквивалентно, что «не A» и «не B» истинны). Зная это, дизъюнкция A и B также должна быть ложной. Отрицание указанной дизъюнкции должно, таким образом, быть истинным, и результат идентичен первому утверждению.

Отрицание союза

Применение теоремы Де Моргана к конъюнкции очень похоже на ее применение к дизъюнкции как по форме, так и по обоснованию. Рассмотрим следующее утверждение: «ложно, что A и B оба истинны», которое записывается как:

${\displaystyle \neg (A\land B).}$

Для того чтобы это утверждение было истинным, одно или оба из A или B должны быть ложными, поскольку если бы они оба были истинными, то конъюнкция A и B была бы истинной, делая ее отрицание ложным. Таким образом, одно (по крайней мере) или более из A и B должны быть ложными (или, что эквивалентно, одно или более из «не A» и «не B» должны быть истинными). Это можно записать непосредственно как,

${\displaystyle (\neg A)\lor (\neg B).}$

Изложенное на английском языке, это следует логике, что «поскольку ложно, что две вещи обе истинны, по крайней мере одна из них должна быть ложной».

Работая в обратном направлении, второе выражение утверждает, что по крайней мере одно из "не A" и "не B" должно быть истинным, или, что эквивалентно, что по крайней мере одно из A и B должно быть ложным. Поскольку по крайней мере одно из них должно быть ложным, то их конъюнкция также будет ложной. Отрицание указанной конъюнкции, таким образом, приводит к истинному выражению, и это выражение идентично первому утверждению.

Доказательство теории множеств

Здесь мы используем для обозначения дополнения A, как выше в § Теория множеств и Булева алгебра. Доказательство, которое завершается в 2 шага путем доказательства как и . ${\displaystyle {\overline {A}}}$ ${\displaystyle {\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}}$ ${\displaystyle {\overline {A\cap B}}\subseteq {\overline {A}}\cup {\overline {B}}}$ ${\displaystyle {\overline {A}}\cup {\overline {B}}\subseteq {\overline {A\cap B}}}$

Часть 1

Пусть . Тогда, . ${\displaystyle x\in {\overline {A\cap B}}}$ ${\displaystyle x\not \in A\cap B}$

Потому что , должно быть, или . ${\displaystyle A\cap B=\{\,y\ |\ y\in A\wedge y\in B\,\}}$ ${\displaystyle x\not \in A}$ ${\displaystyle x\not \in B}$

Если , то , так . ${\displaystyle x\not \in A}$ ${\displaystyle x\in {\overline {A}}}$ ${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$

Аналогично, если , то , поэтому . ${\displaystyle x\not \in B}$ ${\displaystyle x\in {\overline {B}}}$ ${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$

Таким образом, ; ${\displaystyle \forall x{\Big (}x\in {\overline {A\cap B}}\implies x\in {\overline {A}}\cup {\overline {B}}{\Big )}}$

то есть, . ${\displaystyle {\overline {A\cap B}}\subseteq {\overline {A}}\cup {\overline {B}}}$

Часть 2

Чтобы доказать обратное направление, пусть , и для отступления предположим . ${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$ ${\displaystyle x\not \in {\overline {A\cap B}}}$

При таком предположении должно быть так, что , ${\displaystyle x\in A\cap B}$

отсюда следует, что и , и таким образом и . ${\displaystyle x\in A}$ ${\displaystyle x\in B}$ ${\displaystyle x\not \in {\overline {A}}}$ ${\displaystyle x\not \in {\overline {B}}}$

Однако это означает , что, вопреки гипотезе , ${\displaystyle x\not \in {\overline {A}}\cup {\overline {B}}}$ ${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$

следовательно, предположение не должно иметь места, то есть . ${\displaystyle x\not \in {\overline {A\cap B}}}$ ${\displaystyle x\in {\overline {A\cap B}}}$

Следовательно, , ${\displaystyle \forall x{\Big (}x\in {\overline {A}}\cup {\overline {B}}\implies x\in {\overline {A\cap B}}{\Big )}}$

то есть, . ${\displaystyle {\overline {A}}\cup {\overline {B}}\subseteq {\overline {A\cap B}}}$

Заключение

Если и , то ; это завершает доказательство закона де Моргана. ${\displaystyle {\overline {A}}\cup {\overline {B}}\subseteq {\overline {A\cap B}}}$ ${\displaystyle {\overline {A\cap B}}\subseteq {\overline {A}}\cup {\overline {B}}}$ ${\displaystyle {\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}}$

Другой закон Де Моргана , доказывается аналогично. ${\displaystyle {\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}}$

Обобщение двойственности Де Моргана

Законы Де Моргана, представленные в виде схемы с логическими вентилями ( схемы Международной электротехнической комиссии )

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

Пусть определяется двойственный оператор любого пропозиционального оператора P( p , q , ...), зависящий от элементарных пропозиций p , q , ... , как оператор, определяемый формулой ${\displaystyle {\mbox{P}}^{d}}$

${\displaystyle {\mbox{P}}^{d}(p,q,...)=\neg P(\neg p,\neg q,\dots ).}$

Расширение предикатной и модальной логики

Эту двойственность можно обобщить на квантификаторы, например, квантификатор всеобщности и квантификатор существования являются дуальными:

${\displaystyle \forall x\,P(x)\equiv \neg [\exists x\,\neg P(x)]}$

${\displaystyle \exists x\,P(x)\equiv \neg [\forall x\,\neg P(x)]}$

Чтобы связать эти кванторные дуальности с законами Де Моргана, создадим модель с некоторым небольшим числом элементов в ее области D , например

Д = { а , б , в }.

Затем

${\displaystyle \forall x\,P(x)\equiv P(a)\land P(b)\land P(c)}$

и

${\displaystyle \exists x\,P(x)\equiv P(a)\lor P(b)\lor P(c).}$

Но, используя законы Де Моргана,

${\displaystyle P(a)\land P(b)\land P(c)\equiv \neg (\neg P(a)\lor \neg P(b)\lor \neg P(c))}$

и

${\displaystyle P(a)\lor P(b)\lor P(c)\equiv \neg (\neg P(a)\land \neg P(b)\land \neg P(c)),}$

проверка кванторных дуальностей в модели.

Затем кванторную дуальность можно распространить далее на модальную логику , связав операторы «ящик» («обязательно») и «ромб» («возможно»):

${\displaystyle \Box p\equiv \neg \Diamond \neg p,}$

${\displaystyle \Diamond p\equiv \neg \Box \neg p.}$

Применительно к алетическим модальностям возможности и необходимости Аристотель наблюдал этот случай, а в случае обычной модальной логики связь этих модальных операторов с квантификацией можно понять, построив модели с использованием семантики Крипке .

В интуиционистской логике

Три из четырех следствий законов де Моргана имеют место в интуиционистской логике . В частности, мы имеем

${\displaystyle \neg (P\lor Q)\,\leftrightarrow \,{\big (}(\neg P)\land (\neg Q){\big )},}$

и

${\displaystyle {\big (}(\neg P)\lor (\neg Q){\big )}\,\to \,\neg (P\land Q).}$

Обратное последней импликации не выполняется в чистой интуиционистской логике. То есть, неудача совместного предложения не может быть обязательно разрешена неудачей любого из двух конъюнктов . Например, из знания того, что не было случая, когда и Алиса, и Боб пришли на свое свидание, не следует, кто не пришел. Последний принцип эквивалентен принципу слабого исключенного третьего , ${\displaystyle P\land Q}$ ${\displaystyle {\mathrm {WPEM} }}$

${\displaystyle (\neg P)\lor \neg (\neg P).}$

Эта слабая форма может быть использована в качестве основы для промежуточной логики . Для уточненной версии несостоятельного закона, касающегося экзистенциальных утверждений, см. менее ограниченный принцип всеведения , который, однако, отличается от . ${\displaystyle {\mathrm {LLPO} }}$ ${\displaystyle {\mathrm {WLPO} }}$

Справедливость остальных трех законов Де Моргана остается верной, если отрицание заменить импликацией для некоторого произвольного постоянного предиката C, что означает, что вышеуказанные законы по-прежнему верны в минимальной логике . ${\displaystyle \neg P}$ ${\displaystyle P\to C}$

Аналогично вышеизложенному, кванторные законы:

${\displaystyle \forall x\,\neg P(x)\,\leftrightarrow \,\neg \exists x\,P(x)}$

и

${\displaystyle \exists x\,\neg P(x)\,\to \,\neg \forall x\,P(x).}$

являются тавтологиями даже в минимальной логике, где отрицание заменено подразумеванием фиксированного , тогда как обратное последнему закону не обязательно должно быть верным в общем случае. ${\displaystyle Q}$

Далее, еще есть

${\displaystyle (P\lor Q)\,\to \,\neg {\big (}(\neg P)\land (\neg Q){\big )},}$

${\displaystyle (P\land Q)\,\to \,\neg {\big (}(\neg P)\lor (\neg Q){\big )},}$

${\displaystyle \forall x\,P(x)\,\to \,\neg \exists x\,\neg P(x),}$

${\displaystyle \exists x\,P(x)\,\to \,\neg \forall x\,\neg P(x),}$

но их инверсия подразумевает исключенное третье . ${\displaystyle {\mathrm {PEM} }}$

В компьютерной инженерии

• Законы де Моргана широко используются в компьютерной инженерии и цифровой логике с целью упрощения схемных решений. ^[13]
• В современных языках программирования, благодаря оптимизации компиляторов и интерпретаторов, различия в производительности между этими вариантами незначительны или полностью отсутствуют.

Смотрите также

• Двойственность конъюнкции/дизъюнкции
• Однородность (лингвистика)
• Изоморфизм
• Список тем по булевой алгебре
• Список установленных тождеств и отношений
• Положительная логика

Ссылки

1. Копи, Ирвинг М.; Коэн, Карл; Макмахон, Кеннет (2016). Введение в логику. doi :10.4324/9781315510897. ISBN 9781315510880.
2. Херли, Патрик Дж. (2015), Краткое введение в логику (12-е изд.), Cengage Learning, ISBN 978-1-285-19654-1
3. Мур, Брук Ноэль (2012). Критическое мышление. Ричард Паркер (10-е изд.). Нью-Йорк: McGraw-Hill. ISBN 978-0-07-803828-0. OCLC  689858599.
4. Теорема ДеМоргана [sic]
5. Кашеф, Арман. (2023), В поисках универсальной логики: краткий обзор эволюции формальной логики, doi : 10.13140/RG.2.2.24043.82724/1
6. Булева алгебра Р. Л. Гудстейна. ISBN 0-486-45894-6 
7. 2000 решенных задач по цифровой электронике, С.П. Бали
8. "Теоремы ДеМоргана". Middle Tennessee State University . Архивировано из оригинала 2008-03-23.
9. История формальной логики Боченского
10. Уильям Оккам, Summa Logicae , часть II, разделы 32 и 33.
11. Жан Буридан, Summula de Dialectica . Перевод Дьюлы Клима. New Haven: Yale University Press, 2001. См. особенно Treatise 1, Chapter 7, Section 5. ISBN 0-300-08425-0 
12. Роберт Х. Орр. "Август Де Морган (1806–1871)". Университет Индианы–Университет Пердью Индианаполис . Архивировано из оригинала 2010-07-15.
13. Вирт, Никлаус (1995), Проектирование цифровых схем для студентов-компьютерщиков: вводный учебник, Springer, стр. 16, ISBN 9783540585770

Внешние ссылки

• «Принцип двойственности», Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Законы де Моргана». Математический мир .
• Законы де Моргана на PlanetMath .
• Двойственность в логике и языке, Интернет-энциклопедия философии .