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

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

Методы синтеза и оценки сложности схем, построенных из элементов предикатного типа тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Шуплецов, Михаил Сергеевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Методы синтеза и оценки сложности схем, построенных из элементов предикатного типа»

Автореферат диссертации на тему "Методы синтеза и оценки сложности схем, построенных из элементов предикатного типа"

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

4842044

. 11 I ь и^^-у

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

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

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

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

Москва — 2011

7 ДПР 2011

4842044

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

Научный руководитель:

Официальные оппоненты:

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

Ложкин Сергей Андреевич

доктор физико-математических наук, ведущий научный сотрудник Института системного анализа РАН Шоломов Лев Абрамович

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

кандидат физико-математических наук, старший научный сотрудник Института системных исследований РАН Кузнецов Юрий Владимирович

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

Защита диссертации состоится 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.

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

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

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

1Shannon С. Е. The synthethis of two-terminal switching circuits // Bell Syst. Techn. J. 1949. V. 28. N 1. P. 59-98.

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

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

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

B. В. Тарасова6, в которых исследовались вопросы полноты для различных классов не всюду определенных булевых функций. Отметим, что структура замкнутых классов для не всюду определенных функций изучалась в работе7 В. Б. Алексеева и А. А. Вороненко.

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

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

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

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

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

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

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

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

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

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

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

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

эЛожкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6. М.: Наука. Физматлит. 1996. С. 189214.

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

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

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

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

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

"Geiger D. Closed systems of fonctions and predicates // Pacific J. Math. 1968. Volume 27. P. 95-100.

12Cook M., Bruck J. Networks of relations for présentation, learning and generalization. In A. Abraham, and J.Abonyi, editors, Proceedings of ttrn Fourth Interantional Conférence on Intelligent System design and Applications, Advances in Soft Computing. Springer-Verilag, 2004.

13Dechter R. Constraint Processing. Morgan Kaufmaon, 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 наименований.

Краткое содержание диссертации

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

Пусть В — {0, 1}, N = {1, 2,...}, и через Вп, п £ М, обозначена п-я декартовая степень множества В. Булевой функцией или функцией алгебры логики (ФАЛ) / (х 1,..., хп) от п переменных называют отображение / : Вп В, 8, булевым предикатом тг(х 1,..., хп) от п переменных — отображение 7Г : Вп —► {И, Л}, где И, Л — истинностные значения "истина" и "ложь". Набор а, а 6 Вп, значений переменных х\,..., хп будем называть допустимым для предиката 7Г, если 7г (а) = И. Пусть А? = {х\, ..., хп,...}(соответственно У = {зд,..., ур,...}) — счетный упорядоченный алфавит полюсных (соответственно внутренних) переменных. Пусть Пг (п) — множество всех булевых предикатов от п переменных XI,..., хп, а Пг — множество всех булевых предикатов от переменных из X. Пусть, кроме того, П™ (п) — множество всех систем из т булевых предикатов от переменных х\,..., хп.

