Упрощение и преобразование нормальной формы ИЛИ с помощью алгебры логики

Упрощение нормальной формы ИЛИ

Нормальная форма ИЛИ воспроизводит содержание таблицы истинности в виде логического уравнения. По этому уравнению может быть синтезирована нужная схема.
По нормальной форме ИЛИ можно синтезировать схему, удовлетворяющую соответствующей таблице истинности.
Часто эта схема не является самым простым вариантом из возможных. Во многих случаях нормальные формы ИЛИ можно упростить. Это упрощение может быть выполнено с помощью алгебры логики.
Пример 1------------------------------------------------------------
Упростите нормальную форму ИЛИ Z = (А а B)v(A а В). Так как обе полные конъюнкции содержат переменную А, то она с помощью распределительного закона может быть вынесена за скобки:
Z = (AaB)v(AaB);
Z = Aa(BvB).
Выражение В v В всегда равно 1 (см. гл. 4).
Z=A л 1.
Логическое сложение переменной с 1 дает в итоге переменную. Результат упрощения нормальной формы ИЛИ:
Z = А.
Пример 2------------------------------------------------------------
Упростите следующую нормальную форму ИЛИ:
Z = (а А В aC^V {а А В aC^V {а А В aC^V {а А В А с).
© ® ® ©
Сначала упрощают полные конъюнкции © и ©. А а В рассматривается как одна переменная и выносится за скобки:
((Л л Б) л С) v л i?) л с) = (Л л 2?) л (С v С) = (Л л 2?) л 1 = (Л л 2?).
Также можно упростить полные конъюнкции (D и ©. А а В рассматривается как одна переменная и выносится за скобки:
((Л А 2?) А с) V ((Л А 5) А с) = (Л А 1?) А (С V С) = (Л А 5) А 1 = (Л А 1?).
Для Z тогда:
Z = [AaB)v{AaB).
В этом уравнении А может быть вынесена за скобки как совместная переменная:
Z = А а{В v Щ\
Z = Aa 1;
Z = А.
Достаточно сложная нормальная форма ИЛИ сильно упростилась в этом примере. Такое сильное упрощение во многих случаях невозможно. Существует много нормальных форм ИЛИ, которые не упрощаются.
Пример 3--------------------------------------------------------------
Упростите следующую нормальную форму ИЛИ:
Z - {А а В а С) v (А а В а С).
Так как обе полные конъюнкции содержат переменную, то она с помощью распределительного закона может быть вынесена за скобки:
Z = С а({АаВ)у(АаЩ.
Можно поспорить, является ли вынесение за скобку С упрощением исходного выражения. Ответ будет очевиден только при сборке схемы на реальных элементах. Существенного преимущества в любом случае не получится.

Преобразование нормальной формы ИЛИ

Схема, которая строится согласно нормальной форме ИЛИ, должна базироваться на основных логических элементах. Во многих случаях можно использовать другие элементы, например И-НЕ или ИЛИ-НЕ. Нормальная форма ИЛИ в этих случаях должна быть преобразована.
Перевести нормальную форму ИЛИ на элементы И-НЕ очень просто. Нормальная форма ИЛИ сначала подвергается двойному отрицанию. Двойное отрицание, как известно, не меняет содержание уравнения. Затем нижняя черта инверсии разделяется согласно второй теореме де Моргана.
Пример 1--------------------------------------------------------------
Z = {^А а В aC^w {А а В а С);
Z - (А а В аС^у {^А а В а С);
Z = АаВаСаАаВаС.
Получающаяся из уравнения схема представлена на рис. 5.10.

Рис. 5.10. Схема только с элементами "И-НЕ"

Если требуется преобразовать нормальную форму ИЛИ так, чтобы схема состояла только из элементов ИЛИ-НЕ, то рекомендуется дважды инвертировать каждую полную конъюнкцию и каждую нижнюю черту ин-
версии преобразовать в соответствии с первой теоремой де Моргана. Затем все выражение еще раз подвергается двойному отрицанию.
Пример 2-----------------------------------------------------------------
Z = (5a5aC)v|^a5aCJ;
Z = (А а В aC^v (А а В а С);
Z = AvBvCvAvBvC;
Z = AvBvCvAvBvC. Схема к этому уравнению изображена на рис. 5.11.

Рис. 5.11. Схема только с элементами "ИЛИ-НЕ"

Похожие статьи