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

Точное решение задачи минимизации предполагает нахождение минимальной ДНФ (КНФ) логической функции. Решение этой задачи осуществляется в три этапа.

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

На втором этапе определяются все приведенные системы простых импликант (имплицент) и строятся тупиковые ДНФ (КНФ) логической функции.

На третьем этапе из числа полученных тупиковых ДНФ (КНФ) логической функции выбираются минимальные ДНФ (КНФ).

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

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

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

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