Московский государственный университет

имени М. В. Ломоносова

На правах рукописи

Шуплецов Михаил Сергеевич

Методы синтеза и оценки сложности схем,

построенных из элементов предикатного типа

Специальность 01.01.09 — дискретная математика

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

Автореферат

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

Москва — 2011

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

Научный руководитель: доктор физико-математических наук, профессор Ложкин Сергей Андреевич

Официальные оппоненты: доктор физико-математических наук, ведущий научный сотрудник Института системного анализа РАН Шоломов Лев Абрамович кандидат физико-математических наук, старший научный сотрудник Института системных исследований РАН Кузнецов Юрий Владимирович

Ведущая организация: Пензенский государственный университет

Защита диссертации состоится 22 апреля 2011 г. в 11 : 00 на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М. В. Ломоносова по адресу: 119991, ГСП–1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ, с текстом автореферата — на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

Автореферат разослан « » марта 2011 г.

Ученый секретарь диссертационного совета профессор Трифонов Н. П.

Общая характеристика работы

Актуальность темы. Задача синтеза управляющих систем является одной из основных задач математической кибернетики. Она возникла в 30-х — 40-х годах прошлого века на основе ряда задач, связанных с логическим описанием и проектированием различных типов дискретных вычислительных устройств, и обрела строгую математическую постановку в работах К. Шеннона1.

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

В диссертации рассматривается задача массового синтеза, которая заключается в изучении асимптотического поведения так называемой функции Шеннона от натурального аргумента n, равной максимальной сложности реализации булевых функций от n переменных в выбранном классе схем. Порядок функции Шеннона, связанной со сложностью контактных схем, где под сложностью понималось общее число контактов схемы, был найден К. Шенноном1. В работах О. Б. Лупанова2 впервые было установлено асимптотическое поведение функции Шеннона для всех основных классов схем (схемы из функциональных элементов, формулы, контактные схемы и др.).

Модели управляющих систем можно условно разделить на два основных типа: функциональные и проводящие. Характерной чертой управляющих систем функционального типа является такой способ функционирования, при котором значения реализуемых функций находятся как решение некоторой системы (булевых) уравнений. Так, например, любая Shannon C. E. The synthethis of two-terminal switching circuits // Bell Syst. Techn. J. 1949. V. 28.

N 1. P. 59–98.

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

136 с.

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

Среди функциональных моделей наряду с моделями явного типа имеются и модели, допускающие неявное описание реализуемых функций при помощи систем уравнений, которые могут содержать переменные, выступающие в роли неизвестных параметров. Основными моделями такого типа являются неявные и параметрические представления булевых функций, сети из функциональных элементов. Отметим, что введенное А. В. Кузнецовым3 понятие неявной и параметрической выразимости, как обобщение понятия выразимости функций суперпозициями, заложило фундамент для модели неявных и параметрических представлений булевых функций. Основные результаты, связанные с решением задачи синтеза для этой модели, были получены О. М. Касим-Заде4. В этой работе была установлена асимптотика функции Шеннона для сложности параметрических представлений над произвольным параметрически полным конечным базисом, а также отмечена связь и проведено сравнение этой модели с моделями СФЭ и сетей из функциональных элементов.

Одним из важных расширений моделей функционального типа, являются классы схем, которые построены из элементов, реализующих не всюду определенные функции. Отметим, что основа для рассмотрения моделей такого типа была заложена в работах Р. В. Фрейвалда5 и В. В. Тарасова6, в которых исследовались вопросы полноты для различных классов не всюду определенных булевых функций. Отметим, что структура замкнутых классов для не всюду определенных функций изучалась в работе7 В. Б. Алексеева и А. А. Вороненко.

Примером модели указанного типа является модель высокоимпедансных СФЭ, которая рассматривалась в работах А. В. Долгополовой8. В данной модели схема состоит из многозначных функциональных элеменКузнецов А. В. О средствах для обнаружения невыводимости или невыразимости // Логический вывод. М.: Наука, 1979. С. 5–33.

Касим-Заде О. М. О сложности параметрических представлений булевых функций // Математические вопросы кибернетики. Вып. 7. М.: Наука. Физматлит. 1998. С. 85–160.

Фрейвалд Р. В. О полноте частичных функций алгебры логики // ДАН СССР. 1966. Т. 167, Т. 6. С. 1249–1250.

