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

• Чухров, Игорь Петрович
• доктор физико-математических наук
• 2013

Оглавление диссертации доктор физико-математических наук Чухров, Игорь Петрович

Содержание

Введение

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

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

Глава 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]. Малая глубина ДНФ дает преимущество в надежности и быстродействии перед другими типами схем, но при этом ДНФ существенно проигрывают в схемной сложности. Это обстоятельство способствовало фокусированию исследований на проблемах, которые возникают при рас-

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

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

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

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

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

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

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

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

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

Множество наборов {(»ь ..., ап) \ аг е {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.

12

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

г

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

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

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

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

I

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

г=1

булевой функции /, если Ым = Л^/.

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

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

Обозначим через ттп — множество перестановок координат в единичном кубе Вп. Для перестановки 7г е 7гп обозначим через 7г (/) — грань,

которая получается из грани I перестановкой координат тт, т.е.

т (К= К^^м = {(^ • ■ ■ ,*,) е в" I ^ы = <п,... = .

Через 7г (М) = {к (/г), г = 1,..., 1} обозначим комплекс граней, который получается из комплекса М = {1г,г = 1,...,/} перестановкой координат тт во всех гранях комплекса.

Комплексы граней называются изоморфными в кубе Вп, если один комплекс может быть получен из другого комплекса перестановкой координат, т.е. для комплексов граней М\ и М2 существует перестановка координат 7г 6 7гп такая, что М\ = -к{М2). При этом грани являются изоморфными только тогда, когда они имеют одинаковую размерность и одинаковое число координат направления грани, для которых в вершинах грани значение равно 0, и, следовательно, одинаковое число координат направления, для которых в вершинах грани значение равно 1.

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

Изоморфизм аналитической и геометрической моделей основан на изоморфизме элементарных конъюнкций и граней единичного куба Вп. Элементарная конъюнкция К = х^ • ... ■ хагТт изоморфна грани В\ = 'ат, ДНФ К\ V ... V К8 изоморфна комплексу граней {Вк ,3 = 1,..., й}, где К3 — элементарная конъюнкция для ] = 1,..., й.

Определение 1. Комплекс граней М называется неприводимым, если после удаления из него любой грани получается комплекс граней не эквивалентный М, т.е. А^м\{1} Для любой грани / е М.

В неприводимом комплексе М каждая грань I е М содержит хотя бы

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

Допустимая грань I для множества вершин С} С. Вп называется максимальной, если не существует грань 3^1 такая, что I С 3 С

Будем говорить, что грань 3 может быть получена уменьшением ранга (увеличением размерности) грани I, если грань 3 может быть получена удалением одной или нескольких координат из направления грани I.

Другими словами, уменьшением ранга (увеличением размерности) из грани I = В^еТ1'1'к'СГк может быть получена любая грань 3 = в^1''^3 такая, что {¿1,... С {гь ... ,ък} и для р = 1,..., в если = гч, то др = ач. При любом уменьшении ранга максимальной грани для множества ф С Вп получается грань, которая не является допустимой для множества ф.

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

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

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

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

з

Представление комплекса граней М в виде М = М^ называется

¿=1

прямым объединением комплексов граней, если любая грань д е М содержится в единственном комплексе М), где ] е {1,... 7}.

Будем использовать следующие обозначения для подмножеств вершин в единичном кубе Вп для 0 < к < т < п:

В^ (а) = {х е Вп | р (а, х) = т} — сфера радиуса т с центром в вершине а;

Б7^ (й) = {х е Вп \ р (а, х) <т] — шар радиуса т с центром в вершине

= (б) = {х е вп I р (6,5) = \\х\\ = к} - т-ый слой куба Вп.

т

$т-кт = {х £ Вп \т — к < ||х|| <т}= У В™ — пояс куба Вп,

г=т—к

состоящий из слоев с номерами г = т — к,..., т.

Функция / е Рп, для которой Nf = где 0 < к < т < п, назы-

вается поясковой булевой функцией и обозначается [х\,... ,хп).

Функция называется симметрической, если она не меняет значения при любой перестановке переменных [8, стр. 110]. Симметрическая функция однозначно представляется в виде дизъюнкции поясковых функций, которые являются компонентами связности симметрической функции.

Понятие сложности комплексов граней базируется на естественном представлении, что при уменьшении ранга или удалении грани сложность

комплекса не возрастает.

Определение 5. Функционал С, определенный на множестве всех комплексов граней (ДНФ), является мерой сложности, если он удовлетворяет аксиомам [82, стр.298]:

1. Аксиома неотрицательности: С (М) > 0 для любого комплекса М.

2. Аксиома монотонности: С (М и {/}) > С (М и {/'}) для любого комплекса М и любой грани I при условии I С V.

3. Аксиома выпуклости: С (М) > £ (Мх) + С (М2) для любого представления комплекса М в виде прямого объединения комплексов М\ и М2.

4. Аксиома инвариантности относительно изоморфизма: С (М) = С (-7Г (М)) для любого комплекса М и любой перестановки координат 7г.

В силу аксиом выпуклости и неотрицательности С (М и {/}) > С (М), т.е. при удалении грани из комплекса мера сложности комплекса не увеличивается.

Примерами мер сложности могут служить следующие функционалы (в терминах ДНФ): Су — число дизъюнкций, — число конъюнкций или — число отрицаний в ДНФ .

Мера сложности, равная числу граней в комплексе М, т.е. число им-пликант в ДНФ (функционал Су + 1), называется длиной и обозначается 1(М).

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

Мера сложности, которая соответствует функционалу где

а + (3 > 0, а > 0, /3 > 0, называется линейной сложностью и обозначается

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

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

Определение 8. Величина С (О) = тт С (М) называется С-слож-

М\Им=Я

ностью множества ф с Вп при покрытии гранями, соответственно, для булевой функции / такой, что Nf = ф, эта величина называется С-сложностью функции / при представлении ДНФ и обозначается £(/).

Определение 9. Прямым объединением множеств комплексов граней и 02 в кубе Вп, для которых не существует граней, которые одновременно принадлежат комплексам из множеств <3\ и 02, называется множество комплексов и 02 = {М | М = Мг и М2, Мг е бъ М2 е 02}.

Будем говорить, что множества С-минимальных комплексов граней и 02, обладают свойством суммируемости для компонент связности, если для любого комплекса М = М\ и М2 е и 02 подмножества и Ым2 являются компонентами связности в единичном кубе, соответственно не имеют одинаковых граней, и М = М\ и М2 является ^-минимальным комплексом.

Для функции / £ Рп и меры сложности С будем обозначать: Т(/) — множество тупиковых комплексов граней функции; М-с (/) — множество ^-минимальных комплексов граней функции;

18

МпС (/) — П — множество С-минимальных комплексов гра-

£е С

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

т (/) — число тупиковых комплексов граней функции;

(/) — число ^-минимальных комплексов граней функции;

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

Хс (/) = т (/)/М£ (/) — отношение числа тупиковых и ^-минимальных комплексов функции;

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

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

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

Максимальное значение параметра qx (/) на множестве функций Рп будем обозначать через qx{'n), например, нс{п) — максимальное число ^-минимальных комплексов граней функции из Рп.

В единичном кубе Вп обозначим:

0п — множество всех граней;

Тп — множество всех тупиковых комплексов граней;

Л4£ — множество ^-минимальных комплексов граней;

Ят-к,тп ~ множество /с-мерных граней в поясе С Вп, где 0 <

к <т <п\

Т'т-кт ~ множество тупиковых комплексов к-мерных граней в поясе С Вп, где 0 < к < т < п;

?т-кт — множество функций из Рп, для которых все максимальные грани являются к-мерными гранями в поясе 3^п_кт и, соответственно,

т (/) С где 0 < к < т < п

Очевидно, что Тп = U Т(/) и М\ = |J Mc(f).

/еР„ /еР„

Асимптотические оценки числовых параметров в единичном кубе Вп всюду получаются при п —> оо.

Знак о (1) означает величину, стремящуюся к нулю при п оо.

Через с£, с'£, с"£ обозначаются сколь угодно малые положительные константы.

Через L^J (соответственно \х]) будем обозначать целую часть (соответственно верхнюю целую часть) числа х.

Под log понимается логарифм по основанию 2.

Под Я (х) понимается функция Н (х) = —xlogx — (1 — x)log(l — х), где 0 < х < 1.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Чухров, Игорь Петрович

Заключение

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

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

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

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

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

Для максимального числа тупиковых (минимальных) комплексов граней функции в кубе Вп получена нижняя оценка по порядку логарифма равная п ■ 2п с константой 1.35 • 2~5 (0.53 • 2~5). Эта оценка превосходит соответствующую оценку для класса симметрических функций, которая по порядку логарифма равна л/п ■ 2п с константой д/2/7г, при п > 256 переменных. Данный факт объясняет существование гипотезы о достижимости максимальных значений числа тупиковых и минимальных ДНФ на классе симметрических функций.

Открытые проблемы. Для кратчайших комплексов граней во всех известных случаях обоснованием /-минимальности комплекса является существование интервально независимого и протыкающего множества собственных вершин для граней кратчайшего комплекса (условие 1 леммы 3.1). Поэтому возникает вопрос о необходимости выполнения этого условия для кратчайших комплексов граней и справедливости следующего утверждения: в единичном кубе мощность максимального интервально независимого множества для подмножества вершин куба совпадает с числом граней в кратчайшем комплексе граней, которые содержат это подмножество вершин.

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

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

Список литературы диссертационного исследования доктор физико-математических наук Чухров, Игорь Петрович, 2013 год

Литература

1. Алон Н., Спенсер Дж. Вероятностный подход. Москва: БИНОМ. Лаборатория знаний, 2007. 320 с.

2. Андреев А. Е. К проблеме минимизации дизъюнктивных нормальных форм // Докл. АН СССР. 1984. Т. 274, № 2. С. 265-269.

3. Андреев А. Е. Об одной модификации градиентного алгоритма // Вестник МГУ. Мат. Мех. 1985. № 3. С. 29-35.

4. Васильев Ю. Л. О длине цикла в п-мерном единичном кубе // Докл. АН СССР. 1963. Т. 148, № 4. С. 753-756.

5. Васильев Ю. Л. О сравнении сложности тупиковых и минимальных д.н.ф. // Проблемы кибернетики. 1963. № 10. С. 5-61.

6. Васильев Ю. Л. К вопросу о числе минимальных и тупиковых дизъюнктивных нормальных форм // Дискретный анализ. Новосибирск: Ин-т математики СО АН СССР. 1964. № 2. С. 3-9.

7. Васильев Ю. Л. Трудности минимизации булевых функций на основе универсальных подходов // Докл. АН СССР. 1966. Т. 171, № 1. С. 13-16.

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

9. Васильев Ю. Л. Массивные классы плотных булевых функций // Методы дискретного анализа в синтезе управляющих систем. Новосибирск: Ин-т математики СО АН СССР. 1978. № 32. С. 21-33.

10. Вебер К. О различных понятиях минимальности дизъюнктивных нормальных форм // Проблемы кибернетики. 1979. № 36. С. 129-158.

11. Винокуров С. Фм Казимиров А. С. Параллельные генетические алгоритмы в задачах минимизации булевых функций // Вестник Томского государственного университета. 2006. № 17. С. 226-230.

12. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с.

13. Глаголев В. В. Верхняя оценка длины цикла в п-мерном единичном кубе // Дискретный анализ. Новосибирск: Ин-т математики СО АН СССР. 1966. № 6. С. 3-7.

14. Глаголев В. В. О длине тупиковой дизъюнктивной нормальной формы // Матем. заметки. 1967. Т. 2, № 6. С. 665-672.

15. Глаголев В. В. Некоторые оценки д. н. ф. булевых функций алгебры логики // Проблемы кибернетики. 1967. Т. 19. С. 75-94.

16. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

17. Дюкова Е. В., Журавлёв Ю. И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // Ж. вы-числ. матем. и матем. физ. 2000. Т. 40, № 8. С. 1264-1278.

18. Евдокимов А. А. О максимальной длине цепи в единичном п-мерном кубе // Матем. заметки. 1969. Т. 6, № 3. С. 309-319.

19. Журавлёв Ю. И. О различных понятиях минимальности д.н.ф. // Сиб. матем. журнал. 1960. Т. 1, № 4. С. 609-611.

20. Журавлёв Ю. И. Об алгоритмах упрощения дизъюнктивных нормальных форм // Докл. АН СССР. 1960. Т. 132, № 2. С. 260-263.

21. Журавлёв Ю. И. О невозможности построения минимальных дизъюнктивных нормальных форм функций алгебры логики в одном классе алгоритмов // Докл. АН СССР. 1960. Т. 132, № 3. С. 504-506.

22. Журавлёв Ю. И. Оценка для числа тупиковых д.н.ф. функций алгебры логики // Сиб. матем. журнал. 1962. Т. 3, № 5. С. 802-804.

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

24. Журавлёв Ю. И. Оценки сложности алгоритмов построения минимальных д.н.ф. для функций алгебры логики // Дискретный анализ. Новосибирск: Ин-т математики СО АН СССР. 1964. № 3. С. 41-47.

25. Журавлёв Ю. И. Алгоритмы построения минимальных дизъюнктивных нормальных форм // Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974. Т. 1. С. 67-98.

26. Журавлёв Ю. И. Об алгоритмах распознавания с представительными наборами (о логических алгоритмах) // Ж. вычисл. матем. и матем. физ. 2002. Т. 42, № 9. С. 1425-1435.

27. Журавлёв Ю. И., Петров И. Б., Рязанов В. В. Дискретные методы диагностики и анализа медицинской информации // Медицина в зеркале информатики. М.: Наука, 2008. С. 113-123.

28. Закревский А. Д., Торопов Н. Р. Минимизация булевых функций многих переменных в классе ДНФ - итеративный метод и программная реализация // ПДМ. 2009. № 1. С. 5-14.

29. Зуев Ю. А. О представлении булевых функций системами линейных неравенств // Кибернетика. 1985. Т. 5. С. 7-9,40.

30. Зуев Ю. А. Пороговые функции и пороговые представления булевых функций // Математические вопросы кибернетики. 1994. Т. 5. С. 5-61.

31. Караханян Л. М., Сапоженко А. А. Оценки параметров д.н.ф. не всюду определенных (частичных) функций алгебры логики // Комбинаторно-алгебраические методы в прикладной математике. Межвузовский сборник. Горький. 1979. С. 48-56.

32. Караханян Л. М. Об эффективности выделения простых импликан-тов минимального ранга // Комбинаторно-алгебраические методы в прикладной математике. Межвузовский сборник. Горький. 1982. С. 66-75.

33. Коршунов А. Д. Сравнение сложности длиннейших и кратчайших д.н.ф. и нижняя оценка числа тупиковых д.н.ф. для почти всех булевых функций // Кибернетика. 1969. Т. 4. С. 1-11.

34. Коршунов А. Д. О сложности кратчайших дизъюнктивных нормальных форм булевых функций // Методы дискретного анализа в изучении булевых функций. Новосибирск: Ин-т математики СО АН СССР. 1981. № 37. С. 9-41.

35. Коршунов А. Д. О сложности кратчайших дизъюнктивных нормальных форм случайных булевых функций // Методы дискретного анализа в оптимизации управляющих систем. Новосибирск: Ин-т математики СО АН СССР. 1983. № 40. С. 25-53.

36. Коспанов Э. Ш. О покрытии шарами единичного радиуса, центры которых несравнимы // Методы дискретного анализа в изучении реализаций логических функций. Новосибирск: Ин-т математики СО АН СССР. 1986. № 44. С. 54-57.

37. Косточка А. В. Максимальный порядок границы фильтра в п-мерном кубе // Методы дискретного анализа в синтезе управляющих систем. Новосибирск: Ин-т математики СО АН СССР. 1984. № 41. С. 49-61.

38. Косточка А. В. Верхняя оценка мощности границы антицепи в п-мерном кубе // Дискретная математика. 1989. Т. 1, № 3. С. 53-61.

39. Кудрявцев В. Б., Андреев А. Е. О сложности алгоритмов // Фундаментальная и прикладная математика. 2009. Т. 15, № 3. С. 135-181.

40. Кузнецов С. Е. О нижней оценке длины кратчайшей д.н.ф. почти всех булевых функций // Вероятностные методы и кибернетика.

Казань: Изд-во Казанского ун-та. 1983. № 19. С. 44-47.

41. Леонтьев В. К. О некоторых метрических задачах в п-мерном кубе // Ж. вычисл. матем. и матем. физ. 2002. Т. 42, № 2. С. 249-255.

42. Леонтьев В. К. Дискретная оптимизация // Ж. вычисл. матем. и

матем. физ. 2007. Т. 47, № 2. С. 338-352.

43. Леонтьев В. К. О гранях единичного п-мерного куба // Ж. вычисл. матем. и матем. физ. 2008. Т. 48, № 6. С. 1126-1139.

44. Лин Син-Лян. О сравнении сложностей минимальных и кратчайших дизъюнктивных нормальных форм для функций алгебры логики // Проблемы кибернетики. 1967. № 18. С. 11-44.

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

46. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. 1963. № 10. С. 63-97.

47. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984. 138 с.

48. Макаров И. М., Виноградская Т. М., Рубчинский А. М., Соколов В. Б. Теория выбора и принятия решений. М.: Наука, 1982. 328 с.

49. Нигматуллин Р. Г. Вариационный принцип в алгебре логики // Дискретный анализ. Новосибирск: Ин-т математики СО АН СССР. 1967. № 10. С. 69-89.

50. Нигматуллин Р. Г. О сложности языков типа иМ // Ж. вычисл. матем. и матем. физ. 1977. Т. 17, № 5. С. 1278-1284.

51. Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991. 240 с.

52. Сапоженко А. А. О наибольшей длине тупиковой дизъюнктивной нормальной формы у почти всех булевых функций // Матем. заметки. 1968. Т. 4, № 6. С. 649-658.

53. Сапоженко А. А. О сложности дизъюнктивных нормальных форм, получаемых с помощью градиентного алгоритма // Дискретный анализ. Новосибирск: Ин-т математики СО АН СССР. 1972. № 21. С. 62-71.

54. Сапоженко А. А. Геометрическое строение почти всех функций алгебры логики // Проблемы кибернетики. 1975. № 30. С. 227-261.

55. Сапоженко А. А. Дизъюнктивные нормальные формы. М.: Издательство МГУ, 1975. 90 с.

56. Сапоженко А. А., Караханян К. JI. Об отрицательных эффектах, связанных с исключением несущественных переменных // Автомат, и вычисл. техн. 1981. № 3. С. 28-35.

57. Сапоженко А. А., Чухров И. П. Минимизация булевых функций в классе дизъюнктивных нормальных форм // Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор. кибернет. 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).

58. Успенский В. А., Верещагин H. К., Шень А. Колмогоровская сложность и алгоритмическая случайность. М.: МЦНМО, 2010. 556 с.

59. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1979. 535 с.

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

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

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

63. Чухров И. П. Оценка максимальной длины тупиковой дизъюнктивной нормальной формы для поясковых функций // Комбинаторно-

алгебраические методы в прикладной математике. Межвузовский сборник. Горький. 1981. С. 137-148.

64. Чухров И. П. О числе тупиковых дизъюнктивных нормальных форм //Докл. АН СССР. 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).

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

66. Чухров И. П. О числе минимальных дизъюнктивных нормальных форм // Докл. АН СССР. 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).

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

68. Чухров И. П. О тупиковых комплексах граней в единичном кубе // Дискретная математика. 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).

69. Чухров И. П. О ядровых и кратчайших комплексах граней в единичном кубе // Дискретный анализ и исследование операций. 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).

70. Чухров И. П. О минимальных комплексах граней в единичном ку-

бе // Дискретный анализ и исследование операций. 2012. Т. 19, № 3. С. 79-99.

71. Чухров И. П. О соотношении тупиковых и минимальных комплексов граней в единичном кубе // Дискретная математика. 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).

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

73. Шоломов JI. А. Представление и исследование порядковых моделей выбора средствами логики первого порядка // Математические вопросы кибернетики. 1998. Т. 7. С. 169-202.

74. Шоломов JI. А. О сложности задач минимизации и сжатия моделей последовательного выбора // Дискретный анализ и исследование операций. 1999. Т. 6, № 3. С. 87-109.

75. Шоломов JI. А. Логические методы построения и анализа моделей выбора // ПДМ. 2009. № 1. С. 38-71.

76. Эрдеш П., Спенсер Дж. Вероятностные методы в комбинаторике. М.: Мир, 1976. 137 с.

77. Юдин Д. Б. Вычислительные методы теории принятия решений. М.: Наука, 1989. 320 с.

78. Яблонский С. В. Функциональные построения в /с-значной логике // Сборник статей по математической логике и ее приложениям

к некоторым вопросам кибернетики. Тр. МИАН СССР. М.: Изд-во АН СССР. 1958. Т. 51. С. 5-142.

79. Яблонский С. В. О невозможности элиминации перебора всех функций из Р2 при решении некоторых задач теории схем // Докл. АН СССР. 1959. Т. 124, № 1. С. 44-47.

80. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. 1959. № 2. С. 75-121.

81. Яблонский С. В. К вопросу об оценке длины тупиковых дизъюнктивных нормальных форм // Проблемы кибернетики. 1962. № 7. С. 229-230.

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

83. Allender Е., Hellerstein L., McCabe P., Pitassi Т., Saks M. Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table // SIAM J. Comput. 2008. Vol. 38, no. 1. P. 38-63.

84. Balas E., Jeroslow R. G. Canonical cuts on the unit hypercube // SIAM J. Appl. Math. 1972. Vol. 23, no. 1. P. 61-69.

85. Buchfuhrer D., Umans C. The complexity of Boolean formula minimization // Journal of Computer and System Sciences. 2011. Vol. 77, no. 1. P. 142-153.

86. 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.

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

88. Coudert O. Two-level logic minimization: an overview // Integration. 1994. Vol. 17, no. 2. P. 97-140.

89. Coudert O., Madre J. New ideas for solving covering problems // The Proceedings of the Design Automation Conference. 1995. P. 641-645.

90. Coudert O., Madre J. On solving covering problems // The Proceedings of the Design Automation Conference. 1996. P. 197-202.

91. Coudert O., Sasao T. Two-level logic minimization // Logic Synthesis and Verification. Kluwer Academic Publishers, 2001. C. 1-21.

92. Furedi Z., Kahn J., Kleitman D. J. Sphere coverings of the hyper-cube with incomparable centers // Discr. Math. 1990. Vol. 83, no. 1. P. 129-134.

93. Gimpel J. F. A method of producing a Boolean function having an arbitrarily prescribed prime implicant table // IEEE Trans. Computers. 1965. no. 14. P. 485-488.

94. Goldsmith J., Hagen M., Mundhenk M. Complexity of DNF minimization and isomorphism testing for monotone formulas // Information and Computation. 2008. Vol. 206, no. 6. P. 760-775.

95. Jeroslow R. G. On defining sets of vertices of hypercube by linear inequalities // Discr. Math. 1975. Vol. 11, no. 2. P. 119-124.

96. Hammer R. L., Ibaraki T., Peled U. N. Threshold numbers and threshold completions // Ann. Discr. Math. 1981. Vol. 11. P. 125-145.

97. Li M., Vitanyi P. An introduction to Kolmogorov complexity and its applications. 2nd edition. Springer-Verlag New York, Inc., 1997. 637 p.

188

98. Meinel Ch., Theobald T.. Algorithms and Data Structures in VLSI-Design: OBDD Foundations. Springer-Verlag, 1998. 267 p.

99. McCluskey, Jr. E. J. Minimization of Boolean functions // Bell Syst. Tech. Jour. 1956. Vol. 35, no. 6. P. 1417-1444.

100. Pippenger N. The shortest disjunctive normal form of a random Boolean function // Random Structures & Algorithms. 2003. Vol. 22, no. 2. P. 161-186.

101. Quine W. V. The problem of simplifying truth functions // The American Mathematical Monthly. 1952. Vol. 59. P. 521-531.

102. Quine W. V. A way to simplify truth functions // The American Mathematical Monthly. 1955. Vol. 62, no. 9. P. 627-631.

103. Quine W. V. On cores and prime implicants of truth functions // The

American Mathematical Monthly. 1959. Vol. 66, no. 9. P. 755-760.

i

104. Sieling D. The complexity of minimizing and learning OBDDs and FBDDs // Discrete Applied Mathematics. 2002. Vol. 122, no. 1-3. P. 263-282.

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