Булевых Функции Метрическая Теория

Направление, связанное с изучением числовых характеристик и метрич. свойств булевых функций. Основные разделы этой теории посвящены исследованию свойств "почти всех" булевых функций (см. Булевых функций минимизация), свойств совокупности всех булевых функций данного числа переменных и специальных подклассов булевых функций. Кроме того, изучается строение областей истинности булевых функций с помощью числовых характеристик, появившихся в основном в задачах, связанных с минимизацией булевых функций и теорией локальных алгоритмов. Этими характеристиками являются размерность и протяженность функции. Пусть — множество вершин единичного и-мерного куба, на к-рых функция равна единице. Рассмотрим все максимальные интервалы функции и выделим среди них интервал наибольшей размерности r. Величина rназ. размерностью функции и обозначается через . С помощью размерности оцениваются отношения сложностей самой сложной тупиковой и кратчайшей дизъюнктивных нормальных форм (д. н. ф.) функции: f (см. Булевых функций нормальные формы). Сверху это отношение оценивается величиной В то же время для "почти всех" булевых функций имеет место неравенство При решении задачи минимизации булевых функций представляет интерес вычисление размерности "типичных" максимальных интервалов. Доказано, что "почти все" максимальные интервалы "почти всех" булевых функций имеют размерность, близкую к Пусть — главная окрестность k-го порядка (см. Алгоритм локальный).элементарной конъюнкции , входящей в сокращенную д. н. ф. функции , и — минимальное значение порядка окрестности, при к-ром включает в себя все элементарные конъюнкции, входящие в сокращенную д. н. ф. . Величина наз. протяженностью функции f. Для "почти всех" булевых функций Пусть Известно, что величина реализуется на булевой функции специального вида, называемой цепью. Функция наз. цепью, если множество единиц этой функции можно представить в виде последовательности такой, что , где — расстояние Хемминга (см. Код);расстояние между другими парами (может быть, за исключением пары ) больше единицы, и в множестве единиц функции не содержится целиком ни один интервал размерности 2. Протяженность цепи равна Поэтому задача вычисления сводится к построению в n-мерном единичном кубе цепи с максимальным q. Прямым построением таких цепей доказано, что где — константы. Построение замкнутых цепей (циклов), т. е. цепей, у к-рых , с максимальной мощностью множества является важной составной частью доказательства теоремы о невычислимости свойств конъюнкций "входить в минимальные или кратчайшие д. н. ф." в классе локальных алгоритмов. Следующий результат выясняет строение областей истинности "почти всех" булевых функций. Множество М вершин n-мерного единичного куба наз. связным, если для всякой точки существует точка из Мтакая, что Точка в множестве Мназ. изолированной, если для всех таких, что , выполнено условие: . Имеет место следующее утверждение: у "почти всех" булевых функций множество единиц разбивается на сумму одного связного множества и нек-рого множества изолированных точек. При этом мощность связного множества не меньше — , а число изолированных точек не превосходит . С результатами по вычислению протяженности "почти всех" булевых функций тесно связаны результаты по вычислению радиусов и диаметров графов, порождаемых булевыми функциями. Графом , порожденным булевой функцией f, наз. граф, вершинами к-рого являются точки множества- , а ребрами — пары точек множества , расстояние Хэмминга между к-рыми равно единице. Расстояние между вершинами графа определяется как длина минимальной цепи, связывающей и (предполагается, что вершины принадлежат одной компоненте связности графа ). Отклоненное т ь ю вершины в графе наз. величина , где максимум берется по всем вершпнам G, принадлежащим вместе сак одной компоненте связности. Радиус о.