Введение к работе
Актуальность темы, функциональные системы (ф.с.) являются одним из главных объектов математичеокой кибернетики,- Под ф.о. понимается пара< J^j ,_0.> ГД8 М - некоторое множество функций, ЛІ. - некоторое множество операций над ними со значениями из М .
Простейшим примером такой системы является класс Рд функций алгебры логики, т.е. функций вида : -[0,4] —»- ^0,-А с операциями суперпозиции.
В 1921 г. Э.Постом [і] была решена задача описания всех замкнутых классов в РА . Таких классов оказалось счетное множество и все они явно указаны им.
При переходе к Р^ , при к.>3 » т.е. к рассмотрению классов функций вида j: {о,4,...,К-1}""—- {о,4,...,«Н] » Ю.И.Яновым и А.А.Мучником[2J было установлено, что решетка замкнутых классов в этом случае континуальна. Тем самым было установлено принципиальное отличие [\ от Ргс при 1С -р-И . Позже для более общего объекта, который образован классом г^ неоднородных функций
ввда ^{{ЛГУ-Ш"55}- Bj . <Н к.'..,*з
где множества J^L, t. е { -J,..., S J ,и ( конечны и
фиксированы, а 22 = {{Л,...,.As! , {Вм,..., В*}.} С операдд~ ями суперпозиции, в работе [ 3^ также установлена континуальность множества замкнутых классов для всех Pg , кроме Р, .
Выяснению природы этого континуума посвящено большое число работ [4-I5*j . Их объединяет общая тенденция, состоящая в ра-смотрении подклассов функций в rfe и изучении решеток в них. Принципами выборов подклассов являлись либо особая их значимость, типа предполнота в Рк , либо удобная аналитическая описуемость, типа линейности, полиномиальной характеризуемости и др.
2.
В этой работе изучается континуальная решетка замкнутых классов в ф.с. г , являющейся ф.с. типа Р2 и "бл образом обобщая ' Р^ . При этом строение решетки Ра является инструментальным средством для описания свойств решетки Р .
Цель работы. Исследовать строение решетки замкнутых классов неоднородных функций класса Р , являющегося одним из "ближайших" обобщений типа R, для класса Р .
Методы исследований. В работе используются методы дискретного анализа, теории функциональных систем и теории решеток.
Научная новизна. В диссертации решена задача описания характеров семейств классов заданной глубины. Классификация семейств в Р ведется с помощью их "следов", т.е. булевских функдий, лежащих в них. След.таким образом,является классом Поста. Глубина семейства классов из Р с заданным следом определяется глубиной следа в Pz . Под характером семейств классов из Р заданной глубины t понимается набор значений всех мощностей семейств, имеющих заданные следы указанной глубины . Таким образом, характер глубины очень быстро обретает универсальность.
Теоретическая и практическая ценности. Работа носит теоретический характер, однако полученные в ней результаты могут быть использованы при проектировании сложных вычислительных систем.
Апробация. Результаты диссертации докладывались на международной конференции по интеллектуальным система (Москва, 1991, 1992), на конференции "Дискретная математика" (Москва, 1991, 1993), на семинарах по теории автоматов на механико-математическом факуль-, тете МГУ под руководством академика АТН РФ В.Б.Кудрявцева.
Публикации. По теме диссертации автором опубликовано 5 работ, список которых приводится в конце автореферата.
3.
Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения и списка литературы 19 наименований, содержит 7 рисунков. Общий объем диссертации I2Q страниц.