Для описания предиката 7Г {х\,..., хп) будем использовать его характеристическую функцию Хтг, которая принимает значение 1 на наборе а, а € Вп, тогда и только тогда, когда 7г (а) = И, и равна 0 на всех остальных наборах. Кроме того, в некоторых случаях предикат будем описывать при помощи множества его допустимых наборов. Будем считать, что предикат я(х1,... ,хп) существенно зависит от переменной Х{, 1 ^ г < п, если его характеристическая функция х* существенно зависит от этой переменной. В дальнейшем, как ФАЛ, так и предикаты будем рассматривать с точностью до добавления и изъятия несущественных переменных. Предполагается, что константные предикаты (ФАЛ) имеют пустое множество существенных переменных.

Базисом будем называть произвольную конечную систему предикатов © = {7Гх,..., я-;,}, в которой предикат тг*, г = 1,..., Ь, существенно зависит от переменных из Л" и ему сопоставлено положительное действительное число С(яч), характеризующее "вес" этого предиката.

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

ющей структуры:

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

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

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

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

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

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

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

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

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

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

В третьей части введения ставится задача синтеза для класса Ив — класса предикатных схем, построенных в полном предикатном базисе 23. При этом под сложностью предикатной схемы Е, Е G U<s, понимается сумма "весов" её предикатных элементов, а под сложностью Ь®(7г) предиката 7г — минимальная из сложностей реализующих его схем в базисе 93. Введем обычным образом функцию Шеннона

L<s(n) = шах L<в(7г) яеп2(п)

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

16Марченков С. С. Предполнота замкнутых классов в Р*: предикатный подход // Математические вопросы кибернетики. Вып. 6. М.: Наука. Физматлит, 1996. С. 117-132.

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

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

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

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

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

Так в разделе 1.2 отмечается эффект "распадения" предиката на "блоки". При этом блочным называется предикат, характеристическая функ-

1вЗахарова Е.Ю. Яблонский C.B. Некоторые свойства невырожденных суперпозиций в Рл // Математические заметки. Т. 12. № 1. 1972. С. 3-12.

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

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

При этом макропеременной мощности г предиката 7г(а;1,..., а:п) называется множество М, состоящее из г, 1 < г < п, существенных переменных этого предиката. Для натурального п, п > 2, ФАЛ / (х\,..., хп) будем называть функцией отождествления переменных ..., хп, если для неё верно представление:

/ (^Ь • ■ ■ I = £¿1 • • • • ' " • • • ' V ' . . . • • ... ■ Х{п,

где ¿1,..., г„ — некоторая перестановка чисел 1,..., п и к > [|]. Макропеременная М предиката 7Г называется его квазипеременной, если существует такая функция отождествления / переменных из М, для которой (7 —Хп) = 1, и если М является максимальной по включению макропеременной, обладающей указанным свойством.

Набор а, а € Вп, будем называть основным набором переменной

предиката 7г (щ,..., хп), если

Хп (а) = Хп{а) = 1 и Хтг (/?) = О,

где р — соседний с а по переменной ж,- набор куба Вп. Пусть М — некоторая макропеременная предиката 7Г, не содержащая его переменную ж. Пару 9Л = (М, х) будем называть обобщенной переменной указанного предиката, если существует такой набор /3 булевых констант, подстановка которого вместо всех переменных предиката 7Г, не входящих в Ми{ж}, даёт предикат тг' от переменных М и {а;}, обладающий хотя бы одним основным набором для переменной х. При этом считается, что обобщенная переменная Ш = (М, х) является минимальной по включению, то есть для любой переменной у, у б М, пара (М \ {у} , х) не является обобщенной переменной предиката 7Г. Отметим, что понятие обобщенной переменной из работы8 можно рассматривать как частный случай введенного выше понятия. Основными утверждениями раздела 1.2 являются теоремы, которые описывают изменение множества обобщенных переменных предикатов при бесповторных суперпозициях специального вида.

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

, ( V — 2, если предикат 7Г является линейным,

Л № = 1 1

[ V - 1, иначе,

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

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

Для предикатного базиса <8 = {7Г1,..., щ} его расширенным базисом назовем предикатный базис 03, содержащий все предикаты, получающиеся из предикатов базиса В при помощи операций снятия и отождествления полюсов (включая все предикаты базиса 93). При этом считается, что "вес" С (тг) предиката 7г, тг € который получается из базисного предиката щ, 1 < г < Ь, при помощи применения указанных операций, равен С (щ). В разделе 1.3 для предикатного базиса В введены его приведенный вес рдз и обобщенный приведенный вес р%, которые задаются равенствами

. £(тг) Л . ¿(тг) Рв = тт —^ /За = тт -т-г-у,

тгеш к (ж) о (7Г)

к(тг)>1 <5()г)>0

и определены для произвольного полного базиса 03.

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

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

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

Будем считать, что какое-либо свойство выполнено для почти всех предикатных базисов, если для любых натуральных А; и m, а также любого набора положительных действительных чисел (С[,..., С'т) доля тех наборов (к'ц..., ir'm) из Пf (к), задающих базис

для которых выполнено указанное свойство, больше, чем 1 — s (к), где е (к) стремится к нулю при к стремящемся к бесконечности. В разделе 1.4 доказывается следующая теорема.

Теорема. 1.8. Для любых натуральных к um, а также любого набора положительных действительных чисел (£[,..., С'т) доля тех наборов (flj,..., из Tlf(k), для которых ps< = РВ'> где 03' — базис вида = {(^îi А) > ■ • ■ I (nmi £'т)}> не меньше, чем k{k -1) 1

Из указанной теоремы следует, что для почти всех базисов приведенный вес и обобщенный приведенный вес совпадают. Отметим, что аналогичный подход использовался В. А. Орловым18 при исследовании приведенного веса для функционально полных базисов в P/t. Кроме того, в разделе 1.4 доказывается, что для всех базисов 05, содержащих предикаты от не более чем трех переменных, приведенный вес р® равен обобщенному приведенному весу pis.

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

Пусть ||W®(£,n)|| — число попарно неэквивалентных предикатных схем в классе сложности не превосходящей реализующих предикаты от п переменных. Для получения нижних оценок функции Шеннона L<s(n) используются обычные "мощностные" соображения, которые основаны на использовании "мощностного" равенства

||^ш(Ып),п)|| = 22".

Отметим, что при получении верхних оценок для ||тг) || возникает ряд трудностей, связанных с отмеченным выше эффектом "распадения" предикатов на "блоки".

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

Для преодоления указанных трудностей в разделе 2.1 доказывается утверждение о возможности "перехода" от базиса Ш, содержащего блочные предикаты, к базису 25 без блочных предикатов, для которого (п) ^ (п) и р§ ^ Основным результатом раздела 2.1 является следующая теорема.

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

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

X,j(z, а) = /(5) © z © h(a) или xdfo а) = /(5) V (z © Л(а)).

При этом функцию h будем называть сигнальной функцией моделирования ф. Рассмотрим произвольный предикат ip (tto, щ,..., ир) от (р + 1) переменной и выделим некоторую переменную этого предиката (не ограничивая общности рассуждений, будем считать, что это переменная щ). Множество ФАЛ G, G С Р2(тп), будем называть предикатным гр-универ-сальным множеством порядка т, если существует такая сигнальная ФАЛ h(xi, ..., хт), что для любой ФАЛ g(xi, ..., хт) существует предикат i? и в множестве G найдутся такие ФАЛ д\, др, что пара (h, ■&) слабо моделирует ФАЛ д и для предиката верно следующее представление при помощи (3, &)-формулы15:

19(z, хи ..., Хт) = (3 Y)ip{z, 2/i, • - -, ур) Д Ы = 9i(x ь ■ • •, хт)),

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

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

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

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

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

Пусть <р(х 1, ..., хп), п ^ 3, — некоторый предикат с двумя выделенными переменными (не ограничивая общности рассуждений, будем считать, что это переменные х\ и хг), и для любого г, i = 3, ..., п, существует такой набор а® = (аз, ..., «¿-ь а,+ъ • • • > ап), что характеристическая функция х<р(х1> х2, аз, ..., aj-i, Xi, Qfj+i, ..., а„) равна

хр V х? V хр или (xi ф Xi ф cr4) V х?, а также существует набор /3 = (/?з, ..., /?„) такой, что Xv{xx, х2, Рп) = Аъ v

где (7i,..., <7в — булевы константы. Предикат <р, который обладает указанными свойствами, будем называть проводящим. Отметим, что любой проводящий предикат у является неблочным и нелинейным, а число его полюсов равно к (</?) + 1. Полный предикатный базис 93 назовём обобщенно-проводящим, если в множестве базисных предикатов, на которых достигается приведенный вес р® базиса 23, найдётся проводящий предикат ¡р, имеющий максимальное число полюсов среди всех предикатов указанного множества.

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

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

Теорема. 3.3. Если Î8 — обобщенно-проводящий базис, то для функции Шеннона L<s {п) верна следующая асимптотическая оценка высокой степени точности:

2»/ (2 + ф1)\оё2п±0(1)\

Ьв (п) = рв— 1 + ->-- ,

ni п J

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

Основные результаты диссертации

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

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

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

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

Публикации по теме диссертации

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

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

3. Шуплецов М. С. Асимптотика функции Шеннона для сложности предикатных схем в некоторых базисах блочного типа // Материалы XVII Международной школы-семинара "Синтез и сложность управляющих систем" имени академика О. Б. Лупанова (Новосибирск, 27 октября - 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.

Напечатано с готового орипинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано в печать 21.03.2011 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 116. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

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

Введение

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

Модель схем из предикатных элементов и способы её представления

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

Глава 1. Модель схем из предикатных элементов и её основные характеристики

1.1 Структурное моделирование управляющих систем из некоторых классов при помощи схем из предикатных элементов

1.2 Обобщенные переменные и их изменение при суперпозициях

1.3 Некоторые числовые характеристики базисных предикатов и полных базисов.

1.4 Совпадение приведенного и обобщенного приведенного весов для некоторых классов базисов.

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

2.1 Нижние оценки функции Шеннона для сложности схем из предикатных элементов.

2.2 Построение предикатных универсальных множеств функций для специальных систем обобщенных переменных.

2.3 Верхние оценки функции Шеннона для сложности схем из предикатных элементов.

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

3.1 Уточнение нижних оценок функции Шеннона для сложности схем из предикатных элементов.

3.2 Селекторные разбиения множества переменных предикатов

3.3 Синтез схем из предикатных элементов с использованием селекторных разбиений переменных.•.

Введение диссертация по математике, на тему "Методы синтеза и оценки сложности схем, построенных из элементов предикатного типа"

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

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

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

В диссертации рассматривается задача массового синтеза, которая заключается в изучении асимптотического поведения так называемой функции Шеннона от натурального аргумента п, равной максимальной сложности реализации булевых функций от п переменных в выбранном классе схем. В работах О. Б. Лупанова (см.,например, [15]) впервые было установлено асимптотическое поведение функции Шеннона для всех основных классов схем (схемы из функциональных элементов (СФЭ), формулы, контактные схемы и др.).

Среди моделей управляющих систем можно условно выделить два основных типа: функциональные и проводящие. Характерной чертой управляющих систем функционального типа является такой способ функционирования, при котором значения реализуемых функций находятся как решение некоторой системы (булевых) уравнений. Так, например, любая формула или СФЭ может быть описана при помощи системы явных уравнений (см., например, [30, 21]), допускающих прямое последовательное вычисление реализуемых функций.

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

Одним из важных расширений моделей функционального типа, являются классы схем, которые построены из элементов, реализующих не всюду определенные функции. Отметим, что основа для рассмотрения моделей такого типа была заложена в работах Р. В. Фрейвалда [23] и В. В. Тарасова [22], в которых исследовались вопросы полноты для различных классов не всюду определенных булевых функций. Структура замкнутых классов для не всюду определенных функций изучалась в работе [1] и др.

Примером модели указанного типа является модель высокоимпеданс-ных СФЭ, которая рассматривалась в работах А. В. Долгополовой [4, 5]. В данной модели схема состоит из многозначных функциональных элементов, на выходах которых наравне с булевыми значениями 0 и 1 могут появляться неопределенные значения двух типов: "высокий импеданс" и "короткое замыкание", а сама схема строится из таких элементов при помощи обычной операции суперпозиции и операции объединения выходов по принципу проводного "или". При этом неопределенность типа "высокий импеданс" совпадает с неопределенностью из работы [22] и позволяет, в ряде случаев, существенно уменьшить сложность реализации функций в этой модели по сравнению с моделью классических СФЭ, а неопределенность типа "короткое замыкание" совпадает с неопределенностью, рассмотренной в работе [23].

Результаты работ [4, 5] показывают, что в некоторых случаях использование таких моделей позволяет строить более "экономные" по сравнению с моделью классических СФЭ схемы на КМОП-транзисторах.

Модели проводящего типа характеризуются тем, что их функционирование определяется наличием или отсутствием проводимости между входными и выходными полюсами при различных фиксированных значениях управляющих переменных. К моделям такого типа можно отнести контактные схемы, двоичные решающие диаграммы (ВБО), итеративно-контактные схемы и др., а также различные модификации и обобщения указанных моделей (см., например, [7, 11, 16, 20]).

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

Основу для появления моделей предикатного типа заложила работа [2], где рассматривалась операция суперпозиции и вопросы полноты для предикатов. Указанные вопросы полноты были решены в ней с помощью установления так называемого соответствия Галуа между замкнутыми относительно обычной операции суперпозиции классами функций и замкнутыми относительно введенной операции суперпозиции классами предикатов. Независимо этот результат был также получен в [37]. Для моделей предикатного типа в работе [14] была предложена естественная схемная интерпретация в виде двудольного графа специальной структуры. Зарубежными авторами похожая схемная интерпретация для предикатных моделей была предложена независимо в [33, 34, 35] (в этих работах для схем такого типа в основном используются термины "networks of relations" и "predicate graphs").

Модели предикатного типа находят свое применение в различных областях науки. Схемы такого типа используются, например, при решении задач моделирования и анализа нейронных сетей [33], различных задач выполнимости с ограничениями [34, 36] (в зарубежной литературе для таких задач используется термин "constraint satisfaction problems") и др. Особо следует отметить то, что модели предикатного типа можно эффективно применять для решения задач анализа и синтеза различных типов дискретных управляющих систем, включающих в себя как проводящие, так и функциональные элементы. Указанная особенность характеризует, в частности, современные СБИС типа "система на кристалле".

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

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

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

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

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

Модель схем из предикатных элементов и способы её представления

Пусть В = {0, 1}, N = {1, 2,.}, и через Вп, п е К, обозначена п-я декартовая степень множества В. Булевой функцией или функцией алгебры логики (ФАЛ) / (жх?., хп) от п переменных называют отображение / : Вп —» В, а булевым предикатом 7г (жх, ■ • •, хп) от п переменных — отображение 7Г : Вп —> {И, Л}, где И, Л — истинностные значения "истина" и "ложь". Набор а, а е Вп, значений переменных жх,., жп будем называть допустимым для предиката 7Г, если 7г (а) = И. Пусть А" = {жх,., хп,.} (соответственно У = • • •, уР, ■ ■ •}) — счетный упорядоченный алфавит полюсных (соответственно внутренних) переменных. Через Рг (п) (соответственно П2 (п)) обозначим множество всех ФАЛ (соответственно булевых предикатов) от п переменных х\,., хп, а для множества всех ФАЛ (соответственно булевых предикатов) от переменных из X будем использовать обозначение (соответственно П2). Кроме того, для множества всех систем из т ФАЛ (соответственно булевых предикатов) от переменных ж15., хп будем использовать обозначение Р2т (п) (соответственно П™ {п)).

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

Базисом будем называть произвольную конечную систему предикатов 05 = {7Гх,., 1Гь}, в которой предикат щ, г = 1,., 6, существенно зависит от переменных из X и ему сопоставлено положительное действительное число С {■Кг), характеризующее "вес" этого предиката.

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

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

2) каждая вершина второй доли1 помечена некоторым символом 7гг из множества 93 и соединена к{ ребрами, пронумерованными числами 1,., кг, с вершинами из первой доли.

Вершины из первой доли будем называть узлами схемы, а вершины из второй доли — её предикатными элементами. Узлы схемы, соединенные ребрами с предикатным элементом, будем называть полюсами этого элемента, а узлы, соответствующие входным переменным, — полюсами схемы. При этом считается, что узел является ] -м полюсом предикатного элемента и соответствует его ^'-ой переменной, если соединяющее их ребро имеет номер э. Полюс схемы, которому приписано более одной входной переменной, называется кратным полюсом этой схемы. Будем считать элементарной такую предикатную схему, которая состоит либо из изолированной полюсной вершины, либо только из одного предикатного элемента 7гг, 1 ^ г < Ь, и к( полюсных узлов, являющихся полюсами указанного элемента.

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

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

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

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

Замыканием базиса *В назовем множество всех предикатов, каждый из которых можно реализовать предикатной схемой в указанном базисе. Будем говорить, что базис является полным, если его замыкание совпадает с множеством всех предикатов, то есть с П2.

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

1) переименование полюсной переменной схемы, которое сводится к объединению этой схемы с изолированным полюсным узлом, отождествлению этого узла с узлом указанной переменной и приписыванию новой вершине полюсной переменной изолированного узла;

