Введение к работе
Актуальность темы. Вопросы синтеза управляющих систем (УС) занимают одно из центральных мест в проблематике математической кибернетики П71. Общая актуальность исследований в этой области обусловлена важностью многочисленных задач синтеза, возникающих в различных разделах науки и техники.
К числу важнейших модельных объектов математической теории синтеза УС относятся формулы (суперпозиции) и схемы из функциональных элементов, реализующие булевы функции. Эти классы УС хорошо изучены, здесь имеется значительное число работ и результатов (см. [8,9,11,20,21.]). Гораздо менее до последнего времени были изучены некоторые близкие классы УС, такие как введенные А. В. Кузнецовым неявные и параметрические представления функций [51, описанные А. Берксом и Дж. Райтом сети из функциональных элементов И] и некоторые другие. Общей чертой, сближающей эти УС с формулами и схемами из функциональных элементов, является использование систем функциональных уравнений для описания их функционирования. Отличие состоит в том, что в случае формул и схем системы уравнений оказываются явными и допускают прямое вычисление реализуемых функций, в то время как в в случае рассматриваемых УС реализуемые функции отыскиваются как решения систем неявных уравнений.
Понятие параметрического (неявного) представления было введено А. В. Кузнецовым как обобщение понятия представления функций й-значной логики Pfi формулами (суперпозициями). В общем случае рассматривается система уравнений
' VT1 гя,у{,-...,уч.хг) = ^Ц xn,yv...,yq,z),
(1)
. *рЦ хпщ ц,г\ = *рЦ хп,щ yq.z).
где «1 *р, ^, .... *р - некоторые формулы над заданной
системой функций A, 4s Pfe, составленные из символов функций, входящих в А, символов основных переменных Jj , .... X внутренних переменных {трсшетров) у,, ..., у_, и выделенной переменной 2 (в частности, эти формулы могут являться символами переменных). Говорят, что система (1) является паралетрическиж представлениел функции f{x^,...,xn), если эта система имеет по
меньшей мере одно решение ^ = ^Ц хп) у =
gq{xv... ,хп), z = g0(i1 хп) в функциях от основных
переменных, причем во всяком таком решении значение выделенной
переменной z определено однозначно и равно /Ц хп) (т. е. в
любом решении ^0Ц,...дп) з /ц хп)). Если параметры
отсутствуют (q = 0), то система (1) называется неявный, представлениел функции /.
Понятия параметрического и неявного представления были также перенесены А. В. Кузнецовым в область логических исчислений (в рамках двузначной логики Р^ и связанного с ней классического исчисления высказываний оба подхода фактически равносильны (51). В данной работе эти понятия рассматриваются в их первоначальном, чисто функциональном виде, однако поскольку в работе изучаются исключительно функции двузначной логики (булевы функции), большинство полученных результатов о параметрических и неявных представлениях допускает однозначную интерпретацию и с точки зрения классического исчисления высказываний. Параллели с понятиями параметрического и неявного представления можно отыскать также во многих других областях математики. Особенно тесно эти понятия связаны с известным в математической логике понятием описательного определения [41. Сходные понятия рассматривались также А. И. Мальцевым в теории алгебраических
систем (понятия производной функции и предиката [123) и Г. Биркгофом в универсальной алгебре (в связи с введенным в [21 понятием криптоизоморфизма алгебр).
Выразительные возможности параметрических представлений булевых функций были с исчерпывающей полнотой исследованы А. В. Кузнецовым [5]. Для описания отношений выразимости удобно использовать понятие замыкания (расширения) системы функций. Множество всех функций, для которых имеются параметрические (неявные) представления над данной системой функций 4, называется паралетричестл залыначиел (неаЗныл расширением) системы А, и обозначается через Р{А) (соответственно, 1{А)). В любой многозначной логике Рй операция параметрического замыкания является операцией замыкания в обычном смысле и порождает систему паралетричест залкнутых классов - множеств A s Рй, таких, что РШ = А. Система всех параметрически замкнутых классов в двузначной логике Р2 найдена А. В. Кузнецовым [51. Эта система, называемая селействол Кузнецова (или, короче, селействол К), конечна и состоит из следующих двадцати пяти замкнутых относительно суперпозиции классов булевых функций (классов Поста; обозначения даны по [181): ^, С2, С^, С^, ^, D3> Р|, Р3> Р5. Р^у Sj, So, Sc, Sc> ij > ip, 3> 4, ir, О.,, 0^, Og, Og, On, On. Из этого результата А. В. Кузнецова, в частности, видно, что параметрическая выразимость в двузначной логике превосходит по своим возможностям выразимость формулами - под действием операции параметрического замыкания счетная система всех классов Поста "сжимается" в конечное семейство К. В то же время, вопрос о неявной выразимости в ?2 оставался открытым. В работе [5] этот вопрос был сформулирован в списке открытых проблем как следующая проблела 12: влечет ли неявная сводимость в Р^ неявную
- і -
выразимость в Р2? (Неявная сводимость равнозначна замыканию по неявной выразимости, т. е. по существу бесконечной итерации операций неявного расширения; в [51 было установлено, что в ?2 неявная сводимость эквивалентна параметрической выразимости, поэтому в Рр неявная сводимость и параметрическая выразимость одашаково соотносятся с неявной выразимостью.) Вопросы сложности параметрических и неявных представлений в Ш не рассматривались. Другой важный класс УС составляют сети из функциональных элементов, описанные А Берксом и Дж. Райтом в работе Ш под названием правильных производящих логических сетей (схемы из функциональных элементов, составляющие подкласс этого класса, были описаны в Ш под названием вполне правильных производящих логических сетей). Содержательно сеть из функциональных элементов это объект, получаемый путем произвольного соединения функциональных элементов при единственном ограничении: выходы элементов не могут присоединяться к входным вершинам сети. В отличие от схем из функциональных элементов в сетях допустимы ориентированные циклы из элементов и возможно присоединение выходов нескольких элементов к одной вершине. Функционирование сети описывается с помощью системы уравнений, соответствующих ее элементам; каждое уравнение описывает связь, налагаемую данным элементом на переменные, приписанные вершинам сети, 'к которым присоединены его входы и выходы. В И] был поставлен вопрос о сравнений сетей и схем из функциональных элементов с точки зрения выразимости и сложности (понимаемой как число элементов). При этом в Ш рассматривались сети и схемы лишь над одним конкретным базисом S, состоящим из единственного двувходового элемента с функцией "штрих" Шеффера (х\уИ~у), и был сделан вывод о том, что с точки зрения выразимости сети не имеют существенных преимуществ
перед схемами {здесь сказалось функциональная полнота базиса S). В то же время в Ш было показано, что в принципе с точки зрения сложности некоторые функции могут быть реализованы в классе сетей над базисом 5 более экономно, чем в классе схем над тем же базисом. Однако вопрос о точных границах такой экономии оставался .открытым. Оставались также открытыми проблема выразимости и проблема сложности для сетей над произвольными базисами.
Интерес к исследованию рассматриваемых классов УС пробудился с новой силой приблизительно десять - пятнадцать лет тому назад. Приведем лишь несколько примеров. С. Баррис и Р. Уиллард [191 доказали справедливость гипотезы А. В. Кузнецова о конечности числа параметрически замкнутых классов в любой конечнозначной логике, решив тем самым проблему 15 из [51 (ранее А. Ф. Данильченко установила справедливость этой гипотезы в трехзначной логике). М. Ф. Раца и И. В. Куку были найдены решения проблем параметрической полноты и полноты по неявной сводимости в цепных логиках. В. А. Орловым были обнаружены нетривиальные новые эффекты в асимптотической теории сложности логических сетей Беркса-Райта с памятью И51. Однако при всей глубине и яркости этих исследований и довольно значительном продвижении в исследовании вопросов выразимости, результаты в области сложности оставались малочисленными и фрагментарными. В свете сказанного актуальность систематического исследования проблемы сложности для этих классов УС представляется несомненной.
Цель работы. Главной целью данной работы является систематическое изучение вопросов сложности для'некоторых классов УС, связанных с неявными и параметрическими представлениями булевых функций. Основное внимание уделено исследованию самих неявных и параметрических представлений, рассматриваемых как
важнейшие модельные классы УС. Конкретно ставилось целью разработать метода синтеза УС из рассматриваемых классов, оптимальные по отношению к различным естественным мерам сложности, получить как можно более точные оценки соответствующих функций Шеннона, исследовать асимптотическое поведение этих функций, установить характер зависимости их от Оазиса. В более широком плане цель исследований состояла в накоплешаї результатов для осмысления общих закономерностей синтеза УС.
Методы исследований. Специфика рассматриваемых классов УС и их существенное отличие от традиционных модельных объектов математической теории синтеза УС потреоовали развития новых подходов к получению оценок сложности и разработки принципиально новых методов оптимального синтеза таких УС. Были также разработаны новые методы для решения некоторых задач *лз области дискретного анализа, возникших в ходе этих исследований. Наряду с новыми в работе использованы известные подходы и методы из области асимптотической теории сложности УС, теории булевых функций, дискретного анализа, теории графов, теории булевых уравнений и других разделов дискретной математики и математической кибернетики.
Научная новизна. Данная работа является первым систематическим исследованием проблем сложности неявных и параметрических представлений булевых функций и связанных с ними классов УС. Все основные результаты работы являются новыми.
В работе рассматриваются две основные меры сложности неявных и параметрических представлений. Первая из этих мер носит название ранга. Рангол неявного (параметрического) представления называется число входящих в него уравнений. Для произвольной системы булевых функций A s р? вводятся функции Шеннона: в случае
неявных представлений - ранговая функция я,(п) = max min я(зі)
/зі
(максимум берется по всем функциям / от л переменных, / є 1(.4), минимум - по всевозможным неявным представлениям зі над А, реализующим /), в случае параметрических представлений -Р-ранговая функция ИЛп) = max rain я(?) (максимум берется по
всем функциям / от л переменных, / є ?{А), минимум - по всевозможным параметрическим представлениям ? над А, реализующим /). В работе получены, точные по порядку роста оценки ранговых и Р-ранговых функций для всех систем А булевых функций. До появления работ автора [9, 11] таких оценок известно не было.
Успешное решение задачи о поведении ранговых функций было бы невозможным, если бы прежде не удалось выяснить выразительные возможности неявных представлений в двузначной логике Р2- Автором 16) (см. также [4, 9)) решена долгое время остававшаяся открытой проблема неявной выразимости в >: дано исчерпывающее описание совокупности всех неявных расширений систем булевых функций. Попутно решена упоминавшаяся выше открытая проблема 12, поставленная А. В.- Кузнецовым в работе [5]. Решение проблемы неявной выразимости в двузначной логике повлекло за собой решение еще двух известных открытых проблем. Автором [9] получена исчерпывающая классификация всех алгебр на множестве из двух элементов с точностью до криптоизоморфизма (частный случай общей задачи классификации универсальных алгебр с точностью до криптоизоморфизма, поставленной Г. Биркгофом в книге [21). Это, по-видимому, единственное известное описание всех алгебр на множестве фиксированной мощности с точностью до криптоизоморфизма (если исключить тривиальный случай одноэлементных алгебр). Автором [101 также найдено полное решение долгое время остававшейся открытой проблемы выразимости булевых функций в
классе сетей из фушсционалышх элементов. Этот результат позволил существенно уточнить вывода, сделанные в HI насчет соотношения выразительных возможностей сетей и схем из функциональных элементов: из результатов ПО] вытекает, что в случае произвольных базисов выразительные возможности сетей из функщюнальных элементов, вообще говоря, значительно превосходят выразительные возможности схем.
Помимо ранга в работе рассмотрена еще одна естественная мера сложности параметрических представлений, обобщающая известную меру сложности формул и схем из функциональных элементов П_П: предполагается, что каждой функции v из базиса А приписано некоторое положительное действительное ЧИСЛО \[<р) - вес этой функции, и под сложностью всякого параметрического представления V вида (1) над А понимается сумма bj(p) весов всех вхождений функциональных символов из 4 в уравнения этого представления. В такой постановке проблема сложности параметрических и неявных представлений, по-видимому, впервые рассмотрена автором [3, 12]. Обычным образом вводится соответствующая функция Шеннона,
отвечающая Оазису A: Ъ^{п) = max mln LAP), где максимум берется
/ Р по всем функциям / от л переменных, / є р(4), а минимум - по
всевозможным параметрическим представлениям р над А, реализующим
/. В работе получены асимптотически точные оценки функций Шеннона
LA{n) при п - <о для всех конечных параметрически полных базисов
с произвольными фиксированными положительными весами функций. До
работ автора 13, 12] таких оценок известно не было. Выявлен
нетривиальный новый эффект, связанный с зависимостью-
мультипликативной константы в асимптотике функций Шеннона от
функциональных свойств базиса. Для получения верхних оценок
функций Шеннона разработан принщпшалыю новый метод синтеза
асимптотически оптимальных по сложности параметрических представлений.
В работе впервые систематически разработаны вопросы сложности сетей из функвдюнальных элементов и найден точный вид асимптотики функций Шеннона для сетей над любым конечным //-полным базисом с произвольными положительными весами элементов. Для таких базисов дан окончательный (с точки зрения асимптотического подхода, т. в. справедливый для почти всех булевых функций) ответ на поставленный в (П вопрос о соотношении сложностей сетей и схем; в частности, для рассмотренного в Ш базиса Шеффера S .установлено, что реализация почти всех булевых функций сетями над этим базисом требует асимптотически вдвое меньшего числа .элементов, чем реализация схемами. В работе впервые рассмотрена реализация булевых функций в классе сетей из функциональных элементов над бесконечными базисами. Для ряда известных функционально полных бесконечных базисов найдены порядки роста соответствующих функций Шеннона. При сравнении сложностей реализации булевых функций в классах сетей и схем над бесконечными базисами обнаружены нетривиальные новые эффекты, в частности, установлена возможность экспоненциального расхождения соответствующих функций Шеннона.
В работе изложены также результаты исследований автора по проблеме сложности в одной математической модели электронных схем на дополняющих МОП-транзисторах (КМОП-схем), предложенной А. А. Сапоженко и С. А. Ложкиным в работе (161 (для краткости схемы из (161 названы в данной работе Г-схемами). Точное определение Т-схем достаточно громоздко; скажем только, что всякая Г-схема -это некоторый помеченный конечный граф, вершинам и ребрам которого приписаны символы переменных (вершины соответствуют
узлам моделируемой "физической" схемы, а ребра - входящим в нее
транзисторам). Функционирование Г-схем напоминает работу хорошо
известных релейно-контактных схем - грубо говоря, ребра г-схемн
работают как проводящие (замыкающие и размыкающие) контакты,
однако в отличие от релейно-контактных схем управление
проводимостью ребер осуществляется с помощью значений переменных,
приписанных полюсам и внутренним вершинам Г-схемы ("потенциалов
вершин", подаваемых на "затворы транзисторов"). Как показано в
116), всякая булева функция допускает реализацию некоторой
Г-схемой. Наименьшее число ребер ("транзисторов"), достаточное
для реализации всякой булевой функции от п переменных подходящей
Г-схемой, обозначается через Ш). Поведение функции Шеннона Цп)
при п - о рассматривалось в работе [16], где для этой функции
были установлены оценки, различающиеся асимптотически в 1,5 раза.
Точный вид асимптотики функции 1(п) был впервые найден автором
[1, 2] с использованием идей, разработанных при решении проблемы
синтеза асимптотически оптимальных параметрических представлений.
Впоследствии модель U6] была обобщена, и в таком виде
рассматривалась М. А. Зыряновым (31, нашедшим ряд асимптотик для
соответствующих таким обобщениям функций Шешюна (в этом нап
равлении имеются также глубокие результаты С. А. Ложкина 16, 71).
Основные результаты, выносимые на
з а щ и т у. На защиту выносятся следующие основные результаты
диссертации: точные по порядку роста оценки ранговых функций для
всех систем булевых функций; асимптотически точные оценки функций
Шеннона сложности параметрических представлений над произвольным
конечным параметрически полным базисом с произвольными
положительными весами базисных функций; асимптотически точные оценки функций Шешюна сложности сетей из функциональных
элементов над произвольным конечным Jf-полным Оазисом с положительными весами; асимптотически точные оценки функции Шеннона для сложности Г-схем; доказательство эквивалентности неявной выразимости и параметрической выразимости в ?р и решение проблема А. В. Кузнецова о транзитивности отношения неявной выразимости в Р~, классификация всех двухэлементных алгебр с точностью до крилтоизоморфизма, описание системы всех ^-замкнутых классов и критерий /У-полноты.
Теоретическая и практическая ценность. Данная работа носит теоретический характер. Полученные в ней результаты составили довольно полную картину поведения основных мер сложности неявных и параметрических представлений булевых функций и ряда близких к ним классов УС. Некоторые из обнаруженных эффектов (например, специфическая зависимость мультипликативного коэффициента в асимптотике функции Шеннона сложности параметрических представлений от функциональных свойств базиса) характерны для многих классов УС близкого типа и имеют существенное значение для понимания общих закономерностей синтеза УС. Полученные результаты создают теоретическую базу для более широкого использования неявных и параметрических представлений в качестве средства задания функций при решении различных задач в области математической кибернетики и ее приложений. Результаты и методы данной работы могут найти применение в дискретной математике, математической логике, алгебре, а также в технике при математическом моделировании и логическом проектировании больших и сверхбольших интегральных схем. Растущий интерес к изучению и использованию УС, связанных с неявными и параметрическими представлениями функций дает основания предполагать дальнейшее активное использование
результатов и идей данной работы в таких исследованиях.
Апробация работы и публикации.
Результаты диссертации докладывались в разное время на семинарах
по математическим вопросам кибернетики (рук. чл.-корр. РАН С. В.
Яблонский), синтезу управляющих систем (рук. чл.-корр. РАН 0. Б.
Лупанов), дискретному анализу (рук. д. ф. - м. н. А. А.
Сапоженко) в МГУ, на VIII Всесоюзной конференции по проблемам
теоретической кибернетики (Горький, 1988 г.), на Международном
рабочем семинаре "Математические вопросы кибернетики" (МВК'90,
Братислава, Чехословакия, 1990), на Всесоюзных и
Межгосударственных школах-семинарах "Синтез и сложность управляющих систем" (Львов, 1988; Новосибирск, 1989; Минск, 1993; Н. Новгород, 1994; Минск, 1995).
Все основные результаты диссертации опубликованы. По теме диссертации автором опубликовано 12 печатных работ.
Структура работы. Диссертация состоит из Введения, четырех глав и списка литературы. Глава 1 разбита на четыре параграфа, глава 2 на пять параграфов, глава 3 на десять параграфов и глава 4 на два параграфа. Список литературы содержит 102 наименования. Общий объем работы составляет 303 стр. машинописного текста.