О синтезе некоторых классов управляющих систем, связанных с неявными и параметрическими представлениями булевых функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. М. В. ЛОМОНОСОВА

О СИНТЕЗЕ НЕКОТОРЫХ КЛАССОВ УПРАВЛЯЮЩИХ СИСТЕМ, СВЯЗАННЫХ С НЕЯВНЫМИ И ПАРАМЕТРИЧЕСКИМИ ПРЕДСТАВЛЕНИЯМИ БУЛЕВЫХ ФУНКЦИИ

01.01.09 - математическая кибернетика

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

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

РГ6 од

ь ДЬК 1996

На правах рукописи УДК 519.6

Касим-Заде Октай Мурад оглы

Москва - 1996

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета им. М. В. Ломоносова

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

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

Ведущая организация:

Защита состоится 16 час. 05 мин.

Институт математики им. С. Л. Соболева Сибирского Отделения РАН.

1996 г. совета

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

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

Автореферат разослан " ¡¿Ос^сдрЛ-_ 1996 г.

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

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Вопросы синтеза управляющих систем (УС) занимают одно из центральных мест в проблематике математической кибернетики П71. Общая актуальность исследований в этой области обусловлена важностью многочисленных задач синтеза, возникающих в различных разделах науки и техники.

К числу важнейших модельных объектов математической теории синтеза УС относятся формулы (суперпозиции) и схемы из функциональных элементов, реализующие булевы функции. Эти классы УС хорошо изучены, здесь имеется значительное число работ и результатов (см. [8,9,]_1,20,2П). Гораздо менее до последнего времени были изучены некоторые близкие классы УС, такие как введенные А. В. Кузнецовым неявные и параметрические представления функций [5], описанные А. Берксом и Дж. Райтом сети из функциональных элементов И] и некоторые другие. Общей чертой, сближающей эти УС с формулами и схемами из функциональных элементов, является использование систем функциональных уравнений для описания их функционирования. Отличие состоит в том, что в случае формул и схем системы уравнений оказываются явными и допускают прямое вычисление реализуемых функций, в то время как в в случае рассматриваемых УС реализуемые функции отыскиваются как решения систем неявных уравнений.

Понятие параметрического (неявного) представления было введено А. В. Кузнецовым как обобщение понятия представления функций й-значной логики формулами (суперпозициями). В общем случае рассматривается система уравнений ' .....^,¡/,,-...,^.2) = .....

О)

..........Уд.2) = *рЦ..........г).

- г -

где ..... «р, ^, ..., 9р - некоторые формулы над заданной

системой функций А, А я Р^, составленные из символов функций, входящих в символов основных переменных ^, ..., х

внутренних переменных (параметров) у,, ..., у^, и выделенной переменной г (в частности, эти формулы могут являться символами переменных). Говорят, что система (1) является паралетричестм представлениел функции ....,агп), если эта система имеет по

меньшей мере одно решение ^ = .....хп)..... у =

... ,хп), г = .....хп) в функциях от основных

переменных, причем во всяком таком решении значение выделенной

переменной г определено однозначно и равно /Ц.....хп) (т. е. в

любом решении = /Ц.....хп)). Если параметры

отсутствуют = 0), то система (1) называется неявный,

представлениел функции /.

