Введение к работе
АКТУАЛЬНОСТЬ ТЕМЫ. В математической кибернетике функциональные системы (ф.с.) давно стали центральным объектом исследования. В основополагающей работе ti] начала 60-х годов А.А.Ляпунов и С.В.Яблонский разработали концептуальныг основы исследований в области математической кибернетики. Было замечено, что при описании функционирования некоторых классов пребразователей информации появляются системы функций k-значной логики.
Важным этапом в развитии теории ф.с. явились работы В.Б.Кудрявцева и его учеников [2,3]. Были получены, в частности, результаты указывающие на зависимость от типа операций сложности решения проблемы полноты. В работах В.А.Буевича, С.С.Марченкова и других авторов проведены исследования ф.с, связанных с конечными автоматами, частично определенными функциями .
Следует отметить, что вид функций k-значной логики, описывающих функционирование преобразователей информации, в ряде случаев существенно зависит от способа кодирования входной и выходной информации. Подооная ситуация ( при k-2 ) обнаружена давно, при к>2 данное обстоятельство становится существенным.
Ниже более подробно обсуждается взаимносвязь способов кодирования входно-выходной информации и реализации (в частности схемами) преобразователей.
Во-первых, при технической реализации преобразователей информации необходима согласованность между способом кодирования и операцией суперпозиции. Это означает, что при взаимнооднозначном кодировании в информации преобразователь f, полученный суперпозицией
преобразователей вин, f»h(G) , должен быть идентифицирован с преобразователем fs-hs(08). Таким'образом, операции кодирования и суперпозиции являются, в некотором смысле, перестановочными.
Во-вторых , из физических соображений (т.е. на языке схем) вместо множества UPk) всех замкнутых, относительно суперпозиции, классов функций k-значной логики достаточно рассматривать только множество ijjtf,,) тех замкнутых классов (з.к.) функций к-значной логики, которые обладают симметрией относительно некоторого класса кодирований с ( т.е. все "копии" каждой функции из з.к., полученные кодированием sec, также содержатся в з.к.).
Приведенные выше соображения лежат в основе нашего рассмотрения специального класса кодирований, соответствующих понятие двойственности функций относительно групп симметрии. Нетрудно видеть, что преобразователи, описываемые двойственными относительно перестановки в подгруппы с симметрической группы s(Ek)(над множеством значений переменных Ек) k-значными функциями f и f" идентичны ив задает некоторое взаимно-однозначное кодирование, которое можно отождествить с перестановкой в . Класс кодирований в этом
СЛУЧае МОЖНО ОТОЖДеСТВИТЬ С ГРУППОЙ G. Определяемое В работе G-38-
мыкание произвольной системы Е k-значных функций , является замы-калием множества всех таких функций, каждая из которых двойственна к некоторой функции из т. относительно некоторой перестановки группы с. На основе понятия с-замыкания естественным образом вводятся понятия с-з.к. , о-критериальной системы , G-предполного класса, с-порядка.
Очевидно, что G-з.к. является одновременно з.к. в обычно* смысле. Образуемую такими з.к. структуру обозначим через i^p, Каждая структура ic(Pk) является некоторым "приближением" структуры ВСеХ З.К. L(Pk), ГДЄ Le (Pk) L(Pk> ГфИ ЄДИНИЧНОЙ ПОДГруППе efc,
а структура ls(ie . (Pk), согласно работе [4], совпадает со структу-
рой. всех- з.к. , сохраняемых всеми автоморфизмами k-зачной логики (т.е. всеми внутренними автоморфизмами к-значной логики). З.к. структуры ls(e .(Pk) будем называть в дальнейшем симметрически з.к.
Важно отметить, что такие известные финитные свойства з.к. как существование конечной порождающей системы, предикатная описуемость сохраняются при с-замыкании.
В 1954 г. С.В.Яблонским [5І была решена задача о полноте в 3 -значной логике, при этом все 18 предполных классов были явно описаны. Отсюда вытекает алгоритм распознавания полноты для любой конечной системы к-значных функций. Идея решения задачи о полноте в терминах предполных классов стала одной из главных для ф.с. В дальнейшем , А.И.Мальцев в 1964 г. решил задачу о полноте для 4-значной логики, С.В.Яблонским , А.В.Кузнецовым, Ло Чжу-каем, И.Розенбергом и др. [5-9], были последовательно описаны все семейства предполных классов для к--значных логик. Завершающее описание опубликовано в 1970 г. И.Розенбергом.
Отметим, что проблема полноты для произвольных к-значных логик с операциями суперпозиции (т.е. з.к. из PJ не имеет окончательного решения. Причиной этого, по видимому, является принципиальная невозможность получения счетного описания решетки L(P ) з.к.из Рк при к*з, аналогичного полученному Э.Постом для двузначной логики в монографии [10]. В работе [II] было показано, что су-шествуют з.к. со счетным базисом, и мощность множества з.к. кон-тину ална. Отдельные фрагменты решетки з.к. к-значной логики исследовались С.С.Марченковым, И.А.Мальцевым, Д.Лау, Я.Деметровичем, Я.Базинским, Л.Ханаком, В.Чаканым, Х.Масидрй [12-22].
Описания конечных структур t-B(fk) для определенных типов
подгрупп с, с одной стороны, означают полное решение проблемы полноты для произвольных к-значных логик с оператором с -замыкания, с другой стороны, являются описаниями некоторых известных типов з.к. из МіРк)(з.к., самодвойственных относительно группы С).
Из вышеизложенного вытекает актуальность вопросов, рассмотренных в диссертации.
ЦЕЛЬ РАБОТЫ. I/ Исследовать структуры ^(р^) , с - подгруппа
симметрической группы s(Ек). Получить эффективное описаше структур ^(р,,). рассматривая структуры «-е(Рк) как -приближения" структуры MPJ.
2/ Получить полное описание структуры ls.e j (Pk) всех симметрических з.к. к-значной логики. Найти для каждого з.к. из "s(e ) (0V его s(Ek>-критериальную систему, s(Ek)-базис и порядок.
ОБЩАЯ МЕТОДИКА ВЫПОЛНЕНИЯ ИССЛЕДОВАНИЯ. Основными методами , используемыми в работе являются методы теории функциональных систем и теории групп, теории универсальных алгебр.
НАУЧНАЯ НОВИЗНА. Все результаты диссертации являются новыми. Основными результатами являются следующие:
I/ Получены эффективные критерии полноты для симметрически замкнутых систем к-значной логики.
2/ Получено достаточное условие для групп с при выполнешш которого структура >-с(Рк> конечна и эффективно описываем...
3/ Получено полное описание структуры симметрических з.к. ls(e ) (BV ' Для кажДГ0 3>к- из "-sdE і (pk> описана его siEj-кри-
териальная система, построен его s(ej-базис и найден его порядок. Построены-диаграммы структуры is{c . (оу и J-s(e } (р4) .
ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Работа носит теоретический характер. Полученные результаты найдут применения в теории функциональных систем, конечных алгебр, а также в теории синтеза схем из многозначных элементов.
АПРОБАЦИЯ. Результаты диссертации докладывались на семинаре "Алгебра и логика" акад. РАН Ю.Л.Ершова в институте математике СО РАН'/Новосибирск, І989-І99ІГГ./, на семинаре кафедры математической информатики КГУ проф. А.В.Анисимова /Киев,1988г./, на семинаре по теории автоматов в МТУ акад.АТН, проф.В.Б.Кудрявцева /Москва, 1990г./, на межреспубликанской школе-семинаре "Математическая теория по синтезу и сложности управляющих систем" 'под руководством чл.-корр. РАН О.Б.Лупанова /Минск, 1993г./, на семинаре кафедры математической' кибернетики МТУ "математические вопросы кибернетики" под руководством чл.-корр; РАН С.В.Яблонского /Москва,1994г./, на межгосударственном семинаре по дискретной математике, посвященной 70-летию С.В.Яблонского , под руководством чл.-корр. РАН О.Б.Лупанова /Москва; 1995г./.
ПУБЛИКАЦИИ. Основные результаты по теме диссертации опублико- ' ваны в работах {23-34].
ОБЪЕМ И СТРУКТУРА ДИССЕРТАЦИИ. Диссертация состоит из введения, пяти глав, приложения и списка литературы из 60 наименований. Глава і состоит из 4 параграфов., глава 11 состоит из 2 параграфов, глава ш состоит из 2 параграфов, глава iv состоит из 2 параграфов, глава v состоит из 2 параграфов. Приложение содержит 3 диаграммы и один сводный каталог из 31 таблицы . Общий объем диссертации составляет 250 страниц машинописного текста.