Теоремы Де Моргана: освоение булевой инверсии и эквивалентности гейтов

Фундаментальная концепция булевой алгебры, теоремы Де Моргана связывают поведение логических гейтов при инверсии их входов или выходов. Эти правила, названные в честь математика Августа Де Моргана, позволяют инженерам преобразовывать гейты И, ИЛИ, NAND и NOR друг в друга, упрощая как логические выражения, так и физические схемы.

В булевой алгебре «групповая инверсия» обозначается длинной чертой над несколькими переменными, указывая на инверсию всего произведения или суммы. Это отличается от символа штриха ('), который может инвертировать только одну переменную. Например, (AB)^′ не то же самое, что A′B′; скобки обязательны, чтобы показать, что черта распространяется на всё произведение.

Когда все входы гейта инвертированы, его основная функция меняется: гейт ИЛИ со всеми инвертированными входами ведёт себя как NAND, а гейт И с инвертированными входами — как NOR. Теоремы Де Моргана формализуют это наблюдение, показывая, что инверсия выхода гейта даёт тот же эффект, что смена типа гейта и инверсия его входов.

Ниже приведена визуальная иллюстрация основной эквивалентности:

Когда длинная черта в булевом выражении «ломается», операция прямо под ломом меняется на обратную — сложение становится умножением и наоборот — а куски черты остаются над отдельными переменными. Это тонкое правило определяет, как выражения упрощаются.

В выражениях со множественными слоями черт наиболее безопасной стратегией является ломание самой длинной, верхней черты первой. Попытка сломать две черты одновременно может привести к ошибкам.

Например, упрощение (A + (BC)′)′ выполняется так:

Сначала ломаем внешнюю черту:

Получаем трёхвходовый гейт И с инвертированным входом A.

Никогда не ломайте более одной черты за один шаг:

Вместо этого можно сначала сломать более короткую внутреннюю черту, но это потребует дополнительного шага:

Обратите внимание: ломание черты в нескольких местах за один шаг допустимо; ограничение касается только одновременного ломания нескольких отдельных черт.

Скобки играют критическую роль, потому что черта работает как символ группировки. После ломания черты сгруппированные термы должны оставаться вместе для сохранения правильного приоритета операций.

Рассмотрим выражение, демонстрирующее важность правильной группировки:

Теперь применим теоремы Де Моргана к реальной гейтовой схеме. Первый шаг — перевести схему в булево выражение, пометив выход каждого гейта:

Двигаясь системно, запишем выходы первого NOR и NAND гейтов, не упуская черт инверсии, разделяя пред-инверсионное выражение от финального инвертированного выхода:

Наконец, выразим выход последнего NOR гейта:

Редукция получившегося выражения с помощью булевых тождеств и теорем Де Моргана даёт компактную форму:

Эквивалентная упрощённая схема показана ниже:

Ключевые выводы

• Теоремы Де Моргана показывают, что инверсия выхода гейта эквивалентна смене его типа (И ↔ ИЛИ) при инверсии входов.
• Ломание черты инверсии меняет базовую операцию; куски черты остаются над затронутыми переменными.
• Всегда ломайте самую длинную верхнюю черту первой и никогда не пытайтесь сломать две разные черты за один шаг.
• Черты служат символами группировки; после ломания сохраняйте правильную группировку скобками для сохранения приоритета.

Связанные рабочие листы

• Рабочий лист по булевой алгебре