Булевых функции метрическая теория

направление, связанное с изучением числовых характеристик и метрич. свойств булевых функций. Основные разделы этой теории посвящены исследованию свойств "почти всех" булевых функций (см. Булевых функций минимизация), свойств совокупности всех булевых функций данного числа переменных и специальных подклассов булевых функций. Кроме того, изучается строение областей истинности булевых функций с помощью числовых характеристик, появившихся в основном в задачах, связанных с минимизацией булевых функций и теорией локальных алгоритмов. Этими характеристиками являются размерность и протяженность функции. Пусть [img: http://localhost:8080/file/010219-121.jpg] - множество вершин единичного и-мерного куба, на к-рых функция [img: http://localhost:8080/file/010219-122.jpg] равна единице. Рассмотрим все максимальные интервалы функции [img: http://localhost:8080/file/010219-123.jpg] и выделим среди них интервал наибольшей размерности r. Величина rназ. размерностью функции [img: http://localhost:8080/file/010219-124.jpg] и обозначается через [img: http://localhost:8080/file/010219-125.jpg]. С помощью размерности оцениваются отношения сложностей самой сложной тупиковой и кратчайшей дизъюнктивных нормальных форм (д. н. ф.) функции: f (см. Булевых функций нормальные формы). Сверху это отношение оценивается величиной [img: http://localhost:8080/file/010219-126.jpg] В то же время для "почти всех" булевых функций имеет место неравенство [img: http://localhost:8080/file/010219-127.jpg] При решении задачи минимизации булевых функций представляет интерес вычисление размерности "типичных" максимальных интервалов. Доказано, что "почти все" максимальные интервалы "почти всех" булевых функций [img: http://localhost:8080/file/010219-129.jpg] имеют размерность, близкую к [img: http://localhost:8080/file/010219-128.jpg] Пусть [img: http://localhost:8080/file/010219-130.jpg] - главная окрестность k-го порядка (см. Алгоритм локальный).элементарной конъюнкции [img: http://localhost:8080/file/010219-131.jpg], входящей в сокращенную д. н. ф. [img: http://localhost:8080/file/010219-132.jpg] функции [img: http://localhost:8080/file/010219-133.jpg], и [img: http://localhost:8080/file/010219-134.jpg] - минимальное значение порядка окрестности, при к-ром [img: http://localhost:8080/file/010219-135.jpg] включает в себя все элементарные конъюнкции, входящие в сокращенную д. н. ф. [img: http://localhost:8080/file/010219-136.jpg]. Величина [img: http://localhost:8080/file/010219-137.jpg] наз. протяженностью функции f. Для "почти всех" булевых функций [img: http://localhost:8080/file/010219-138.jpg] Пусть [img: http://localhost:8080/file/010219-139.jpg] Известно, что величина [img: http://localhost:8080/file/010219-140.jpg] реализуется на булевой функции специального вида, называемой цепью. Функция [img: http://localhost:8080/file/010219-141.jpg] наз. цепью, если множество [img: http://localhost:8080/file/010219-142.jpg] единиц этой функции можно представить в виде последовательности [img: http://localhost:8080/file/010219-143.jpg] такой, что [img: http://localhost:8080/file/010219-144.jpg], где [img: http://localhost:8080/file/010219-145.jpg] - расстояние Хемминга (см. Код);расстояние между другими парами [img: http://localhost:8080/file/010219-146.jpg] (может быть, за исключением пары [img: http://localhost:8080/file/010219-147.jpg]) больше единицы, и в множестве единиц функции [img: http://localhost:8080/file/010219-148.jpg] не содержится целиком ни один интервал размерности 2. Протяженность цепи [img: http://localhost:8080/file/010219-149.jpg] равна [img: http://localhost:8080/file/010219-150.jpg] Поэтому задача вычисления [img: http://localhost:8080/file/010219-151.jpg] сводится к построению в n-мерном единичном кубе цепи с максимальным q. Прямым построением таких цепей доказано, что [img: http://localhost:8080/file/010219-152.jpg] где [img: http://localhost:8080/file/010219-153.jpg] - константы. Построение замкнутых цепей (циклов), т. е. цепей, у к-рых [img: http://localhost:8080/file/010219-154.jpg], с максимальной мощностью множества [img: http://localhost:8080/file/010219-155.jpg] является важной составной частью доказательства теоремы о невычислимости свойств конъюнкций "входить в минимальные или кратчайшие д. н. ф." в классе локальных алгоритмов. Следующий результат выясняет строение областей истинности "почти всех" булевых функций. Множество М вершин n-мерного единичного куба наз. связным, если для всякой точки [img: http://localhost:8080/file/010219-156.jpg] существует точка [img: http://localhost:8080/file/010219-157.jpg] из Мтакая, что [img: http://localhost:8080/file/010219-158.jpg] Точка [img: http://localhost:8080/file/010219-159.jpg] в множестве Мназ. изолированной, если для всех [img: http://localhost:8080/file/010219-160.jpg] таких, что [img: http://localhost:8080/file/010219-161.jpg], выполнено условие: [img: http://localhost:8080/file/010219-162.jpg]. Имеет место следующее утверждение: у "почти всех" булевых функций [img: http://localhost:8080/file/010219-163.jpg] множество единиц [img: http://localhost:8080/file/010219-164.jpg] разбивается на сумму одного связного множества и нек-рого множества изолированных точек. При этом мощность связного множества не меньше [img: http://localhost:8080/file/010219-165.jpg] - [img: http://localhost:8080/file/010219-166.jpg], а число изолированных точек не превосходит [img: http://localhost:8080/file/010219-167.jpg]. С результатами по вычислению протяженности "почти всех" булевых функций тесно связаны результаты по вычислению радиусов и диаметров графов, порождаемых булевыми функциями. Графом [img: http://localhost:8080/file/010219-168.jpg], порожденным булевой функцией f, наз. граф, вершинами к-рого являются точки множества- [img: http://localhost:8080/file/010219-169.jpg], а ребрами - пары точек множества [img: http://localhost:8080/file/010219-170.jpg], расстояние Хэмминга между к-рыми равно единице. Расстояние [img: http://localhost:8080/file/010219-171.jpg] между вершинами [img: http://localhost:8080/file/010219-172.jpg] графа [img: http://localhost:8080/file/010219-173.jpg] определяется как длина минимальной цепи, связывающей [img: http://localhost:8080/file/010219-174.jpg] и [img: http://localhost:8080/file/010219-175.jpg] (предполагается, что вершины [img: http://localhost:8080/file/010219-176.jpg] принадлежат одной компоненте связности графа [img: http://localhost:8080/file/010219-177.jpg]). Отклоненное т ь ю вершины [img: http://localhost:8080/file/010219-178.jpg] в графе [img: http://localhost:8080/file/010219-179.jpg] наз. величина [img: http://localhost:8080/file/010219-180.jpg], где максимум берется по всем вершпнам G, принадлежащим вместе сак одной компоненте связности. Радиус о.. Величина [img: http://localhost:8080/file/010219-182.jpg] [img: http://localhost:8080/file/010219-183.jpg], где максимум берется по всем компонентам связности графа G, наз. радиусом графа G. Диаметром графа Gназ. число [img: http://localhost:8080/file/010219-184.jpg] [img: http://localhost:8080/file/010219-185.jpg], где максимум берется по всем парам вершин [img: http://localhost:8080/file/010219-186.jpg] принадлежащим одной компоненте связности. Для "почти всех" булевых функций [img: http://localhost:8080/file/010219-187.jpg] величины [img: http://localhost:8080/file/010219-188.jpg] и [img: http://localhost:8080/file/010219-189.jpg] таковы, что [img: http://localhost:8080/file/010219-190.jpg] [img: http://localhost:8080/file/010219-191.jpg] и [img: http://localhost:8080/file/010219-192.jpg]. Из результатов, относящихся к вычислению числовых характеристик отдельных классов булевых функций, выделяются результаты, относящиеся к монотонным булевым функциям. Пусть [img: http://localhost:8080/file/010219-193.jpg], [img: http://localhost:8080/file/010219-194.jpg] - бинарные наборы. Говорят, что [img: http://localhost:8080/file/010219-195.jpg], если [img: http://localhost:8080/file/010219-196.jpg]. Булева функция наз. монотонной, если из соотношения [img: http://localhost:8080/file/010219-197.jpg] следует, что [img: http://localhost:8080/file/010219-198.jpg]. Представляет интерес определение точного числа [img: http://localhost:8080/file/010219-199.jpg] различных монотонных булевых функций от переменных [img: http://localhost:8080/file/010219-200.jpg]. Это число известно лишь для небольших значений п. Известно также асимптотич. равенство [img: http://localhost:8080/file/010219-201.jpg] Большое число приложений при решении дискретных экстремальных задач имеет задача оптимальной расшифровки монотонной булевой функции. Пусть задан алгоритм А, позволяющий вычислять монотонную булеву функцию [img: http://localhost:8080/file/010219-202.jpg] в каждой точке [img: http://localhost:8080/file/010219-203.jpg] Если в процессе вычислений установлено, что [img: http://localhost:8080/file/010219-204.jpg] для нек-рой точки [img: http://localhost:8080/file/010219-205.jpg] для всех [img: http://localhost:8080/file/010219-206.jpg]. При [img: http://localhost:8080/file/010219-207.jpg] функция [img: http://localhost:8080/file/010219-208.jpg] известна (равна нулю) во всех точках [img: http://localhost:8080/file/010219-209.jpg]. Поэтому для расшифровки, т. е. полного восстановления функции [img: http://localhost:8080/file/010219-210.jpg], алгоритм Адолжен вычислить ее значения лишь в нек-ром множестве точек. Пусть [img: http://localhost:8080/file/010219-211.jpg] обозначает минимальное число точек, в к-рых достаточно вычислить [img: http://localhost:8080/file/010219-212.jpg] для полного восстановления f. Пусть [img: http://localhost:8080/file/010219-213.jpg] Величина [img: http://localhost:8080/file/010219-214.jpg] удовлетворяет асимптотич. равенству: [img: http://localhost:8080/file/010219-215.jpg] Оценка для [img: http://localhost:8080/file/010219-216.jpg] может быть понижена, если известна дополнительная информация о монотонной булевой функции. С задачей расшифровки монотонных булевых функций связана задача вычисления числовых характеристик совокупностей существенных переменных не всюду определенных булевых функций, т. е. функций, заданных на нек-ром подмножестве множества вершин единичного n-мерного куба. Совокупность переменных [img: http://localhost:8080/file/010219-217.jpg] наз. существенной для не всюду определенной булевой функции [img: http://localhost:8080/file/010219-218.jpg], если [img: http://localhost:8080/file/010219-219.jpg] и существует не всюду определенная булева функция [img: http://localhost:8080/file/010219-220.jpg] такая, что [img: http://localhost:8080/file/010219-221.jpg] на всей области определения F. Существенная совокупность наз. тупиковой для F, если никакая истинная часть этой совокупности не является существенной для F. У каждой всюду определенной булевой функции имеется единственная тупиковая совокупность переменных. Для не всюду определенных булевых функций строение совокупностей существенных переменных отличается большим разнообразием. Пусть [img: http://localhost:8080/file/010219-222.jpg] - система подмножеств множества [img: http://localhost:8080/file/010219-223.jpg], удовлетворяющая условию: если [img: http://localhost:8080/file/010219-224.jpg] и [img: http://localhost:8080/file/010219-225.jpg] - произвольное подмножество множества [img: http://localhost:8080/file/010219-226.jpg]. Тогда существует не всюду определенная булева функция [img: http://localhost:8080/file/010219-227.jpg] такая, что система существенных для [img: http://localhost:8080/file/010219-228.jpg] наборов переменных есть [img: http://localhost:8080/file/010219-229.jpg]. Пусть [img: http://localhost:8080/file/010219-230.jpg] - число различных тупиковых наборов для [img: http://localhost:8080/file/010219-231.jpg] и [img: http://localhost:8080/file/010219-232.jpg] Известно, что [img: http://localhost:8080/file/010219-233.jpg] Алгоритм построения всех тупиковых совокупностей переменных для [img: http://localhost:8080/file/010219-234.jpg] имеет максимальную трудоемкость [img: http://localhost:8080/file/010219-235.jpg], причем этот максимум достигается (здесь единицей трудоемкости считается трудоемкость проверки, является ли данная совокупность переменных существенной для F). К Б. ф. м. т. относят также задачи вычисления характеристик, связанных с задачей минимизации булевых функций.