2) введение фиктивной полюсной переменной схемы, которое сводится к добавлению изолированного полюсного узла, помеченного символом этой переменной;

3) проекция или снятие полюсной переменной схемы, которое сводится к объединению этой схемы с изолированным полюсным узлом, отождествлению этого узла с узлом указанной переменной и приписыванию новой вершине новой внутренней переменной;

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

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

В работах [34, 35] рассматривался частный случай модели предикатных схем, отличающийся тем, что сложность дублирования информации в указанной модели считается сравнимой со сложностью "вычисления" некоторого предиката. При этом степень узлов таких схем не превосходит 2, а для организации "ветвления" узлов схемы используется тернарный предикат равенства е х2, £з), который задается следующей характеристической функцией:

Хе х2, я3) = хгх2х3 V х^х^. (1)

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

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

Напомним определение сохранения функции предикатом (см. [9]): ФАЛ (х1,., хп) от п переменных сохраняет предикат 7Г (ж1,., хт) от т переменных тогда и только тогда, когда для любых п допустимых наборов аг = (а1!,., агт), I = 1,., п, значений переменных предиката 7Г набор значений (а*,. тоже является допустимым для предиката тх. На основе этого определения введем следующие множества:

1) То (соответственно Т\) — множество всех предикатов, сохраняющих константную ФАЛ 0 (соответственно 1);

