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

Законы де Мо́ргана (правила де Мо́ргана) — логические правила, связывающие пары логических операций при помощи логического отрицания. Названы в честь шотландского математика Огастеса де Моргана. В краткой форме звучат так:

Отрицание конъюнкции есть дизъюнкция отрицаний.

Отрицание дизъюнкции есть конъюнкция отрицаний.

Огастес де Морган первоначально заметил, что в классической пропозициональной логике справедливы следующие соотношения:

не (a и b) = (не a) или (не b)

не (a или b) = (не a) и (не b)

Символьно это можно записать так:

${\displaystyle {\begin{matrix}\neg {(a\wedge b)}=\neg {a}\vee \neg {b}\\\neg {(a\vee b)}=\neg {a}\wedge \neg {b}\end{matrix}}}$000 или по-другому: 000${\displaystyle {\begin{matrix}{\overline {(a\wedge b)}}={\overline {a}}\vee {\overline {b}}\\{\overline {(a\vee b)}}={\overline {a}}\wedge {\overline {b}}\end{matrix}}}$

В теории множеств:

${\displaystyle {\begin{matrix}{\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}\\{\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}\end{matrix}}}$000 или по-другому: 000${\displaystyle {\begin{matrix}(A\cap B)^{C}=A^{C}\cup B^{C},\\(A\cup B)^{C}=A^{C}\cap B^{C}.\end{matrix}}}$

Эти правила также действительны для множества элементов (семейств):

${\displaystyle {\overline {\bigcap _{i\in I}A_{i}}}=\bigcup _{i\in I}{\overline {A_{i}}}}$00000 и 00000${\displaystyle {\overline {\bigcup _{i\in I}A_{i}}}=\bigcap _{i\in I}{\overline {A_{i}}}}$.

В исчислении предикатов:

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

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

Следствия:

Используя законы де Моргана, можно выразить конъюнкцию через дизъюнкцию и три отрицания. Аналогично можно выразить дизъюнкцию:

${\displaystyle a\wedge b=\neg (\neg {a}\vee \neg {b})}$

${\displaystyle a\vee b=\neg (\neg {a}\wedge \neg {b})}$

В виде теоремы:

Если существует суждение, выраженное операцией логического умножения двух или более элементов, то есть операцией «и»: ${\displaystyle {(A\wedge B)}}$, то для того, чтобы найти обратное${\displaystyle {\neg (A\wedge B)}}$ от всего суждения, необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, то есть операцией «или»: ${\displaystyle (\neg {A}\vee \neg {B})}$. Закон работает аналогично в обратном направлении: ${\displaystyle \neg (A\vee B)=(\neg {A}\wedge \neg {B})}$.

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

Законы де Моргана могут использоваться в программировании для организации и улучшения читаемости кода.

Пример на Python:

# Исходное выражение (дизъюнкция отрицаний)ifnotaornotb:# ...# Преобразованное выражение (отрицание конъюнкции)ifnot(aandb):# ...

Пример на Java:

// Исходное выражение (отрицание дизъюнкции)if (!(a || b)) {    // ...}// Преобразованное выражение (конъюнкция отрицаний)if (!a && !b) {    // ...}

В современных языках программирования, благодаря оптимизации компиляторов и интерпретаторов, различия в производительности между этими вариантами ничтожны или полностью отсутствуют. Поэтому выбор между, например, !a || !b и !(a && b) зависит от читаемости, логической ясности и предпочтений программиста. При выборе варианта следует учитывать, какое выражение проще понять другим и какое лучше отражает логику задачи.

Противоречащая противоположность дизъюнктивного суждения — конъюнктивное суждение, составленное из противоречащих противоположностей частей дизъюнктивного суждения.

Оригинальный текст (англ.)

The contradictory opposite of a disjunctive proposition is a conjunctive proposition composed of the contradictories of the parts of the disjunctive proposition.

— Уильям Оккам, Summa Logicae

• Формула включений-исключений

• Weisstein, Eric W.Законы де Моргана (англ.) на сайте Wolfram MathWorld.

В статье есть список источников, но не хватает сносок.

Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены.(21 января 2014)