2-2. ПОСТАНОВКА ЗАДАЧИ МИНИМИЗАЦИИ В КЛАССЕ ДНФ

В предыдущем параграфе мы наметили основные пути построения МДНФ для данной функции алгебры логики. На первом этапе однозначно по данной функции строится СДНФ, а на втором этапе, выбрасывая из СДНФ лишние максимальные интервалы, находим МДНФ. В отличие от первого этапа второй этап неоднозначен. Эта неоднозначность нахождения МДНФ определяется двумя факторами: во-первых, для данной функции может существовать несколько МДНФ; во-вторых, само выбрасывание максимальных интервалов делается на основании перебора.

Рис. 2-5.

Пример 2-5. На рис. 2-5 показано покрытие, соответствующее СДНФ для функции

На рис. 2-6,а и б показаны два возможных варианта покрытия, полученных путем выбрасывания некоторых избыточных интервалов из покрытия рис. 2-5. Эти варианты покрытия соответствуют двум возможным МДНФ для данной функции:

и

Необходимость перебора на втором этапе минимизации вызывает серьезные затруднения при автоматизации процесса нахождения МДНФ.

Рис. 2-6.

Определенные трудности вызывает и построение СДНФ.

Если к исходной ДНФ применять лишь операции склеивания (2-2) и элементарного поглощения

то наступит момент, когда эти преобразования окажутся уже невозможными. В этом случае получим тупиковую ДНФ (ТДНФ). Среди множества ТДНФ содержится и МДНФ. Получая все возможные тупиковые ДНФ для данной функции и сравнивая их по числу букв, входящих в них, можно найти все минимальные формы для данной функции. При этом встает вопрос о величине перебора при таком подходе к проблеме минимизации. Величина перебора определяется числом элементов класса тупиковых ДНФ для функции алгебры логики, зависящей от аргументов. Оценка числа тупиковых ДНФ была дана Ю. И. Журавлевым. Оказалось, что

для достаточно больших число тупиковых ДНФ оценивается как

Таким образом, уже для порядка 10—15 перебор становится весьма большим и подобный процесс нахождения МДНФ — малоэффективен.

Встает вопрос: нельзя ли ограничиться нахождением только произвольной тупиковой ДНФ? Другими словами, не является ли справедливым утверждение о том, что тупиковые ДНФ отличаются от МДНФ на небольшое число букв. Как показал . Васильев, это утверждение несправедливо.

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

Ввиду трудностей, связанных с задачей нахождения минимальных ДНФ, можно попытаться провести приближенную минимизацию не по числу букв, входящих в ДНФ, а по ее длине. Такая постановка задачи приводит к проблеме нахождения не МДНФ, а КДНФ. Алгоритм нахождения кратчайшей ДНФ для данной функции был построен Е. К. Войшвилло. Однако, как показал Ю. И. Журавлев, среди КДНФ может и не содержаться минимальных ДНФ и для достаточно больших существуют такие функции алгебры логики, для которых кратчайшая ДНФ содержит на букв больше, чем МДНФ, построенная для той же функции. А. Д. Коршуновым был получен еще более неприятный для практики результат. Оказалось, что для почти всех функций кратчайшие ДНФ и тупиковые ДНФ не совпадают. Если для достаточно больших наугад построить ТДНФ, то с вероятностью, близкой к единице, она не будет кратчайшей ДНФ.

Трудности, связанные с проблемой минимизации, хорошо видны при формулировании проблемы минимизации в виде задачи целочисленного лннейного программирования. Сведение задачи минимизации к задаче

целочисленного линейного программирования было осуществлено Т. Л. Майстровой. Покажем, как осуществляется это сведение.

Пусть для функции СДНФ имеет вид:

Здесь соответствуют конъюнкциям, входящим в СДНФ данной функции, а индекс означает некоторую нумерацию этих конъюнкций. Пусть теперь

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

Определение 2-12. Вектор координаты которого определены с помощью соотношения следующего вида:

называется соответствующим для ДНФ F.

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

Таким образом,

Здесь — множество индексов элементарных конъюнкций образующих конъюнкцию

Сопоставим теперь СДНФ и ДСНФ данной функции алгебраические суммы

где буквы, сопоставленные соответствующим конъюнкциям , а - некоторые числовые коэффициенты.

Поставим теперь в сумму, сопоставляемую вместо на основании Получим:

или после очевидных преобразований

Здесь соответствует множеству индексов таких, что после преобразования являются коэффициентами при

Из этих преобразований вытекает, что к к

Это равенство возможно, если все коэффициенты справа и слева соответственно равны между собой, т. е.

Теорема 2-4. Координаты соответствующего вектора для удовлетворяют системе неравенств

Множество индексов определяет соответствующее множество различных

Справедливость теоремы следует из того, что для каждого номера уравнения существует по крайней

мере одно в противном случае не была бы эквивалентной

Теорема 2-5. Если координаты вектора принимают значения 0 или 1 и удовлетворяют (2-9), то этому вектору соответствует члены которой определяются на основании (2-5), эквивалентная функции

Доказательство очевидно.

Теоремы 2-4 и 2-5 устанавливают соответствие между ДНФ, эквивалентными данной функции, и системой неравенств (2-9).

Теперь можно сформулировать задачу о нахождении КДНФ или МДНФ для данной функции алгебры логики в виде следующих задач линейного программирования:

Задача нахождения КДНФ. Найти минимум

при условии, что

и

Задачи нахождения МДНФ. Найти минимум

при условии, что

где — число букв в конъюнкции

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

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

В последующих параграфах рассмотрим несколько методов, пригодных для нахождения МДНФ.