Минимальные формы

Любая булева функция представима в СН(Д или К) формах. Более того, такое представление является первым шагом перехода от табличного задания функций к ее аналитическому выражению.

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

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

Такие формы называют минимальными.

Формула, представленная в ДНФ, упрощается многократным применением операции склеивания и операций поглощения и (дуальные тождества для конъюнктивной нормальной формы имеют вид:

).

Здесь под а и b можно понимать любую форму булевой алгебры.

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

Среди тупиковых форм находится и минимальная ДНФ, причем она может быть неединственной. Чтобы убедиться в том, что данная тупиковая форма — минимальная, необходимо найти все тупиковые формы и сравнить их по числу входящих в них букв.

Пусть, например, функция задана в СНДФ:

Группируя члены и применяя операцию склеивания, имеем

.

При другом способе группировки получим:

.

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

В первом случае таким членом может быть . Тогда

.

Добавляя член , получим:

.

Перебрав все возможные варианты, можно убедиться, что две последние формы минимальны.

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