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

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

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

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

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

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

Определение

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

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

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

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

$\begin{array}{c}\mathrm{\neg }(a\wedge b)=\mathrm{\neg }a\vee \mathrm{\neg }b\\ \mathrm{\neg }(a\vee b)=\mathrm{\neg }a\wedge \mathrm{\neg }b\end{array}$ Шаблон:0 или по-другому: Шаблон:0 $\begin{array}{c}\overline{(a\wedge b)}=\bar{a}\vee \bar{b}\\ \overline{(a\vee b)}=\bar{a}\wedge \bar{b}\end{array}$

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

$\begin{array}{c}\overline{A\cap B}=\bar{A}\cup \bar{B}\\ \overline{A\cup B}=\bar{A}\cap \bar{B}\end{array}$ Шаблон:0 или по-другому: Шаблон:0 $\begin{array}{c}(A\cap B{)}^C=A^C\cup B^C,\\ (A\cup B{)}^C=A^C\cap B^C.\end{array}$

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

$\overline{\bigcap _{i\in I}{A}_i}=\bigcup _{i\in I}\overline{A_i}$ Шаблон:0 и Шаблон:0 $\overline{\bigcup _{i\in I}{A}_i}=\bigcap _{i\in I}\overline{A_i}$.

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

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

$\mathrm{\neg }\mathrm{\exists }xP(x)\equiv \mathrm{\forall }x\mathrm{\neg }P(x).$

Следствия:

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

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

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

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

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

Применение

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

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

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

Пример на Python:

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

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

Пример на Java:

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

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

В современных языках программирования, благодаря оптимизации компиляторов и интерпретаторов, различия в производительности между этими вариантами ничтожны или полностью отсутствуют. Поэтому выбор между, например, Шаблон:Code и Шаблон:Code зависит от читаемости, логической ясности и предпочтений программиста. При выборе варианта следует учитывать, какое выражение проще понять другим и какое лучше отражает логику задачи.

История

Шаблон:Начало цитаты Противоречащая противоположность дизъюнктивного суждения — конъюнктивное суждение, составленное из противоречащих противоположностей частей дизъюнктивного суждения. Шаблон:Оригинальный текст Шаблон:Конец цитаты

См. также

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

Ссылки

• Шаблон:MathWorld