2) <5 — множество всех предикатов, сохраняющих ФАЛ х;

3) И (соответственно К) — множество всех предикатов, сохраняющих произвольную дизъюнкцию (соответственно конъюнкцию) двух и более переменных;

4) 5М — множество всех предикатов, сохраняющих все монотонные самодвойственные ФАЛ;

5) БЬ — множество всех предикатов, сохраняющих все линейные самодвойственные ФАЛ.

В работе [2] было установлено соответствие Галуа между замкнутыми классами функций и замкнутыми классами предикатов, которое сопоставляет каждому замкнутому классу ФАЛ, содержащему селекторные функции, замкнутый класс предикатов, содержащий диагонали, и наоборот. При этом минимальным замкнутым классам в Р2 соответствуют предполные классы в П2, а минимальным классам в Щ — предполные в Р2. Из результатов работы [2] с учетом диаграммы Поста (см., например, [31]) следует, в частности, что классы предикатов Т\, То, 5, .О, К, БМ и БЬ являются замкнутыми относительно операции суперпозиции и, более того, предпол-ными классами предикатов, причем в П2 нет других предиолных классов. Таким образом справедливо следующее утверждение.

Теорема (о полноте). Система булевых предикатов является полной тогда и только тогда, когда эта система не содержится целиком ни в одном из следующих семи классов булевых предикатов, замкнутых относительно суперпозиции: Ti, Tq, S, D, К, SM и SL.

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

