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

• Автор: Тайманов, Владимир Асанович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 142 c. : ил

Введение

§ 0.1. Общая характеристика диссертации

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

Глава I. О декартовых степенях Яг

§ 1.1. Основные понятия и определения. Некоторые

вспомогательные факты

§ 1.2. Теоремы о базисах замкнутых классов

Глава 2. функциональные системы к -значной логики с

операциями замыкания программного типа

§ 2.1. Основные понятия и определения. Некоторые

вспомогательные результаты

§ 2.2. Критерии сравнимости и совпадения двух
операций
§ 2.3. О некоторых свойствах операций
§ 2.4. О некоторых мощностных и структурных
свойствах множеств операций
Литература

ВВЕДЕНИЕ § 0.1. Общая характеристика диссертации.
СДной из основных задач математической кибернетики является изучение управляющих систем. Формализация1 понятия управляющей системы приводит к понятию функциональной системы (ф.с.). Ф.с. представляет собой пару (7Т1 , 5? ) , где 77Ъ - множество функций, а 5Р множество операций, которые применяются к элементам множества , причём, в результате применения
этих операций получаются элементы множества 'УО'Ъ . Примерами ф.с. могут служить (РК/ С)- множество функций к -значной логики с операцией суперпозиции, множество о.-д. функций с операциями суперпозиции и обратной связи и др.
Изучению ф.с. уделялось и уделяется большое внимание. Проблематика исследований очень обширна. В число наиболее важных вопросов входят проблема полноты и вопросы, связанные с описанием структуры замкнутых классов и изучением базисов замкнутых классов. Особенно подробно исследована ф.с. ( Р2, С). Э. Постом а также [3]) была полностью описана структура замкнутых классов функций алгебры логики. Оказалось, что существует лишь счётное число попарно различных замкнутых классов, причём, в каждом замкнутом классе существует конечный базис. Проведение аналогичного исследования других ф.с. наталкивается на значительные трудности. Если проблема полноты для ф.с. ( РК, С) при к *3 усилиями многих авторов ( см. [4-14]) была полностью решена, то структура замкнутых классов функций из Р* является труднообозримой. В работе [*15] было показано, что существуют замкнутые классы без базиса, замкнутые классы со счётным базисом, а мощность множества замкнутых классов равна мощности кон-

тинуума.
В связи с этим представляет интерес изучение ф.с. к -значной логики с естественными, имеющими^ держательный смысл, операциями, более сильными, чем операция суперпозиции. Заметим, что некоторые варианты таких ф.с., а также различные обобщения ф.с. рассматривались ранее рядом авторов (см., например, [і6-2о])
В данной диссертации определяется и исследуется семейство ф.с. к -значной логики с операциями программного типа (ф.с. (к) п.). Каждая из ф.с. (к) и. однозначно определяется базисным множеством предикатов. Заметим, что ф.с. (Я, С) является частным случаем ф.с. (к) п., т.е. для некоторых множеств предикатов ф.с. (к) п., порождаемая ими, совпадает с (Рг,С)
Изучение ф.с. (к) п. представляет интерес не только с точки зрения, указанной выше, но и по другим причинам. В числе последних, помимо вопросов теоретического программирования, следует упомянуть и возможность практического применения исследований ф.с. (к) п.
Для некоторых реальных процессов, например, технологических, математической моделью может служить программа. Если функциональные операторы трактовать как элементарные технологические операции, а операторы условного перехода - как проверку качества сырья, промежуточных изделий и т.д., то задача организации технологического процесса изготовления определённой продукции, исходя из данного набора элементарных операций и проверок, сводится к задаче написания программы, вычисляющей определённую функцию, с использованием данного набора функциональных операторов и операторов условного перехода. Последняя задача, как легко видеть, приводит к изучению ф.с. (к) п.
Большое внимание в диссертации уделено и изучению ф.с.

Осталось заметить, что:
1) ■(%*£) =гл-2* ‘2я-Лс-1гл(Ъ.
2) ^ = Ху Х* • Х$ ■ Х5 • Хб (Хз) у %х ■ Хг • 2”,$,
3) Ху • х, • х3 = Ху • Ху • 23 ■ К (**. хЛ ъ) V* Ху -х3.
Следовательно, ^(г) можно представить в виде
<*л’^-ъв-гс-К(**,Ъ)А> %-2г’*4-%-2с-к.(ъ) *},
$ -г4-г3 • ^ ($, агЛ гс) ^ . Тем самым для частного случая всё доказано.
Доказательство для общего случая проводится точно так же. Лемма доказана.
Лемма 1.2.19. В любом з.к.с.ф. (и.) Р вида <( 011} 01г, . . . , $*), где 01„. . . , ОЬн. - любые из классов: Р1 ,
/7" , г*, м,, с. , существует конечный базис.
Доказательство. В силу лемм 1.1.8. и 1.1.1.
можно считать, что для любого се Г/, 2, ., и.}
Из этого и из леммы 1.1.9. вытекает, что если =
£(*)>• • .,&(£)>€ к , то ~<М£(х),
М£(*), ...,М^(*))€И и Кь (у, у(х)) ей.
Из леммы 1.2.17. следует, что в Я существует конечная система с.ф.(н) (обозначим её через V/ ) , порождающая все с.ф.(а) из Р , которые удовлетворяют условию
Следовательно, для доказательства леммы достаточно показать, что существует конечная система с.ф.(а) из Р (обозначим её через V ) , порождающая те с.ф.(а) из Р , у которых все ярусы
являются монотонными функциями.
Действительно, так как (х) £ [У], Р-ь.(у> ^ (*■)) € ],
то у(Л) - /С ( <£, Ш, 4>(х)) Ы,у), V, V/].
В силу сказанного, достаточно доказать лемму, предполагая,