Математическая энциклопедия - булевых функции минимизация

представление булевых функций нормальными формами (см. Булевых функций нормальные формы). простейшими относительно нек-рой меры сложности. Обычно под сложностью нормальной формы понимается число букв в ней. В этом случае простейшая форма наз. минимальной. Иногда в качестве меры сложности рассматривается число элементарных конъюнкций в дизъюнктивной нормальной форме или число сомножителей в конъюнктивной нормальной форме. В этом случае простейшая форма наз. кратчайшей. В силу двойственности дизъюнктивных и конъюнктивных нормальных форм достаточно рассматривать только дизъюнктивные нормальные формы (д. н. ф.). Построение кратчайших и минимальных д. н. ф. имеет каждое свою специфику. Множества минимальных и кратчайших д. н. ф. одной и той же функции могут находиться в любых теоретико-множественных соотношениях: содержаться одно в другом, иметь пустое пересечение или непустую симметрическую разность. Если для функции f обозначить через сложность минимальной д. н. ф., через минимальную сложность кратчайшей д. н. ф., а через наибольшее из отношений по всем функциям от ппеременных, то справедливо асимптотич. соотношение:

.

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

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

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