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

• Автор: Чухров, Игорь Петрович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 189 с. : ил.

Содержание
Введение
Определения и обозначения
Обзор литературы
Глава 1. Тупиковые комплексы граней
1.1. Описание конструкции
1.2. Основные результаты
1.3. Оценки числа граней тупиковых комплексов
1.4. Оценки числа тупиковых комплексов
Глава 2. Ядровые и кратчайшие комплексы граней
2.1. Описание конструкции
2.2. Основные результаты
2.3. Оценки числа граней ядровых комплексов
2.4. Оценки числа кратчайших комплексов граней
Глава 3. Минимальные комплексы граней
3.1. Специальные классы мер сложности
3.2. Описание конструкции
3.3. Основные результаты
3.4. Оценки числа минимальных комплексов граней
Глава 4. Соотношение тупиковых и минимальных комплексов граней
4.1. Описание конструкции
4.2. Основные результаты

4.3. Оценки соотношения числа тупиковых и минимальных комплексов граней
Глава 5. Монотонные комплексы граней с максимальной тенью
нижних единиц
5.1. Описание конструкции
5.2. Основные результаты
5.3. Оценки мощности тени нижних единиц монотонного комплекса граней
Заключение
Литература

Введение
Актуальность работы. Исследования экстремальных комплексов граней в единичном кубе, которым посвящена диссертация, непосредственно связаны с задачей минимизации булевых функций в классе дизъюнктивных нормальных форм (далее ДНФ).
Суть задачи минимизации булевых функций в классе ДНФ состоит в построении формулы вида «дизъюнкция конъюнкций» минимальной сложности для произвольно заданной булевой функции. Эта задача обычно рассматривается в двух эквивалентных моделях — аналитической и геометрической [78]. В аналитической модели используются понятия: булева функция, импликанта, ДНФ, зависящие от п переменных. В геометрической модели эквивалентными понятиями являются подмножество вершин, грань, комплекс граней в п-мерном единичном кубе Вп.
Прикладные задачи минимизации булевых функций возникают в самых различных областях в связи с применением языка алгебры логики. Это задачи синтеза управляющих устройств, задачи анализа надежности, задачи распознавания образов и классификации, задачи принятия решения для представления знаний, задачи оптимизации представления и обработки информации в информационно-коммуникационных технологиях и т.д. Прикладное значение таких задач общепризнано.
Задача минимизации булевых функций может рассматриваться как частный случай задачи синтеза управляющих систем, а именно, как задача синтеза минимальных по сложности формул глубины 2 в базисе {V. & , ->} [45]. Малая глубина ДНФ дает преимущество в надежности и быстродействии перед другими типами схем, но при этом ДНФ существенно проигрывают в схемной сложности. Это обстоятельство способствовало фокусированию исследований на проблемах, которые возникают при рас-

где Шп — множество монотонных булевых функций, которые зависят от п переменных.
Ю. А. Зуев [29] получил оценку
а затем им же эта оценка была уточнена при п —> сю:
где д (п) — максимальная мощность границы антицепи в кубе Вп. С одной стороны, так как, д (п) < 2П это позволило улучшить верхнюю оценку для /гот (п). С другой стороны, породило гипотезу о том, что при п —» сю
справедливость которой позволила бы получить порядок роста для /гщх(п). Однако эта гипотеза была достаточно быстро опровергнута.
Э. Ш. Коспанов [36] получил нижнюю оценку вида д{п) > п“1/6 • 2”. Это привело к тому, что строгие гипотезы о порядке роста д (п) не выдвигались, но казалось естественным, что д (п) = о(2п) при п —>■ оо.
В конце 1987 г. появилось сообщение о том, что 3. Фареди, Дж. Кан, Д. Клейтман получили на основе конструкции А. В. Косточки [37] нижнюю оценку для д (п) порядка 2" с константой 0,05. Данный результат был опубликован в [92], а кроме того, ими была высказана гипотеза, что д{п) < с - 2", где с < 1, при п —> оо.
Кроме тривиальной верхней оценки д (п) < 2п сначала была известна лишь единственная нетривиальная оценка сверху, вытекающая также из результатов А. В. Косточки [37], которая при п —>■ сю имела вид
/йш («) < (1 + 1пп) + 1,