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

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

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

В логике высказываний и булевой алгебре законы Де Моргана , ^{[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. Применение Оператор И для этих двух поисков (поиск 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]

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

• Изоморфизм - оператор NOT как изоморфизм между положительной логикой и отрицательной логикой
• Список тем по булевой алгебре
• Список установленных личностей и отношений
• Позитивная логика

Рекомендации

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 г. в Wayback Machine на mtsu.edu.
9. История формальной логики Боченского
10. Уильям Оккам, Summa Logicae , часть II, разделы 32 и 33.
11. Жан Буридан, Сумма диалектики . Пер. Дьюла Клима. Нью-Хейвен: Издательство Йельского университета, 2001. См. особенно Трактат 1, Глава 7, Раздел 5. ISBN 0-300-08425-0. 
12. Огастес Де Морган (1806–1871). Архивировано 15 июля 2010 г. в Wayback Machine Робертом Х. Орром.
13. "Теоремы Де Моргана | Заметки GATE" . БИДЖУС . Проверено 21 декабря 2022 г.

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

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