Функциональные системы с операциями замыкания програмного типа

Оцной из основных задач математической кибернетики является изучение управляющих систем. Формализация1 понятия управляющей системы приводит к понятию функциональной системы (ф.с.). Ф.с. представляет собой пару (7YI, 2), где — множество функций, а С — множество операций, которые применяются к элементам множества If^TL, причём, в результате применения этих операций получаются элементы множества ТТЬ. Примерами ф.с. могут служить (Рк, С) — множество функций кзначной логики с операцией суперпозиции, множество о.-д. функций с операциями суперпозиции и обратной связи и др.

Изучению ф.с. уделялось и уделяется большое внимание. Проблематика исследований очень обширна. В число наиболее важных вопросов входят проблема полноты и вопросы, связанные с описанием структуры замкнутых классов и изучением базисов замкнутых классов. Особенно подробно исследована ф.с. (Pz, С), Э. Постом ([l, 2], а ташсе [з]) была полностью описана структура замкнутых классов функций алгебры логики. Оказалось, что существует лишь счётное число попарно различных замкнутых классов, причём, в каждом замкнутом классе существует конечный базис. Проведение аналогичного исследования других ф.с. наталкивается на значительные трудности. Если проблема полноты для ф.с. (РК, С) при к усилиями многих авторов (см. [4−14]) была полностью решена, то структура замкнутых классов функций из Р* является труднообозримой. В работе [lb] было показано, что существуют замкнутые классы без базиса, замкнутые классы со счётным базисом, а мощность множества замкнутых классов равна мощности континуума.

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

В данной диссертации определяется и исследуется семейство ф.с. кзначной логики с операциями программного типа (ф.с. (к) п.). Каждая из ф.с. (к) п. однозначно определяется базисным множеством предикатов. Заметим, что ф.с. (Рг, С) является частным случаем ф. с, (к) п., т. е. для некоторых множеств предикатов ф.с. (к) п., поролщаемая ими, совпадает с (PZ, C) .

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

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

Большое внимание в диссертации уделено и изучению ф.с. Р2П, С), h. z 2, которые являются декартовыми степенями ф.с. (P2t С). Это объясняется в первую очередь тем, что результаты, связанные с ф.с. (Р*, С), используются при доказательстве ряда теорем о ф.с. (к) п. Кроме того, ф.с. (Pz. 0) представляет и самостоятельный интерес (например, с точки зрения ф.с. с несколькими выходами).

Из сказанного выше вытекает актуальность вопросов, рассмотренных в диссертации.

Результаты диссертации докладывались на семинарах по математической кибернетике в МГУ и в институте математики СО АН СССР.

Основные результаты диссертации опубликованы в работах [31−33] .

Автор выражает глубокую благодарность доктору физико-математических наук Ю. И. Янову, под руководством которого была выполнена эта работа.

1. Post E. 1. troduction to q yenerat theory of elementary propositions. — Amer. J. Math., 4−3,1924, f).163-iS5.

2. Post E. Tke twovatued iterative, systems of mathematical loyic. Princeton.: Princeton Univ. Press, № 1, p. 122.

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

4. Яблонский С. В. О функциональной полноте в трёхзначном исчислении. ДАН СССР, 1954, т. 95, J66, C. II53-II56.

5. Яблонский С. В. функциональные построения в кзначной логике. Труды МИАН, 1958, т.51, с.5−142.

6. Кузнецов А. В. О проблемах тождества функциональной полноты алгебраических систем. Труды Третьего Всесоюзного математического съезда. II. — М.: АН СССР, 1956, с.145−146.

7. Мартынюк В. В. Исследования некоторых классов функций в многозначных логиках. В сб. Проблемы кибернетики, вып. З, М.: Наука, I960, с.49−60.

8. Пан Юн-цзе. Один разрешающий метод для отыскания всех предполных классов в многозначной логике. Acta Sci. hlatur. Univ. JilLnensis, 1962, v. 2.

