ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА МИНИМАЛЬНАЯ

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

Лит.: Журавлев Ю. И. Теоретико-множественные методы в алгебре логики. «Проблемы кибернетики», 1962, в. 8; Акдон Ф. И. Алгоритм упрощения д. н. ф. булевых функций. «Кибернетика», 1966, № 6; Андон Ф. И. Минимизация д. н. ф. функций алгебры логики методом последовательного анализа вариантов. «Теория автоматов и методы формализованного синтеза вычислительных машин и систем». 1968, в. 3. И. И. Бропа.