ru.wikipedia.org

Законы де Моргана — Википедия

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

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

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

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

не (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}}} или по-другому: {\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}}} или по-другому: {\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}}}} и {\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: 

# Исходное выражение (дизъюнкция отрицаний)
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.