Тарасов В. В. Критерий полноты для не всюду определенных функций алгебры логики // Проблемы кибернетики. Сборник статей. Вып. 30, М., Наука, 1975. С. 319–325.

Алексеев В. Б., Вороненко А. А. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика. 1994. Т. 6. Вып. 4. С. 58–79.

Долгополова А. В. Задача синтеза и проблемы полноты для одного класса схем из функциональных элементов, связанных с электронными схемами // Диссертация на соискание ученой степени кандидата физико-математических наук: 01.01.09 М., 2003.

тов, на выходах которых наравне с булевыми значениями 0 и 1 могут появляться неопределенные значения двух типов: “высокий импеданс” и “короткое замыкание”, а сама схема строится из таких элементов при помощи обычной операции суперпозиции и операции объединения выходов по принципу проводного “или”. При этом неопределенность типа “высокий импеданс” совпадает с неопределенностью из работы В. В. Тарасова и позволяет, в ряде случаев, существенно уменьшить сложность реализации функций в этой модели по сравнению с моделью классических СФЭ, а неопределенность типа “короткое замыкание” совпадает с неопределенностью, рассмотренной в работе Р. В. Фрейвалда7.

Результаты работ А. В. Долгополовой8 показывают, что в некоторых случаях использование таких моделей позволяет строить более “экономные” по сравнению с моделью классических СФЭ схемы на КМОП-транзисторах.

Модели проводящего типа характеризуются тем, что их функционирование определяется наличием или отсутствием проводимости между входными и выходными полюсами при различных фиксированных значениях управляющих переменных. К моделям такого типа можно отнести контактные схемы, двоичные решающие диаграммы (Binary Decision Diagrams, BDDs), итеративно-контактные схемы и др., а также различные модификации и обобщения указанных моделей.

Отметим, что в работах С. А. Ложкина9 рассматривался класс функционально-проводящих схем, который обобщает многие модели проводящего типа, а также некоторые модели функционального типа. Данные схемы строятся из элементов специального вида, каждый из которых представляет собой контакт, проводимостью которого управляет выход функционального элемента с прямыми и итеративными входами. Для некоторых типов базисов С. А. Ложкиным9 была установлена асимптотика функции Шеннона, связанной со сложностью указанных схем, причем в ряде случаев для неё были получены асимптотические оценки высокой степени точности.

Исследуемый в диссертации класс предикатных схем обобщает большинство моделей как функционального, так и проводящего типа, причем рассматриваемая модель обладает рядом интересных свойств, которые отличают её от моделей указанных видов. Поэтому данный класс следуЛожкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6. М.: Наука. Физматлит. 1996. С. 189– 214.

ет отнести к третьему типу управляющих систем, которые будем далее называть предикатными.

Основу для появления моделей предикатного типа заложила работа В. Г. Боднарчука, Л. А. Калужнина, В. Н. Котова и Б. А. Ромова, где рассматривалась операция суперпозиции и вопросы полноты для предикатов. Указанные вопросы полноты были решены в ней с помощью установления соответствия Галуа между замкнутыми относительно обычной операции суперпозиции классами функций и замкнутыми относительно введенной операции суперпозиции классами предикатов. Отметим, что независимо этот результат был также получен Д. Гейгером11. Для моделей предикатного типа в работе [1] была предложена естественная схемная интерпретация в виде двудольного графа специальной структуры. Зарубежными авторами похожая схемная интерпретация для предикатных моделей была предложена независимо в работах12 М. Кука и Дж. Брука (в этих работах для схем такого типа в основном используются термины “networks of relations” и “predicate graphs”).

Модели предикатного типа находят свое применение в различных областях науки. Схемы такого типа используются, например, при решении задач моделирования и анализа нейронных сетей12, различных задач выполнимости с ограничениями13 (в зарубежной литературе для таких задач используется термин “constraint satisfaction problems”) и др. Следует отметить то, что модели предикатного типа можно применять для решения задач анализа и синтеза различных типов дискретных управляющих систем, включающих в себя как проводящие, так и функциональные элементы. Указанная особенность характеризует, в частности, современные сверхбольшие интегральные схем (СБИС).

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

Боднарчук В. Г., Калужнин Л. А., Котов В. Н., Ромов Б. А. Теория Галуа для алгебр Поста // Кибернетика. 1969. № 3. C. 1–10; №5. С. 1–9.