Понятия параметрического и неявного представления были также перенесены А. В. Кузнецовым в область логических исчислений (в рамках двузначной логики Р^ и связанного с ней классического исчисления высказываний оба подхода фактически равносильны (51). В данной работе эти понятия рассматриваются в их первоначальном, чисто функциональном виде, однако поскольку в работе изучаются исключительно функции двузначной логики (булевы функции), большинство полученных результатов о параметрических и неявных представлениях допускает однозначную интерпретацию и с точки зрения классического исчисления высказываний. Параллели с понятиями параметрического и неявного представления можно отыскать также во многих других областях математики. Особенно тесно эти понятия связаны с известным в математической логике понятием описательного определения [41. Сходные понятия рассматривались также А. И. Мальцевым в теории алгебраических

систем (понятия производной функции и предиката [123) и Г. Биркгофом в универсальной алгебре (в связи с введенным в [2] понятием крштоизоморфизма алгебр).

Выразительные возможности параметрических представлений булевых функций были с исчерпывающей полнотой исследованы А. В. Кузнецовым [5]. Для описания отношений выразимости удобно использовать понятие замыкания (расширения) системы функций. Множество всех функций, для которых имеются параметрические (неявные) представления над данной системой функций 4, называется паралет.ри.чески.и залынаниел {неаЗныл расширением) системы А, и обозначается через РЦ) (соответственно, IU)). В любой многозначной логике Р^ операция параметрического замыкания является операцией замыкания в обычном смысле и порождает систему паралетричест затнутых классов - множеств А s Рй, таких, что РШ = А. Система всех параметрически замкнутых классов в двузначной логике Р2 найдена А. В. Кузнецовым [51. Эта система, называемая селействол Кузнецова (или, короче, селействол К), конечна и состоит из следующих двадцати пяти замкнутых относительно суперпозиции классов булевых функций (классов Поста; обозначения даны по [18]): Су С2, С3, С^, й3, Pf, Р3, Р5, Р6, S,, s3, s5, S6, lv Ig, i3. ov 04, 05, 06, Oq, o9.

Из этого результата А. В. Кузнецова, в частности, видно, что параметрическая выразимость в двузначной логике превосходит по своим возможностям выразимость формулами - под действием операции параметрического замыкания счетная система всех классов Поста "сжимается" в конечное семейство К. В то же время, вопрос о неявной выразимости в ?2 оставался открытым. В работе [5] этот вопрос был сформулирован в списке открытых проблем как следующая проблем 12: влечет ли неявная сводимость в Рg неявную

- л -

выразимость в Р2? (Неявная сводимость равнозначна замыканию по неявной выразимости, т. е. по существу бесконечной итерации операций неявного расширения; в С53 было установлено, что в ?2 неявная сводимость эквивалентна параметрической выразимости, поэтому в ?2 неявная сводимость и параметрическая выразимость одинаково соотносятся с неявной выразимостью.) Вопросы сложности параметрических и неявных представлений в [51 не рассматривались.

Другой важный класс УС составляют сети из функциональных элементов, описанные А Берксом и Дне. Райтом в работе И] под названием правильных производящих логических сетей (схемы из функциональных элементов, составляющие подкласс этого класса, были описаны в [П под названием вполне правильных производящих логических сетей). Содержательно сеть из функциональных элементов это объект, получаемый путем произвольного соединения функциональных элементов при единственном ограничении: выходы элементов не могут присоединяться к входным вершинам сети. В отличие от схем из функциональных элементов в сетях допустимы ориентированные циклы из элементов и возможно присоединение выходов нескольких элементов к одной вершине. Функционирование сети описывается с помощью системы уравнений, соответствующих ее элементам; каждое уравнение описывает связь, налагаемую данным элементом на переменные, приписанные вершинам сети, 'к которым присоединены его входы и выходы. В И1 был поставлен вопрос о сравнений сетей и схем из функциональных элементов с точки зрения выразимости и сложности (понимаемой как число элементов). При этом в (П рассматривались сети и схемы лишь над одним конкретным базисом г, состоящим из единственного двувходового элемента с функцией "штрих" Шеффера (х\уз5~у), и был сделан вывод о том, что с точки зрения выразимости сети не имеют существенных преимуществ

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

Интерес к исследованию рассматриваемых классов УС пробудился с новой силой приблизительно десять - пятнадцать лет тому назад. Приведем лишь несколько примеров. С. Баррис и Р. Уиллард [191 доказали справедливость гипотезы А. В. Кузнецова о конечности числа параметрически замкнутых классов в любой конечнозначной логике, решив тем самым проблему 15 из 151 (ранее А. Ф. Данильченко установила справедливость этой гипотезы в трехзначной логике). М. Ф. Раца и И. В. Куку были найдены решения проблем параметрической полноты и полноты по неявной сводимости в цепных логиках. В. А. Орловым были обнаружены нетривиальные новые эффекты в асимптотической теории сложности логических сетей Беркса-Райта с памятью [15]. Однако при всей глубине и яркости этих исследований и довольно значительном продвижении в исследовании вопросов выразимости, результаты в области сложности оставались малочисленными и фрагментарными. В свете сказанного актуальность систематического исследования проблемы сложности для этих классов УС представляется несомненной.

Цель работы. Главной целью данной работы является систематическое изучение вопросов сложности для'некоторых классов УС, связанных с неявными и параметрическими представлениями булевых функций. Основное внимание уделено исследованию самих неявных и параметрических представлений, рассматриваемых как

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

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

Научная новизна. Данная работа является первым систематическим исследованием проблем сложности неявных и параметрических представлений булевых функций и связанных с ними классов УС. Все основные результаты работы являются новыми.

В работе рассматриваются две основные меры сложности неявных и параметрических представлений. Первая из этих мер носит название ранга. Рангол неявного (параметрического) представления называется число входящих в него уравнений. Для произвольной системы булевых функций А 2 Р? вводятся функции Шеннона: в случае

неявных представлений - ранговая функция шЛп) = шах min я(Я)

/31

(максимум берется по всем функциям f от п переменных, f е НА),

минимум - по всевозможным неявным представлениям я над А,

реализующим Я, в случае параметрических представлений -

Р-ранговая функция 41,(п) = шах rain nt(p) (максимум берется по

А / Р

всем функциям / от п переменных, / е Р(4), минимум - по всевозможным параметрическим представлениям ? над А, реализующим /). В работе получены, точные по порядку роста оценки ранговых и Р-ранговых функций для всех систем А булевых функций. До появления работ автора [9, 111 таких оценок известно не было.

Успешное решение задачи о поведении ранговых функций было бы невозможным, если бы прежде не удалось выяснить выразительные возможности неявных представлений в двузначной логике Р2- Автором Í6] (см. также [4, 91) решена долгое время остававшаяся открытой проблема неявной выразимости в Р2: дано исчерпывающее описание совокупности всех неявных расширений систем булевых функций. Попутно решена упоминавшаяся выше открытая проблема 12, поставленная А. В.- Кузнецовым в работе [5]. Решение проблемы неявной выразимости в двузначной логике повлекло за собой решение еще двух известных открытых проблем. Автором [9] получена исчерпывающая классификация всех алгебр на множестве из двух элементов с точностью до криптоизоморфизма (частный случай общей задачи классификации универсальных алгебр с точностью до криптоизоморфизма, поставленной Г. Биркгофом в книге (21). Это, по-видимому, единственное известное описание всех алгебр на множестве фиксированной мощности с точностью до криптоизоморфизма• (если исключить тривиальный случай одноэлементных алгебр). Автором [101 также найдено полное решение долгое время остававшейся открытой проблемы выразимости булевых функций в

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

Помимо ранга в работе рассмотрена еще одна естественная мера сложности параметрических представлений, обобщающая известную меру сложности формул и схем из функциональных элементов ПП: предполагается, что каждой функции v из базиса А приписано некоторое положительное действительное число \[<р) - вес этой функции, и под сложностью всякого параметрического представления р вида (1) над А понимается сумма bj(p) весов всех вхождений функциональных символов из 4 в уравнения этого представления. В такой постановке проблема сложности параметрических и неявных представлений, по-видимому, впервые рассмотрена автором [3, 121. Обычным образом вводится соответствующая функция Шеннона, отвечающая Оазису A: L¿(n) - шах mln Р), где максимум берется

/ Р

по всем функциям / от л переменных, f е Р(А), а минимум - по всевозможным параметрическим представлениям р над А, реализующим /. В работе получены асимптотически точные оценки функций Шеннона LA(n) при п - <о для всех конечных пара метрически полных базисов с произвольными фиксированными положительными весами функций. До работ автора 13, 12] таких оценок известно не было. Выявлен нетривиальный новый эффект, связанный с зависимостью-мультипликативной константы в асимптотике функций Шеннона от функциональных свойств базиса. Для получения верхних оценок функций Шеннона разработан принципиально новый метод синтеза

асимптотически оптимальных по сложности параметрических представлений.

В работе впервые систематически разработаны вопросы сложности сетей из функциональных элементов и найден точный вид асимптотики функций Шеннона для сетей над любым конечным //-полным базисом с произвольными положительными весами элементов. Для таких базисов дан окончательный (с точки зрения асимптотического подхода, т. в. справедливый для почти всех булевых функций) ответ на поставленный в СП вопрос о соотношении сложностей сетей и схем; в частности, для рассмотренного в Ш базиса Шеффера 5 .установлено, что реализация почти всех булевых функций сетями над этим базисом требует асимптотически вдвое меньшего числа .элементов, чем реализация схемами. В работе впервые рассмотрена реализация булевых функций в классе сетей из функциональных элементов над бесконечными базисами. Для ряда известных функционально полных бесконечных базисов найдены порядки роста соответствующих функций Шеннона. При сравнении сложностей реализации булевых функций в классах сетей и схем над бесконечными базисами обнаружены нетривиальные новые эффекты, в частности, установлена возможность экспоненциального расхождения соответствующих функций Шеннона.

В работе изложены также результаты исследований автора по проблеме сложности в одной математической модели электронных схем на дополняющих МОП-транзисторах (КМОП-схем), предложенной А. А. Сапоженко и С. А. Ложкиным в работе (161 (для краткости схемы из [161 названы в данной работе Г-схемами). Точное определение Т-схем достаточно громоздко; скажем только, что всякая Г-схема -это некоторый помеченный конечный граф, вершинам и ребрам которого приписаны символы переменных (вершины соответствуют

узлам моделируемой "физической" схемы, а ребра - входящим в нее транзисторам). Функционирование Г-схем напоминает работу хорошо известных релейно-контактных схем - грубо говоря, ребра г-схемн работают как проводящие (замыкающие и размыкающие) контакты, однако в отличие от релейно-контактных схем управление проводимостью ребер осуществляется с помощью значений переменных, приписанных полюсам и внутренним вершинам Т-схемы ("потенциалов вершин", подаваемых на "затворы транзисторов"). Как показано в Иб], всякая булева функция допускает реализацию некоторой Г-схемой. Наименьшее число ребер ("транзисторов"), достаточное для реализации всякой булевой функции от п переменных подходящей Г-схемой, обозначается через £(п). Поведение функции Шеннона Цл) при п - » рассматривалось в работе [16], где для этой функции были установлены оценки, различающиеся асимптотически в 1,5 раза. Точный вид асимптотики функции 1(п) был впервые найден автором [1, 2] с использованием идей, разработанных при решении проблемы синтеза асимптотически оптимальных параметрических представлений. Впоследствии модель U6] была обобщена, и в таком виде рассматривалась М. А. Зыряновым (31, нашедшим ряд асимптотик для соответствующих таким обобщениям функций Шеннона (в этом направлении имеются также глубокие результаты С. А. Ложкина 16, 71).

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

элементов над произвольным конечным «-полным Оазисом с положительными весами; асимптотически точные оценки функции Шеннона для сложности Г-схем; доказательство эквивалентности неявной выразимости и параметрической выразимости в Р^ и решение проблемы А. В. Кузнецова о транзитивности отношения неявной выразимости в Р2> классификация всех двухэлементных алгебр с точностью до криптоизоморфизма, описание системы всех //-замкнутых классов и критерий У-полноты.

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

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

Апробация работы и публикации. Результаты диссертации докладывались в разное время на семинарах по математическим вопросам кибернетики (рук. чл.-корр. РАН С. В. Яблонский), синтезу управляющих систем (рук. чл.-корр. РАН 0. Б. Лупанов), дискретному анализу (рук. д. Ф- - м. н. А. А. Сапоженко) в МГУ, на VIII Всесоюзной конференции по проблемам теоретической кибернетики (Горький, 1988 г.), на Международном рабочем семинаре "Математические вопросы кибернетики" (МВК'90, Братислава, Чехословакия, 1990), на Всесоюзных и Межгосударственных школах-семинарах "Синтез и сложность управляющих систем" (Львов, 1988; Новосибирск, 1989; Минск, 1993; Н. Новгород, 1994; Минск, 1995).

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

Структура работы. Диссертация состоит из Введения, четырех глав и списка литературы. Глава 1 разбита на четыре параграфа, глава 2 на пять параграфов, глава 3 на десять параграфов и глава 4 на два параграфа. Список литературы содержит 102 наименования. Общий объем работы составляет 303 стр. машинописного текста.

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

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

В главе 1 изучаются общие свойства параметрических и неявных представлений. В § 1.1 даны подробные определения основных понятий, описана их связь с аналогичными понятиями в алгебре и математической логике, установлен ряд используемых в работе общих

фактов. В § 1.2 изучаются вопросы двойственности для параметрических и неявных представлений и устанавливается соответствующий принцип двойственности, широко используемый в дальнейшем. В § 1.3 рассматриваются вопросы параметрической и неявной выразимости в двузначной логике. Кратко излагаются известные результаты А. В. Кузнецова о параметрической выразимости в Р2 ' и (подробно) результаты автора о неявной выразимости в Р2. Здесь доказано, что неявное расширение всякой системы булевых функций совпадает с наиленъшил по включению классом селейства К, объеллщал эту сиспелу (теорема 1.3.3 диссертации). Тем самым показано, что совокупность всех неявных расширений систем булевых функций исчерпывается двадцатью пятью классами, составляющими семейство К. Как следствие установлено, что неявное расширение всякой систем булевых функций совпадает с парааетрическил зачыканиел этой систем (теорема 1.3.4). Таким образом, показано, что в двузначной логике ?2 неявная выразимость эквивалентна параметрической выразимости. Установлен критерий неявной полноты в двузначной логике, совпадающий с найденным А. В. Кузнецовым критерием параметрической полноты в Р2 (система булевых функций называется неявно (параметрически) полной, если любая булева функция неявно (соответственно, параметрически) выразима над этой системой): показано, что систем функций является неявно полной д Р2 тогда, и только тогда, когда эта систем, не содержится целиком ни в одном из классов С2, Сд,

(те0Рема 1-3.5). Здесь же приведено полученное автором решение поставленной А. В. Кузнецовым проблем 12 из [51: для любой систем булевых функций А выполняется соотношение 1(1(А)1 = ПА) (теорема 1.3.6), откуда вытекает, что в двузначной логике Р2 отношение неявной выразимости является транзитивным и в Р2

неявная сводимость влечет неявную выразимость.

В § 1.3 также изложено попутно найденное автором исчерпывающее решение проблемы криптоизоморфизма двухэлементных алгебр. Обозначим элементы произвольного двухэлементного множества M через 0 и 1 и придадим этим элементам смысл булевых значений. Введем специальные обозначения для следующих алгебраических операций на множестве И, M = (0, 1): нульарных постоянных операции 0 и 1 , унарной тождественной операции е(х) = х, унарной операции циклического сдвига п(х) = х + 1 (mod 2), бинарных операций верхней грани d{x,y) = х - у, и нижней грани Ш,у) = х - у, определяющих на множестве И, соответственно, верхнюю и нижнюю полурешетки с наибольшим элементом 1 и наименьшим элементом 0, и двух тернарных операций - медианы m(x,y,z) = (х л у) - (у л 2) - (z * х), и линейной операции (линеалы) l(x,y,z) = х + у + z (той 2). Показано, что всякая алгебра на двухэлелентнол множестве M крилтоизолорфна одной из следукщих двадцати пяти попарно не криптоизолорфных алгебр: (М, (е>), (I, (0)), (М, (1}), (М, (л)), (Н, Ш), Ш, Ш), (М, Ш), (М, Ш), (И, (0,1)), (#, (0,п>), (М, (0,М), (И, (O.tJ}), (И, со.ш, (M, CO.mî}, (M, (1,Й>), Ш, <М>). {M, (1,1)), (M, (1,!ÏI}), (M, (n.fe)), (if, (n,D), (a, (П.И)), (if, iÈ.d)), (if. (0,1,£)), (if, (0,1,d>), (Jf, {0,1,1}) (теорема 1.3.10). Отметим, что уже на множестве из трех элементов существует континуальное число попарно не криптоизоморфных алгебр [41.

В главе 2 изучается поведение ранговых и Р-ранговых функций. В § 2.1 вводятся основные определения и устанавливаются важнейшие общие свойства ранговых функций. Здесь, в частности, показано, что для всякой системы булевых функций А при всех натуральных п выполняются равенства тА{п) = ffl^j(n) и Мд{п) = tf^tn), и потому

поведение ранговых и Р-ранговых функций над любой системой 4 £ Р2 однозначно определяется видом замыкания [Л] этой системы по суперпозиции. Тем самым, задача нахождения ранговых и Р-ранговых функций для всех систем А г сводится к нахождению этих функций для классов Поста. В § 2.1 и в' последующих параграфах главы 2 устанавливаются оценки ранговых (§§ 2.2 - 2.4) и Р-ранговых (§ 2.5) функций для всех классов Поста. Ниже основные результаты главы 2 для большей наглядности сведены воедино, со ссылками на соответствующие теоремы диссертации. Пусть А' -произвольная cucme.ua булевых функций, тогда: (1) если зашкание [А] систем А совпадает с однил из классов ^ - С4, Р,, ?3, ?5, Р6, , Бд, Яд, ^ - 15, 01 - Од, то при всех п 1 1

шА(п) = МА(п) = )

(теорема 2.1.1); (2а) если 1А] совпадает с классом 4,, то при всех п ? 1

ША(П) = Цп + 1 )/2\ + 1 и ^(п) = 2; (26) если [4] совпадает с А^ или 4д, то при всеа тА(п) = Г(п + 1 )/2] и МЛ(Л) = ■

(26) если Ш совпадает с А^, то при всех п 2 1

и4(п) = Цп + 1 )/2] и МА(п) = |