Важной формой представления предикатных моделей являются также (3, &;)-формулы (см., например, [18]). Указанные формулы строятся над некоторым множеством базисных предикатов, выступающих в роли элементарных формул, с помощью операции конъюнкции и операции проекции, которая заключается в переименовании части переменных формулы и связывании этих переменных при помощи квантора существования. Кроме того, используется набор вспомогательных операций перестановки и отождествления переменных.

Пусть, по-прежнему, 95 = {7Г1,., пг&} — предикатный базис, в котором предикат щ, г = 1,., Ь, существенно зависит от ki переменных из X. Рассмотрим произвольную предикатную схему Е в базисе 95 с п полюсами xi,., хп и т внутренними переменными Y — (г/i,., ут), которая реализует предикат -к {х\,., хп). Пусть, кроме того, схема Е имеет р кратных входов, причем кратному входу с номером q, q — 1,., р, приписаны входные переменные из множества Xq = ., j>, а также содержит r¿, г = 1,., 6, предикатных элементов, помеченных символом щ, причем I-му, 1 ^ 1 ^ ki, полюсному узлу j-го, 1 ^ j ^ ri, элемента данного типа приписана переменная из множества {х\,., хп, г/j,., ут}. Тогда схему Е можно задать при помощи (3, &;) -формулы следующего вида: *(т,.,*„) = Д Д («м = «2.) (ЗУ) (Д Д* .,

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

Пусть Ы\в — класс предикатных схем, построенных в полном предикатном базисе 05. Тогда под сложностью Ь{Е) предикатной схемы Е, Е £ Ы^,, понимается сумма "весов" её предикатных элементов, а под сложностью (тг) предиката 7Г — минимальная из сложностей реализующих его схем в базисе 05. При этом считается, что по схеме Е можно однозначно определить класс схем и базис, в котором она построена, поэтому в записи Ь (Е) не используются дополнительные индексы. Введем обычным образом функцию Шеннона

Ь<з(п) = тах Ь^(тг) тгеп2(п) для класса в относительно функционала сложности Ь. Кроме того, для произвольного множества предикатов ф под сложностью (<5) будем понимать следующую величину:

Ьоз [Я) : тах 1/сз (7г).

Отметим, что (п) = Ьг$ (П2 (п)).

Задача синтеза для класса схем Ы® заключается в разработке методов построения по заданному (произвольному) предикату 7Г, 7Г £ П2 (п), реализующей его схемы Е, Е € Ы<в, сложность Ь (Е) которой "близка" к Ь® (7г), и установлении поведения функции Шеннона Ь^ (п) при п стремящемся к бесконечности. При этом поведение функции Шеннона Ь^{п) можно изучать как на уровне асимптотики, так и на уровне асимптотических оценок высокой степени точности (см., например, [11]).

Перейдем к формулировке и характеристике основных результатов диссертации, а также описанию её структуры.

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

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

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

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

В разделе 1.3 на основе некоторых специальных характеристик множеств квазипеременных и обобщенных переменных для произвольного предиката 7г определены его комбинационный ранг к (7г) и информационный ранг 5 (тг). Для предикатного базиса 93 = {7Г1,., 7г^} его расширенным базисом назовем предикатный базис 93, содержащий все предикаты, получающиеся из предикатов базиса 23 при помощи операций снятия и отождествления полюсов (включая все предикаты базиса 93). При этом считается, что "вес" С (тт) предиката 7Г, 7Г 6 93, который получается из базисного предиката щ, 1 ^ ъ ^ Ь, при помощи применения указанных операций, равен С(щ). В разделе 1.3 для предикатного базиса 93 введены его приведенный вес и обобщенный приведенный вес которые задаются равенствами р;в = тт

ТЛЕ 03 к(тг)>1

Ръ = и определены для произвольного полного базиса 23.

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

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

Будем считать, что какое-либо свойство выполнено для почти всех предикатных базисов, если для любых натуральных к и га1, а также любого набора положительных действительных чисел ., С'1П) доля тех наборов (тг^,., 7г'т) из Щ1 (к), задающих базис 93' = {(7ГЬ £[),., (7гт, £'т)}, для которых выполнено указанное свойство, больше, чем 1-е (к), где е (к) стремится к нулю при к стремящемся к бесконечности.

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

