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

Как упростить логическое выражение?

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

Содержание

Логическое выражение упрощают так же, как алгебраическое, только по правилам булевой алгебры. У Kuphaldt в главе «Boolean Algebra» к обычным тождествам — A + 0 = A, A + 1 = 1, A · A' = 0, A + A' = 1 — добавлены три правила, которые делают основную работу:

ПравилоКак получается
A + AB = Aвынести A: A(1 + B) = A · 1
A + A'B = A + Bзаменить A на A + AB и вынести B: A + B(A + A')
(A + B)(A + C) = A + BCраскрыть скобки и применить первое правило

Буква в правиле означает любую переменную или группу: ABC + 1 тоже равно 1.

Пример по шагам

Упростим F = AB + AB' + A'B.

F=A(B+B′)+A′Bвынесли A=A+A′BB+B′=1=A+Bправило A+A′B=A+B\begin{aligned} F &= A(B + B') + A'B &&\text{вынесли } A\\ &= A + A'B &&B + B' = 1\\ &= A + B &&\text{правило } A + A'B = A + B \end{aligned}

Три элемента И, инверторы и элемент ИЛИ на три входа свелись к одному элементу ИЛИ.

Проверка таблицей

ABAB + AB' + A'BA + B
0000
0111
1011
1111

Столбцы совпали во всех четырёх строках — выражения равны. Для любой функции такую таблицу строит калькулятор таблиц истинности.

Порядок действий

  1. Если над группой стоит длинная черта, раскрыть её законами де Моргана — по одной черте, начиная с самой длинной.
  2. Раскрыть скобки и выписать сумму произведений.
  3. Выносить общие множители и сокращать по правилам из таблицы.
  4. Проверить результат таблицей истинности.

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

Похожие вопросы

Как понять, что выражение уже минимальное?

Алгеброй это доказать трудно: может не хватить «обратного» шага, который видно только с опытом. Надёжный признак — карта Карно: если все единицы покрыты наибольшими возможными группами и их наименьшим числом, ДНФ минимальна.

Можно ли упрощать выражение с XOR теми же правилами?

Не напрямую: Kuphaldt отмечает, что тождества сложения, умножения и инверсии к знаку XOR не применяются. Сначала XOR раскрывают как AB' + A'B, упрощают, а в конце сворачивают обратно, если снова получилась эта форма.

Что делать, если в задаче четыре и больше переменных?

Для четырёх переменных — карта Карно 4 × 4, для пяти-шести — составная карта из двух или четырёх таких. По Kuphaldt, карты пригодны до восьми переменных, а дальше упрощение отдают программам. Проверить ответ можно в симуляторе, сравнив таблицы истинности исходной и упрощённой схем.

Источники

  1. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 7 «Boolean Algebra» (CC BY) — разд. «Boolean rules for simplification»: A + AB = A (вынести A, затем B + 1 = 1), A + A'B = A + B (доказывается обратным шагом A → A + AB), (A + B)(A + C) = A + BC; буква в правиле обозначает любую переменную или группу переменных; разд. «DeMorgan's Theorems»: длинную черту разбивают по одной, начиная с самой длинной, операция под разрывом меняется на противоположную; разд. «Circuit simplification examples»
  2. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 8 «Karnaugh Mapping» (CC BY) — алгебра быстрее карты при двух переменных, ещё годится при трёх и становится утомительной при четырёх; карты Карно хорошо работают до шести переменных и пригодны до восьми, дальше — программы автоматизированного проектирования; разд. «Larger 5 & 6-variable Karnaugh maps»

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

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