2-6. АБСОЛЮТНО МИНИМАЛЬНЫЕ ПРЕДСТАВЛЕНИЯ

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

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

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

Отметим прежде всего, что МДНФ зачастую не дает абсолютно минимального выражения.

Пример 2-11. Для функции

в примере 2-8 была найдена следующая МДНФ по методу Квайна:

Если же произвести вынесение за скобки, то

При этом полученное выражение содержит три буквы вместо четырех и, следовательно, является более простым, чем МДНФ этой функции.

Встает вопрос, не являются ли абсолютно минимальными выражения, которые получают из МДНФ путем всевозможных вынесений за скобки и выбором наиболее простого выражения из этих скобочных форм. В 1952 г. Беркхарт (Burkhart) дал отрицательный ответ на поставленный вопрос. Он показал, что существуют такие абсолютно минимальные выражения, которые не могут быть получены за счет операции вынесения за скобки в минимальной ДНФ или КНФ. Абхъянкаром был дан алгоритм непосредственного нахождения абсолютно минимальных выражений для данной функции алгебры логики. Однако этот алгоритм практически неприменим

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

при мы имеем:

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