Проблема полноты для функциональных систем полиномов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

рг 5 Ой

I V

Саратовский государственный университет им. Н.Г. Чернышевского

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

Дарсалия Валерий Шотаевич

ПРОБЛЕМА ПОЛНОТЫ ДЛЯ ФУНКЦИОНАЛЬНЫХ СИСТЕМ ПОЛИНОМОВ

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

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

' Саратов

1998

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

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

доктор физико-математических наук, академик АТН РФ, профессор В.Б. Кудрявцев

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

доктор технических наук, чл.-кор. АТН Украины, профессор Д.В. Сперанский;

кандидат физико-математических наук, доцент Л.В. Кальянов

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

- Московский энергетический инсти тут (технический университет).

■ Защита диссертации состоится " З.С " ¿и,сх±»/^д 1998 г. в час 30 мин. на заседании Специализированного Совета К 063.74.04 Саратов ского государственного университета им. Н.Г. Чернышевского по адресу 410071, г. Саратов, ул. Астраханская, 83, Саратовский государственный уни верситет.

С диссертацией можно ознакомиться в библиотеке Саратовского государст венного университета им. Н.Г. Чернышевского.

Автореферат разослан "30" .до/^о ^_1998 г.

Ученый секретарь Диссертационного совета К 063.74.04, кандидат физико-математических наук, доцент

П.Ф. Недорезо

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

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

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

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

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

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

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

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

Post Е. Two-valued iterativem systems of mathematical logik - Prinston. 1941.

тура замкнутых классов двузначной логики. Это описание по существу эквивалентно решению задачи о полноте. Им же были сделаны шаги по изучению к-значных логик (к>3). В 1954 году C.B. Яблонским2 была решена задача о полноте в 3-значной логике. Решение было сведено к описанию всех прсдполны> классов в ней. Сами предлолные классы были описаны явно. Из этого описа ния вытекал алгоритм распознавания полноты для конечных систем функций Метод решения проблемы полноты в терминах предполных классов стал пос.к этого одним из основных для функциональных систем. Особые усилия различ пых авторов были сосредоточены на решении проблемы полноты для ключе вой функциональной системы, которой является ¿-значная логика. На это."* пути окончательный результат был получен И. Розенбергом3 в 1970 году.

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

Большой интерес представляет функциональная система вычислимы; функций, о чем свидетельствуют многочисленные работы таких математиков < мировым именем, как Д. Гильберт5, К. Гедель6 , К. Клини7 , А. Марков8 , А Тьюринг9 и т.д.

Наряд\- с этими функциональными системами начали интенсивно изучаться и другие важные функциональные системы и, прежде всего, функциональны!

системы недетерминированных функций, неоднородных функций и т.д.

: Яблонский С.В. О функциональной полноте в трехзначном исчислении! ДАН СССР. - 1954. -Т.95, N6. - С. 1153-1156.

3 Rosenberg J. Uber die functionale Vollständigkeit in der mehrwertige

logiken Rozpra\y CSAV, Rada mat. print., - 1970. - V.80, N 4. A Кудрявцев В.Б., Алешин С.В., Подколзин A.C. Введение в теории автоматов. -М.: "Наука", 1986.

5 Hilbert D., Bernays Р. Grundlagen der Mathematik. - Springer-Verlag OHG. Berlin, 1939.

6 GÖdel K. Über formal unentscheidbare Sätze der Principia Mathematica im Verwandter Systeme '-' Monatsh. Math, und Phys., - 1931. - V.38 - P.173-198.

' Клини C.K. Введение в метаматематику. - M.: "ИЛ", 1957.

8 Марков A.A. Теория алгоритмов. - В сб.: Труды математического инстг тута АН СССР, - 1954. -Т.42.

9 Turing A. On computable numbers, with an application to the Entscheidungi problem - Proc. London Math. Soc., ser. - 1936. - V.42, -P.230-265.

В настоящей работе рассматриваются следующие функциональные системы:

/'м - функцштспьная система полиномов с натуральными коэффициентами:

¡7г - функционачъная система полиномов с целыми коэффициентами', /^0 - функциональная система полиномов с рационачъными коэффициентами.

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

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

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

Цель работы. Целью настоящей работы является исследование проблемы полноты для функциональных систем полиномов с натуральными, целыми и рациональными коэффициентами; более подробно, решение следующего круга вопросов:

1. Алгебраический вариант проблемы полноты для ф.с. :

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

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

2. Алгоритмический вариант проблемы полноты для ф.с. : алгоритмически разрешима или нет проблема полноты ?

3. Задача о базисах для ф.с. :

имеет ли базис каждая полная система ?

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

10 Мальцев А. И. Итеративные ачгебры и многообразия Поста?/ Алгебра и логика. - 1966. - Т.5. N 2. - С.5-24.

