Введение к работе
Актуальность темы исследования. Одном из основных задач дискретной математики и математической кибернетики является задача изучения модельных классов управляющих систем с точки зрения их сложности (задача синтеза управляющих систем). Схемы из функциональных элементов и формулы, реализующие булевы функции, относятся к числу основных модельных классов управляющих систем. Задачу синтеза управляющих систем можно охарактеризовать следующим образом. Задан некоторый набор элементарных средств и правила построения из них более сложных объектов (схем или формул). Кроме того заданы меры сложности. Основными мерами сложности схем и формул являются число (или сумма весов) элементов и глубина. Сушу весов элементов называют также сложностью схемы (формулы). Сложность характеризует стоимость, а глубина - время работы построенных схем или формул. Требуется построить для каждой функции такую схему (или формулу), которая реализует эту функцию и является наилучшей относительно выбранной меры сложности. Имеется простой метод для нахождения таких оптимальных схем, основывающийся на переборе всех схем данной сложности. Однако этот метод практически не применим, так как требует для своей реализации большого числа шагов. Поэтому возникает задача о разработке таких методов синтеза, которые позволяют строить для всех функций из заданного множества Н относительно хорошие схемы и при этом существенно проще перебора всех схем. Функции, значения которых равны сложности оптимальных схем или формул для самых сложных (относительно выбранной меры сложности) функций из множества И , получили название функций Шеннона (по данной мере сложности).
Впервые подобные постановки задач были рассмотрены в работах К.Шеннона и Дж.Риордана. Б этих работах для некоторых классов управляющих систем были получены оценки для соответствующих функций Шеннона.
Асимптотическое поведение функции Шеннона при реализации всех булевых функций от п. переменных схемами из функциональных элементов и формулами в произвольном полном конечном базисе с положительными весами всех элементов было полностью изучено
в работах О.Б.Лупанова. Из результатов этих работ следует, что почти все булевы функции от данного числа переменных являются асимптотически самыми сложными. Поэтому, с одной стороны, представляет интерес задача выделения классов функций, допускающих более простую реализации, и разработка асимптотически оптимальных методов синтеза схем и формул для функций из этих классов. С другой стороны, представляется важным для различных естественных классификаций булевых функций иметь описание поведения функции Шеннона при реализации Функций из соответствующих классов схемами или формулами, то есть охарактеризовать даннуэ классификацию со сложностнои точки зрения.
Одной из наиболее известных и лучше всего изученных с функциональной точки зрения классификаций булевых функций является описание Поста множества всех зашшутых относительно операции суперпозиции классов функций алгебры логики. Таким образом, возникает задача о реализации функций из классов Поста схемами и формулами над конечными системами. В этой задаче можно выделить два направления исследований: синтез схем и формул в полных базисах и синтез схем и формул в неполных базисах.
В классификации Поста ванное мсто занимает счетное семейство замкнутых классов монотонных функций. Поведение функции Шеннона при реализации монотонных булевых функций в разных классах управляющих систем изучали многие авторы, в том числе С.В.Яблонский, Э.Й.Нечипорук, В.И.Резник, В.К.Коробков, 2.Ансель, П.П.Редькин. В результате этих исследований были получены верхние оценки для соответствующих функций Шеннона,по порядку равные мощностной нижней оценке. Асимптотически точная формула ддя функции Шеннона при реализации монотонных булевых функций схемами из функциональных элементов в произвольном полном конечном базисе получена автором диссертации в 1974 г. Позднее аналогичный результат был получен Н.Пшшенддером *'.
*) pippetio/л //. У- The г^сві^аііоп of mono iotte вообал fzc/iciionS // Ргечг. fih >?»» ASM S^*,p. on itJrt&vg' c-f Согн^сь-ііьд , //&ыА*« , PA . - f?6 . - / -2^ -no
Pcf>b-et>tit/i /V. у, у/,? сг>)ъуЬ-&хїy с^Ґ л^йв/йре Доо&ал fan с ico-h-i // Маіб . Sys e*,f ТА eciy. - /9 ?P. - t*. - /- 2 *S- 3 -/6.
При рассмотрении классов Поста следующей естественной задачей является задача синтеза схем и формул в базисах, которые состоят из функций, принадлежащих рассматриваемым классам. Следует отметить, что вышеупомянутые методы синтеза схем (и формул) в полных базисах существенным образом использовали полноту базиса, поскольку, как правило, они опирались на принцип локального кодирования, предложенный О.Е.Лупановым. Поэтому эти методы не могли быть автоматически перенесены на случай схем и формул в неполных базисах. Таким образом, задача в такой постановке потребовала разработки новых методов синтеза. Впервые подобные вопросы рассматривались Э.И.Нечипоруком. Им получены асимптотически точные формулы для функций Шеннона при реализации функций, принадлежащих классам сохранения констант, схемами из функциональных элементов в неполных базисах. Для ряда замкнутых классов асимптотически точные формулы для функции Шеннона для схем и формул в неполных базисах получены автором (они не включены в диссертацию). Отметим, что эти результаты получены для замкнутых классов, которые не очень сильно отличаются от от множества Q всех булевых функций. Замкнутые классы монотонных функций сильно.отличаются от множества /% . Поэтому для них нужны методы синтеза, учитывающие специфику рассматриваемых классов. Для класса всех монотонных функций асимптотически наилучшие методы синтеза схем и формул в полных монотонных базисах были разработаны А.Е.Андреевым в 1985 г.
Вопросы, подобные рассмотренным выше, возникают также относительно другой меры сложности схем и формул - глубины. Глубина является одним из основных показателей работы реальных устройств. Поэтому представляется важным разработка методов синтеза схем и формул минимальной глубины. Для полных и полных монотонных конечных систем хорошо известны линейные оценки для функции Шеннона по глубине для схем и формул (см., например, работы С.Б.Гашкова и С.А.Ложкина).
Как правило, при разработке вычислительных устройств возникает необходимость минимизировать сложности схем и формул одновременно по нескольким параметрам, например, по числу элементов и времени работы. Поэтому возникает' вопрос: какова взаимосвязь этих двух мер сложности - числа элементов (или числа вхождений символов переменных) и глубины - для произвольной булевой
функции. Ответ на этот вопрос для случая полных систем получен ВДІ.Храпченко и Ф.Спирой, а для полных монотонных систем И.Ве-генером. Систему функций Ob будем называть равномерной, . если существуют константы с vi d (зависящие от Ol ) такие, что для любой функции ^ из [<9Z] (замкнутого класса порожденного системой 01 ) глубина Doc (4) и сложность
1_ф ({) минимальных формул над Ol , реализующих функцию
/ , удовлетворяют неравенству
В вышеупомянутых работах было показано, что любая полная (полная монотонная) конечная система булевых функций является равномерной.
При построении схем и формул над конечніші системами базисные элементы могут иметь разные сложностью характеристики, что дает определенное преимущество одним элементам перед другими. Причем зта разница может быть столь большой, что можно считать веса (или иные параметры) некоторых элементов нулевыми. Такой подход дает возможность выявить более выпукло роль элементов того или иного типа при реализации функций из заданного множества. Таким образом, возникает задача о синтезе схем и формул в выродценных базисах, а именно, требуется найти минимальное число элементов (сумму весов) некоторых сортов (положительная часть базиса), необходимое для реализации произвольной булевой функции из заданного множества, при использовании произвольного числа элементов других сортов (нулевая часть базиса). Случаи полных систем, нулевая часть которых порождает замкнутые классы линейных функций, конъюнкций или дизъюнкций, изучены Э.И.Нечипоруком. Задачей об инверсионной слозкности схем и формул занимались Э.Гилберт, А.А.Ыарков и Э.И.Иечипорук. Они получили точные формулы для сложности реализации функций схемами и формулами в базисах, нулевая часть которых порождает множество всех монотонных булевых функций, а положительная часть состоит из отрицания.
Известно много примеров, которые говорят о принципиальных отличиях многозначных логик от двузначной (см., например, результаты Ю.И.Янова и А.А.Мучника). Возникает вопрос: каковы эти отличия со слогшостной точки зрения.
Цель работы. Лдя всех нетривиальных заткнутых классов булевых функций получить асимптотически точные формулы для соот-' ветствующих функций Шеннона при реализации функций схемами в произвольном полном конечном базисе с положительными весами всех элементов. Разработать методы синтеза схем и формул в неполных и вырожденных базисах. Для любой конечной системы булевых функций 01 установить взаимосвязь двух мер сложности формул над бь (числа символов переменных и глубины), реализующих функции из множества f^J Выявить отличия многозначных логик от двузначной со слотаостной точки зрения.
Методы исследований. В работе используются методы дискретной математики и математической кибернетики.
Научная новизна. Все основные результаты диссертации являются новыми и опубликованы в работах автора. В диссертации для всех нетривиальных замкнутых классов булевых функций получены асимптотически точные формулы для соответствующих функций Шеннона для схем из функциональных элементов в произвольном полном конечном базисе с положительными весами всех элементов, входящих в базис *'\ разработаны методы синтеза схем и формул в неполных и вырожденных базисах; показано, что любая конечная система булевых функций является равномерной * *'; установлена полиномиальная эквивалентность конечных систем, порождающих один и тот же замкнутый класс булевых функций. В диссертации также приведены: пример неравномерной системы Функций 3-значной логики, пример двух систем функций 4-значной логики, порождающих один и тот же замкнутый класс, не являющихся полиномиально эквивалентными, пример последовательности функций 5-значной логики,
*) Позднее для некоторых классов управляющих систем аналогичные результаты получены А.Е.Андреевым (Андреев А.Е. Метод бесповторной редукции синтеза самокорректирующихся схем// ДАН СССР.- 1985.- 283, 2,- С. 265-269.).
* *) Позднее аналогичный результат получил М.Рагаэ ( ЙО.ОО.Х. М- РАъаЛвс &а.а4ёе a^tgteti // Л*?/,. fi/a.A .
сложность которых в классе формул над некоторой конечной, системой имеет рост двойной экспоненты от числа переменных. Найдены достаточные условия для замкнутых классов к -эначной логики, при выполнении которых глубина любой функции из рассматриваемых классов в классе формул над произвольной конечной системой, порождающей эти классы, имеет не более чем линейный, а сложность - не более чем экспоненциальный, рост от числа переменных, к 2.
Практическая и теоретическая ценность» Диссертация носит теоретический характер. Полученные результаты и разработанные методы могут найти применение при проектировании сложных управляющих систем, в теории функциональных систем, в теории сложности алгоритмов и вычислений.
Апробация работы. Результаты диссертации излагались в Международном математическом Центре им. С.Банаха (Варшава, 1985), на УІ Международной конференции по теории вычислений (Казань, 1987), на III Международном рабочем семинаре по математическим вопросам кибернетики (Братислава, 1987), на советско-германском семинаре по дискретной математике (Самарканд, 1986), на Международном рабочем семинаре по дискретной математике и ее приложениям (Митвайда, 1991), на УІ, УП и УІІІ Всесоюзных конференциях по теоретической кибернетике (Саратов,' 1983; Иркутск, 1985; Горький, 1988), на ІУ Всесоюзной конференции по применению методов математической логики (Таллин, 1986), на I и II Всесоюзных семинарах по дискретной математике и ее приложениям (Москва, 1984 и 1987), на Всесоюзных школах по сложности управляющих систем (Новосибирск, 1989; Ташкент, 1991 ), на Ломоносовских чтениях в МГУ, на семинарах по кибернетике под руководством чл.-корр. РАН С.В.Яблонского и семинарах по теории сложности управляющих систем под руководством чл.-корр. РАН 0.Б.Лупа-нова в МГУ, а такие на некоторых других конференциях, школах и семинарах.
Публикации. Основные результаты диссертации опубликованы в работах автора [I-Il] . список которых приводится в конце автореферата. Среди них нет работ, написанных в соавторстве.
Структура и объем работе. Диссертация состоит из введения, четырех глав и списка литературы. Первая глава разбита на 2 параграфа, вторач - на 6, третья - на 5, четвертая - на 4. Объем
работы 222 страницы. Список литературы содержит 90 наименований.