Экстремальные комплексы граней в единичном кубе

Чухров, Игорь Петрович

Экстремальные комплексы граней в единичном кубе тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Чухров, Игорь Петрович АВТОР

доктора физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Экстремальные комплексы граней в единичном кубе»

Автореферат диссертации на тему "Экстремальные комплексы граней в единичном кубе"

На правах рукописи

Чухров Игорь Петрович

Экстремальные комплексы граней в единичном кубе

01.01.09 - Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание учёной степени доктора физико-математических наук

1 6 МАЙ 2013

005058138

Москва - 2013

005058138

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институт автоматизации проектирования Российской академии наук.

Научный консультант:

Сапоженко Александр Антонович, доктор физико-математических наук, профессор, ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова», профессор.

Официальные оппоненты:

Леонтьев Владимир Константинович, доктор физико-математических наук, профессор, ФГБУН Вычислительный центр имени А. А. Дородницына Российской академии наук, главный научный сотрудник.

Кузюрин Николай Николаевич, доктор физико-математических наук, ФГБУН Институт системного программирования Российской академии наук, заведующий отделом.

Зуев Юрий Анатольевич, доктор физико-математических наук, ФГБОУ ВПО «Московский государственный университет технологий и управления имени К. Г. Разумовского», профессор.

Ведущая организация:

ФГБУН Институт системного анализа Российской академии наук.

Защита состоится 7 июня 2013 г. в 11.00 на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, ауд. 685.

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М. В. Ломоносова.

Автореферат разослан «. апреля 2013 г.

Ученый секретарь диссертационного совета,

кандидат технических наук

Костенко В. А.

Общая характеристика работы

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

Суть задачи минимизации булевых функций в классе ДНФ состоит в построении формулы вида «дизъюнкция конъюнкций» минимальной сложности для произвольно заданной булевой функции. Эта задача обычно рассматривается в двух эквивалентных моделях — аналитической и геометрической [1]. В аналитической модели используются понятия: булева функция, импликанта, ДНФ, зависящие от п переменных. В геометрической модели эквивалентными понятиями являются подмножество вершин, грань, комплекс граней в п-мерном единичном кубе Вп.

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

Задача минимизации булевых функций может рассматриваться как частный случай задачи синтеза управляющих систем, а именно, как задача синтеза минимальных по сложности формул глубины 2 в базисе {V, к , -1} [2]. Малая глубина ДНФ дает преимущество в надежности и быстродействии перед другими типами схем, но при этом ДНФ существенно проиг-

1 Яблонский С. В. Функциональные построения в Ьзначной логике // Сборник статей по математической логике и ее приложениям к некоторым вопросам кибернетики. Тр, МИАН СССР. М.:Изд-во АН

СССР. 1958. Т. 51. С. 5-142.

2 Лупанов О. Б. О реализации функций алгебры логики формулами конечных классов (формулами ограниченной глубины) в базисе «И», «ИЛИ», «НЕ» // Проблемы кибернетики. 1961. Т. 6. С. 5-14.

рывают в схемной сложности. Это обстоятельство способствовало фокусированию исследований на проблемах, которые возникают при рассмотрении минимизации ДНФ как дискретной экстремальной задачи.

Характерной чертой задачи минимизации булевых функций в классе ДНФ является возможность нахождения оптимального решения применением простых локальных операций: уменьшение ранга и удаление импли-кант. Применением этих операций из совершенной ДНФ булевой функции можно получить любую тупиковую, в том числе и минимальную, из произвольной ДНФ можно получить эквивалентную ей тупиковую. Такие преобразования реализуются локальными алгоритмами [3] конечного порядка и их трудоёмкость считается приемлемой.

Задача о поведении максимальных значений числа тупиковых и минимальных ДНФ булевой функции с ростом числа переменных была поставлена С. В. Яблонским в связи с оцениванием трудоемкости алгоритмов минимизации булевых функций.

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

Эффективное решение задачи минимизации возможно для специальных классов функций и только в тех случаях, когда можно обосновать минимальность ДНФ. В общем случае известные алгоритмы минимизации в качестве одного из этапов содержат перебор по определенной стратегии некоторого множества ДНФ и выбор из просмотренного множества, как правило, тупиковой ДНФ с минимальной сложностью. При этом, естественно, возникают вопросы о трудоемкости алгоритма и о возможности получения в результате выполнения алгоритма минимальной ДНФ.

Максимальные значения числа тупиковых и числа минимальных

3 Журавлёв Ю. И. Теоретико-множественные методы в алгебре логики // Проблемы кибернетики. 1962. № 8. С. 5-44.

ДНФ булевой функции являются объективными характеристиками величины неустранимого перебора при минимизации булевой функции с использованием переборных алгоритмов, которые находят точное решение. Максимальное значение отношения числа минимальных к числу тупиковых ДНФ булевой функции является верхней оценкой вероятности нахождения минимальной ДНФ при случайном выборе тупиковой ДНФ.

Большинство задач, которые возникают при минимизации булевых функций в классе ДНФ, относится к полным или трудно решаемым комбинаторным задачам [4,5]. Поэтому актуальными являются задачи выделения эффективно и неэффективно минимизируемых классов булевых функций, определения достаточных критериев минимальности и обоснованности сокращения перебора в алгоритмах минимизации. Все эти аспекты теории минимизации булевых функций в той или иной мере нашли отражение в данной работе. Таким образом, тема диссертации актуальна как в теоретическом, так и в прикладном отношении.

Объектом изучения диссертации являются комбинаторные задачи и задачи минимизации булевых функций, предметом изучения — критерии минимальности, условия существования и методы построения комплексов граней в единичном кубе, обладающих экстремальными свойствами и характеристиками.

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

Исходными для исследования явились результаты, которые получили следующие авторы: C.B. Яблонский, W.V. Quine, Ю.И. Журавлёв,

4 Cook S. A. An overview oí computational complexity // Communications of the ACM. 1983. Vol. 26, no. 6. P. 401-408.

s Umans C., Villa T., Sangiovanni-Vincentelli A. L. Complexity of Two-Level Logic Minimization // IEEE Trans, on CAD ol Integrated Circuits and Systems. 2006. Vol. 25, no. 7. P. 1230-1246.

Ю. JI. Васильев, В. В. Глаголев, А. А. Сапоженко.

Важные результаты по минимизации булевых функций и метрическим задачам в единичном кубе получили также следующие авторы: А. Д. Коршунов, Р. Г. Нигматуллин, Лин Син-Лян, К. Вебер, А. Е. Андреев, В. К. Леонтьев, О. Coudert, Ю. А. Зуев, Э. Ш. Коспанов, А. В. Косточка, N. Pippenger, Е. Allender, Z. Furedi, J. Kahn, D.J. Kleitman и др.

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

Научная новизна. Все представленные в диссертации результаты являются новыми. В работе сформулирован ряд задач минимизации булевых функций для классов мер сложности, исследование которых является новым направлением в теории минимизации булевых функций. Решены некоторые актуальные проблемы математического направления исследований по минимизации булевых функций.

Методика исследований. В работе используются как известные методы, так и новые методы, разработанные автором. К числу известных относятся методы дискретной геометрии, комбинаторики, теории вероятностей, нелинейного программирования. Основным инструментом, создающим методическое единство работы, является разработанный метод сведения задач о существовании комплексов граней с заданными структурными свойствами к метрическим задачам для подмножеств вершин единичного куба, который используется для построения экстремальных тупиковых, ядровых и минимальных комплексов граней.

Новые методы и подходы: метод сведения задач о существовании комплексов граней определенного типа к метрическим задачам в единичном кубе (гл. 1, 2); методы доказательства минимальности или не минимальности комплекса граней на основе порядковых свойств меры сложности

(гл. 3, 4), а также новый подход к вероятностному методу доказательства существования объектов с экстремальными характеристиками путем определения вероятностного пространства с параметрическим неравномерным распределением и оптимизацией при подборе параметров (гл. 1,5).

Практическая и теоретическая ценность. Работа носит теоретический характер. Вместе с тем, полученные результаты могут применяться для повышения обоснованности и эффективности точных и эвристических алгоритмов минимизации булевых функций: достаточные условия минимальности — для сокращения перебора, методы построения комплексов граней с экстремальными характеристиками — для построения тестовых примеров булевых функций «трудных» для алгоритмов минимизации.