(теоремы 2.3.1 и 2.5.2);

(3) если [4] совпадает с однил из классов Р{ 5, 8 и д = 2, 3, ...,«>, то при всех п } 1

и/п) = ИА(п) = [(п + 1 )/2] (теоремы 2.2.1 и 2.5.1);

(4) если (4] совпадает с классом ^ или с однил из классов' где I = 2, 3, б, 7 и и = 2, 3, ..., то при п - »

1, при п = 1,

2, при п 2;

1, при п 2,

2, при п 3

Д где 1 = 1,

выполняются соотношения ) .

= в(п log2 п) и МА(п) = в(п)

(теоремы 2.4.1 и 2.5.3).

В главе 3 изучается в асимптотической постановке проблема сложности параметрических представлений, понимаемой как сумма весов вхождений базисных функциональных символов, и полностью выяснено асимптотическое поведение функций Шеннона Х^(п) при п -ю для всех конечных параметрически полных базисов А, состоящих из булевых функций с произвольными положительными весами. Основной результат главы 3 сформулирован в § 3.1.

Пусть <р - произвольная функция из базиса А, хЫ - вес этой функции, т[ч>) - число ее существенных переменных. Определим редуцированный вес функции ч> е А соотношением

Редуцироваяныа весол базиса А назовем величину r(4) = min *(?>),

