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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Диаграммы Венна, описывающие Законы де Моргана
Представление правил де Моргана через логические элементы

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

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

Определение[править | править вики-текст]

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

не (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&B), то для того, чтобы найти обратное от всего суждения ~(A&B), необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, операцией «или» — (~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).

Ссылки[править | править вики-текст]