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

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

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

Лит.: Яблонский С. В. Функциональные построения в -значной логике. «Труды Математического института им. В. А. Стеклова АН СССР», 1958, т. 51; Журавлев Ю. И. Теоретико-множественные методы в алгебре логики. «Проблемы кибернетики», 1962, в. 8; Журавлев Ю. Оценки сложности алгоритмов построения минимальных дизъюнктивных нормальных форм для функций алгебры логики. «Дискретный анализ», 1964, в. 3.

И. И. Бропа.