Сложность функций из замкнутых классов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ Й ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

механико-математический факультет

л

На правах рукописи 5-92-408

УГОЛЬНИКОВ Александр Борисович

УДК 519.95

СЛОЖНОСТЬ ФУНКЦИЙ ИЗ ЗАМКНУТЫХ КЛАССОВ

Специальность: 01.01.09 - математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва - 1992

Работа выполнена на механико-математическом факультете МГУ

Официальные оппоненты: доктор физико-математических наук,

профессор М.М.Глухов,

доктор физико-математических наук, профессор Н.К.Косовский,

доктор физико-математических наук, профессор Ю.И.Янов

Ведущая организация - Институт математики Сибирского

отделения РАН

Защита диссертации состоится ¥ _ 199«^ г.

в 16 час. 05 мин. на заседании специализированного Совета Д.053.05.05 при Московском государственном университете им. М.В.Ломоносова по адресу: 119899, ГСП, Москва, Ленинские Горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан ¿^^^¿¿Л 199^ г.

Ученый секретарь специализированного Совета Д.053.05.05 при МГУ доктор физико-математических наук

В.НЛубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Одном из основных задач дискретной математики и математической кибернетики является задача изучения модельных классов управляющих систем с точки зрения их сложности (задача синтеза управляющих систем). Схемы из функциональных элементов и формулы, реализующие булевы функции, относятся к числу основных модельных классов управляющих систем. Задачу синтеза управляющих систем можно охарактеризовать следующим образом. Задан некоторый набор элементарных средств и правила построения из них более сложных объектов (схем или формул). Кроме того заданы меры сложности. Основными мерами сложности схем и форьул являются число (или сумма весов) элементов и глубина. Сумму весов элементов называют также сложностью схемы (формулы). Сложность характеризует стоимость, а глубина - время работы построенных схем или формул. Требуется построить для каждой функции талую схему (или формулу), которая реализует эту функцию и является наилучшей относительно выбранной меры сложности. Имеется простой метод для нахождения таких оптимальных схем, основывающийся на переборе всех схем данной сложности. Однако этот метод практически не применим, так как требует для своей реализации большого числа шагов. Поэтому возникает задача о разработке таких методов синтеза, которые позволяют строить для всех функций из заданного множества Н относительно хорошие схемы и при этом существенно проще перебора всех схем. Функции, значения которых равны сложности оптимальных схем или формул дая самых сложных (относительно выбранной меры сложности) функций из множества Н , получили название функций Шеннона (по данной мере сложности).

Впервые подобные постановки задач были рассмотрены в работах К.Шеннона и Дж.Риордана. Б этих работах для некоторых классов управляющих систем были получены оценки для соответствующих функций Шеннона.

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

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

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

В классификации Поста важное место занимает счетное семейство замкнутых классов монотонных функций. Поведение функции Шеннона при реализации монотонных булевых функций в разных классах управляющих систем изучали многие авторы, в том числе С.В.Яблонский, Э.И.Нечипорук, В.И.Резник, В.К.Коробков, Е.Анселъ, Н.П.Редькин. В результате этих исследований были получены верхние оценки для соответствующих функций Шеннона,по порядку равные мощностной нижней оценке. Асимптотически точная формула для функции Шеннона при реализации монотонных булевых функций схемами из функциональных элементов в произвольном полном конечном базисе получена автором диссертации в 1974 г. Позднее аналогичный результат был получен Н.Пшшендаером .

