Электроника:Цифровая электроника/Булева алгебра/Законы де Моргана

Содержание

Теория

Практика

Проверка знаний

Рецепты

Эксперименты

Резерв

Резерв

Резерв

Резерв

Перевод: Макаров В. (valemak)

Проверка/Оформление/Редактирование: Мякишев Е.А.

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

Математик по имени де Морган разработал пару важнейших правил, касающихся сгруппированных дополнений в булевой алгебре.

Под сгруппированным дополнением я имею в виду дополнение группы величин, с общей длинной чертой над более чем одной переменной.

Вы должны вспомнить из главы о логических вентилях, что инвертирование всех входов в вентиль меняет основную функцию этого вентиля с И на ИЛИ и наоборот (с ИЛИ на И), а также инвертирует общий выход.

Таким образом, вентиль ИЛИ со всеми инвертированными входами (вентиль «Отрицательное ИЛИ») ведёт себя так же, как вентиль И-НЕ, а вентиль И со всеми инвертированными входами (вентиль «Отрицательное И») ведёт себя так же, как вентиль ИЛИ-НЕ.

Законы де Моргана утверждают эту же эквивалентность в «обратной» форме: инвертирование выхода любого логического элемента приводит к той же функции, что и вентиль противоположного типа (И против ИЛИ) с инвертированными входами:

Рис. 1. Закон де Моргана, для дополнения произведения, представляемого как сумму дополнений.

Длинная черта над произведением AB, действует как группирующий символ и, полностью отличается от произведения A и B, над каждым из которых своя чёрточка. Другими словами, (AB)' не равно A'B'. Поскольку «простой» символ («'») визуально не может быть растянут на две переменные, приходится использовать круглые скобки, чтобы применить дополнение ко всему произведению AB в предыдущем утверждении.

Однако черта сама по себе действует как самостоятельный группирующий символ, поскольку её можно растянуть над более чем на одной переменной.

Как мы увидим в дальнейшем, это оказывает глубокое влияние на то, как вычисляются и сокращаются логические выражения.

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

Закон де Моргана можно рассматривать в контексте разрыва символа длинной черты, означающей дополнение.

Когда длинная черта разорвана, операция непосредственно под разрывом меняется со сложения на умножение или наоборот, а части сломанного черты остаются над отдельными переменными. Проиллюстрируем:

Рис. 2. Закон де Моргана можно рассматривать в контексте разрыва символа длинной черты.

Для «многослойных» выражений, когда две и более чёрточек находятся друг над другом, можно разделять только одну полосу за раз, и, как правило, проще начать упрощение, разрывая сначала самую длинную (самую верхнюю) полоску.

