Компьютеры
и программирование

Минимизация логических функций методом непосредственных преобразований

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

Caliber [DOI] RU+CIS

Минимизацию обычно проводят в такой последовательности (описывается только процесс минимизации СДНФ, поскольку минимизация СКНФ производится по аналогичной схеме). Сначала ищутся пары минтермов, отличающихся друг от друга только знаком инверсии и лишь в одном из аргументов. Такие минтермы склеиваются. В результате склеивания из двух минтермов образуется импликанта, ранг которой на единицу меньше, чем у склеиваемых минтермов:

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

Далее предпринимается попытка исключить из сокращённой ДНФ избыточные простые импликанты, используя для этого прочие правила булевой алгебры, например, теоремы противоречия, "исключённого третьего", закон поглощения и др. В зависимости от применяемых правил и порядка их использования может получиться несколько вариантов нормальных форм, в которых ни одну из входящих в них простых импликант уже нельзя исключить. Это так называемые тупиковые ДНФ.

Наконец, из тупиковых форм выбирается та, которая имеет наименьший коэффициент сложности (содержит минимальное суммарное количество букв и термов). Это и будет минимальная дизъюнктивная нормальная форма. Если минимальный коэффициент сложности одновременно имеет несколько тупиковых форм, то имеют место и несколько МДНФ.

Пример. Функция трёх аргументов f задана таблицей истинности:

x1x2x3f
0001
0011
0101
0111
1000
1010
1100
1110

Полученное выражение является минимальной дизъюнктивной нормальной формой.

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

10. .