9. Ло Чжу-кай. Предполные классы определяемые нормальнымикарными отношениями в кзначной логике. Acta Sci. Natur. Univ. Jitinensis, 19G4-, v.3.

10. Ло Чжу-кай. Предполнота множества и кольца линейных функций. -Acta Sci. Natur. Univ. Jiiinensis, 196b, v. 2.

11. Ло Чжу-кай, Лю Сюй-хуа. Предполные классы, определяемые бинарными отношениями в многозначной логике. Acta Sci.Alatur. Univ. Jitinensis, 1963, V. 4.

12. Rosent>ercj J. jLq. structure des fonctions de ptusieurs variaides sur an ensemi^efine. — Comtes Rendus Acad, Set. Parts, 1965, v. 260, р. Ш7-$Ш.

13. Захарова Е. Ю. Критерий полноты системы функций из Рк .- В сб. Проблемы кибернетики, вып.18, М.: Наука, 1967, с.5−10.

14. Roseh&erg J. Шег die functionate Voit -$tandiqkeit иг der mehrwertlqen jLogiken. —Rozpravy CSAV, Rada mat. prit., 1970, v. 80, л/4.

15. Янов Ю. И., Мучник А. А. О существовании кзначных замкнутых классов, не имеющих конечного базиса. ДАН СССР, 1959, т.127, Ж, с.144−146.

16. Яновская С. А. Математическая логика и основания математики.- В сб. Математика в СССР за 40 лет, т.1, М.: Физматгиз, 1959, с.13−120.

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

18. Данильченко А. Ф. О параметрической выразимости функций трёхзначной логики. Алгебра и логика, 1977, т.16, № 4, с.397−416.

19. Satomaa A. On the heights of dosed sets of operations in finite aigeSras. ~ Ann. Acad. $. Fennccae S. A, 1965, v. 363.

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

21. Голунков Ю. В. Критерий полноты систем операций в операторных алгоритмах, реализующих функции к значной логики.- Вероятностные методы и кибернетика, 1980, вып.17, с.23−34.

22. Андреева О. В., Голунков Ю. В. Программно-замкнутые классы функций алгебры логики и предикатов. Кибернетика, 1981, Я5, с. 133.

23. Kuclrjawcew W. В., Burosch 6r., block in a & А/VoltstandLykeLts&-edlLixyunyeh fur zwei Atyekrenvom Postschen Тур. Math. Baicahica, i9?3, t.3, s. m-296.

24. Кудрявцев В. Б. Относительно функциональной системы .- ЖВМ, 1974, т.14, М, с.198−208.

25. Непомнящий В. А. Критерий алгоритмической полноты систем операций. В кн. Теоретическое программирование, ч.1, Новосибирск: 1972, с.267−279.

26. Голунков Ю. В. Алгоритмическая полнота и сложность микропрограмм. Кибернетика, 1977, Ш, с.1−15.

27. Курдюмов Г. Л. О предикатах подобных предикату «равенство» в смысле алгоритмической полноты операций. В кн. Системное и теоретическое программирование, Новосибирск: ВЦ СО АН СССР, 1974, с.274−284.

28. Голунков Ю. В. О предполных классах алгоритмов, сохраняющих принадлежность множеству. II. В сб. Вероятностные методы и кибернетика. 1980, вып.17, с.35−51.

29. Янов Ю. И. О вычислениях в одном классе программ. В сб. Проблемы кибернетики, вып.32, М.: Наука, 1977, с.237−245.

30. Харари Ф. Теория графов. М.: Мир, 1973, с. 300.

31. Тайманов В. А. О функциональных системах кзначной логики с операциями замыкания программного типа. Тезисы докладов VI Всесоюзной конференции по математической логике, Тбилиси: 1982, с. 180.

32. Тайманов Б. А. О функциональных системах кзначной логики с операциями замыкания программного типа. ДАН СССР, 1983, т.268, 1Ю, с.1307−1310.

33. Тайманов В. А. О декартовых степенях Р2. ДАН СССР, 1983, т.270, №, с.1327−1330.