БУЛЕВЫХ ФУНКЦИИ МЕТРИЧЕСКАЯ ТЕОРИЯ

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

Пусть - множество вершин единичного и-мерного куба, на к-рых функция равна единице. Рассмотрим все максимальные интервалы функции и выделим среди них интервал наибольшей размерности r. Величина rназ. размерностью функции и обозначается через . С помощью размерности оцениваются отношения сложностей самой сложной тупиковой и кратчайшей дизъюнктивных нормальных форм (д. н. ф.) функции: f (см. Булевых функций нормальные формы). Сверху это отношение оценивается величиной В то же время для "почти всех" булевых функций имеет место неравенство

При решении задачи минимизации булевых функций представляет интерес вычисление размерности "типичных" максимальных интервалов. Доказано, что "почти все" максимальные интервалы "почти всех" булевых функций имеют размерность, близкую к

Пусть - главная окрестность k-го порядка (см. Алгоритм локальный).элементарной конъюнкции , входящей в сокращенную д. н. ф. функции , и - минимальное значение порядка окрестности, при к-ром включает в себя все элементарные конъюнкции, входящие в сокращенную д. н. ф. . Величина

наз. протяженностью функции f. Для "почти всех" булевых функций

Пусть

Известно, что величина реализуется на булевой функции специального вида, называемой цепью. Функция наз. цепью, если множество единиц этой функции можно представить в виде последовательности такой, что , где - расстояние Хемминга (см. Код);расстояние между другими парами (может быть, за исключением пары ) больше единицы, и в множестве единиц функции не содержится целиком ни один интервал размерности 2. Протяженность цепи равна Поэтому задача вычисления сводится к построению в n-мерном единичном кубе цепи с максимальным q. Прямым построением таких цепей доказано, что

где - константы. Построение замкнутых цепей (циклов), т. е. цепей, у к-рых , с максимальной мощностью множества является важной составной частью доказательства теоремы о невычислимости свойств конъюнкций "входить в минимальные или кратчайшие д. н. ф." в классе локальных алгоритмов.

Следующий результат выясняет строение областей истинности "почти всех" булевых функций. Множество М вершин n-мерного единичного куба наз. связным, если для всякой точки существует точка из Мтакая, что Точка в множестве Мназ. изолированной, если для всех таких, что , выполнено условие: . Имеет место следующее утверждение: у "почти всех" булевых функций множество единиц разбивается на сумму одного связного множества и нек-рого множества изолированных точек. При этом мощность связного множества не меньше - , а число изолированных точек не превосходит .

С результатами по вычислению протяженности "почти всех" булевых функций тесно связаны результаты по вычислению радиусов и диаметров графов, порождаемых булевыми функциями. Графом , порожденным булевой функцией f, наз. граф, вершинами к-рого являются точки множества- , а ребрами - пары точек множества , расстояние Хэмминга между к-рыми равно единице. Расстояние между вершинами графа определяется как длина минимальной цепи, связывающей и (предполагается, что вершины принадлежат одной компоненте связности графа ). Отклоненное т ь ю вершины в графе наз. величина , где максимум берется по всем вершпнам G, принадлежащим вместе сак одной компоненте связности. Радиус о. <м компоненты связности Кграфа Gназ. число . Величина , где максимум берется по всем компонентам связности графа G, наз. радиусом графа G. Диаметром графа Gназ. число , где максимум берется по всем парам вершин принадлежащим одной компоненте связности. Для "почти всех" булевых функций величины и таковы, что и . Из результатов, относящихся к вычислению числовых характеристик отдельных классов булевых функций, выделяются результаты, относящиеся к монотонным булевым функциям. Пусть , - бинарные наборы. Говорят, что , если . Булева функция наз. монотонной, если из соотношения следует, что . Представляет интерес определение точного числа различных монотонных булевых функций от переменных . Это число известно лишь для небольших значений п. Известно также асимптотич. равенство

Большое число приложений при решении дискретных экстремальных задач имеет задача оптимальной расшифровки монотонной булевой функции. Пусть задан алгоритм А, позволяющий вычислять монотонную булеву функцию в каждой точке Если в процессе вычислений установлено, что для нек-рой точки для всех . При функция известна (равна нулю) во всех точках . Поэтому для расшифровки, т. е. полного восстановления функции , алгоритм Адолжен вычислить ее значения лишь в нек-ром множестве точек. Пусть обозначает минимальное число точек, в к-рых достаточно вычислить для полного восстановления f. Пусть

Величина удовлетворяет асимптотич. равенству:

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

С задачей расшифровки монотонных булевых функций связана задача вычисления числовых характеристик совокупностей существенных переменных не всюду определенных булевых функций, т. е. функций, заданных на нек-ром подмножестве множества вершин единичного n-мерного куба. Совокупность переменных наз. существенной для не всюду определенной булевой функции , если и существует не всюду определенная булева функция такая, что на всей области определения F. Существенная совокупность наз. тупиковой для F, если никакая истинная часть этой совокупности не является существенной для F.

У каждой всюду определенной булевой функции имеется единственная тупиковая совокупность переменных. Для не всюду определенных булевых функций строение совокупностей существенных переменных отличается большим разнообразием. Пусть - система подмножеств множества , удовлетворяющая условию: если и - произвольное подмножество множества . Тогда существует не всюду определенная булева функция такая, что система существенных для наборов переменных есть . Пусть - число различных тупиковых наборов для и

Известно, что

Алгоритм построения всех тупиковых совокупностей переменных для имеет максимальную трудоемкость , причем этот максимум достигается (здесь единицей трудоемкости считается трудоемкость проверки, является ли данная совокупность переменных существенной для F).

К Б. ф. м. т. относят также задачи вычисления характеристик, связанных с задачей минимизации булевых функций.

Лит.:[1] Глаголев В. В., "Проблемы кибернетики", 1967, в. 19, с. 75-94; [2] Журавлев Ю. И., "Проблемы кибернетики", 1964, в. 11, с. 271-75; [3] Коробков В. К., "Проблемы кибернетики", 1965, в. 13, с. 5-28; [4] Сапоженко А. А., сб. "Дискретный анализ", 1967, в. 10, с. 91 - 119; [5]его же, "Докл. АН СССР", 1968, т. 180, № 1, с. 32-35; [6] Kleitman D., "Proc. Amer. Math. Soc.", 1969, v. 21, № 3, p. 677-82. _ Ю. И. Журавлев.