Булевых Функции Минимизация

Представление булевых функций нормальными формами (см. Булевых функций нормальные формы). простейшими относительно нек-рой меры сложности. Обычно под сложностью нормальной формы понимается число букв в ней. В этом случае простейшая форма наз. минимальной. Иногда в качестве меры сложности рассматривается число элементарных конъюнкций в дизъюнктивной нормальной форме или число сомножителей в конъюнктивной нормальной форме. В этом случае простейшая форма наз. кратчайшей. В силу двойственности дизъюнктивных и конъюнктивных нормальных форм достаточно рассматривать только дизъюнктивные нормальные формы (д. н. ф.). Построение кратчайших и минимальных д. н. ф. имеет каждое свою специфику. Множества минимальных и кратчайших д. н. ф. одной и той же функции могут находиться в любых теоретико-множественных соотношениях: содержаться одно в другом, иметь пустое пересечение или непустую симметрическую разность. Если для функции f обозначить через сложность минимальной д. н. ф., через — минимальную сложность кратчайшей д. н. ф., а через — наибольшее из отношений по всем функциям от ппеременных, то справедливо асимптотич. соотношение: . Обычно под задачей Б. ф. м. понимается задача построения их минимальных д. н. ф. Существует тривиальный алгоритм построения всех минимальных д. н. ф. для произвольной булевой функции Он состоит в просмотре всех д. н. ф. с переменными и выделении тех из них, к-рые реализуют функцию f и имеют минимальную сложность. Этот алгоритм фактически неприменим уже при небольших пввиду быстрого роста числа операций. Поэтому было построено большое число других алгоритмов, к-рые, однако, эффективно применимы не ко всем функциям. Исходным заданием функции в задаче минимизаций обычно считают таблицу, совершенную д. н. ф. (см. Бyлевых функций нормальные формы).или произвольную д. н. ф. На первом этапе от исходного задания осуществляется переход к так наз. сокращенной д. н. ф., к-рая определена для каждой функции однозначно. Существует большое число методов реализации этого перехода. Наиболее универсальный метод состоит в выполнении над д. н. ф. преобразований вида Сокращенная д. н. ф. обладает тем свойством, что любая минимальная д. н. ф. получается из нее удалением нек-рых элементарных конъюнкций. Второй, наиболее трудоемкий, этап состоит в получении из сокращенной д. н. ф. всех тупиковых д. н. ф., среди к-рых содержатся и все минимальные. На этом этапе обычно используется геометрич. представление булевых функций. Пусть Е п обозначает множество всех вершин n-мерного единичного куба. Каждой булевой функции взаимно однозначно соответствует подмножество N^ , таких вершин где Пусть — элементарная конъюнкция ранга r, тогда множество наз. интервалом ранга r, соответствующим элементарной конъюнкции Говорят, что система интервалов образует покрытие множества , если Так как равенства эквивалентны, то задача Б. ф. м. равносильна отысканию покрытий, сумма рангов интервалов к-рых минимальна. Такие покрытия наз. минимальными. Интервал наз. максимальным для функции f, если и не существует интервала такого, что . Построение тупиковых д. н. ф. функции f сводится к отысканию таких покрытий множества максимальными интервалами, никакое собственное подмножество к-рых не является покрытием множества . Эти покрытия соответствуют тупиковым д. н. ф. к наз. неприводимыми. Они получаются из покрытий, соответствующих сокращенным д. н. ф., путем удаления нек-рых интервалов. Выбор минимальных д. н. ф. из всех тупиковых также оказывается весьма трудоемким процессом, поскольку для "почти всех" булевых функций от паргументов различных тупиковых д. н. ф. не меньше, чем . При этом разброс сложностей тупиковых д. н. ф. может быть очень велик, так что выбор случайной тупиковой д. н. ф. вместо минимальной может привести к большой погрешности. Оценки числа тупиковых д. н. ф. и разброса сложностей показывают, что естестве. До применения А-алгоритма все конъюнкции из рассматриваемой д. н. ф. имеют отметку (). Если выполнены шагов и отметку () получили конъюнкции а отметку () — конъюнкции , то -и шаг состоит в следующем. Упорядочивают нек-рым способом конъюнкции из д. н. ф. Если д. н.. ф. пустая, то А- алгоритм заканчивает свою работу. В противном случае после упорядочивания к.-л. способом конъюнкций из этой д. н. ф. выделяются первая по порядку конъюнкция и ее окрестности и в д. н. ф. и проверяется соотношение Если оно выполнено, то отметка над заменяется на и — й шаг А-алгоритма заканчивается. Если оно не выполнено, то проверяется, можно ли представить в виде — множество, регулярное относительно (), а — множество первого типа относительно (). Если можно представить в таком виде, то отметка () над заменяется на отметку (), и ( )-й шаг А-алгоритма заканчивается; если — нельзя, то описанная процедура применяется ко второй по порядку конъюнкции, и т. д. Если при этом ни у одной из конъюнкций отметка не изменится, то после просмотра всех конъюнкций работа А-алгоритма заканчивается. Если за д. н. ф. принять сокращенную д. н. ф. функции , то все конъюнкции, получившие в алгоритме отметку (), не входят ли в одну минимальную д. н. ф. функции f; они удаляются из . Конъюнкции, получившие отметку (), входят во все минимальные д. н. ф. функции f. Рассматривались также различные частные случаи А-алгоритма. Кольцевой алгоритм расставляет над конъюнкциями информационные отметки ( ), значение к-рых то же, что и в А-алгоритме. На каждом шаге кольцевой алгоритм использует конъюнкции, входящие в окрестность k-ro порядка нек-рой конъюнкции, и их информационные отметки. Ниже излагается упрощенный вариант этого алгоритма. В полном виде коль-.цевой алгоритм — наилучший в классе локальных алгоритмов со специальной памятью по окрестностям . Описанные выше алгоритмы являются частными случаями общего кольцевого алгоритма. Если то каждому подмножеству сопоставляется не всюду определенная булева функция множество единиц к-рой есть , а множество нулей есть ; на множестве функция не определена. Множество таких функций обозначается через . До начала работы алгоритма все конъюнкции из рассматриваемой д. н. ф. имеют отметку (). Если выполнены i шагов и отметку () получили конъюнкции а отметку () — конъюнкции то -и шаг состоит в следующем. Упорядочивают нек-рым способом конъюнкции из д. н. ф. Если д. н. ф. пустая, то алгоритм заканчивает свою работу. В противном случае после упорядочения к.-л. способом всех конъюнкций этой д. в. ф. для конъюнкции , являющейся первой из них, и для каждой функции f из множества находятся все д. н. ф., реализующие f на ее области определения, к-рые составлены из конъюнкций окрестности и содержат по сравнению с другими такими д. н. ф. наименьшее число символов переменных. Среди них выделяются все те д. н. ф., к-рые, во-первых, не содержат конъюнкций и, во-вторых, содержат все конъюнкции удовлетворяющие условию Если для всех из конъюнкция входит во все выделенные д. н. ф., то отметка () над заменяется на отметку -и шаг алгоритма заканчивается. Если не входит ни в одну из выделенных д. н. ф., то отметка заменяется на отметку и -и шаг алгоритма заканчивается. В остальных случаях описанная процедура применяется ко второй по порядку конъюнкции и т. д. Если ни у одной из конъюнкций не удается изменить отметку, то на -м шаге работа алгоритма заканчивается. Все конъюнкции, получившие в кольцевом алгоритме над сокращенной д. н. ф. функции отметки (соответственно ), входят во все минимальные д. н. ф. (соответственно не входят ни в одну минимальную д. н. ф.) функции f. Результат применения описанных выше алгоритмов не зависит от способа упорядочения конъюнкций в д. н. ф. Задача выделения всех конъюнкций, входящих хотя бы в одну и не входящих ни в одну минимальную д. н. ф., не может быть решена алгоритмами, работающими с при k, ограниченных пли недостаточно быстро растущих с ростом пчисла переменных. Ситуация не изменится, если к запоминаемым в алгоритме свойствам P1 , Р 2 добавить ограниченное или недостаточно быстро растущее с ростом пмножество свойств. Лит.:[1] Яблонский С. В., Функциональные построения в k-значной логике, 1958 ("Тр. Матем. ин-та АН СССР", т. 51); [2] Журавлев Ю. И., "Проблемы кибернетики", 1962, в. 8, с. 5-44; [3] Quine W. V., "Amer. Math. Monthly", 1959, т. 66, № 9, p. 755-60. Ю. И. Журавлев.