Основными результатами диссертации являются:

1. Доказано существование тупиковых комплексов /с-мерных граней с числом граней порядка 2П при к < \ (1 - е), а при к = о(п) асимптотически равном 2". Для числа тупиковых комплексов граней получен порядок логарифма равный п • 2п. Мощность множества функций, для которых число тупиковых комплексов по порядку логарифма равно п • 2", сравнима по порядку логарифма с числом всех булевых функций п переменных.

2. Доказано существование ядровых комплексов Яс-мерных граней с числом граней порядка 2П при к < | (1 - е).

3. Доказано, что число кратчайших комплексов /с-мерных граней совпадает по порядку логарифма с числом комплексов, которые состоят из не более 2™-1 различных /с-мерных граней, при к < |(1 - е). Для числа кратчайших комплексов граней получен порядок логарифма равный п • 2я.

4. Сформулирован ряд задач минимизации булевых функций для классов мер сложности. Определены специальные классы мер сложности (Л„, Л;, Л^)6, которые обладают определенными порядковыми свойствами. Доказаны достаточные условия минимальности комплексов граней.

6 Определение классов мер сложности представлено на стр. 21, 26.

5. Доказано, что число Л,,.-минимальных комплексов граней размерности не более к совпадает по порядку логарифма с числом комплексов, которые состоят из не более 2П_1 различных граней размерности не более к, при к < | (1 - е). Для числа Л^-минимальных комплексов граней получен порядок логарифма равный тг ■ 2п. Мощность множества функций, для которых число Л^-минимальных комплексов по порядку логарифма равно п • 2™, сравнима по порядку логарифма с числом всех булевых функций п переменных.

6. Доказано, что максимальное отношение числа тупиковых и минимальных комплексов граней функции по порядку логарифма равно п ■ 2п для всех мер сложности класса Л* П Л;. Максимальное число тупиковых комплексов граней функции может быть по порядку логарифма равно п • 2" и в случае единственного минимального комплекса граней функции для всех мер сложности класса Л* П Л£. Мощность множества функций с такими соотношениями числа тупиковых и минимальных комплексов (для указанных классов мер сложности) сравнима по порядку логарифма с числом всех булевых функций п переменных.

7. Доказано существование в единичном кубе Вп монотонного комплекса граней, который имеет тень нижних единиц мощности порядка 2™ с константой больше 0.225. Доказано, что почти все вершины из пояса куба, который расположен в средних слоях куба и имеет ширину могут входить в тень нижних единиц монотонного комплекса граней.

Таким образом, для числа граней определенной размерности в тупиковых, ядровых, кратчайших комплексах граней и для мощности тени нижних единиц монотонного комплекса граней доказано, что мощностные верхние оценки достижимы по порядку. Для числа комплексов граней определенного вида (тупиковых, кратчайших, Ля-минимальных) доказана достижимость по порядку логарифма мощностных верхних оценок. При этом верхние оценки максимального числа ДНФ определенного вида для

булевой функции считались тривиальными и ставилась задача получения нетривиальных верхних оценок [7, стр. 102].

Апробация работы. Результаты работы были представлены на следующих конференциях: V конференция «Проблемы теоретической кибернетики» (Новосибирск, 1980); VI конференция «Проблемы теоретической кибернетики» (Саратов, 1983); VI международная конференция «Основы теории вычислений (РСТ-87)» (Казань, 1987); XI Международный семинар «Дискретная математика и её приложения» (Москва, 2012).

Диссертация прошла апробацию на заседаниях семинаров кафедры математической кибернетики факультета ВМиК МГУ им. М.В. Ломоносова (2010-2013), на семинаре по сложности вычислений ВЦ РАН (2013), на Всероссийском научном семинаре «Математические вопросы кибернетики» МГУ им. М.В. Ломоносова (2013).

Публикации. По теме диссертации автором опубликовано 15 научных работ, отражающие основное содержание диссертации, в том числе семь работ в журналах, рекомендованных ВАК [1-7].

Личный вклад автора. Все представленные в диссертации результаты получены лично автором.

Структура и объем диссертации. Диссертация состоит из введения, определений и обозначений, обзора литературы, пяти глав, содержащие в совокупности 18 разделов, заключения и списка литературы. Общий объем диссертации — 189 страниц, из них 174 страницы текста, включая 17 рисунков и 4 таблицы. Список литературы включает 105 наименований на 12 страницах.

7 Васильев Ю. Л., Глаголев В. В. Метрические свойства дизъюнктивных нормальных форм // Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974. Т. 1. С. 99-148.

Содержание работы

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

Определения и обозначения. Комплексом граней называется неупорядоченный набор граней п-мерного единичного куба Вп. Условие включения в комплекс только различных граней оговаривается специально.

Обозначим через Им — множество вершин куба, которые содержатся в гранях комплекса М. Комплекс граней М называется комплексом граней булевой функции /, если множество наборов значений переменных, на которых функция обращается в единицу, совпадает с множеством Им-

Изоморфизм аналитической и геометрической моделей основан на изоморфизме элементарных конъюнкций и граней единичного куба Вп. Элементарная конъюнкция К = хЦ ■ ... ■ изоморфна грани 52- = в?'аиГат, ДНФ К\ V ... V К3 изоморфна комплексу граней

Комплексы граней называются эквивалентными, если они являются комплексами граней одной булевой функции.

Комплексы граней называются изоморфными, если один комплекс может быть получен из другого комплекса перестановкой координат. Соответственно, грани изоморфны, если одна грань может быть получена из другой перестановкой координат. Комплексы граней называются 7г-изоморфными, если один комплекс может быть получен из другого комплекса заменой граней на изоморфные грани.

Комплекс граней называется неприводимым, если после удаления из него любой грани получается не эквивалентный комплекс граней. В неприводимом комплексе каждая грань содержит хотя бы одну вершину, которая не содержится в других гранях комплекса. Такая вершина называется соб-

ственной вершиной грани в неприводимом комплексе. Обозначим через 1м,х — грань неприводимого комплекса М, которая содержит собственную вершину х.

Множество вершин 1(а,(3) = {х € Вп \ р{а,х) + р{х,0) < /э(а,/3)}, представляет наименьшую грань, содержащую одновременно вершины а и /3, где р(а,Р) — расстояние Хэмминга. В таком представлении множество вершин грани называется интервалом размерности к, где к = р(а,/3). Минимальную и максимальную вершины грани I обозначим через 5тщ(/) и ¿тах(7) соответственно.

Любая грань, которая содержится в множестве С} (в Мм) называется допустимой гранью множества С} (комплекса М). Допустимая грань I для множества вершин С Вп называется максимальной, если не существует грань I' ф I такая, что 7 С I' С ф.

Комплекс граней М называется тупиковым, если он является неприводимым и все грани являются максимальными для множества Ым-

Грань I называется ядровой для множества вершин С} С Вп, если она является максимальной для множества С} и существует вершина йе/, которая не принадлежит никакой другой грани, максимальной для С}. Вершины ядровой грани, которые не содержатся в других максимальных гранях множества <2, называются собственными вершинами ядровой грани.

Комплекс граней М в кубе Вп называется ядровым, если любая грань комплекса М является ядровой для множества вершин Л^.

Функционал £, определенный на множестве всех комплексов граней, является мерой сложности, если он удовлетворяет аксиомам неотрицательности, монотонности, выпуклости и инвариантности относительно изоморфизма [8, стр. 298].

Комплекс граней называется С-минимальным, если он имеет наименьшую меру сложности £ среди эквивалентных комплексов граней.

8 Яблонский С. В. Введение в дискретную математику. — М.: Высшая школа, 2003. 384 с.

¿-сложность минимального комплекса граней булевой функции / называется С-сложностью функции и обозначается ¿ (/).

Кратчайшим называется ¿-минимальный комплекс и минимальным называется ¿-минимальный комплекс, где I — число граней и Ь — сумма рангов граней в комплексе.

Для произвольного класса мер сложности С комплекс граней называется С-минимальным комплексом (минимальным относительно класса мер сложности С), если он является ¿-минимальным для любой меры сложности из класса С.

Множество булевых функций п переменных обозначается через Р„. Для функции / е Р„ будем обозначать:

7~(/) — множество тупиковых комплексов граней функции; Мс (/) — множество ¿-минимальных комплексов граней функции; •Мпс (/) = П -М-с (/) — множество С-минимальных комплексов гра-

