Понятие о минимизации логических функций

При построении цифровых устройств, реализующих заданные

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

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

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

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

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