Любая булева функция представима в СН(Д или К) формах. Более того, такое представление является первым шагом перехода от табличного задания функций к ее аналитическому выражению.
В дальнейшем будем исходить из дизъюнктивной формы, а соответствующие результаты для конъюнктивной формы получаются на основе принципа двойственности.
Каноническая задача синтеза логических схем в булевом базисе сводится к минимизации булевых функций, т.е. к представлению их в дизъюнктивной нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний).
Такие формы называют минимальными.
Формула, представленная в ДНФ, упрощается многократным применением операции склеивания и операций поглощения и (дуальные тождества для конъюнктивной нормальной формы имеют вид:
).
Здесь под а и b можно понимать любую форму булевой алгебры.
В результате приходим к такому аналитическому выражению, когда дальнейшие преобразования оказываются невозможными, т.е. получаем тупиковую форму.
Среди тупиковых форм находится и минимальная ДНФ, причем она может быть неединственной. Чтобы убедиться в том, что данная тупиковая форма — минимальная, необходимо найти все тупиковые формы и сравнить их по числу входящих в них букв.
Пусть, например, функция задана в СНДФ:
Группируя члены и применяя операцию склеивания, имеем
.
При другом способе группировки получим:
.
Обе тупиковые формы не являются минимальными. Чтобы получить минимальную форму, нужно догадаться повторить в исходной формуле один член (это всегда можно сделать, т.к. ).
В первом случае таким членом может быть . Тогда
.
Добавляя член , получим:
.
Перебрав все возможные варианты, можно убедиться, что две последние формы минимальны.
Работа на таком уровне подобна блужданию. Процесс поиска минимальных форм становится более наглядным и целеустремленным, если использовать графические и аналитические представления.