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

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

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

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

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

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

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

В математике это выглядит так:

000 или по-другому: 000


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

000 или по-другому: 000


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

00000 и 00000 .


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


Следствия:

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


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

Если существует суждение, выраженное операцией логического умножения двух или более элементов, т.е. операцией «и»: , то для того, чтобы найти обратное от всего суждения, необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, т.е. операцией «или»: . Закон работает аналогично в обратном направлении: .

Применение[править | править вики-текст]

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

История[править | править вики-текст]

  • «Противоречащая противоположность дизъюнктивного суждения — конъюнктивное суждение, составленное из противоречащих противоположностей частей дизъюнктивного суждения (The contradictory opposite of a disjunctive proposition is a conjunctive proposition composed of the contradictories of the parts of the disjunctive proposition)» (Уильям Оккам, Summa Logicae).

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