где минимум берется по всем функциям р из базиса А, удовлетворяющим условию лМ г 2. Всякую функцию <р из базиса А, удовлетворяющую соотношению гЫ = 7(4) будем называть главной функцией этого базиса. Тогда имеет место следующее утверждение (теорема 3.1.1): для всякого конечного паралетрияески полного базиса А с произ&олъныли положытелъныли веса.ш функций при п - °°

где 7[А) - редуцированный вес базиса А.

В § 3.1 также сформулированы различные обобщения и варианты

\(<р)/т(<р), если функция <р является нелинейной,

- 1). если <р является линейной и ш(ч>) } 2.

<р

LÄ(n) = г(А)

(2)

') Соотношение а(п) = @{Ь{п)) обозначает равенство порядков роста функций а(п) и bin) при п -

этого результата (в частности, оценка (2) перенесена на случай так называемых регулярных параметрических представлений, что впоследствии позволяет перенести ее и на случай сетей из функциональных элементов). Оставшаяся часть главы 3 посвящена доказательству этих результатов. Нижние оценки устанавливаются в § 3.2, верхние (доказательство которых распадается на ряд случаев в зависимости от вида главных функций базиса ) - в §§ 3.3 - 3.10.

В § 3.1 проведено также сравнение полученных результатов с