£еС

ней функции для класса мер сложности С;

т (/) ~ число тупиковых комплексов граней функции; Не (/) — число ¿-минимальных комплексов граней функции; /¿пс(Я — число С-минимальных комплексов граней функции для класса мер сложности С;

Хс (/) = г (/) — отношение числа тупиковых и ¿-минимальных

комплексов функции;

Хс(/) = пип хс{1) — минимальное отношение числа тупиковых и ¿-минимальных комплексов функции для класса мер сложности С;

т (/ | цс (/) = 1) — число тупиковых комплексов функции при условии существования единственного ¿-минимального комплекса;

т{1 \fJ-c (/) = 1) — число тупиковых комплексов функции при условии Не (/) = 1 для любой меры сложности ¿ из класса мер сложности С.

Максимальное значение параметра на множестве функций Рп

будем обозначать через дх (п), например, г (п) или не (п).

В единичном кубе В" обозначим: Т" — множество всех тупиковых комплексов граней; Ml — множество ¿-минимальных комплексов граней; 7m-km ~ множество тупиковых комплексов к-мерных граней в поясе S£_fc,m С Вп, где 0 < к < т < п;

~ множество функций из Р„, для которых все максимальные грани являются fc-мерными гранями в поясе и, соответственно,

Г (/) С 7^_fc,m, где 0 < к < т < п

Асимптотические оценки числовых параметров в единичном кубе Вп всюду получаются при п -> оо. Знак о( 1) означает величину, стремящую ся к нулю при 71 —^ оо. Через се, de, с"е обозначаются сколь угодно малые положительные константы. Через [xj (соответственно |V|) будем обозначать целую часть (соответственно верхнюю целую часть) числа х. Под log понимается логарифм по основанию 2. Под Я (ж) понимается функция Н (х) = —хlog х — (1 — х) log (1 - х), где 0 < х < 1.

Обзор литературы содержит описание результатов, которые характеризуют различные аспекты задачи минимизации булевых функций в классе ДНФ: особенности минимальной реализации, в сравнении с реализаций в других классах управляющих систем; алгоритмические трудности минимизации в классе локальных алгоритмов; вычислительную сложность задач, которые возникают при минимизации булевых функций; точные и эвристические алгоритмы решения задачи минимизации; оценки для экстремальных характеристик комплексов граней в единичном кубе и способы их получения.

Отметим, что в кубе Вп мощность множества комплексов различных граней не превосходит 2°("2П) при п оо, если в комплексах множества либо число граней равно о(2П), либо число граней равно О (2") и все грани размерности о(п). Поэтому мощность множества неприводимых комплексов граней может быть по порядку логарифма равна п • 2™ только для

комплексов, которые содержат порядка 2" граней размерности порядка п.

Из известных нижних оценок числа тупиковых и минимальных комплексов граней булевой функции в кубе Вп следует, что log |Р„| = 2" является величиной о (log г (п)) и o(\ogfiL (п)). Это означает эквивалентность задач о максимальном числе тупиковых или минимальных комплексов граней булевой функции п переменных и о числе тупиковых или минимальных комплексов граней в кубе Вп с точностью до асимптотики логарифма.

В первой главе рассмотрены методы построения тупиковых комплексов граней в единичном кубе с экстремальными значениями характеристик.

Результаты главы 1 опубликованы в работах [1, 4].

В разделе 1.1 приводится описание методов построения тупиковых комплексов граней в поясе единичного куба.

Пусть S С Вп и подмножество вершин А С S. Вершина х £ S называется (A, S)-внутренней вершиной, если существует такая вершина а £ А, что 1{а,х) С S и интервал 1{а,х) не является максимальным для множества S. Вершина х £ S называется (А, 3)-граничной вершиной, если для любой вершины a £ А, либо I (а, я) с S и интервал I (а, х) является максимальным для множества S, либо I (а, х) S.

Подмножество А с S, относительно которого рассматриваются множества граничных и внутренних вершин, будем называть опорным подмножеством. Множество {A, S)-внутренних вершин будем обозначать через W(j4,5), а множество (Л,5)-граничных вершин через G(A,S).

Лемма 1.1. Пусть А с S и для I = \G (А, 5)| комплекс интервалов Т(A,S) = {Ij = I(£j,а), j = l,...,l} определяется следующим образом. Для каждой (А, Б)-граничной вершины xj, j = 1,..., I, в комплекс включается один интервал, который содержит вершину ij и некоторую вершину а € А, для которой интервал I (ij,a) С S и является максимальным для множества S. Тогда комплекс Т (А, S) является тупиковым, при этом каждая вершина ij £ G(A,S) является собственной

вершиной для содержащего ее интервала I (¡¿¡а) 6 Т(Д 5).

Для построения множества тупиковых комплексов (рис. 1.3) по произвольному тупиковому комплексу Т £ Т£_кдП1 используется метод, основанный на сечении по слою граней тупикового комплекса, имеющие собственные вершины в поясе

Рис. 1.3. Построение множества комплексов граней О" (Т,Ст, 3!^_к0:ГП,р,к)

Таким образом, задача о числе тупиковых комплексов граней в кубе Вп сводится к задаче построения опорного множества вершин в поясе единичного куба, при этом ширина пояса должна быть порядка п, число вершин в поясе должно быть порядка 2П и число граничных вершин должно быть сравнимо с мощностью пояса.

В разделе 1.2 приводятся формулировки основных результатов о числе граней в тупиковом комплексе и числе тупиковых комплексов граней в единичном кубе.

Теорема 1.1. Пусть в = ит8 = тилиЗ = 5£_го,п_т+А ит8 = п-

т, где ёеп <т<\ик<"^(\~ с"г). Существует опорное множество

А\ С S такое, что для тупикового комплекса граней Т е T{S,A\) справедливо при п —> оо

\S\ (1 - е-л) (l - <l(T) = |С (Ал, S)| < |S|,

где се < А < min - 2 — се,о(п)}. При этом в тупиковом комплексе Т каждая грань имеет размерность к, содержит одну вершину из опорного подмножества А\ и одну вершину из множества (Ад, Заграничных вершин, которая является собственной для содержащей ее грани.

В качестве следствия из теоремы 1.1 при п ->• оо получаем:

1) Если к = о(п), то l(T) ~ |5|.