Теорема 1.8.Для любых натуральных к и т, а также любого набора положительных действительных чисел (£'1:., £'т) доля тех наборов (тт[, ., 7г^) из П™ (к), для которых р& = 'р^, где 03' — базис вида 03' — {(7Г1, £[),., (тгт, £'т)}, не меньше, чем

Из теоремы 1.8 следует, что для почти всех базисов приведенный и обобщенный приведенный веса совпадают. Отметим, что в работе [19] использовался аналогичный подход при исследовании приведенного веса для функционально полных базисов в Кроме того, в разделе 1.4 доказывается, 1к(к - 1) 1 что для всех базисов , содержащих предикаты от не более чем трех переменных, приведенный вес р© равен обобщенному приведенному весу ■

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

Пусть ||¿¿в (А п) || — число попарно неэквивалентных предикатных схем в классе U<% сложности не превосходящей реализующих предикаты от п переменных. Для получения нижних оценок функции Шеннона Ь^(п) используются обычные "мощностные" соображения, которые основаны на использовании "мощностного" тождества

Отметим, что при получении верхних оценок для |Щв(£,п)|| возникает ряд трудностей, связанных с отмеченным выше эффектом "распадения" предикатов на "блоки".

Для преодоления указанных трудностей в разделе 2.1 доказывается утверждение о возможности "перехода" от базиса 05, содержащего блочные предикаты, к базису 05 без блочных предикатов, для которого L® (n) ^ Lg (п) и ^ р<в- Основным результатом раздела 2.1 является следующая теорема.

