9. Правило де Моргана

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

История и определение 

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

not (P and Q) = (not P) or (not Q)

not (P or Q) = (not P) and (not Q)

Обычная запись этих законов в формальной логике:

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

Формулы де-Моргана применимы при любом числе аргументов. Они иллюстрируют глубокую взаимную симметрию операций И и ИЛИ: если операция И избирательно реагирует на совпадение прямых сигналов, то операция ИЛИ так же избирательно реагирует на совпадение их инверсий. Элемент ИЛИ прозрачен для любого сигнала, элемент И — для любой инверсии. Пользуясь формулами де-Моргана, можно легко переводить логические схемы из базиса НЕ, И, ИЛИ, в котором человеку привычнее всего мыслить и составлять исходные логические выражения, в инвертирующие базисы, которые эффективнее всего реализуются интегральной технологией.