Законы де Мо́ргана (правила де Мо́ргана) — логические правила, связывающие пары логических операций при помощи логического отрицания. Названы в честь шотландского математика Огастеса де Моргана. В краткой форме звучат так: Отрицание конъюнкции есть дизъюнкция отрицаний. Отрицание дизъюнкции есть конъюнкция отрицаний.
Определение Огастес де Морган первоначально заметил, что в классической пропозициональной логике справедливы следующие соотношения: не (a и b) = (не a) или (не b) не (a или b) = (не a) и (не b)
Символьно это можно записать так: или по-другому:
В теории множеств: или по-другому:
Эти правила также действительны для множества элементов (семейств): и .
В исчислении предикатов:
Следствия:
Используя законы де Моргана, можно выразить конъюнкцию через дизъюнкцию и три отрицания. Аналогично можно выразить дизъюнкцию:
В виде теоремы:
Если существует суждение, выраженное операцией логического умножения двух или более элементов, то есть операцией «и»: , то для того, чтобы найти обратное от всего суждения, необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, то есть операцией «или»: . Закон работает аналогично в обратном направлении: .
Применение Законы де Моргана применяются в таких важных областях, как дискретная математика, электротехника, физика и информатика; например, используются для оптимизации цифровых схем посредством замены одних логических элементов другими.
В программировании Законы де Моргана могут использоваться в программировании для организации и улучшения читаемости кода.
Пример на Python: # Исходное выражение (дизъюнкция отрицаний) if not a or not b: # ...
# Преобразованное выражение (отрицание конъюнкции) if not (a and b): # ...
Пример на Java: // Исходное выражение (отрицание дизъюнкции) if (!(a || b)) { // ... }
// Преобразованное выражение (конъюнкция отрицаний) if (!a && !b) { // ... }
В современных языках программирования, благодаря оптимизации компиляторов и интерпретаторов, различия в производительности между этими вариантами ничтожны или полностью отсутствуют. Поэтому выбор между, например, и зависит от читаемости, логической ясности и предпочтений программиста. При выборе варианта следует учитывать, какое выражение проще понять другим и какое лучше отражает логику задачи.
История
Противоречащая противоположность дизъюнктивного суждения — конъюнктивное суждение, составленное из противоречащих противоположностей частей дизъюнктивного суждения.
См. также Формула включений-исключений
Ссылки
Категория:Булева алгебра Моргана Категория:Математическая логика Моргана