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


Определение
Огастес де Морган первоначально заметил, что в классической пропозициональной логике справедливы следующие соотношения:
- не (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[en]
См. также
Ссылки
- Weisstein, Eric W. Законы де Моргана (англ.) на сайте Wolfram MathWorld.