11 Whitlock H.J. A composition algebra for multiplace function'/ Math. Ann., - 1964. - V. 157. N 2. - P.167-178.

системы базис ?

4. Задача об универсальных функциях для ф.с. : су ществует ли универсальная функция ? найти число универсальных функций.

5. Задача об относительной полноте для ф.с. Г\:

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

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

6. О связи ф.с. ^н, Р~г и FQ:

найти глубину класса Рц в классе класса Р?. в классе Л,> и класса Рц в классе Л?;

задача об относительной полноте множеств в Рц относительно Ру для пар (имыш&м.^г)» (£?,Л0. (здесь Хе {N,2^}, а Рц, Р/. и Рц - множества всех полиномиальных функций соответственно с натуральными, целыми и рациональными коэффициентами).

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

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

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

В функциональной системе полиномов с натуральными коэффициентами:

1. Множество всех предполных классов является (приведенной) критери-

альной системой [следствие 1 теоремы 2.3.1];

2. Мощность множества всех предполных классов равна 4 [следствие 2 теоремы 2.3.1];

3. Проблема полноты алгоритмически разрешима [теорема 2.3.2];

4. Каждая полная система имеет бате, состоящий либо из трех, либо

из четырех функции [теорема 2.4.11:

5. Существует алгоритм, который /и любой конечной полной системы

выделит Оазис (теорема 2.4.2];

6. Проблема выразимости алгоритмически разрешима (теорема 5.3.11.

В функциональной системе полиномов с целыми коэффициентами;

1. Множество всех предполных классов является (приведенной) критериальной системой [теорема 3.3.11;

2. Мощность множества всех предполных классов равна с [теорема 3.3.2|:

3. Проблема полноты алгоритмически неразрешима |теорема 3.3.3);

4. Каждая полная система имеет базис; более того, для любого положительного целого числа п существует базис мощности п [теорема 3.4.1|;

5. Не существует алгоритм, который из любой конечной полной системы выделит базис [теорема 3.4.2];

6. Существует счетное число универсачьиых функций [теорема 3.5.2];

7. Проблема выразимости алгоритмически неразрешима |теорема 5.3.2]:

В функциональной системе полиномов с рациональными коэффициентами:

1. Множество всех предполных классов является (приведенной) критериальной системой [теорема 4.3.1];

2. Мощность множества всех предполных классоа равна с [теорема 4.3.2]:

3. Существует полная система, не имеющая базиса [теорема 4.4.1]:

4. Проблема выразимости алгоритмически неразрешима [теорема 5.3.3].

Теоретическая и практическая ценность.

Рассмотренные функциональные системы полиномов Ь\ и играют ключевую роль в теории чисел, теории алгоритмов и теории функций. К изучению их свойств сводятся многие проблемы указанных разделов математи-

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

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

Практическая направленность работы обусловлена возможными приложениями в синтезе нейронных сетей и вычислительных чипов.

Полученные результаты могут быть использованы как в научной работе, так и в разработке учебных курсов.

Апробация. Результаты диссертации докладывались и обсуждались на семинарах по теории автоматов механико-математического факультета Московского государственного университета им. М.В. Ломоносова (руководитель семинара академик В.Б. Кудрявцев).

Публикации. Основные результаты диссертации опубликованы в работах автора, список которых приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из предисловия, 5 глав и списка литературы. Текст диссертации изложен на 116 страницах. Список литературы содержит 32 наименование.

Содержание работы

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

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

Введем некоторые "стандартные" обозначения: N - множество всех натуральных чисел (включая число 0); Z -- множество всех целых чисел: Q - множество всех ршшональных чисел: 111 - мощность множества .1 : Со- мощность счетного множества; с - мощность континулма.

Для удобства полагаем, чю по определению 0=1.

Пусть L'={ut,...//„....} - исходный алфавит переменных (аргументов).

Пусть Л' - некоторое (конечное или бесконечное) множество, содержащее не менее двух элементов.

Обозначим через 1\ множество всех функций Ди,.....и,п) (и( *иг при

переменные которых определены на множестве X и сами функции принимают значения из этого же множества Л". Предполагается, что множество Рх содержит и все функции от нулевого числа переменных, т.е. функции, являющиеся просто элементами (константами) множества Л'.

Чтобы избежать сложных обозначений ял я индексов переменных, мы будем употреблять в качестве мстаобозначений (обозначений для произвольных символов алфавита t ) символы x.y.z.....а также эти символы с индексами. Таким образом, запись .....дг„) понимается как запись функции из

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

и,(*и,г при

Следуя А.И. Мальцеву, введем четыре унарных операции г|, т, Д, V и одну бинарную операцию * н;и функциями из Рх так:

(T|/)(.V|,.Y;......v„)=/lv;..v,......v„.v,) при ;i>2 и (г|/)=/при /1=1;

......г,,)=Ax:..y,..v,......г,,) при п>2 и (zj)=f при п= 1;

(Д/)(х,,дг2.....хп 1)=Ддг,..г,.д-:.....хп |) при п>2 и (ДУ)=/ при п=1;

(V/)(x,,x2.....хп.хп1,)=/(х:.х,.....Arn,xn+i).

Далее, если имеютсяДг|..г:.....дгп) и g(xnt,,...,xn+m) из Рх, то полагаем

