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

Диаграммы Венна законов де Моргана

Представление правил де Моргана через логические элементы

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

$\neg \forall x\,P(x)\equiv \exists x\,\neg P(x),$

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

Следствия:

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

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

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

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

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

Применение

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

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

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

Пример на Python:

# Исходное выражение (дизъюнкция отрицаний)
if not a or not b:
    # ...

# Преобразованное выражение (отрицание конъюнкции)
if not (a and b):
    # ...

Пример на 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.