Geiger D. Closed systems of functions and predicates // Pacific J. Math. 1968. Volume 27. P. 95–100.

Cook M., Bruck J. Networks of relations for presentation, learning and generalization. In A. Abraham, and J.Abonyi, editors, Proceedings of the Fourth Interantional Conference on Intelligent System design and Applications, Advances in Soft Computing. Springer-Verilag, 2004.

Dechter R. Constraint Processing. Morgan Kaufmann, 2003.

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

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

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

Публикации и апробирование. По теме диссертации опубликовано 7 печатных работ [1]–[7], из которых статьи [4, 7] — в изданиях, рекомендованных ВАК. Результаты диссертации докладывались на семинарах кафедры математической кибернетики факультета ВМК МГУ, а также на семинаре кафедры дискретной математики механико-математического факультета МГУ и, кроме того, докладывались и обсуждались на следующих конференциях и семинарах:

1. XVI международная школа-семинар «Синтез и сложность управляющих систем» (Санкт-Петербург, 26–30 июня 2006);

2. XV международная конференции «Проблемы теоретической кибернетики» (Казань, 2–7 июня 2008);

3. XVII международная школа-семинар «Синтез и сложность управляющих систем» (Новосибирск, 27 октября – 1 ноября 2008);

4. XVIII международная школа-семинар «Синтез и сложность управляющих систем» (Пенза, 28 сентября – 3 октября 2009);

5. X международный семинар «Дискретная математика и её приложения» (Москва, 1–6 февраля 2010).

Структура и объем работы. Диссертация состоит из введения, трёх глав и списка литературы. Текст изложен на 114 страницах, диссертация содержит 6 рисунков. Список литературы включает 39 наименований.

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

Пусть B = {0, 1}, N = {1, 2,...}, и через B n, n N, обозначена n-я декартовая степень множества B. Булевой функцией или функцией алгебры логики (ФАЛ) f (x1,..., xn ) от n переменных называют отображение f : B n B, а булевым предикатом (x1,..., xn ) от n переменных — отображение : B n {И, Л}, где И, Л — истинностные значения “истина” и “ложь”. Набор, B n, значений переменных x1,..., xn будем называть допустимым для предиката, если () = И. Пусть X = {x1,..., xn,...}(соответственно Y = {y1,..., yp,...}) — счетный упорядоченный алфавит полюсных (соответственно внутренних) переменных. Пусть 2 (n) — множество всех булевых предикатов от n переменных x1,..., xn, а 2 — множество всех булевых предикатов от переменных из X. Пусть, кроме того, m (n) — множество всех систем из m булевых предикатов от переменных x1,..., xn.

Для описания предиката (x1,..., xn ) будем использовать его характеристическую функцию, которая принимает значение 1 на наборе, B n, тогда и только тогда, когда () = И, и равна 0 на всех остальных наборах. Кроме того, в некоторых случаях предикат будем описывать при помощи множества его допустимых наборов. Будем считать, что предикат (x1,..., xn ) существенно зависит от переменной xi, 1 i n, если его характеристическая функция существенно зависит от этой переменной. В дальнейшем, как ФАЛ, так и предикаты будем рассматривать с точностью до добавления и изъятия несущественных переменных. Предполагается, что константные предикаты (ФАЛ) имеют пустое множество существенных переменных.

Базисом будем называть произвольную конечную систему предикатов B = {1,..., b }, в которой предикат i, i = 1,..., b, существенно зависит от ki переменных из X и ему сопоставлено положительное действительное число L (i ), характеризующее “вес” этого предиката.

Схемой из предикатных элементов или предикатной схемой в базисе B назовем помеченный неориентированный двудольный граф следующей структуры:

1) каждая вершина из первой доли помечена некоторым символом из алфавита Y или множеством символов из алфавита X, причем множества символов, приписанных разным вершинам, попарно не пересекаются;

2) каждая вершина второй доли14 помечена некоторым символом i из множества B и соединена ki ребрами, пронумерованными числами 1,... , ki, с вершинами из первой доли.

