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

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

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