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

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

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

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

Определение

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

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

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

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

[math]\displaystyle{ \begin{matrix} \neg {(a \wedge b)} = \neg{a} \vee \neg{b} \\ \neg {(a \vee b)} = \neg{a} \wedge \neg{b} \end{matrix} }[/math] 000 или в другой записи: 000 [math]\displaystyle{ \begin{matrix} \overline{(a \wedge b)} = \overline{a} \vee \overline{b} \\ \overline{(a \vee b)} = \overline{a} \wedge \overline{b} \end{matrix} }[/math]

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

[math]\displaystyle{ \begin{matrix} \overline{A \cap B} = \overline{A} \cup \overline{B} \\ \overline{A \cup B} = \overline{A} \cap \overline{B} \end{matrix} }[/math] 000 или в другой записи: 000 [math]\displaystyle{ \begin{matrix} (A\cap B)^C=A^C\cup B^C, \\ (A\cup B)^C=A^C\cap B^C. \end{matrix} }[/math]

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

[math]\displaystyle{ \overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i} }[/math] 00000 и 00000 [math]\displaystyle{ \overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i} }[/math].

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

[math]\displaystyle{ \neg \forall x \, P(x) \equiv \exists x \, \neg P(x), }[/math]

[math]\displaystyle{ \neg \exists x \, P(x) \equiv \forall x \, \neg P(x). }[/math]

Следствия:

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

[math]\displaystyle{ a \wedge b = \neg(\neg{a} \vee \neg{b}) }[/math]

[math]\displaystyle{ a \vee b = \neg(\neg{a} \wedge \neg{b}) }[/math]

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

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

Применение

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

История

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

Оригинальный текст (англ.)[показатьскрыть]

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

— Уильям Оккам, Summa Logicae^[en]

См. также

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

Ссылки

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