Вершины из первой доли будем называть узлами схемы, а вершины из второй доли — её предикатными элементами. Узлы схемы, соединенные ребрами с предикатным элементом, будем называть полюсами этого элемента, а узлы, соответствующие входным переменным, — полюсами схемы. При этом считается, что узел является j-м полюсом предикатного элемента и соответствует его j-ой переменной, если соединяющее их ребро имеет номер j. Будем считать элементарной такую предикатную схему, которая состоит либо из изолированной полюсной вершины, либо только из одного предикатного элемента i, 1 i b, и ki полюсных узлов, являющихся полюсами указанного элемента.

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

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

В общем случае вторая доля может быть пустым множеством.

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

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

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

Кроме того, во второй части введения отмечается связь суперпозиции предикатных схем с операцией суперпозиции для предикатов, рассмотренной в работе10, и приводится вытекающая из неё теорема о полноте для предикатных схем, а также описывается представление предикатных схем при помощи (, &)-формул15.

В третьей части введения ставится задача синтеза для класса UB — класса предикатных схем, построенных в полном предикатном базисе B.

При этом под сложностью предикатной схемы, UB, понимается сумма “весов” её предикатных элементов, а под сложностью LB () предиката — минимальная из сложностей реализующих его схем в базисе B. Введем обычным образом функцию Шеннона для сложности предикатных схем в классе UB. В третьей части введения формулируются основные результаты диссертации, связанные с описаниМарченков С. С. Предполнота замкнутых классов в Pk : предикатный подход // Математические вопросы кибернетики. Вып. 6. М.: Наука. Физматлит, 1996. С. 117–132.

ем поведения указанной функции Шеннона в различных классах базисов.

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

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

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

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

Так в разделе 1.2 отмечается эффект “распадения” предиката на “блоки”. При этом блочным называется предикат, характеристическая функЗахарова Е.Ю. Яблонский С.В. Некоторые свойства невырожденных суперпозиций в Pk // Математические заметки. Т. 12. № 1. 1972. С. 3–12.

Ложкин С.А. Об асимптотическом поведении функции Шеннона для сложности схем из функциональных элементов в k-значной логике // Труды IV Международной конференции “Дискретные модели в теории управляющих систем”(19–25 июня 2000г.). Москва. “МАКС Пресс”. 2000. С. 64–67.

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

При этом макропеременной мощности r предиката (x1,..., xn ) называется множество M, состоящее из r, 1 r n, существенных переменных этого предиката. Для натурального n, n 2, ФАЛ f (x1,..., xn ) будем называть функцией отождествления переменных x1,..., xn, если для неё верно представление:

где i1,..., in — некоторая перестановка чисел 1,..., n и k 2. Макропеременная M предиката называется его квазипеременной, если существует такая функция отождествления f переменных из M, для которой f 1, и если M является максимальной по включению макропеременной, обладающей указанным свойством.

Набор, B n, будем называть основным набором переменной xi, i = 1,..., n, предиката (x1,..., xn ), если где — соседний с по переменной xi набор куба B n. Пусть M — некоторая макропеременная предиката, не содержащая его переменную x.

Пару M = (M, x) будем называть обобщенной переменной указанного предиката, если существует такой набор булевых констант, подстановка которого вместо всех переменных предиката, не входящих в M {x}, даёт предикат от переменных M {x}, обладающий хотя бы одним основным набором для переменной x. При этом считается, что обобщенная переменная M = (M, x) является минимальной по включению, то есть для любой переменной y, y M, пара (M \ {y}, x) не является обобщенной переменной предиката. Отметим, что понятие обобщенной переменной из работы8 можно рассматривать как частный случай введенного выше понятия. Основными утверждениями раздела 1.2 являются теоремы, которые описывают изменение множества обобщенных переменных предикатов при бесповторных суперпозициях специального вида.

В разделе 1.3 для произвольного предиката определены его комбинационный ранг () и информационный ранг (). Линейным назовем предикат с линейной характеристической функцией, которая существенно зависит от трёх и более переменных. Комбинационным рангом () неблочного предиката будем называть величину, которая задается следующим равенством:

где v — число квазипеременных предиката. Комбинационный ранг блочного предиката определяется как сумма комбинационных рангов блоков, на которые он распадается.

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