2) Если dtn < к < ^(1 -с"£), то |5| • tp(А0,ж) < 1{Т) < |5|, где х ~ k/ms, <р(А,х) = (l — е~А) (l — yrfi) и значение Ао выбирается из условия максимизации по А функции (А, х) при 0 < А < 1 /х — 2.

Для 1т (п, к) - максимального числа fc-мерных граней в тупиковом комплексе получены следующие оценки: 1т (п, к) ~ 2п, если к = о(п), к -> оо, и 1т (п, к) > 2п, если den < к < ^ (1 - с"е), при п -* оо.

Теорема 1.2. Для тупикового комплекса граней в единичном кубе Вп число граней размерности не менее к не превосходит 2" — jj^FIj)-

Нижние оценки числа тупиковых комплексов граней, получены путем построения по тупиковому комплексу Т € Т£_кот множества тупиковых комплексов ft? (T,CT,S^_ko m,p,k) с где параметры р и fc удовле-

творяют условию 0 < р < к < fco-

Теорема 1.3. Пусть сеп<т< ¿¿п < ко < % (1 - с"е) и ко/т = х. Если к < ко и к/^/п —оо при п-ь оо, то

logl'C.fc \>К-к,т\-ко-Н(к/ко)-<р(Х,х),

где ч>{Х,х) = (1 - e-Ä) (1 - и 0 < А < i - 2.

Как следствие, для числа тупиковых комплексов fc-мерных граней в кубе Вп получен порядок логарифма равный п ■ 2", если к ~ с-п и 0 < с < 0.25.

Нижняя оценка числа тупиковых комплексов вытекает из оценки для множества тупиковых комплексов граней и V^-m+i,n-m+i+k< гДе

т = [п/2J. При оптимальном выборе параметров (к и 0.0526 -п) для числа тупиковых комплексов граней в Вп и для максимального числа тупиковых комплексов граней функции из Рп, так как log т(п) ~ log T(n), справедлива оценка:

Теорема 1.4. Т(п) > (2*")™ где с > 1.355 • 2~5, при п -> оо.

В разделе 1.3 приводятся доказательства утверждений о максимальном числе граней определенной размерности в тупиковом комплексе.

В разделе 1.4 приводятся доказательства утверждений о числе тупиковых комплексов граней.

Во второй главе рассмотрены методы построения ядровых и кратчайших комплексов граней в единичном кубе с экстремальными значениями характеристик.

Результаты главы 2 опубликованы в работах [2, 5]. В разделе 2.1 приводится описание методов построения ядровых и кратчайших комплексов граней в единичном кубе.

Определение 2.1. Для множества вершин Q С Вп подмножество вершин X С Q называется интервально независимым для Q множеством вершин, если любая допустимая грань для множества Q содержит не более одной вершины из X. Для комплекса граней М множество вершин называется интервально независимым, если оно является интервально независимым для множества Nm-

Определение 2.2. Пусть А произвольное подмножество вершин куба Вп. Вершина х е Вп называется простой к-граншной вершиной множества А, если р(А,х) = min p(ä,x) > к и существует ровно одна вершина ä е А

а еА

такая, что р(а,х) = к. Подмножество А с Вп, относительно которого рассматривается множество простых ¿-граничных вершин, будем называть опорным подмножеством в единичном кубе Вп.

Обозначим через С* (А) множество простых ¿-граничных вершин множества Л с В" и определим однозначное отображение Фа,к'- А, которое каждой вершине г еб^ (А) ставит в соответствие единственную вершину фл,к (я) € А, такую что р(х, Фа,к (я)) = ¿-

Будем говорить, что подмножество X С Вп состоит из изолированных вершин, если в подмножестве X нет пар соседних вершин.

Пусть множество С? есть некоторое подмножество изолированных простых ¿-граничных вершин опорного множества А с Вп. Определим комплекс граней М = = I (х^, Фа,к (я?)), ^ = 1,..., £}, где I = то есть для каждой простой ¿-граничной вершины ^ебв комплекс включается единственная, однозначно определенная ¿-мерная грань, которая содержит вершины ^еби Фа,к (£;) € А. Тогда справедлива

Лемма 2.1. Комплекс граней М является ядровым, при этом каждая вершина ¡з е (7 является собственной вершиной для содержащей ее к-мерной ядровой грани = I (5,-, фА,к (%))•

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

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

В разделе 2.2 приводятся формулировки основных результатов о числе граней в ядровом комплексе и числе кратчайших комплексов граней в единичном кубе.

Теорема 2.1. Для 1 < к < § -т}(п), где т){п)/у/п -> оо прип-> оо, существует ядровой комплекс к-мерных граней М, построенный по подмножеству изолированных простых к-граничных вершин С? с Оь (^4) для некоторого опорного множества А с Вп, такой что

1 /• я ¿л 2П-1 (п — 2к 2 (А; + 1) (га — 2к) 1 2""1 /АЛ тах {ттгаГ' (п-к)2 } ~ ~У'

где 1рс (х) = При этом в комплексе М каждая грань

содержит одну вершину из опорного подмножества А и одну вершину из подмножества <3, которая является собственной для содержащей ее ядровой грани.

Из теоремы 2.1 следует существование ядровых комплексов /с-мерных граней с числом граней порядка 2П для 1 < к < | (1 - с£) при п оо:

2П-1

если 1 < к = о (п), то-< с* (п) < 2П_1;

б , 2 п-1

если к/п ~ х, где 0 < х < 0.5, то -<рс(х) < ск{п) < 2"-1, где

' е

0 < <рс{х) < 1.

Так как ядровые комплексы являются тупиковыми, то 1т (п, к) > ск (п) для любого к и, следовательно, 1Т (п, к) х 2П при 1 < к < § (1 - с£).

Множества кратчайших комплексов граней, кратчайших комплексов Л-мерных граней и кратчайших комплексов /¡-мерных граней длины тп в единичном кубе В" обозначим через Л4[\ М?'к и М"'к,т соответственно. Их мощности обозначим М\ (п), Мг (п, к) и М\ (п, к, т).

Нижние оценки числа кратчайших комплексов получаются при построении подмножества комплексов граней из множества М"'к,т. Построение выполняется по ядровому комплексу &0-мерных граней М максимальной длины Cfco(n) и некоторому подмножеству собственных вершин С С См мощности т < ска (п). При этом log Mi (п, к,т)>т ■ log(^), если l<k<konm<Ck0 (п). С использованием оценки максимальной длины ядрового комплекса &о-мерных граней отсюда следует, что

log М, (п, ч > ^ ■ % (£) ■ log(^)

для 1 <к <ко -Г] (п), где г) (п)/у/п оо, при п оо.

Пусть D„,fc (ш) — число комплексов из не более т различных граней размерности к в единичном кубе В".

Теорема 2.2. Для 1 < к < § (1 - сс) при п оо

log Mi (п, к) х log (2n_1).

Если 1 < к = о (п), то

on—1 п , п

£_ . blog£ < log Mi (n,fc) < 2 • к ■ log-, Если к ~ х-п, где 0 < х < 0.5, то

п ■ 2п~5 ■ Cmin (г) < log Mi (п, к) < п ■ Т~ь • cw (х), где с™,, (ж) = 25 max ф (у) Н (х/у), cmax (х) = 24 (Я (г) - х), ф (t) = (t).

у\х<у<0.Ь

Таким образом, для fc-мерных граней число кратчайших комплексов и число всех комплексов из не более 2n_1 различных граней по порядку логарифма совпадают при 1 < к < - се).

Для числа кратчайших комплексов граней в кубе Вп и, соответственно, для максимального числа кратчайших комплексов граней функции из Р„, так как logw(n) ~ logMi(n) > logMj(n,к), при оптимальном выборе параметров (к « 0.191 • п) справедлива оценка:

Теорема 2.3. М1 (п) > (22")от, где с > 1.0614 ■ 2~ь, при п-+ оо.

В разделе 2.3 приводятся доказательства утверждений о максимальном числе граней определенной размерности в ядровом комплексе.

В разделе 2.4 приводятся доказательства утверждений о числе кратчайших комплексов граней.

В третьей главе рассмотрены методы обоснования минимальности комплексов граней и построения минимальных комплексов с экстремальными значениями характеристик в единичном кубе.

Результаты главы 3 опубликованы в работах [2, 6, 14, 15].

В разделе 3.1 определяются специальные классы мер сложности, сформулированы критерий минимальности неприводимых комплексов граней и качественные результаты о множествах минимальных комплексов граней. Обозначим:

Л — множество всех функционалов, которые являются мерами сложности на множестве комплексов граней;

Л„ — класс мер сложности, которые удовлетворяют усиленному свойству инвариантности относительно изоморфизма, т.е. 7г-изоморфные комплексы имеют одинаковую ¿-сложность;

Л; — класс мер сложности, которые удовлетворяют свойству строгой монотонности относительно длины, т.е. ¿-сложность комплекса уменьшается при удалении произвольной грани;

Аь — класс мер сложности, которые удовлетворяют свойству строгой монотонности относительно сложности, т.е. ¿-сложность комплекса уменьшается при уменьшении ранга или удалении произвольной грани.

Все используемые при минимизации функционалы являются мерами сложности из классов Л^ П Л( или Л* П Аь- Для меры сложности ¿ е Л^ любой ¿-минимальный комплекс является неприводимым. Для меры сложности ¿ € Ль любой ¿-минимальный комплекс является тупиковым.

Понятие интервально независимого множества при определенных

условиях позволяет обосновать минимальность комплекса граней. Для неприводимого комплекса граней М обозначим:

См — подмножество собственных вершин граней комплекса М, которое содержит по одной произвольной, если их несколько, собственной вершине для каждой грани комплекса;

1м,х ~ грань комплекса М, которая содержит вершину х £ См-

Подмножество вершин называется протыкающим для комплекса граней, если в каждой грани комплекса содержится хотя бы одна вершина подмножества.

Грани I и Г называются изоморфными, если существует такая перестановка КООрДИНаТ 7Г, ЧТО 7Г (/') = I.

Грань I доминирует грань /', если существует такая перестановка

КООрДИНаТ 7Г, ЧТО 7Г (/') С I.

Лемма 3.1. Пусть <ВМ — подмножество собственных вершин для граней неприводимого комплекса М и определены условия:

1. Подмножество 93м является интервально независимым и протыкающим для комплекса граней.

2. Для каждой вершины х € 23м ранг грани 1м,х не больше, чем ранг любой допустимой грани комплекса, которая содержит вершину х.

3. Для каждой вершины х е Ъм грань 7м,г изоморфна или доминирует любую допустимую грань комплекса, которая содержит вершину х.

Тогда комплекс М является

— кратчайшим, если выполнено условие 1,

— минимальным и кратчайшим, если выполнены условия 1 и 2,

— Ах-минимальным, если выполнены условия 1 и 3.

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

выделить подмножество собственных вершин 03м, которое является интер-вально независимым и протыкающим. Если кратчайший комплекс не является минимальным, то может выполняться условие 1 и не выполняться условие 2 для максимальной грани 1м,х некоторой вершины х е

Л^-минимальные комплексы, удовлетворяющие условиям 1 и 3 леммы 3.1, также обладают свойством суммируемости для компонент связности (лемма 3.2). Как следствие получаем, что для симметрических функций ¿-минимальные комплексы являются Л^-минимальными.

Множества ядровых комплексов граней, Л^-минимальных комплексов граней и минимальных комплексов граней для любой меры сложности в единичном кубе Вп обозначим через .М£ег, М"л„ и -^пл соответственно. Очевидно, что .М£ег С МС На самом деле справедлива

В разделе 3.2 приводится описание метода построения в единичном кубе комплексов граней определенной размерности, которые являются минимальными для любой меры сложности из класса Л^..

Множества ¿-минимальных комплексов граней, ¿-минимальных комплексов граней размерности не более к и комплексов нулевой ¿-сложности в единичном кубе Вп обозначим через М\, Мп£к и Мпс=0 соответственно. Их мощности обозначим через Мс (п), Мс (п,к) и Мс=о («)•

Пусть М — произвольный ядровой комплекс ^-мерных граней в единичном кубе Вп и параметры ко, к, р, г удовлетворяют ограничениям 0<2р<к<к0ир<г<п-р. Обозначим через П" (М, См, к0, к,р, г) — множество комплексов, построенных по пучкам граней Р{х) для вершин из множества См П 5Г"_Р1Г+Р ядрового комплекса М, состоящего из граней размерности к0 (рис. 3.3). Любой комплекс из этого множества является Л^-минимальным, грани в пучках имеют размерность от [§] - р до к и

Рис. 3.3. Построение множества комплексов П" (М, См, ко, к,р,г) Нижние оценки Мпл„ (п, к) получаются при построении множеств минимальных комплексов по ядровому комплексу с максимальным числом граней определенной размерности.

В разделе 3.3 приводятся формулировки основных результатов о числе Л^-минимальных комплексов граней в единичном кубе.

Теорема 3.1. Если к~х-п, где 0 < х < 0.5, то при п -> оо

с (х) ■ п ■ 2" < log Мпл, (п, к) < log f • п ■ 2"-1 + О (2П),

гдес(х)= max %-(рс(у) Н(х/у), ус{у) = -maxí l,^- }.

y|i<y<o.5 4е i — у l1_í/J

Из теоремы 3.1 следует, что log-Мпл, (ji,k) ж п ■ 2", если к ~ х ■ п и

О < х < 0.5, при п -> оо. При оптимальном выборе параметров получаются

нижние оценки числа Л^-минимальных комплексов граней в кубе Вп и

максимального числа Л^-минимальных комплексов граней функции из Р„.

Теорема 3.2. Для с„ > 0.5307 • 2-4 прип-^оо

с* • п • 2"-1 < log^nA, (п) < log Мпл, (n) < log | • п ■ 2"-1 + О (2П).

Из теоремы 3.2 следует, что \ogpn\4{n) ~ log Мпл„ (п) х п ■ 2" при п оо, т.е. существуют функции, для которых число Л^-минимальных комплексов по порядку логарифма равно п ■ 2™.

Обозначим через (t) = {/ е Р„ | logMnAl (/) > t • сж ■ n • 2"-1} множество функций с «большим» числом А^-минимальных комплексов.

Теорема 3.3. log (t)| > a -Ti(t) ■ 2п, где а > 0.0868, h(t) = 1 для

0 < t < 5 и % (t) = Н (t) для | < t < 1, при п -> оо.

Для произвольной меры сложности ¿-минимальный комплекс не обязательно является неприводимым. Однако существенное увеличение числа ¿-минимальных комплексов для £ёЛ, может произойти только за счет комплексов нулевой сложности.

Теорема 3.4. log цс (n) ~ п ■ 2" + log М£=0 (п) для ¿ € при п оо.

В случае fc = о(п), а именно для к — о{ф\), получение высоких нижних оценок основано на возможности объединения Л^-минимальных комплексов граней, которые содержатся в «узких» и несвязных поясах куба Вп, с сохранением свойства Л^-минимальности.

Теорема 3.5. Для 1 < fc = о (п) при п -»■ оо

cfc • 2"-1 -к- log ^ < log Мпл, (п, к) < 2""1 • к ■ log р

где ск = ± при ^ ^ co, ск = ± при п0 < к = О (<Jn) и ск = ~ при

1 < Jfe < п0, п0 = [16е - 2] = 42.

В разделе 3.4 приводятся доказательства лемм и теорем о минимальных комплексах граней.

В четвертой главе рассмотрены методы построения булевых функций с экстремальным отношением числа тупиковых и минимальных комплексов граней.

Результаты главы 4 опубликованы в работах [1, 4, 7].

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

Рассматриваются классы мер сложности Лг и Л£, которые являются расширением классов строгой монотонности, соответственно, относительно длины и сложности, но исключаются требования к граням содержащим вершину б или 1. Исключение таких граней, позволяет рассматривать меры сложности, которые не являются строго монотонными относительно длины и сложности, например, зависят от числа отрицаний в ДНФ.

Нижняя оценка ХлдПл, (п) основана на построении функции Ф, е Рп (рис. 4.1) по функции / е следующим образом:

Ф/ (ц,..., хя) = S„-ixnS^12fc m (zi,..., In-2) V

V Xn-lXnSn\m (®1. • • ■ > ®n-2) ■ • • . 2) (xi © . . . e Xn-2) V

V Хп-гх^Хп (®1,..., x„-2) /(an,..., ®n-a) (®i Ф ■ ■ • Ф *n-2 ® 1),

где (хь..., xn_2) - поясковая функция в Вп~2 и 0 < fc < m < [^J.

Доказывается, что т (Ф/) > т (/) и (Ф/) < 2°^'2П) для любой меры сложности С е Аж П Ль а также справедливость аналогичных утверждений для двух симметричных компонент связности, расположенных ниже и выше середины куба Вп (леммы 4.2-4.4). Из теорем 1.3-1.4 следует существование такой функции / <Е что logr (/) > с,- (п - 2) 2"-3, где с? > 1.355 • 2-5. Тогда справедлива оценка

bgxW")^-"'2"-2-

Нижняя оценка г (тт. | Мл,пАг = основана на построении функции Ф/ е -Рп (рис. 4.2) по функции / € Р„-з, имеющей максимальное число

Рис. 4.1. Определение функции Ф/ тупиковых комплексов т (п - 3), следующим образом:

Ф/ (II, . . . , Хп) = Хп-1Хп (хп-2 V Хп-2/ • ■ ■ > ®п-з)) V

V хп_11п (II © • • • © хп-г) (хп_2/(х 1,..., х„_з) V хп-2/ (ац,..., Яп-з)) V

V Х„_1Х„ (II ф . . . © Хп-2 ® 1) (ё„_2/ (хь • • • , ^п-з) V Х„_2/ (жь . . . , Хп-з)) •

Доказывается, что, если г (/) > 1 и / (!) = 0 для функции / € Р„-3. где п > 5, то д£(Ф/) = 1 и т(Ф/) > т(/) для любой меры сложности

£еЛжп л£.

Нижние оценки числа функций из Рп вида 2е'2", где 0 < с < 1, для которых характеристики г(/), Хл„пА, (/). г (/ I (/) = имеют П0"

рядок логарифма равный п ■ 2", используют конструкцию для построения тупиковых комплексов граней из теорем 1.3-1.4. Эта конструкция позволяет определять различные множества тупиковых комплексов граней для подмножеств собственных вершин экстремального тупикового комплекса, которым соответствуют различные функции. При преобразованиях Ф и Ф различные функции преобразуются в различные функции из Рп. Соответственно, применяя преобразования Ф и Ф, получаем множества функций с

Рис. 4.2. Определение функции Ф/

экстремальным отношением числа тупиковых и минимальных комплексов.

В разделе 4.2 приводятся формулировки основных результатов о соотношении тупиковых и минимальных комплексов граней в единичном кубе. Используемые в оценках константы определим следующим образом:

с,- = 0.5 • С (х, у, А) > 1.355 ■ 2~5 и <гт = tp (А, у) > 0.4025,

где С (х, у, А) = у ■ у (А, у) H (s/y), tp (А, у) = (1 - е~А) (l - и пара-

метры х = 0.1052, у = 0.2104, Л = 1.0087.

Теорема 4.1. Для любой меры сложности £ G Л*. П Àj яри п -> оо справедливы оценки

j • п • 2" < logx^râ, (") < l°gX£ (") < log ^ • п • 2" + 2" • loge.

Из теоремы 4.1 следует, что log Хл„пл, (п) И Х£ (п) имеют порядок равный п • 2™ для любой меры сложности £ G Л*- П Àj.

Теорема 4.2. При п > 5 справедлива оценка т (п | Мл„пль = 1) > т (п — 3).

Теорема 4.3. Для любой меры сложности С € Л*- П Л£ при п оо справедливы оценки

| • п • 2" < log г (п | = 1) < log т (п | рс = 1) < log | • п • 2" + 2" ■ log е.

Из теоремы 4.3 следует, что log г (п | рЛ]гПль = 1) и log г (п | рс = 1) имеют порядок равный п • 2" для любой меры сложности £ € П Ль. Обозначим множества функций п переменных:

P„(tIr) = {/eP„|logT(/)>i-cr.n-2n}) Рп («, ХА.ПА,) = {/ е Pn I log Хл,пл| (/)£«■*■"• 2П_2} , (i. Т I л, = 1) = {/ € Рп I log Г (Я > t ■ Сг ■ п ■ 2П_3, (/) = 1} ,

где 0 < t < 1 и рс(/) = 1 означает, что pc(f) = 1 Для любой меры сложности £ € С. Число функций в этих подмножествах соответственно обозначим через рп (t, т), рп (t, Хл„пл,) и Рп (*>т i ma„nâl =

Теорема 4.4. При п -» оо справедливы оценки

\ogPn(.t,T)>aT-h{t)-2n,

logp„ (t,r I = 1) > «7T ■ й (0 ■ 2П_3,

гае 7i (i) = 1 аля 0 < t < \ и П (t) = Я (i) для | < t < 1.

Из теоремы 4.4 следует, что мощность таких множеств функций по порядку логарифма совпадает с числом функций п переменных.

В разделе 4.3 приводятся доказательства лемм и теорем главы 4.

В пятой главе рассмотрен метод построения монотонных комплексов граней с максимальной тенью нижних единиц в единичном кубе. Результаты главы 5 опубликованы в работе [3].

В разделе 5.1 приводится описание метода построения специального вероятностного пространства монотонных комплексов граней и оценки средней мощности тени нижних единиц монотонных множеств этого пространства.

Подмножество X С Вп называется монотонным, если х G X и х < у, то у е X. Подмножество X с Вп называется антицепью, если любые вершины Й1,Й2 € X являются несравнимыми. Множеством нижних единиц X С Вп называется множество Е (X) = е X | /3 е X, 0 < а о Р = а|.

В единичном кубе понятия антицепь и множество нижних единиц монотонного подмножества являются эквивалентными.

Множества монотонных подмножеств и антицепей в кубе Вп обозначим через Шп и An соответственно.

Тенью подмножества X С Вп называется множество

дХ = {/? е Вп\Х \ЗабХ p(áj) = 1, Ь < «}■

Положим t(X) = |<ЭХ| и обозначим через t{n) = max í(X) =

X 6ЛП

max \дЕ(Х)\ — максимальное значение мощности тени антицепей (ниж-хсалп'

них единиц монотонного множества) в единичном кубе Вп.

Обозначим через D множество целых чисел {р+1,... ,п —1,п}, где О < р < п. Пусть £ — случайная целочисленная величина, которая принимает значения из D и имеет функцию распределения (ф.р.) F^{s) = p{£ = ¿} при s = р + 1,...,п и F((n) = 1. Будем считать, что все

p<i<s

вершины р-го слоя куба Вп пронумерованы, т.е. = {ái,..., ím}.

Обозначим m-ую декартову степень множества D через Dm. Для вектора z G Dm будем обозначать через z¡ значение координаты, которая соответствует номеру вершины х <Е В%. На множестве Dm определим веро-

ятностную меру Р^, положив {z} — П Р {£ = z¿}-

¿=i

Определим отображение Dm 9Я„, сопоставив каждому вектору

z е Dm монотонное множество М (z) = U {a G Вп \ а > х и ||а|| > zj}.

íes»

Обозначим:

Шпр - {M G Шп | 3 z G Dm: M = M (z)} — подмножество монотонных множеств в кубе Вп, которые являются образом Dm в ШТ„,

(ЗЯ„,Р, Р) — вероятностное пространство, которое состоит из монотонных подмножеств единичного куба Вп принадлежащих 9ЯП)Р, и вероятность Р {М} для M 6 ®l„iP полагается равной

р{м}= p{m(-z)}= ]г рН2}.

zeDm|M=Af(Z) î€Bm|Af=M(f)

В силу эквивалентности понятий антицепь и множество нижних единиц монотонного подмножества в единичном кубе однозначно определено вероятностное пространство {Лп,Р, Р), которое состоит из множества антицепей Лп>р = {А с Вп | ЗМ g 9ЯП,Р : А = Е (М)} и для каждой антицепи л = Е (m) g Лч», где m g 9я„,р, полагается р {л} = р {М}.

Обозначим P(s) = P {M G 9Я„,р \ à G дЕ (M) П В?} для s = 0,..., п. Тогда Р (s) = 0, для 0 < s < р или s = п, и справедливо утверждение.

Лемма 5.1. Для любой вершины à G В" и любой ф.р. Fç при р < s < п-1

P(s) > (l-F€(e + l))(î)x

х (l - (l - (1 -F( (s))(»'-J + (1 - f£ (s + ЦРУ") •

Положим P {£ = s} = ^ (s) - (s - 1) = /

О, если s < so или so + /i + l<s<n,

= если so + 1 < s < sq +1 + Л,

p w 1-

, so+h+l . , P . , ^

Ë (p) . еСЛИ s = n-

i=«o+l

Использование конкретного вида ф.р. Fç при дополнительных предположениях о параметрах p, sq, h и Л позволяет получить оценку для P(s).

Лемма 5.3. Если для параметров ф.р. ^ (я) имеют место соотношения р-> оо, к оо, р2 • к + р • к2 = о (з§) и $ ехр = о (1) при п оо, то для й = ЙО! • • • ) + Л

Нижние оценки мощности тени нижних единиц монотонного множества основаны на существовании антицепи А е Лп,р такой, что

__«о+л , ч

г(А)>Цп,р,^)= £ ¿2Р{М\схедЕ(М)пв»} = У£{)Р(*).

0<«<пйеВ? «=«о ^ '

В разделе 5.2 приводятся формулировки основных результатов.

Теорема 5.1. Существует антицепь А, тень которой содержится в поясе 5"01,0+/1 С Вп, и для ~ »г/2 при п ->• оо

¿(Л) ~ если к = о{\/п), т.е. почти все вершины пояса

могут принадлежать тени антицепи;

Ь (А) > если к х у/п, и t (А) х 2П, если |в0 - п/2\ = О (л/п).

Нижняя оценка максимального значения тени антицепи получается при оптимальном выборе параметров р, ¿о. к и А.

Теорема 5.2. £ (п) > с■ 2п, где с > 0.225, при достаточно больших п.

В разделе 5.3 приводятся доказательства лемм и теорем главы 5.

В Заключении кратко суммированы основные результаты работы, сформулирована гипотеза о необходимости для кратчайших комплексов граней условия существования интервально независимого и протыкающего множества собственных вершин, приведены некоторые нерешенные проблемы.

Список публикаций по теме диссертации

1. Чухров И. П. О числе тупиковых дизъюнктивных нормальных форм // Докл. АН СССР. 1982. Т. 262, № 6. С. 1329-1332. (Перевод статьи: Chukhrov I. P. On the number of irredundant disjunctive normal forms // Sov. Math. Dokl. 1982. Vol. 25. P. 254-257).

2. Чухров И. П. О числе минимальных дизъюнктивных нормальных форм // Докл. АН СССР. 1984. Т. 276, № 6. С. 1335-1339. (Перевод статьи: Chukhrov I. P. On the number of minimal disjunctive normal forms // Sov. Math. Dokl. 1984. Vol. 29. P. 714-718).

3. Чухров И. П. О максимальной мощности тени антицепи // Дискретная математика. 1989. Т. 1, № 4. С. 78-85.

4. Чухров И. П. О тупиковых комплексах граней в единичном кубе // Дискретная математика. 2011. Т. 23, № 1. С. 132-158. (Перевод статьи: Chukhrov I. P. On irredundant complexes of faces in the unit cube // Discrete Math. Appl. 2011. Vol. 21, no. 2. P. 243-274).

5. Чухров И. П. О ядровых и кратчайших комплексах граней в единичном кубе // Дискретный анализ и исследование операций. 2011. Т. 18, № 2. С. 75-94. (Перевод статьи: Chukhrov I. P. On the kernel and shortest face complexes in the unit cube // Journal of Applied and Industrial Mathematics. 2012. Vol. 6, no. 1. P. 42-55).

6. Чухров И. П. О минимальных комплексах граней в единичном кубе // Дискретный анализ и исследование операций. 2012. Т. 19, № 3. С. 79-99.

7. Чухров И. П. О соотношении тупиковых и минимальных комплексов граней в единичном кубе // Дискретная математика. 2012. Т. 24, № 2. С. 46-74. (Перевод статьи: Chukhrov I. P. On the relation between the irredundant and minimal complexes of faces in the unit cube // Discrete Math. Appl. 2012. Vol. 22, no. 3. P. 273-306).

8. Чухров И. П. О числе минимальных дизъюнктивных нормальных

форм поясковой функции // Прикладная математика и математическое обеспечение ЭВМ. М.: Изд-во МГУ, 1980. С. 55-56.

9. Чухров И. П. Оценка числовых характеристик поясковых функций // V Всесоюзная конференция по проблемам теоретической кибернетики. Тезисы докладов. Новосибирск: 1980. С. 179-180.

10. Чухров И. П. Оценки числа минимальных дизъюнктивных нормальных форм для поясковой функции // Методы дискретного анализа в исследованиях функциональных систем. Новосибирск: Ин-т математики СО АН СССР. 1981. № 36. С. 74-92.

11. Чухров И. П. Оценка максимальной длины тупиковой дизъюнктивной нормальной формы для поясковых функций // Комбинаторно-алгебраические методы в прикладной математике. Межвузовский сборник. Горький. 1981. С. 137-148.

12. Чухров И. П. О покрытиях конечного множества подмножествами // Комбинаторно-алгебраические методы в прикладной математике. Межвузовский сборник. Горький. 1983. С. 192-207.

13. Сапоженко А. А., Чухров И. П. Минимизация булевых функций в классе дизъюнктивных нормальных форм // Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор. кибернет. 1987. Т. 25. С. 68-116. (Перевод статьи: Sapozhenko A. A. and Chukhrov I. P. Boolean function minimization in the class of disjunctive normal forms // J. Sov. Math. 1989. Vol. 46, no. 4. P. 2021-2052).

14. Chukhrov I. P. On the number of DNF minimal relatively arbitrary measures of complexity // Fundamentals of computation theory. International Conference FCT '87, Kazan, USSR, June 22-26, 1987. Proceedings. Berlin: Springer-Verlag, 1987. P. 92-94.

15. Чухров И. П. О критериях минимальности комплексов граней в единичном кубе // Материалы XI Международного семинара «Дискретная математика и ее приложения» (Москва, МГУ, 18-23 июня 2012 г.). М.: Изд-во механико-математического факультета МГУ, 2012. С. 315-317.

Напечатано с готового оригинал-макета

Подписано в печать 09.04.2013 г. Формат 60x90 1/16. Усл.печл. 2,0. Тираж 120 экз. Заказ 097.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Текст научной работы диссертации и автореферата по математике, доктора физико-математических наук, Чухров, Игорь Петрович, Москва

Федеральное государственное бюджетное учреждение науки Институт автоматизации проектирования Российской академии наук

На правах рукописи

052013^0894 ^ТТ"

Чухров Игорь Петрович

Экстремальные комплексы граней в единичном кубе

01.01.09 - Дискретная математика и математическая кибернетика

ДИССЕРТАЦИЯ на соискание ученой степени доктора физико-математических наук

Научный консультант Сапоженко Александр Антонович, доктор физико-математических наук, профессор

Москва - 2013

Содержание

Введение......................................................................4

Определения и обозначения..............................................11

Обзор литературы..........................................................21

Глава 1. Тупиковые комплексы граней................................39

1.1. Описание конструкции......................40

1.2. Основные результаты..............................................45

1.3. Оценки числа граней тупиковых комплексов ..................48

1.4. Оценки числа тупиковых комплексов............................63

Глава 2. Ядровые и кратчайшие комплексы граней................70

2.1. Описание конструкции............................................71

2.2. Основные результаты ............................................76

2.3. Оценки числа граней ядровых комплексов......................78

2.4. Оценки числа кратчайших комплексов граней..................85

Глава 3. Минимальные комплексы граней............................92

3.1. Специальные классы мер сложности............................93

3.2. Описание конструкции......................102

3.3. Основные результаты.......................106

3.4. Оценки числа минимальных комплексов граней........108

Глава 4. Соотношение тупиковых и минимальных комплексов граней ..................................127

4.1. Описание конструкции......................128

4.2. Основные результаты.......................137

4.3. Оценки соотношения числа тупиковых и минимальных комплексов граней ..........................

Глава 5. Монотонные комплексы граней с максимальной тенью

нижних единиц.............................157

5.1. Описание конструкции......................157

5.2. Основные результаты.......................163

5.3. Оценки мощности тени нижних единиц монотонного комплекса граней...........................164

Заключение.................................175

Литература .................................178

Введение

Суть задачи минимизации булевых функций в классе ДНФ состоит в построении формулы вида «дизъюнкция конъюнкций» минимальной сложности для произвольно заданной булевой функции. Эта задача обычно рассматривается в двух эквивалентных моделях — аналитической и геометрической [78]. В аналитической модели используются понятия: булева функция, импликанта, ДНФ, зависящие от п переменных. В геометрической модели эквивалентными понятиями являются подмножество вершин, грань, комплекс граней в п-мерном единичном кубе Вп.

Задача минимизации булевых функций может рассматриваться как частный случай задачи синтеза управляющих систем, а именно, как задача синтеза минимальных по сложности формул глубины 2 в базисе {V. & , ->} [45]. Малая глубина ДНФ дает преимущество в надежности и быстродействии перед другими типами схем, но при этом ДНФ существенно проигрывают в схемной сложности. Это обстоятельство способствовало фокусированию исследований на проблемах, которые возникают при рас-

смотрении минимизации ДНФ как дискретной экстремальной задачи.

Характерной чертой задачи минимизации булевых функций в классе ДНФ является возможность нахождения оптимального решения применением простых локальных операций: уменьшение ранга и удаление импли-кант. Применением этих операций из совершенной ДНФ булевой функции можно получить любую тупиковую, в том числе и минимальную, из произвольной ДНФ можно получить эквивалентную ей тупиковую. Такие преобразования реализуются локальными алгоритмами [23] конечного порядка и их трудоёмкость считается приемлемой.

Максимальные значения числа тупиковых и числа минимальных ДНФ булевой функции являются объективными характеристиками величины неустранимого перебора при минимизации булевой функции с

использованием переборных алгоритмов, которые находят точное решение. Максимальное значение отношения числа минимальных к числу тупиковых ДНФ булевой функции является верхней оценкой вероятности нахождения минимальной ДНФ при случайном выборе тупиковой ДНФ.

Большинство задач, которые возникают при минимизации булевых функций в классе ДНФ, относится к полным или трудно решаемым комбинаторным задачам [87, 105]. Поэтому актуальными являются задачи выделения эффективно и неэффективно минимизируемых классов булевых функций, определения достаточных критериев минимальности и обоснованности сокращения перебора в алгоритмах минимизации. Все эти аспекты теории минимизации булевых функций в той или иной мере нашли отражение в данной работе. Таким образом, тема диссертации актуальна как в теоретическом, так и в прикладном отношении.

Исходными для исследования явились результаты, которые получили следующие авторы: C.B. Яблонский, W. V. Quine, Ю.И. Журавлёв, Ю.Л. Васильев, В. В. Глаголев, A.A. Сапоженко.

В. К. Леонтьев, О. Coudert, Ю. А. Зуев, Э. Ш. Коспанов, А. В. Косточка, N. Pippenger, Е. Allender, Z. Furedi, J. Kahn, D.J. Kleitman и др.

Основными результатами диссертации являются:

1. Доказано существование тупиковых комплексов /с-мерных граней с числом граней порядка 2" при к < | (1 — е), а при к = о(п) асимптотически равном 2п. Для числа тупиковых комплексов граней получен порядок логарифма равный п-2п. Мощность множества функций, для которых число тупиковых комплексов по порядку логарифма равно п • 2п, сравнима по

порядку логарифма с числом всех булевых функций п переменных.

2. Доказано существование ядровых комплексов к-мерных граней с числом граней порядка 2П при к < | (1 — е).

3. Доказано, что число кратчайших комплексов А;-мерных граней совпадает по порядку логарифма с числом комплексов, которые состоят из не более 2П_1 различных к-мерных граней, при к < § (1 — £)■ Для числа кратчайших комплексов граней получен порядок логарифма равный п • 2П.

4. Сформулирован ряд задач минимизации булевых функций для классов мер сложности. Определены специальные классы мер сложности (Ля-, Л/, Ах,)1, которые обладают определенными порядковыми свойствами. Доказаны достаточные условия минимальности комплексов граней.

5. Доказано, что число Л^-минимальных комплексов граней размерности не более к совпадает по порядку логарифма с числом комплексов, которые состоят из не более 2П_1 различных граней размерности не более к, при к < | (1 — г). Для числа А^-минимальных комплексов граней получен порядок логарифма равный п • 2П. Мощность множества функций, для которых число А^-минимальных комплексов по порядку логарифма равно п ■ 2п, сравнима по порядку логарифма с числом всех булевых функций п переменных.

6. Доказано, что максимальное отношение числа тупиковых и минимальных комплексов граней функции по порядку логарифма равно п ■ 2п для всех мер сложности класса Ап П А/. Максимальное число тупиковых комплексов граней функции может быть по порядку логарифма равно п ■ 2п и в случае единственного минимального комплекса граней функции для всех мер сложности класса Ап ПАх,. Мощность множества функций с такими соотношениями числа тупиковых и минимальных комплексов (для указанных классов мер сложности) сравнима по порядку логарифма с чис-

1 Определение классов мер сложности представлено на стр. 94, 129.

лом всех булевых функций п переменных.

7. Доказано существование в единичном кубе Вп монотонного комплекса граней, который имеет тень нижних единиц мощности порядка 2П с константой больше 0.225. Доказано, что почти все вершины из пояса куба, который расположен в средних слоях куба и имеет ширину о(л/п), могут входить в тень нижних единиц монотонного комплекса граней.

Таким образом, для числа граней определенной размерности в тупиковых, ядровых, кратчайших комплексах граней и для мощности тени нижних единиц монотонного комплекса граней доказано, что мощностные верхние оценки достижимы по порядку. Для числа комплексов граней определенного вида (тупиковых, кратчайших, Л^-минимальных) доказана достижимость по порядку логарифма мощностных верхних оценок. При этом верхние оценки максимального числа ДНФ определенного вида для булевой функции считались тривиальными и ставилась задача получения нетривиальных верхних оценок [8, стр. 102].

Публикации. По теме диссертации автором опубликовано 15 научных работ, отражающие основное содержание диссертации, в том числе семь работ в журналах, рекомендованных ВАК РФ [64, 66-71].

Личный вклад автора. Все представленные в диссертации результаты получены лично автором.

Определения и обозначения

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

Множество наборов {(»ь ..., ап) \ аг е {0,1} , г = 1,..., п} называется п-мерным единичным кубом и обозначается Вп, при этом любой набор а = (ах,..., ап) е Вп называется вершиной куба. Вершины (0,...,0) е и (1,..., 1) е Вп обозначаются б и, соответственно, 1 = (1,..., 1) б Вп.

Бинарное отношение, заданное на множестве пар вершин а = (ах,..., ап) и ¡3 = (/?!,...,/Зп) единичного куба Вп, которое определяется условием: аг < /Зг для всех г = 1 ,...,п, называется отношением предшествования и обозначается а < ¡3.

Отношение предшествования определяет частичный порядок на множестве вершин куба Вп. Если ни одна из двух вершин а и ¡3 не предшествуют другой, то вершины а и ¡3 называются несравнимыми.

Расстояние Хэмминга р(й,/3) между вершинами а = (скх,..., ап) и ¡3 = (А, • • • единичного куба Вп называется число координат, для которых вершины различаются, т.е. аг ^ Д , где г = 1,..., п.

Число единичных координат вершины называется нормой вершины и обозначается ||а||.

п п

Очевидно, что р(а,/3) = ^ |аг - ¡Зг\ = ^ (<*г 0 (Зг), где ф — сумма по

г=1 1=1

модулю 2, и ||а|| = ^ аг = р (а, б).

г=1

Гранью единичного куба Вп называется множество вершин

= {(х1,---,хп)евп\хг1=а1,...,хгк = ак},

где сгА. 6 {0,1} для б — 1,... Множество индексов {¿1,..., называется направлением грани, число к — рангом и число (п — к) — размерностью

грани. Множество всех вершин куба Вп является гранью ранга 0 (размерности п).

Грань может быть представлена в виде {х е Вп \ а < х < /3}, где а и /3 — минимальная и максимальная вершины грани, при этом расстояние Хэмминга р{а,/3) равно размерности грани. В таком представлении множество вершин грани называется интервалом размерности к (/с-мерным интервалом).

Если для а = (ai,... ,ап) и ¡3 = (fii,... ,/Зп) обозначить вершины

а к ¡3 = {ai к /?ь ... ,ап к (Зп) и а V /3 = (ai V /Зь ..., ап V @п),

то выполняется а к ¡3 < а V ¡3 и \а V /3|| — ||а к ¡3 | = р{а,р). Тогда интервал /(ск & (3,а\/ ¡3), т.е. интервал с минимальной вершиной а к (3 и максимальной вершиной а V /3, является минимальным интервалом, который содержит одновременно вершины а, (3 и имеет размерность р(а>(3).

Множество вершин {х е Вп | р(о;,х) + р(х,р) < р(а,р)}, в случае сравнимых вершин а < ¡3, совпадает с интервалом /(¿к,/3), а в случае несравнимых вершин а и /3 совпадает с интервалом /(а & /3, а V/?), т.е. представляет наименьший интервал, содержащий одновременно вершины а и (3.

Будем использовать следующие обозначения:

1{а.,Щ — наименьшая грань (интервал), которая содержит одновременно вершины а и /3,

^min (I) и Jmax (-0 — минимальная и максимальная вершины грани I.

Для множества вершин Q С Вп любая грань ICQ называется допустимой гранью.

Подмножество S С Вп называется связным в Вп, если для любых вершин х,у е S существует такая последовательность граней {Ij,j = 1,...,£}

ДОПУСТИМЫХ ДЛЯ S, ЧТО X G Д, у £ It И Ij П /j+i ф 0 для j = 1,..., £ — 1.

Подмножества с Вп, где з = 1,.. • ,г, называются компонентами связности в Вп, если все подмножества являются связными в В" и не

существует грани, которая является допустимой для множества У ^ и содержит вершины из различных подмножеств 5г и 5,.

Булевой функцией п переменных f (х 1,... ,хп) называется отображение Вп —> {0.1}. Множество вершин куба Вп, т.е. множество наборов значений переменных, на которых функция / обращается в единицу (в ноль), обозначается через Nf (соответственно Л^). Множество булевых функций п переменных обозначается через Рп.

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

Комплекс граней М — {1Г, г = 1,..., 1} содержит множество вершин

Мм = и 1Г С Вп. Комплекс граней М называется ком