Перейти к содержанию

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

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

Обновлено Редакция GAW

Законы де Моргана (De Morgan's laws, теоремы де Моргана) — два тождества булевой алгебры, которые связывают инверсию с операциями И и ИЛИ:

A⋅B‾=A‾+B‾,A+B‾=A‾⋅B‾\overline{A \cdot B} = \overline{A} + \overline{B}, \qquad \overline{A + B} = \overline{A} \cdot \overline{B}

Словами: инверсия произведения равна сумме инверсий, инверсия суммы — произведению инверсий. Законы верны для любого числа переменных: (ABC)' = A' + B' + C'.

Что это значит для логических элементов

Kuphaldt формулирует законы через элементы: И-НЕ (NAND) эквивалентен элементу ИЛИ с инверсными входами (Negative-OR), а ИЛИ-НЕ (NOR) — элементу И с инверсными входами (Negative-AND). Интуиция тут подводит: И с инверсными входами совпадает не с И-НЕ, а с ИЛИ-НЕ. Отсюда два следствия:

  • Схему И-ИЛИ можно перестроить на одних элементах И-НЕ — именно это делает И-НЕ универсальным элементом. Например, микросхема с четырьмя элементами 2И-НЕ, такая как 74HC00, заменяет и И, и ИЛИ, и инвертор.
  • На схемах один и тот же элемент рисуют двумя способами, чтобы подчеркнуть, активен ли сигнал высоким или низким уровнем.

«Разбиение» черты

Правила работы с длинной чертой инверсии по Kuphaldt:

  1. Разбивать за один шаг только одну черту, начиная с самой длинной — верхней.
  2. В месте разрыва операция меняется: И на ИЛИ, ИЛИ на И; куски черты остаются над своими членами.
  3. Черта действует как скобки: члены под ней остаются сгруппированными.

Пример из учебника: (A + (BC)')' после разрыва верхней черты даёт A' · (BC)'', двойная инверсия снимается, и получается A'BC — трёхвходовый элемент И с инверсией на входе A.

Те же правила работают в коде: !(a && b) равно !a || !b. Проверить преобразование на всех комбинациях входов можно в симуляторе логических схем, а связь законов с остальными тождествами разобрана на странице «Цифровая логика».

Частые вопросы

Как применять закон де Моргана к выражению с несколькими чертами?

По Kuphaldt: разбивать за один шаг только одну черту, начиная с самой длинной, верхней. При разрыве черты операция под местом разрыва меняется — И на ИЛИ или наоборот, — а куски черты остаются над своими членами. Черта работает как скобки, поэтому сгруппированные под ней члены остаются в скобках.

Почему элемент И-НЕ можно нарисовать как ИЛИ с кружками на входах?

Это и есть первый закон де Моргана: (AB)' = A' + B'. Выход И-НЕ равен нулю только при двух единицах на входах, а ИЛИ инверсных входов даёт ноль тоже только тогда, когда оба входа равны единице. На схемах такое изображение подчёркивает, что сигналы активны низким уровнем.

Где законы де Моргана встречаются в программировании?

В условиях: !(a && b) эквивалентно !a || !b, а !(a || b) — !a && !b. Так упрощают отрицание сложного условия и переписывают проверки битов: ~(x | y) равно ~x & ~y. Компиляторы делают такие замены сами, но для чтения кода их полезно знать.

Источники

  1. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 7 «Boolean Algebra», разд. «DeMorgan's Theorems» (CC BY) — теоремы описывают эквивалентность элементов с инверсными входами и с инверсным выходом: NAND эквивалентен Negative-OR, NOR — Negative-AND; при «разбиении» черты дополнения операция под разрывом меняется на противоположную, а куски черты остаются над своими членами; сначала разбивать самую длинную черту, никогда не две за один шаг; черта работает как скобки; пример (A + (BC)')' — трёхвходовое И с инверсией A
  2. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 3 «Logic Gates» (CC BY) — Negative-AND — И с инвертированными входами, по таблице истинности совпадает с NOR, а не с NAND; Negative-OR совпадает с NAND

Нашли ошибку?

Смотрите также