Для предикатного базиса B = {1,..., b } его расширенным базисом назовем предикатный базис B, содержащий все предикаты, получающиеся из предикатов базиса B при помощи операций снятия и отождествления полюсов (включая все предикаты базиса B). При этом считается, что “вес” L () предиката, B, который получается из базисного предиката i, 1 i b, при помощи применения указанных операций, равен L (i ). В разделе 1.3 для предикатного базиса B введены его приведенный вес B и обобщенный приведенный вес B, которые задаются равенствами и определены для произвольного полного базиса B.

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

В разделе 1.4 доказывается следующая теорема.

Теорема. 1.7. Для почти всех предикатов комбинационный ранг предиката равен его информационному рангу.

Будем считать, что какое-либо свойство выполнено для почти всех предикатных базисов, если для любых натуральных k и m, а также любого набора положительных действительных чисел (L1,..., Lm ) доля тех наборов (1,..., m ) из m (k), задающих базис для которых выполнено указанное свойство, больше, чем 1 (k), где (k) стремится к нулю при k стремящемся к бесконечности.

В разделе 1.4 доказывается следующая теорема.

Теорема. 1.8. Для любых натуральных k и m, а также любого набора положительных действительных чисел (L1,..., Lm ) доля тех наборов (1,..., m ) из m (k), для которых B = B, где B — базис вида B = {(1, L1 ),..., (m, Lm )}, не меньше, чем Из указанной теоремы следует, что для почти всех базисов приведенный вес и обобщенный приведенный вес совпадают. Отметим, что аналогичный подход использовался В. А. Орловым18 при исследовании приведенного веса для функционально полных базисов в Pk. Кроме того, в разделе 1.4 доказывается, что для всех базисов B, содержащих предикаты от не более чем трех переменных, приведенный вес B равен обобщенному приведенному весу B.

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

Пусть UB (L, n) — число попарно неэквивалентных предикатных схем в классе UB сложности не превосходящей L, реализующих предикаты от n переменных. Для получения нижних оценок функции Шеннона LB (n) используются обычные “мощностные” соображения, которые основаны на использовании “мощностного” равенства Отметим, что при получении верхних оценок для UB (L, n) возникает ряд трудностей, связанных с отмеченным выше эффектом “распадения” предикатов на “блоки”.

Орлов В.А. Об оптимальности почти всех базисов в Pk // ДАН. Т. 363. № 5. 1998. С. 602–603.

Для преодоления указанных трудностей в разделе 2.1 доказывается утверждение о возможности “перехода” от базиса B, содержащего блочные предикаты, к базису B без блочных предикатов, для которого LB (n) LB (n) и B B. Основным результатом раздела 2.1 является следующая теорема.

Теорема. 2.2. Если B — произвольный полный предикатный базис, то для функции Шеннона LB (n) справедлива следующая нижняя оценка:

В разделе 2.2 понятие универсального множества функций9 обобщается на случай произвольного булевого предиката. Пусть h(x1,..., xn ) — ФАЛ от n переменных, а (z, x1,..., xn ) — предикат от (n + 1) переменной. Тогда пара P = (h, ) слабо моделирует функцию f (x1,..., xn ), если для любого набора, B n, значений переменных x1,..., xn и характеристической функции предиката выполняется одно из следующих равенств:

При этом функцию h будем называть сигнальной функцией моделирования P. Рассмотрим произвольный предикат (u0, u1,..., up ) от (p + 1) переменной и выделим некоторую переменную этого предиката (не ограничивая общности рассуждений, будем считать, что это переменная u0 ).

Множество ФАЛ G, G P2 (m), будем называть предикатным -универсальным множеством порядка m, если существует такая сигнальная ФАЛ h(x1,..., xm ), что для любой ФАЛ g(x1,..., xm ) существует предикат и в множестве G найдутся такие ФАЛ g1,..., gp, что пара (h, ) слабо моделирует ФАЛ g и для предиката верно следующее представление при помощи (, &)-формулы15 :

где Y = {y1,..., yp }. Используя это понятие, в разделе 2.2 рассматривается построение разложений предиката по специальным системам обобщенных переменных, а также приводится доказательство некоторых вспомогательных утверждений необходимых для получения верхних оценок функции Шеннона LB (n).

Основным результатом раздела 2.3 является следующая теорема.

Теорема. 2.3. Если B — произвольный полный предикатный базис, то для функции Шеннона LB (n) справедлива следующая верхняя оценка:

Третья глава диссертации посвящена получению асимптотических оценок высокой степени точности для функции Шеннона LB (n) в базисах B определенного вида.