P¿pреп-ул. /V. У- The zea,6¿^.a.i¿on о{ -mono éo tte вообая

¿zc/!cí¿or>$ // Рыс. #¿h ASM en

P с Тб* x¿ éy &oo¿fas>

f-1/ъс íiO-h-i // Maí/}. S-ys TA ecig-. - /9 - f. 2 ÍS-3 76.

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

тонных функций сильно.отличаются от множества . Поэтому

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

Вопросы, подобные рассмотренным выше, возникай? также относительно другой меры сложности схем и формул - глубины. Глубина является одним из основных показателей работы реальных устройств. Поэтому представляется важным разработка методов синтеза схем и формул минимальной глубины. Для полных и полных монотонных конечных систем хорошо известны линейные оценки для функции Шеннона по глубине для схем и формул (см., например, работы С.Б.Гадшова и С.А.Ложкина).

Как правило, при разработке вычислительных устройств возникает необходимость минимизировать сложности схем и формул одновременно по нескольким параметрам, например, по числу элементов и времени работы. Поэтому возникает' вопрос: какова взаимосвязь этих двух мер сложности - числа элементов (или числа вховдений символов переменных) и глубины - дая произвольной булевой

функции. Ответ на этот вопрос для случая полных систем получен ВЛиХрапченко и Ф.Сшрой, а для полных монотонных систем И.Ве-генером. Систему функций 01 будем называть равномерной, . если существуют константы с и (зависящие от Оь ) такие, что для любой функции / из [<52] (замкнутого класса порожденного системой 01 ) глубина (4) и сложность ({) минимальных формул над 01 , реализующих функцию £ , удовлётворяют неравенству

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

При построении схем и формул над конечный! системами базисные элементы могут иметь разные сложностные характеристики, что дает определенное преимущество одним элементам перед другими, Причем зта разница может быть столь большой, что можно считать веса (или иные параметры) некоторых элементов нулевыми. Такой подход дает возможность выявить более выпукло роль элементов того или иного типа при реализации функций из заданного множества. Таким образом, возникает задача о синтезе схем и формул в выродценных базисах, а именно, требуется найти минимальное число элементов (сумму весов) некоторых сортов (положительная часть базиса), необходимое для реализации произвольной булевой функции из заданного множества, при использовании произвольного числа элементов других сортов (нулевая часть базиса). Случаи полных систем, нулевая часть которых порождает замкнутые классы линейных функций., конъюнкций или дизъюнкций, изучены Э.И.Кечипоруком. Задачей об инверсионной сложности схем и формул занимались Э.Гилберт, А.А.Марков и Э.И.Иечипорук. Они получили точные формулы для сложности реализации функций схемами и формулами в базисах, нулевая часть которых порождает множество всех монотонных булевых функций, а положительная часть состоит из отрицания.

Известно много примеров, которые говорят о принципиальных отличиях многозначных логик от двузначной (см., например, результаты Ю.И.Янова и А.А.Мучника). Возникает вопрос: каковы эти отличия со слогшостной точки зрения.

А

Цель работы. Лдя всех нетривиальных заткнутых классов булевых функций получить асимптотически точные формулы для соот-' ветствутощих функций Шеннона при реализации функций схемами в произвольном полном конечном базисе с положительными весаш всех элементов. Разработать методы синтеза схем и формул в неполных и выроди,энных базисах. Для любой конечной системы булевых функций 01 установить взаимосвязь двух мер сложности формул над бь (числа символов переменных и глубины), реализующих функции из множества Г1^1! • Выявить отличия многозначных логик от двузначной со слотаостной точки зрения.

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

Научная новизна. Все основные результаты диссертации являются новыми и опубликованы в работах автора. В диссертации для всех нетривиальных замкнутых классов булевых функций получены асимптотически точные формулы для соответствующих функций Шеннона для схем из функциональных элементов в произвольном полном конечном базисе с положительными весаш всех элементов, входящих в базис разработаны методы синтеза схем и формул в неполных и вырожденных базисах; показано, что любая конечная система булевых функций является равномерной * ; установлена полиномиальная эквивалентность конечных систем, порождающих один и тот ж замкнутый класс булевых функций. В диссертации также приведены: пример неравномерной системы функций 3-значной логики, пример двух систем функций 4-значной логики, порождающих один и тот же замкнутый класс, не являющихся полиномиально эквивалентными, пример последовательности функций 5-значной логики,

•*) Позднее для некоторых классов управляющих систем аналогичные результаты получены А.S.Андреевым (Андреев А.Е. Метод бесповторной редукции синтеза самокорректирующихся схем// ДАН СССР.- 1985.- 283, 2,- С. 265-269.).

* *) Позднее аналогичный результат получил М.Рагаз ( Йа.% a.Z M■ РАъаЛвс & a.a4ée аЛреёъал, // Лтг/,. Aîné/,. ¿O^C UneC G г-а-леС Рл^m Son -¡сАьсьд .'-

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

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

Апробация работы. Результаты диссертации излагались в Международном математическом Центре им. С.Банаха (Варшава, 1985), на У1 Международной конференции по теории вычислений (Казань, 1987), на III Международном рабочем семинаре по математическим вопросам кибернетики (Братислава, 1987), на советско-германском семинаре по дискретной математике (Самарканд, 1986), на Международном рабочем семинаре по дискретной математике и ее приложениям (Митвайда, 1991), на У1, УН и УШ Всесоюзных конференциях по теоретической кибернетике (Саратов,' 1983; Иркутск, 1985; Горький, 1988), на 1У Всесоюзной конференции по применению методов математической логики (Таллин, 1986), на I и II Всесоюзных семинарах по дискретной математике и ее приложениям (Москва, 1984 и 1987), на Всесоюзных школах по сложности управляющих систем (Новосибирск, 1989; Ташкент, 1991 ), на Ломоносовских чтениях в МГУ, на семинарах по кибернетике под руководством чл.-корр. РАН С.В.Яблонского и семинарах по теории сложности управляющих систем под руководством чл.-корр. РАН 0.Б.Лупа-нова в МГУ, а также на некоторых других конференциях, школах и семинарах.

Публикации. Основные результаты диссертации опубликованы в работах автора [I-Il] . список которых приводится в конце автореферата. Среда них нет работ, написанных в соавторстве.

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы. Первая глава разбита на 2 параграфа, вторая: - на 6, третья - на 5, четвертая - на 4. Объем

работы 222 страницы. Список литературы содержит 90 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Во второй главе рассматривается задача о реализации булевых функций из замкнутых классов схемами из функциональных элементов в произвольном полном конечном базисе с положительными весами всех функций, входящих в базис. Основным результатом этой главы является теорема 2.1, в которой для любой полной конечной системы (X получена верхняя оценка для функции /Л(Р33Сго) (функции Шеннона при реализации монотонных

булевых функций от переменных эс1 , аг^ , удовлетворяющих условию < а.1 > , схемами в базисе Ос ). На основе этой оценки полностью решается вопрос о поведении (функции Шеннона при реализации булевых функций из замкнутых классов схемами над произвольной полной конечной системой и устанавливаются асимптотически точные формулы для функций Шеннона всех "нетривиальных" замкнутых классов булевых функций. Показано, что для любого полного конечного базиса 01 и любого замкнутого класса булевых функций функция Шеннона, соответствующая этому классу, или имеет не более чем линейный порядок роста, или асимпто-

, п-г

тически равна либо $ — , либо 5 , либо

Л- л.

Гг * о л 2Л

» либо о/у^- , где § - минимальным при-

веденный вес элементов из (теорема 2.2 диссертации). Та-

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

Б § I описываются упорядоченные разбиения множества наборов из нулей и единиц на непересекающиеся цепи. В § 2 дается кодирование монотонных функций. В § 3 строится схема, реализующая

оператор декодирования. В §§ 4,5 доказываются теоремы 2.1 и 2.2 соответственно. В § 6 приводятся вспомогательные операторы, использующиеся при построении оператора декодирования.

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

01 и любой функции из [¿£-3 . Изучается также вопрос о сложности реализации функций схемами из функциональных элементов в базисах, содержащих элементы с нулевыми весами.

В § I приведены две серии представлений монотонных функции. Показано, что каждая монотонная булева функция может быть получена суперпозицией функций, получающихся из нее отождествлением переменных, и специальной функции, удовлетворяющей условию < а""1 > (или А "" > ) от фиксированного числа переменных, т =2, 3,...

В § 2 на основе приведенных представлений для любой конечной системы булевых функций 01 и любой функции / из получены линейные верхние оценки для глубины и экспоненциальные верхние оценки для сложности (числа символов переменных) формул над 01 , реализующих функцию / (теоремы 3.1 и 3.2 диссертации). На основе этих результатов впервые получено полное (с точностью до порядка роста) описание поведения функции Шеннона по глубине для всех замкнутых классов булевых функций. Показано, что для любой конечной системы булевых функций 01 функция Шеннона по глубине, соответствующая классу [<52] , или равна константе, или по порядку равна либо тг , либо ^ н

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

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

конечных систем булевых функций Ol и ¿г таких, что

£ [.&] > существуют такие константа с и oi (зависящие от 01 и •£- ), что для всякой функции { из [0Z] выполняется неравенство

(п $ «к < а))с

(теорема 3.4 диссертации).

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

Z> ^ С/) . Отметим также, что хотя, как известно, при реализации функций схемами из функциональных элементов любые две конечные системы функций (порождающие один и тот же замкнутый класс) линейно эквивалентны, получить усиление теоремы 3.4, то есть установить аналогичное утверждение для формул, вообще говоря, нельзя дахе для полных систем (см., например, работы Э.П.Печшюрука, Г,;.Ы. Рохлиной, П.А.Субботовской, В.м.Храпченко).

Б § 5 получены верхние и нижние оценки дал сложности реализации функций из замкнутых классов схемами из функциональных элементов и базисах OL , нороэдаацих эти классы, и таких, что пх нулевая часть П (&) порождает мю'хество F^"1 (шояеетво

всех функций, удовлетворяющих условию <г ^ > ), ^ =2, 3..... м . Получено описание соответствующих функций Шеннона. Показано, что если (ог) порождает множество F^*3 , то для любого замкнутого класса F , удовлетворяющего условию £ F » соответствующая функция Шеннона или по порядку равна либо константе, либо П. , или имеет экспоненциальный рост; если не (Gt) порождает множество F."1 (2 « ^ < ),

то для любого замкнутого класса Р , удовлетворяющего условию Р™ ё Р , соответствующая функция Шеннона или по порядку равна константе, или имеет полиномиальный рост (теоремы 3.9 и 3.10 диссертации). При получении серии этих результатов используются разработанные автором методы получения верхних и нижних оценок для сложности реализации функций, удовлетворяющих условию < й"1 > , схемаг® из функциональных элементов в базисе = 1-* , (где + х1 , ...

•••» + 1 ) = V Х;*)), = 2, 3, ... Эти методы

7 £ ' * У 5 л> «■ 1

основываются на оценках для сложности реализации этих же функций схемами в полном базисе и { 0} и монотонных функций, удовлетворяющих условию >, схемами в базисе { ^ ^^ ] .

В частности, показано, что минимальные схемы в базисе ,

реализующие минимальные функции в шожестве ^ (то есть такие, меньше которых нет в Р™ ) не содержат импликаций. Это позволяет переносить известные нижние оценки для сложности реализации монотонных функций схемами в полном монотонном базисе (см., например, работы А.Е.Андреева и А.А.Разборова) на случай схем в базисе , реализующих "соответствующие" минимальные функции из класса Р^

В четвертой главе рассматривается задача о реализации функций из Рк (множества всех функций к -значной логики) формулами в неполных базисах, к £ 2. Теоремы, приведенные в главе 4, выявляют отличия многозначных логик от двузначной с точки зрения теории сложности. Приведены также обобщения некоторых результатов для функций двузначной логики.

В § I приведен пример неравномерной системы функций в Р2 (теорема 4,1 диссертации). В § 2 приведен пример двух систем функций 4-значной логики, которые порождают один и тот же замкнутый класс в Р^ и при этом не являются полиномиально эквивалентными (теорема 4.2 диссертации). В § 3 построен пример последовательности функций 5-значной логики, сложность которых в классе формул над некоторой неполной конечной системой имеет рост двойной экспоненты от числа переменных (теорема 4.3 диссертации).

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

семейства, и любой последовательности функций { ( агг , ... ..., ) из F глубина минимальных формул над любой конечной системой (порождающей f ) имеет не более чем линейный, а сложность - не более чем экспоненциальный, рост от числа переменных (теоремы 4.5-4.7 диссертации).

Таким образом, в диссертации получены следующие основные результаты»

1. Для всех нетривиальных замкнутых классов булевых функций получены асимптотически точные формулы для соответствующих функций Шеннона (по сложности) при реализации функций схемами из функциональных элементов в произвольном полном конечном базисе из элементов с положительными весами.

I

2. Для любой конечной системы булевых функций Ol и любой функции / из [iTt] получены линейные верхние оценки для глубины и экспоненциальные верхние оценки (от числа переменных) для сложности формул над Ol , реализующих функцию / ,

3. Показано, что любая конечная система булевых функций является равномерной.

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

4. Приведен пример последовательности функций 5-значной логики, сложность которых в классе формул над некоторой конечной системой имеет рост двойной экспоненты от числа переменных.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Угольников А.Б. О реализации функций из замкнутых классов схемами из функциональных элементов в полном базисе // ДАН СССР,- 1983.- 271, I.- С. 49-51.

2. Угольников А.Б. О сложности реализации булевых функций схемами в базисе из медианы и импликации // Вестник Московского ун-та. Сер. I. Математика. Механика,- 1987.- 3.- С. 87-89.

3. Угольников А.Б. О глубине и полиномиальной эквивалентности формул для замкнутых классов двузначной логики // Математические заметки.- 1987.- 42, 4,- С. 602-612.

4. Угольников А.Б. Синтез схем и формул в неполных и вырожденных базисах // III Международный рабочий семинар "Математи-

ческие вопросы кибернетики. МВК-07".- Тезисы докладов.-Братислава, Г987.- С. 56-60.

5. Угольников А.Б. О реализации функций из замкнутых классов схемами из функциональных элементов // Математические вопросы кибернетики. Вып. I,- К.: Наука, 1988.- С. 89-113.

6. Угольников А.Б. О глубине форьзул в неполных базисах // Математические вопросы кибернетики. Вып. I,- М.: Наука, 1988.- С. 242-245.

7. Угольников А.Б. О глубине и сложности формул, реализующих функции из замкнутых классов // ДАН СССР,- 1988,- 298, 6,-С. I34I-I344.|

8. Угольников А.Б. Синтез схем в вырожденных базисах // Тезисы докладов 8-й Всес. конф. "Проблемы теоретической кибернетики", Горький,- 1988.- ч. 2.- С. 141.

9. Угольников А.Б. О сложности реализации формулами одной последовательности функций многозначной логики // Математические вопросы кибернетики. Вып. 2.- М.: Наука, 1989.- С. 174-176.

10. Угольников А.Б. Глубина формул в некоторых классах к -значной логики // Вестник Московского ун-та. Сер. I. Математика. Механика,- 1991,- 4.- С. 44-47.

11. Zi^ot'xiIrov A.ß■ Coibfy&xiiy cunoi Uepih &f

ttCL&xing ^■ze./ia'iconi

c£a£4eS // Pioc. of Ръ/пс/лю&н iaA о/ &>»,/>. , ¿ес€иъе ¿*> Cor»/*. Sc<'. J ?J>.-

S9S?.- SftiAg&c - t - f>. -46 f.

Рукопись поступила в издательский отдел 2 октября 1992 года.