Введение к работе
Актуальность тещ. Одной из важнейших в теории функционалъ- . них систем является задача о полноте. Эта задача наиболее глубоко изучена Э. Постом для F^ . Им была , по существу, решена задача о полноте для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции. СВ. Яблонским была решена задача о полноте для R , при этом предполные классы были явно описаны. В дальнейшем, А.И. Мальцев в 1964 году решил задачу о полноте для f^ . СВ. Яблонским, В.А« Кузнецовым, Ло Чжу-каеы, И. Розенбергом и др. были последовательно построены в явном вида все предполные классы для к-значных логик. Завершающее построение при этом провел в 1970 году последний из них.
Проблема полноты для произвольных к-значных логик с операциями суперпозиции ( т.е. замкнутых классов из f^ ) не имеет окончательного решения. Причиной этого, по видимому, является принципиальная невозможность получения описания решетки замкнутых классов из F}< , аналогичнorD полученному Э. Постом для двузначной ло*' гики. Поэтому представляет определенный интерес исследование более "грубых" структур замкнутых классов из F^ , получающиеоя отождествлением замкнутых классов, имеющих одинаковый список стабилизаторов ( всего три типа стабилизаторов ), функций, принадлежащих отождествляемым замкнутый классам.
Цель работы. Каждой функции к-значной логики поставим в соответствие стабилизатор одного из трех типов ( G- » G- , L -стабилизатор ). Два замкнутых класса назнваютоя (г-эквива-лентныаи ( G- , I— -эквивалентными) если множества Or , ( Or , L_ )- стабилизаторов функций из этих замкнутых классов совпадают.
Целью работы являются исследование и построение структур клас-
сов О, & I- -эквивалентностей для Рк f к %. %
Метод исследования. Основными методами, используемыми в диссертации являются методы теории функциональных систем и теории групп.
Основные результаты и научная новизна.
В случае к= Ь , используя диаграмму замкнутых классов Э. Поста получено в явном виде описание всех структур классов
G , О- , L. -эквивалентностей. Структуры классов От -эквивалентности и L -эквивалентности оказываются проще по сравнению со структурой замкнутых классов Поста. Структура классов О"-эквивалентности содержит б элементов.
Доказано, что мощность структур классов О" ( G* » L ) -эквивалентности континуальна при t<.^V .
При к.=Ь получены исчерпавшие результаты о строении верхней части структуры классов L-эквивалентности. Это, в частности, позволило получить критерий L-эквивалентности произвольного замкнутого класса всей ij
Построена бесконечная убивающая цепочка замкнутых классов,
G -полных в F^ ( т.е. G" -эквивалентных всей F^ ), при этом при к^-н длина цепочки континуальна.
Естественно вводится понятие G"-границы, содержательно означающее "границу" между G" -полными и не. G--полными замкнутыми классами в решетке замкнутых классов из l~^ . Доказано, что G"-граница не менее чем счетна при к~5 и континуальна при к>, *\ .
Апробация работы. Основные результаты работы докладывались на семинаре "Алгебра и логика" в институте математики СО АН СССР и на семинарах кафедры высшей алгебры БГУ.
Публикации. Основные результаты диссертации опубликованы в
? печатных работах.
Объем работы. Дисоертащш состоит из введения и трех глав, списка литературы, включающего 24 наименования. Содержит 124 с. машинописного текста, 3 рисунка, 2 таблицы.