Теорема 2.2. Если 05 — произвольный полный предикатный базис, то для функции Шеннона L^{n) справедлива следующая ниэюняя оценка: 2

2Все логарифмы в диссертации берутся по основанию 2, поэтому основание логарифмов будем опускать. n),n)|| = 22".

В разделе 2.2 понятие универсального множества функций (см., например, [11]) обобщается на случай произвольного булевого предиката. Используя это понятие, в данном разделе рассматривается построение разложений предиката по специальным системам обобщенных переменных, а также приводится доказательство некоторых вспомогательных утверждений необходимых для получения верхних оценок функции Шеннона L(п).

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

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

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

Линейным назовем предикат с линейной характеристической ФАЛ, существенно зависящей от трёх и более переменных. Используя специальное представление предикатных схем, в разделе 3.1 уточняется нижняя оценка функции Шеннона Ь^{п) для случаев, когда среди базисных предикатов, на которых достигается приведенный вес базиса найдется неблочный нелинейный предикат 7г, число полюсов которого равно к (7г)+1.

Пусть 1р(х1, ., хп): п ^ 3, — некоторый предикат с двумя выделенными переменными (не ограничивая общности рассуждений, будем считать, что это переменные х\ и жг), и для любого г, г = 3, ., п, существует такой набор аг — (скз, ., «¿+1, ., о;п), что характеристическая функция Хч>(хъ х2, «з, • • ■, оч-1, Жг, «г+ь • • •, «п) равна3