Для иллюстрации возьмём выражение «(A + (BC)')'» и сократим его, используя закон де Моргана:

Рис. 3. Упростим выражение «(A + (BC)')'» с помощью закона де Моргана.

Следуя совету сначала рвать самую длинную (самую верхнюю) черту, начнём с того, что разобьём черту, покрывающую всё выражение, в качестве первого шага:

Рис. 4. В 2 шага упрощаем искомое выражение.

В результате исходная схема сокращается до логического элемента И с тремя входами, один из которых (A) инвертирован:

Рис. 5. Исходная схема сокращена до логического элемента И с тремя входами (вход A инвертирован).

Никогда не следует разбивать более одной чёрточки за один шаг, как показано здесь:

Рис. 6. Если одновременно разбивать более одной черты в выражении, то, скорее всего, это приведёт к ошибочному результату.

Как бы ни хотелось сэкономить шаги и разломать более одной планки за раз, это часто приводит к неверному результату, так что не делайте так!

Чтобы правильно упростить это выражение, сначала лучше разобраться с короткой чёрточкой, а не длинной:

Рис. 7. В данном примере удобнее начать с короткой черты для части выражения, а не с той, что над всем выражением.

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

Обратите внимание, как на третьем этапе мы сломали длинную черту сразу в двух местах.

Вот уже здесь всё сделано математически правильно, в отличие от того, как мы разрывали одновременно две черты за один присест!

Запрещено разрывать более чем одну черту за один шаг, а вот разрывать одну черту сразу в нескольких местах можно, иногда это кратчайший путь к верному результату.

Разрыв черты в более чем в одном месте за один шаг – это нормально; разрыв более чем одной черты за один шаг – недопустимо.

Вам, должно быть, интересно, почему круглые скобки были заключены в подвыражение B'+ C', учитывая тот факт, что я просто удалил их на следующем шаге.

Я сделал это, чтобы подчеркнуть важный (и в то же время часто упускаемый из виду) аспект правила де Моргана.

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

В данном примере это непринципиально, можно было и не ставить скобки после того, как была разорвана короткая чёрточка, но бывают случаи, когда это важно.

Рассмотрим такой пример:

Рис. 8. В этом примере показано, как может возникнуть ошибка, если пренебречь группировкой после разрыва чёрточки.

Как видите, сохранение группировки, подразумеваемой верхними полосками дополнения для этого выражения, имеет решающее значение для получения правильного ответа. Применим закон де Моргана при упрощении такой вентильной схемы:

Рис. 9. Упростим данную схему, используя закон де Моргана.

Как обычно, стоит начать с создания эквивалентного логического выражения.

Мы можем сделать это, подписав подвыражения на выходе каждого элемента, когда входные данные станут известны. Вот первый шаг в этом процессе:

Рис. 10. Подпишем выходы элементов, которые первыми принимают входные данные.

Затем мы можем пометить выходы первого логического элемента ИЛИ-НЕ и И-НЕ.

Имея дело с вентилями с инвертированным выходом, проще написать выражение для выхода вентилей, как будто бы нет инверсии, указав стрелкой, прямо перед «пузырьком», означающим инверсию.

Затем на проводе, ведущем из вентиля (после «пузырька»), написать полное дополненное выражение.

Это страхует от того, что не забыть дополняющую черту в подвыражении, ибо задача разделена на два этапа:

Рис. 11. До «пузырька» инверсии (результат со стрелкой) подписано, будто бы инверсии нет. После «пузырька» указан выход вентиля с учётом инверсии.

И наконец, пишем выражение (или выражение и его дополнение, если там есть инвертор) для последнего элемента ИЛИ-НЕ:

Рис. 12. Последний вентиль инвертирован, так что и для него пишем выражение без учёта инверсии (со стрелкой) и с учётом инверсии.

Теперь сокращаем это последнее выражение, используя тождества, свойства, правила и теоремы (в том числе закон де Моргана) булевой алгебры:

Рис. 13. Упрощаем, используя методы булевой алгебры.

Эквивалентная вентильная схема для этого значительно упрощённого выражения:

Рис. 14. Итоговая упрощённая вентильная схема.

Итог

• Законы де Моргана описывают эквивалентность вентилей с инвертированными входами и вентилей с инвертированными выходами. Проще говоря, вентиль И-НЕ эквивалентен вентилю «Отрицательное ИЛИ», а вентиль ИЛИ-НЕ эквивалентен вентилю «Отрицательное И».
• При «разрыве» чёрточки дополнения в логическом выражении операция непосредственно под разрывом (сложение или умножение) меняется на противоположную, и части разорванной полоски остаются над соответствующими членами выражения.
• Зачастую проще начать, разорвав самую длинную (самую верхнюю) черту, прежде чем разламывать какие-либо черты под ней. Никогда не пытайтесь разорвать две черты за один шаг!
• Чёрточки дополнения функционируют как группирующие символы. Следовательно, когда черта разорвана, величины под ней должны оставаться сгруппированными. Эти сгруппированные величины можно заключить в круглые скобки, чтобы не потерять правильный приоритет в выполнении операций.