Используя специальное представление предикатных схем, в разделе 3.1 уточняется нижняя оценка функции Шеннона LB (n) для случаев, когда среди базисных предикатов, на которых достигается приведенный вес B базиса B, найдется неблочный нелинейный предикат, число полюсов которого равно ()+1.

Пусть (x1,..., xn ), n 3, — некоторый предикат с двумя выделенными переменными (не ограничивая общности рассуждений, будем считать, что это переменные x1 и x2 ), и для любого i, i = 3,..., n, существует такой набор i = (3,..., i1, i+1,..., n ), что характеристическая функция (x1, x2, 3,..., i1, xi, i+1,..., n ) равна а также существует набор = (3,..., n ) такой, что где 1,..., 6 — булевы константы. Предикат, который обладает указанными свойствами, будем называть проводящим. Отметим, что любой проводящий предикат является неблочным и нелинейным, а число его полюсов равно () + 1. Полный предикатный базис B назовём обобщенно-проводящим, если в множестве базисных предикатов, на которых достигается приведенный вес B базиса B, найдётся проводящий предикат, имеющий максимальное число полюсов среди всех предикатов указанного множества.

В разделе 3.2 для произвольного булевого предиката вводится понятие селекторного разбиения переменных, которое обобщает понятие селекторного разбиения переменных ФАЛ9, строятся нетривиальные селекторные разбиения для предикатов специального вида и доказываются некоторые вспомогательные утверждения, необходимые для уточнения верхних оценок функции Шеннона LB (n) для обобщенно-проводящих базисов B.

Основным результатом раздела 3.3 является следующая теорема.

Теорема. 3.3. Если B — обобщенно-проводящий базис, то для функции Шеннона LB (n) верна следующая асимптотическая оценка высокой степени точности:

где kB — максимальное число полюсов у базисных предикатов, на которых достигается приведенный вес B базиса B.

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

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

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

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

1. Ложкин С. А., Шуплецов М. С. Асимптотические оценки высокой степени точности для сложности предикатных схем из одного класса // Материалы XVI Международной школы-семинара “Синтез и сложность управляющих систем” (Санкт-Петербург, 26-30 июня г.). М.: Изд-во механико-математического факультета МГУ, 2006.

С. 72–77.

2. Шуплецов М. С. Оценки сложности предикатных схем в некоторых базисах // Проблемы теоретической кибернетики. Тезисы докладов XV Международной конференции (Казань, 2-7 июня 2008 г.). Под редакцией Ю. И. Журавлева. Казань: Отечество, 2008. С. 134–135.

3. Шуплецов М. С. Асимптотика функции Шеннона для сложности предикатных схем в некоторых базисах блочного типа // Материалы XVII Международной школы-семинара “Синтез и сложность управляющих систем” имени академика О. Б. Лупанова (Новосибирск, октября – 1 ноября 2008 г.). Под редакцией О. М. Касим-Заде. Новосибирск: Изд-во ИМ СО РАН, 2008. С. 196–201.

4. Шуплецов М. С. Оценки высокой степени точности для сложности предикатных схем в некоторых базисах // Учен. зап. Казан. ун-та.

Сер. Физ.-матем. науки. 2009. Т. 151, кн. 2, С. 173–184.

5. Шуплецов М. С. О синтезе предикатных схем на основе разложений по обобщенным переменным // Материалы XVIII Международной школы-семинара “Синтез и сложность управляющих систем” имени академика О. Б. Лупанова (Пенза, 28 сентября – 3 октября 2009 г.). Под редакцией О. М. Касим-Заде. М.: Изд-во механикоматематического факультета МГУ, 2009. С. 123–128.

6. Шуплецов М. С. О сложности предикатных схем в базисах из элементов с не более чем тремя полюсами // Материалы X Международного семинара “Дискретная математика и ее приложения” (Москва, МГУ, 1–6 февраля 2010 г.). Под редакцией О.М.Касим-Заде. М.: Изд-во механико-математического факультета МГУ, 2010. С. 164–166.

7. Шуплецов М. С. Об одном подходе к синтезу предикатных схем на основе обобщенных переменных // Вестник московского университета. Сер. 15. Вычислительная математика и кибернетика. М., 2010.

№ 4. С. 24–30.