известными результатами 0. Б. Лупанова, относящимися к классам '

формул и схем из функциональных элементов над функционально

полными базисами [8,9] (сравнение естественно считать законным,

если параметрическое замыкание базиса совпадает с замыканием

этого базиса по суперпозиции). По характеру поведения функций

Шеннона параметрические представления ближе к схемам из

функциональных элементов, чем к формулам (порядки роста функций

Шеннона в этом случае совпадают), однако в асимптотиках этих

функций наблюдаются значительные различия. В случае схем из

функциональных элементов при п - « асимптотика функции Шеннона

дается известным соотношением

2н 1ое2 п

^) = Ршт(!49 (___)),

где р(А) - приведенный вес базиса А [8, Ш. Поэтому для всякого функционально полного конечного базиса А при п - °° отношение Х^(п)/14(п) стремится к конечному пределу 5(4), 5(4) = р(А)/г(А) > 1. Само по себе отношение функций Шеннона, вообще говоря, не несет особого смысла, однако (это установлено в главе 3) для параметрических представлений как и для схем из функциональных, элементов имеет место так называемый эффект Шеннона, в силу чего величина 5(4) фактически может служить мерой относительного расхождения сложности параметрических представлений и схем из

функциональных элементов в одном и том же базисе 4 для почти всех булевых функций. В работе показано, что для любого функционально полного конечного базиса А с полохтельнши веса.ш выполняются неравенства 1 < 5(4) $ 2, причел равенство 6(4) = 1 имеет место тогда и только тогда, когда хотя бы одна из главных функций базиса А явмется лилейной, а равенство 5(4) = 2 ложет выполняться лишь в том случае, если базис А содержит хотя бы одну нелинейную функцию от двух переленных (теорема 3.1.4).

В главе 4 описаны применения разработанных методов синтеза неявных и параметрических представлений и лежащих в их основе идей к исследованию проблем сложности в некоторых- других классах УС. Эти применения показаны на примере двух классов УС: сетей из функциональных элементов И] и Т-схем Цб].

