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

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

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

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

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

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

или

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

или

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

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

В теории множеств и булевой алгебре они формально записываются как

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

где

• ${\displaystyle A}$и являются наборами, ${\displaystyle B}$
• ${\displaystyle {\overline {A}}}$является дополнением , ${\displaystyle A}$
• ${\displaystyle \cap }$это пересечение , и
• ${\displaystyle \cup }$это союз .

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

На формальном языке правила записываются как

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

и

${\displaystyle \neg (P\land Q)\iff (\neg P)\lor (\neg Q)}$

где

• P и Q — предложения,
• ${\displaystyle \neg }$– логический оператор отрицания (НЕ),
• ${\displaystyle \land }$– логический оператор конъюнкции (И),
• ${\displaystyle \lor }$– логический оператор дизъюнкции (ИЛИ),
• ${\displaystyle \iff }$— это металогический символ, означающий «может быть заменен в логическом доказательстве на», который часто читается как «тогда и только если». Для любой комбинации значений «истина/ложь» для P и Q левая и правая стороны стрелки после оценки будут иметь одно и то же значение истинности.

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

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

${\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 {\overline {(A\cdot B)}}\equiv ({\overline {A}}+{\overline {B}})}$

и

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

где:

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

Текстовый поиск

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

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

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

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

Документ 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] Жан Буридан в своей книге «Суммы диалектики» также описывает правила конверсии, которые следуют законам Де Моргана. ^[11] Тем не менее, Де Моргану приписывают изложение законов в терминах современной формальной логики и включение их в язык логики. Законы де Моргана легко доказать и даже могут показаться тривиальными. ^[12] Тем не менее, эти законы помогают делать обоснованные выводы в доказательствах и дедуктивных аргументах.

Неофициальное доказательство

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

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

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

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

Поскольку установлено, что ни А, ни В не истинно, из этого должно следовать, что и А неверно, и В неверно, что можно записать непосредственно как:

${\displaystyle (\neg A)\wedge (\neg 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, как указано выше в § Теория множеств и булева алгебра. Доказательство, которое завершается в два этапа доказательством обоих и . ${\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 , например:

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). Введение в логику. дои : 10.4324/9781315510897. ISBN 9781315510880.
2. Херли, Патрик Дж. (2015), Краткое введение в логику (12-е изд.), Cengage Learning, ISBN 978-1-285-19654-1
3. Мур, Брук Ноэль (2012). Критическое мышление. Ричард Паркер (10-е изд.). Нью-Йорк: МакГроу-Хилл. ISBN 978-0-07-803828-0. ОКЛК  689858599.
4. Теорема ДеМоргана [так в оригинале]
5. Кашеф, Арман. (2023), В поисках универсальной логики: краткий обзор эволюции формальной логики, doi :10.13140/RG.2.2.24043.82724/1
6. Булева алгебра Р. Л. Гудштейна. ISBN 0-486-45894-6 
7. 2000 Решенные проблемы в цифровой электронике, SP Bali
8. «Теоремы ДеМоргана». Государственный университет Среднего Теннесси . Архивировано из оригинала 23 марта 2008 г.
9. История формальной логики Боченского
10. Уильям Оккам, Summa Logicae , часть II, разделы 32 и 33.
11. Жан Буридан, Сумма диалектики . Пер. Дьюла Клима. Нью-Хейвен: Издательство Йельского университета, 2001. См. особенно Трактат 1, Глава 7, Раздел 5. ISBN 0-300-08425-0. 
12. Роберт Х. Орр. «Огастес Де Морган (1806–1871)». Университет Индианы – Университет Пердью, Индианаполис . Архивировано из оригинала 15 июля 2010 г.
13. Вирт, Никлаус (1995), Проектирование цифровых схем для студентов-компьютерщиков: вводный учебник, Springer, стр. 16, ISBN 9783540585770

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

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