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

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

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

Определение

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

не (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})}$ .

Применение

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

История

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

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

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 .