Эти операции называются операциями суперпозиции.

Легко заметить, что операции суперпозиции включают в себя: перестановку переменных; отождествление переменных; переименование переменных (без отождествления);

введение фиктивной переменной; удаление фиктивной переменной; подстановку одной функции в другую.

Алгебру где />={г|д.Д.У,*}, а Р[ произвольное непустое

подмножество множества Рх. при этом Рх замкнуто относительно операций из О. назовем функциональной системой (ф.с.).

Для произвольного подмножества Л/ множества Рх обозначим через /п(А/) множество всех функций из Р'х , которые получаются из функций Л/ с помощью конечного числа применения операций из О.

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

Рх в себя.

Оператор, переводящий произвольное подмножество А/ множества Рх на множество /а(А/), называется оператором замыкания (относительно операций из О) и обозначается через /п.

Фу нкции из /п(Л/) называются суперпозициями функций множества М. Само множество /ц(Л/) называется замыканием множества А/.

Множество А/ (Л/с; Рх ) называется (функционально) замкнутым, если /и(Л/)=А/. Замкнутое множество принято называть замкнутым кчассом.

Множество Л/ (А/с Рх) называется {функционально) полным, если 1ц{\1)= Р*.. Полное множество принято называть полной системой.

Функция f из Рх называется универсачьной функцией, если {/}является полной системой.

Назовем систему А/ базисом полной системы 7(А/.7'с Р V ). если А/сТ и А/ полна в Р'х, но всякая ее собственная подсистема не является полной в В частности, система А/ является базисом ф.с. , если А/ полна в Рх, но всякая ее собственная подсистема не является полной в Рх.

Множество А/ (Л/с Рх ) называется предполным (максимачьньш) кчассом. если /п(А/) * Рх , но для любой функции / из Рх \ А/ выполнено /п(А/и(/})= р;.

Система А замкнутых подмножеств множества Рх называется критериальной системой, если любое подмножество Л/ (Л/с: Рх ) является полным в /<х тогда и только тогда, когда оно целиком не содержится ни в одном множестве системы К.

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

Известно, что в ф.с. приведенная критериальная система, если она существует, определяется однозначно и состоит из всех предполных классов в Рх .'"

В ф.с. /ч множество (Л/с Рх ) называется полной системой относительно множества О (Ос Рх). если Ос А/ и Л/ полная система в ф.с. ■

Ф.с. Гх называется конечно-порожденной, если в /%; существует конечный базис и называется счетно-порожденной, если в /*х существует счетный базис и нет конечного базиса.

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

Функциональные системы =(РМ ,/Т). Рг =(Рг и Гд ,17), где Ры -множество всех н.п. функций, Рг - множество всех ц.п. функций и Л} -множество всех р.п. функций, а /2={г),т,Д,У,*}. назовем соответственно функциональной системой полиномов с натуральными, целыми и рациональными коэффициентами.

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

А именно, доказано, что конечная система функций {0,1,^+у, ху} явля-

Кудрявцев В. Б. Функциональные системы - М.: Изд-во МГУ, 1982.

ется базисом ф.с. , и что каждый базис состоит либо из 3, либо из 4 функций; следовательно, ф.с. является конечно-порожденной; поэтому множество всех предполных классов является (приведенной) критериальной системой. Далее доказано, что в ф.с. существуют всего 4 предполных класса и эти классы описаны явно:

I о - предполный класс, состоящий из всех н.п. функций., кроме 0;

1\ - предполный класс, состоящий из всех н.п. функций., свободный член которых не единица;

К - предполный класс, состоящий из всех не аддитивных функций (н.п. функция Лх],...,хп) называется аддитивной, если для некоторых / и ] (1 </</'¿0) найдутся числа а^ из £2={0Л} 1,2,...,/-1,/+1,...1/'-11/'+1,...,/7) такие, что /{аи...,аы,хх,а1Н.....

I* - предполный класс, состоящий из всех не мультипликативных функций

(н.п. функцияДх|,...х„) называется мультипликативной, если для некоторых ; иу (1</</<п) найдутся числа ак из /?:={0,1}(А'=1,..../-1,;+1,...^-11/'+1,...,л), такие, что

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

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

А именно, доказано, что конечная система функций {1.г-у. ху} является базисом ф.с. , и что для любого положительного целого числа п существует базис, состоящий из п функций; следовательно, ф.с. Рг является конечно-порожденной; поэтому множество всех предполных классов является (приведенной) критериальной системой. Далее доказано, что мощность множества всех предполных классов равна с; с этой целью построены конкретные предполные классы. В ф.с. ^ существует универсальная функция, и число таких функций равно с0; в частности, ц.п. функция Лх,у,г)=х2-у2+г+1 является универсальной.

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

функций A'/f={0,2z.2z+l,-2z-l, (Л*ь...Л)+1)(*+>0, </2(^....л)+1)(ху)}, где ^ь - Л) - произвольная функция из Pz ; A-/f является полной в ф.с. Fz тогда и только тогда, когда f(x\,...,x„) имеет корень в Z; следовательно, алгоритмическая разрешимость проблемы полноты сводится к алгориппгческой разрешимости 10-й проблемы Гильберта (задаче о разрешимости диофантова уравнения), которая имеет "отрицательный" ответ.13

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

f "lili А именно, доказано, что система — у,ху,~—где р -

любое простое число, является базисом Fq, следовательно, Fq является счетно-порожденной . Далее установлено, что в ф.с. Fq не всякая полная система имеет базис, и приведен пример такой системы. А множество всех предполных классов является (приведенной) критериальной системой. Найдено число предполных классов; оно равно с; с этой целью построены конкретные предполные классы.

В конце этой главы рассматривается задача об относительной полноте. Глава 5. В этой главе рассматриваются некоторые вопросы, связанные с проблемой полноты, а именно: аналог теоремы Колмогорова о суперпозициях непрерывных функций; взаимосвязь ф.с. FN> Fz, Fq и алгоритмический вариант проблемы выразимости для этих функциональных систем.

К проблеме полноты примыкает известная теорема Колмогорова о суперпозициях непрерывных функций действительного переменного14:

При любом целом л>2 существуют такие определенные на единичном

pq

отрезке /=[0,1] непрерывные действительные функции ¥ (х), что каждая определенная на n-мерном единичном кубе I непрерывная действительная функция/[хи...,хп) может быть представлено в виде

13 Матиясевич Ю .В. Десятая проблема Гильберта - М.: Физматлит, 1993.

14 Колмогоров А.Н. О представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций одного переменного и сложения-'/ Доклады АН СССР. - 1957. - Т. 114, N 5. - С.953-956.

2п+\

9=1

Л'ч(у) действительны и непрерывны.

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

Представляет интерес следующий вопрос: имеет ли место аналог теоремы Колмогорова для ф.с. /ч, (Л'е{Л'Д(9}), т.е. образуют ли множество всех функций одной переменной из Ру^ и функция х+у полную систему в Fx г>

В ф.с. /"м и /"г аналог теоремы Колмогорова не имеет места, а в ф.с. Рд аналог теоремы Колмогорова имеет место.

Далее, доказано, что Ры является предполным юассо.м в ф.с.

. а Рц и Рг

не являются предполными классами в ф.с. Р^, более того, глубины замкнутых кчассов и Рг в ф.с. Р^равны с0.

В конце этой главы рассматривается алгоритмический вариант проблемы выразимости. Установлено, что в ф.с. Ры проблема выразимости алгоритмически разрешима, а в ф.с. Рг и Р^ - нет.

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

Основные результаты диссертации опубликованы в следующих работах автора:

1. Дарсалия В.Ш. Условия полноты для полиномов с натуральными, целыми и рациональными коэффициентами!/ Фундаментальная и прикладная математика. - 1996. - Т. 2, вып.2. - С.365-374.

2. Дарсалия В.Ш. О мощностях множеств всех предполных классов в функциональных системах полиномов// Теоретические проблемы информатики и ее приложения. - 1997. -Вып. 1. -С.35-44.

Кроме того, по результатам диссертации подготовлены и сданы в редакции: следующие работы автора:

1. Дарсалия В.Ш. О связи функциональных систем полиномов// \\тъл-лсктуальные системы (в печати).

2. Дарсалия В.Ш. Об алгоритмической разрешимости свойства выразимости для полиномов/1 Фундаментальная и прикладная математика (е печати).

3. Дарсалня В.Ш. О базисах функциональных систем полиномов// Фундаментальная и прикладная математика (в печати).

4. Дарсалия В.Ш. Относительная полнота для функциональных систем полиномов// Фундаментальная и прикладная математика (в печати).

Перечисленные работы приняты к печати.

Автор выражает глубокую благодарность своему научному руководителю академику Российской академии технологических паук, профессору Московского государственного университета им. М.В.Ломоносова, доктору физико-математических наук В.Б. Кудрявцеву за постановку задачи и постоянную поддержку при выполнении данной работы.