3) х*1 V ха22 V <3 ИЛИ (xi <Г4) V X?,

3Символом а с различными индексами будем обозначать булевы константы. а также существует набор ¡3 = (/?з, ., ¡Зп) такой, что

Х<р{хь х2, /?3, • • ■, /Зп) = V х\

Ре 2 •

Предикат обладающий указанными свойствами, будем называть проводящим. Полный предикатный базис 03 назовём обобщенно-проводящим, если в множестве базисных предикатов, на которых достигается приведенный вес р® базиса 03, найдётся проводящий предикат </?, имеющий максимальное число полюсов среди всех предикатов указанного множества.

В разделе 3.2 для произвольного булевого предиката вводится понятие селекторного разбиения переменных, которое обобщает понятие селекторного разбиения переменных ФАЛ (см., например, [11]), строятся нетривиальные селекторные разбиения для предикатов специального вида и доказываются некоторые вспомогательные утверждения необходимые для уточнения верхних оценок функции Шеннона Ь% (п) для обобщенно-проводящих базисов 03.

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

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

Результаты первой главы опубликованы в работах [28, 29]. Основные результаты второй главы диссертации опубликованы в работах [24, 25, 27, 29], а третьей главы — в работах [14, 26].

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Шуплецов, Михаил Сергеевич, Москва

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

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

3. Васин А. А., Морозов В. В. Теория игр и модели математической экономики. М.: МАКС Пресс, 2005. 272 с.

4. Долгополова А. В. Асимптотическое поведение функции Шеннона для одного класса схем из функциональных элементов // Вестник московского университета. Сер. 15. Вычислительная математика и кибернетика. М., 1997. № 1. С. 37-41.

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

6. Захарова Е.Ю. Яблонский C.B. Некоторые свойства невырожденных суперпозиций в Рк // Математические заметки. Т. 12. К2 1. 1972. С. 312.

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

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

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

10. Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6. М.: Наука. Физматлит. 1996. С. 189-214.

11. Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Диссертация на соискание ученой степени доктора физико-математических наук, Москва, 1997.

12. Ложкин С. А. Лекции по основам кибернетики: учебное пособие. М.: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова. 2004. 256 с.

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

14. Лупанов О. Б. О сложности реализации функции алгебры логики релейно-контактными схемами // Проблемы кибернетики. Вып. 11. М.: Наука, 1964. С. 25-48.

15. Марковский A.B., Редькин H.H. О реализации булевых функций схемами из блоков // Сб. "Проблемы кибернетики". Вып. 28. М.: Физматгиз, 1974. С. 81-100.

16. Марченков С. С. Предполнота замкнутых классов в Р^: предикатный подход // Математические вопросы кибернетики. Вып. 6. М.: Наука. Физматлит, 1996. С. 117-132.

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

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

19. Сэвидж Дж. Э. Сложность вычислений. М.: Факториал, 1998. 368 с.

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

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

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

23. Шуплецов М. С. Оценки высокой степени точности для сложности предикатных схем в некоторых базисах // Учен. зап. Казан, ун-та. Сер. Физ.-матем. науки. 2009. Т. 151, кн. 2, С. 173-184.

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

25. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.

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

27. Burks A. W., Wright J. В. Theory of logical nets // Proc. IRE. 1953. V. 41, № 10. P. 1357-1365. Рус. пер.: Беркс А., Райт Дж. Теория логических сетей // Кибернетич. сб. Вып. 4. М.: ИЛ, 1962. С. 33-57.

28. Cook M., Bruck J. Implementability Among Predicates // California Institute of Technology. Parallel and Distributed Computing Laboratory. Pasadena, California, 2005.

29. Cook M. Networks of relations // Ph.D. Thesis. California Institute of Technology. Pasadena, California, 2005.

30. Dechter R. Constraint Processing. Morgan Kaufmann, 2003. 450 p.

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

32. Shannon C. E. A symbolic analysis of relay and switching circuits // Trans. AIEE 57. 1938. P. 713-723.

33. Shannon C. E. The synthethis of two-terminal switching circuits // Bell Syst. Techn. J. 1949. V. 28. N 1. P. 59-98.