Сети из функциональных элементов рассматриваются в § 4.1. Вводится понятие Е-за-ткания системы булевых функций А, определяемого как множество всех булевых функций, допускающих реализацию в классе сетей из функциональных элементов над системой 4. Устанавливается, что операция Я-замыкания является операцией замыкания в обычном смысле и определяет в двузначной логике ?2 соответствующую систему $-за.итутых классов. Далее доказывается, что система всех Я-заикнутых классов булевых функций совпадает с селействол К (теорема 4.1.1) и устанавливается критерий ^-полноты (система булевых функций 4 называется Н-полной, если ^-замыкание этой системы совпадает с множеством всех булевых функций): система булевых функций является И-полной тогда и только тогда, когда эта систем не содержится целиком ни в одном из классов С2, С3, В3, ?6>. I, (теорема 4.1.4). С использованием полученных в главе 3 результатов о сложности параметрических представлений в § 4.1

доказано следующее утверждение: для всякого конечного ¡¡-полного

базиса А с произволъныш положительными, 6eca.nu функций при п - »

2n logT и

jJ(„, = ,(4) _ (1 + в (—) ),

где гЦ) - редуцированный вес базиса А (теорема 4.1.5).

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

17 q

через tfj(ri) и I¿(п))- Автором недавно установлено (см. [81), что для всякого бесконечного функционально полного (if-полного) базиса А при п - »' выполняется соотношение l|(n) = 0( 2П/2) (соответственно, L^(n) = 0(2п/2)). В § 4.1 показано, . что для бесконечного бази&а £, состоящего из всех линейных функций вида ¡ш = х^ ® ... ® гщ, где л ) 2 л функции "штрих" Шеффера при п -«о выполняется соотношение i^f(n) = в(2П/2) (теорема 4.1.6). Известно U3], что в классе схем из функциональных элементов 1®(д) = в(2п/2), откуда следует, что с точки зрения порядка роста функций Шеннона сети над базисом я не имеют существенных преимуществ перед схемами. Вместе с тем, для бесконечного базиса а, состоящего из всех антицепных булевых функций (антцепныли называются булевы функции, принимающие единичные значения лишь на-попарно несравнимых наборах), показано, что при п - «

и

выполняется соотношение L£(n) = 0(1) (теорема 4.1.7). Сравнение этого результата с установленными автором в [5, 7] оценками

l|(n) = 0(n), L^(n) = n((n/log п)1/2), обнаружило новый эффект: с ростом числа переменных, функция Шеннона для класса сетей над базисом а ограничена, притом что функция Шеннона для класса схем над тем же базисом растет. Наиболее впечатляющий пример, показывающий с точки зрения сложности превосходство сетей над схемами в случае бесконечных базисов дает бесконечный базис i, состоящий из всех пороговых булевых функций. В работе показано, при п - <» выполняется соотношение 1%(п) = 9(1) (теорема 4.1.8), в то время как известно [io, Н), что l|(n) = е((2п/п)1/2). Таким образом, функция Шеннона для сетей над базисом х ограничена, а для схем над тем же базисом имеет экспоненциальный рост.

В § 4.2 основные идеи, разработанные при синтезе параметрических представлений применяются для получения асимптотических оценок функции Шеннона в случае Г-схем. Здесь показано, что для отвечающей Т-схемам функции Шеннона Un) при п

