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

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

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

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

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

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

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

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

Т7/ — функциональная система полиномов с целыми коэффициентамифункциональная система полиномов с рациональными коэффициентами, где в качестве операций над полиномиальными функциями выступают операции суперпозиции. Для этих функциональных систем исследуется проблема полноты, а также порожденные ее решением задачи «функционального» характера, а именно, изучение замкнутых и предполных классов, исследование базисов.

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

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

Диссертация состоит из.

• 5 глав, которые содержат, соответственно, по 5, 5, 6, 5 и 3 параграфа;

• списка литературы.

Общий объем диссертации 116 страниц.

При изложении материала в основном используется терминология книг [17] и [22].

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

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

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

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

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

В заключении дается некоторая сравнительная оценка ф.с. Р7 и .Рд (их особенности — отличие и сходство).

В конце диссертации приведен список используемой литературы.

Нумерация для каждой главы своя.

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

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

1. Ван дер Варден Б. Л. Алгебра-М.: «Наука», 1976.

2. Гаврилов Г. П. О функциональной полноте в счетнозначной логике — В кн.: Проблемы кибернетики, вып. 15, М.: «Наука», 1965, с.5−64.

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

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

5. Дарсалия В. Ш. О связи функциональных систем полиномов! I Интеллектуальные системы (в печати).

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

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

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

9. Дэвенпорт Г. Высшая арифметика.

Введение

в теорию чисел М.: «Наука», 1965.

10. Клини С. К.

Введение

в метаматематику. -М.: «ИЛ», 1957.

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

12. Кудрявцев В. Б. Вопросы полноты для автоматов! I ДАН СССР. 1960. — Т. 130, N 6. -С.1189−1192.

13. Кудрявцев В. Б. О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами! ДАН СССР. 1963. -T.151,N3.-С.493−496.

14. Кудрявцев В. Б. О мощностях множеств предполных множеств некоторых функциональных систем, связанных с автоматами В кн.: Проблемы кибернетики, вып. 13. -М.: «Наука», 1965. — с.45−74.

15. Кудрявцев В. Б. Теорема полноты для одного класса автоматов без обратных связей // ДАН СССР. 1960. — Т. 132, N 2. — С.272−274.

16. Кудрявцев В. Б. Теорема полноты для одного класса автоматов без обратных связей В кн.: Проблемы кибернетики, вып.8. — М.: «Наука», 1962. — с.91−115.

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

18. Кудрявцев В. Б., Алешин C.B., Подколзин A.C.

Введение

в теорию автоматов. М.: «Наука», 1986.

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

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

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

22. Яблонский C.B.

Введение

в дискретную математикуМ.: «Наука», 1986.

23. Яблонский C.B. О функциональной полноте в трехзначном исчисленииII ДАН СССР. 1954. — Т.95, N 6. — С.1153−1156.

24. Яблонский C.B. Функциональные построения в k-значнойлогике. В кн.: Труды Математического института им. В. А. Стеклова. -1958.-Т.51.-С.5−142.

25. GOdel К. Uber formal unentscheidbare Satze der Principia Mathematica und Verwandter Systeme// Monatsh. Math, und Phys., 1931. — V.38 — P.173−198.

26. Hilbert D., Bernays P. Grundlagen der Mathematik. Springer-Verlag OHG, Berlin, 1939.

27. Post E. Two-valued iterativem systems of mathematical logik Prinston, 1941.

28. Rosenberg J. Uber die functionale Vollstandigkeit in der mehrwertigen logiken// Rozpravy CSAV, Rada mat. print., 1970. — V.80, N 4.

29. Slupecki J. Kriterium pelnosci wielowar tosciowych systemow logiki zdan// Comptes Rendus des Seances de la Societe des Sciences et des Lettres de Varsovie. — 1939. — Cl. III, 32. — P. 102−128.

30. Turing A. On computable numbers, with an application to the Entscheidungsproblem// Proc. London Math. Soc., ser. 1936. — V.42, — P.230−265.

31. Turing A. On computable numbers, with an application to the Entscheidungsproblem// Proc. London Math. Soc., ser. 1936. — V.43, — P.544−546.

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