- « имеет лесто соотношение

, 2п log2 п

Ш) =--(1 + 0(-))

2 п п

(теорема 4.2.1). Последний результат ощутимо показывает значение параметрических представлений как важнейшего модельного класса УС: идеи, возникшие при исследовании параметрических представлений находят применение не только при синтезе таких близких к ним во многих отношениях УС, какими являются, например, сети из функциональных элементов, но и сохраняют свою действенность в отношении таких, на первый взгляд, непохожих на них УС, как Т-схет.

Литература i- Burks А. П., Wright J. В. Theory or logical nets II Proc. IRE. 1953. V. 41, }ê 10. P. 1357-1365. Имеется перевод: Беркс А.,

Райт Дне. Теория логических сетей // Кибернетический сборник. Вып. 4. М.: ИЛ, 1962. С. 33-57.

2. Биркгоф Г. Теория решеток. М.: Наука, 1984.

3. Зырянов М. А. О сложности реализации некоторых классов функциональных булевских матриц' проводимости многополюсными ориентированными итеративными контактными схемами // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 1994, №4. С. 57 - 64.

4. Клини С. Введение в метаматематику. М.: ИЛ, 1957.

5. Кузнецов А. В. О средствах для обнаружения невыводимости или невыразимости. В сб.: Логический вывод. М.: Наука, 1979. С. 5-33.

6. Ложкин С. А'. О синтезе ориентированных контактных схем // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 1995, №2. С. 36-42.

7. Ложкин С. А. О синтезе некоторых типов схем на основе сдвиговых разбиений, порожденных универсальными матрицами // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. 1996, Л 1. С. 62-69.

8. Лупанов 0. Б. Об одном методе синтеза схем // Известия ВУЗ, сер. Радиофизика. 1958. Т. 1, 1. с. 120-140.

9. Лупанов 0. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. М.: Физматгиз, 1960. С. 61-80.

]0. Лупанов О. Б. О синтезе схем из пороговых элементов // Проблемы кибернетики. Вып. 26. М.: Наука, 1973. С. 109-140.

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

12. Мальцев А. И. 0 производных операциях и предикатах // Доклады АН СССР. 1957. Г. 116, ЛИ. С. 24-27.

]3. Нечипорук Э. И. О сложности схем в некоторых базисах, содержащих нетривиальные элементы с нулевыми весами // Проблемы кибернетики. Вып. 8. М.: Физматгиз, 1962. С. 123-160.

|4. Нечипорук Э. И. О синтезе схем из пороговых элементов // Проблемы кибернетики. Вып. 11. М. : Наука, 1964. С. 49-62.

15. Орлов В. А. О двух классах схем в автоматных базисах // Кибернетика. 1981. № 5. С. 131 - 135.

|6. Сапоженко А. А., Ложкин С. А. Методы логического проектирования и оценки сложности схем на дополняющих М0П-транзисторах//Микроэлектороника. 1983. Т. 12, вып. 1. С. 42 - 47.

17. Яблонский С. В. Основные понятия кибернетики // Проблемы кибернетики. Вып. 2. М.: Физматгиз, 1959. С. 7-38.

18. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.

19. Burris S., Willard R. Finitely many primitive positive clones H Proc. Amer. Math. Soc. 1987 . 7. 101, № 3. P. 427 - 430.

20. Savage J. E, ïïie compleilty of computing. Wiley, 1976.

21_. Wegener I. The complexity ol Boolean functions. - Stuttgart: Wiley & Teubner, 1987.

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

1. Касим-Заде 0. M. О сложности реализации булевых функций в одной модели, электронных схем на дополняющих МОП-транзисторах // Тезисы докладов VIII Всесоюзной конференции по проблемам теоретической кибернетики. Горький, 1988. С.148-149.

2. Касим-Заде О. М. 0 сложности реализации булевых функций в одной модели электронных схем // Математические вопросы кибернетики. Вып. 2. М.: Наука, 1989. С. 145-160.

3. Касим-Заде О. М. О сложности параметрического представления функций алгебры логики // Дискретный анализ (Методы дискретного

анализа в изучении булевых функций и графов). Вып. 48. Новосибирск, 1989. С. 97.

4. Касим-Заде 0. М. 0 неявной выразимости булевых функций // Сибирский журнал исследования операций. 1994. Т. 1, №1. С. 79-80.

5. Касим-Заде 0. М. О сложности схем в одном бесконечном базисе // Вестник Московского университета. Сер. 1. Математика. Механика. 1994. №6. С. 40-44.

6. Касим-Заде 0. М. 0 неявной выразимости булевых функций // Вестник Московского университета. Сер. 1. Математика. Механика. 1995. Я 2. С. 44-49.

7. Касим-Заде 0. М. О сложности реализации булевых функций схемами в одном бесконечном базисе // Дискретный анализ и исследование операций. 1995. Т. 2, № 1. С. 7-20.

8. Касим-Заде 0. М. 0 сложности схем в бесконечных базисах// Дискретный анализ и исследование операций. 1995. Т.2, № 1. С. 74.

9. Касим-Заде 0. М. О неявной выразимости в двузначной логике и криптоизоморфизмах двухэлементных алгебр // Доклады РАН. 1996. Т. 348. № 3. С. 299-301.

10. Касим-Заде 0. М. 0 синтезе сетей из функциональных элементов // Доклады РАН. 1996. Т. 348. № 2. С.159-161. ,

11. Касим-Заде 0. М. 0 ранге параметрических и неявных представлений булевых функций // Второй Сибирский конгресс по прикладной и индустриальной математике. Тезисы докладов, часть II. Новосибирск, 1996. С. 115-116.

12. Касим-Заде 0. М. 0 сложности параметрических представлений функций алгебры логики // Проблемы теоретической кибернетики. Тезисы докладов XI Международной конференции. Ульяновск, 1996. С. 86-88.