Вопросы выразимости и мощностной характеризации для дискретных функциональных систем с операцией суперпозиции тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

^ #

С^ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

5 ^ ИМЕНИ М. В. ЛОМОНОСОВА

%

Факультет вычислительной математики и кибернетики

Кафедра математической кибернетики

На правах рукописи

ГАВРИЛОВ Гарий Петрович

ВОПРОСЫ ВЫРАЗИМОСТИ И МОЩНОСТЬЮ?! ХАРАКТЕРИЗАЦИИ ДЛЯ ДИСКРЕТНЫХ ФУНКЦИОНАЛЬНЫХ СИСТЕМ С ОПЕРАЦИЕЙ СУПЕРПОЗИЦИИ

Специальность 01.01.09 — математическая кибернетика

Диссертация в виде научного доклада

на соискание ученой степени доктора физико математических наук

Москва — 1997

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета им. М. В, Ломоносова

Официальные оппоненты: доктор физико-математических наук

профессор В. А. Вуевич, доктор физико-математических наук профессор Ю. В. Голунков, доктор физико-математических наук профессор В. К. Леонтьев

Ведущая организация — Научно-исследовательский институт прикладной математики и кибернетики при Нижегородском государственном университете им. Н. И. Лобачевского

Защита состоится \ дд^ г в Ц час. 00 миа.

на заседании диссертационного Совета Д.053.05.38 факультета вычислительной математики и кибернетики МГУ по адресу: 119899, ГСП, Воробьевы горы, МГУ, факультет ВМиК

С диссертацией в виде паучного доклада можно ознакомиться в

библиотеке факультета ВМиК МГУ Диссертация в виде научного доклада разослана

Г.

Ученый секретарь диссертационного Совета профессор

Н. П. Трифонов

Введение

Функциональная система представляет собой пару {F, О.), состоящую из носителя F — совокупности функций (возможно, и частичных), определенных на некотором непустом множестве М, — и совокупности ÍI операций (которые могут быть частичными), заданных на множестве F. Обычно полагают, что функциональная система содержит только конечноместные (в частности, нульместные) операции. Из приведенного определения следует, что функциональные системы являются частным случаем универсальных алгебр [44], а значит, и алгебраических систем [61].

Первый этап в развитии теории универсальных алгебр связан с именем Л. Н. Уайтхеда [126] и начался в 1898 году. Современное представление об универсальных алгебрах стало формироваться в 30-х годах нашего столетия в работах Г. Виркгофа [104, 105], А. Тарского [124] и А. И. Мальцева [57].

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

В 10-30-х годах текущего столетия функциональные системы широко применялись для интерпретаций логических исчислений (исчислений высказываний, исчислений предикатов и др.) с целью установления их непротиворечивости и полноты, а также доказательства независимости аксиом и правил вывода, используемых при построении этих исчислений [91, 108].

В последующем функциональные системы нашли также приложение в задачах, связанных с синтезом разнообразных управляющих устройств [70, 94, 119, 120], к частности, релейно-контактных схем и схем из функциональных элементов [53-55], конечных автоматов [1,

7, 29, 39, 45, 73, 86} и др. В связи с этим вводились и исследовались различные «естественные» операции, осуществляемые над элементами изучаемых систем (схемы рекурсивных вычислений и операция минимизации [37, 58], операция обратной связи [1] и пр.). В настоящее время широко привлекаются программные операции [30-34, 50, 79, 102, 106], описание которых удобно давать на языке отношений (предикатов) и, тем самым, использовать язык алгебраических систем.

Семантическое построение классической логики высказываний предполагает оперирование с булевыми функциями (или, иначе, функциями алгебры логики). Описание всех замкнутых (относительно операции суперпозиции) классов булевых функций было дано Э. Постом; краткое сообщение об этом результате появилось в Американском математическом журнале [109] в 1921 г., а подробное изложение его было опубликовано в книге [110]. Эти классы, названные впоследствии классами Поста [19, 20, 98, 99], образуют по включению счетнобескопсчное частично упорядоченное множество, называемое часто диаграммой включений Поста. С помощью этой диаграммы можно описать процедуру распознавания выразимости (полноты) в классической логике высказываний, а именно, для любого конечного множества ^ булевых функций, заданных таблицами их значений или формулами, решить вопрос о представимости (выразимости, реализуемости) произвольной булевой функции через функции множества Р. Используя диаграмму включений, можно строить разнообразные базисы и полные системы в каждом замкнутом классе Поста, а также для всякого конечного множества булевых функций находить семейства классов Поста такие, что объединение классов, образующих семейство, включает рассматриваемое множество функций.

Дальнейшее развитие проблематики выразимости в классической логике и в ее многозначных обобщениях было инициировано в 50-е годы текущего столетия приложениями математической логики в кибернетике [93]; этому в частности способствовали лекции П. С. Новикова [70, 75] и С. В. Яблонского [95] в Московском государственном университете. Важную роль сыграла в пробуждении интереса к многозначным логикам книга [116].

С. В. Яблонским [93, 95] был получен критерий полноты для трехзначной логики, т. е. для функциональной системы (Р3, С), где Рз — множество всех функций, определенных на Ез = {0,1,2} и принима-

ющих значения тоже из Ез, а С — операция суперпозиции. Критерий формулировался в терминах так называемых предполных классов функций из Р3, т. е. максимальных, замкнутых относительно С, функциональных подсистем системы (Рз,С), которых оказалось ровно 18. Кроме того, С. В. Яблонским было описано [95] несколько семейств предполных классов в Ж-значных логиках Рк, т. е., иначе говоря, в системах {1\,С), и при к > 4. В частности, были выделены классы монотонных (относительно линейного порядка) функций, классы функций, сохраняющих разбиения множества Ек — {0,1,..., к — 1}, к > 3, классы линейных функций (относительно операций сложения и умножения по модулю к), классы самодвойственных функций и классы типа Т, которые, как выявилось впоследствии [38], образуют наиболее мощпое семейство предполных классов в Рк ■

В это же время А. В. Кузнецовым была установлена [95; 98, стр. 54] теорема о полноте в системе Рк, гласящая: можно эффективно построить конечное множество замкнутых классов в Рк такое, что любая совокупность функций из Рк полна в Pk тогда и только тогда, когда она целиком не содержится ни в одном из классов этого множества. Доказательство А. В. Кузнецова опиралось на понятие сохранения функцией предиката, заданного на множестве Ек [6, 46, 47, 70, 78, 100, 101]. В работах [95, 98] доказательство этой теоремы А.В.Кузнецова базируется на понятии множества функций, сохраняющих данную совокупность функций из Рк.

Критерий полноты для Pk при к > 3 сформулировал И. Розенберг [112] в 1965 г., используя шесть семейств предполных классов в Рк, а именно [100, 101] семейства классов: а) монотонных (относительно частичных порядков) функций [63, 95], причем эти порядки имеют наибольший и наименьший элементы; б) самодвойственных (относительно специальных подстановок на Ек) функций [95]; в) функций, сохраняющих нетривиальные разбиения множества Ек [95]; г) квазилинейных функций [95, 107]; д) функций, сохраняющих центральные предикаты; е) функций, сохраняющих предикаты специального вида (так называемые классы типа В). Классы функций, сохраняющих центральные предикаты, представляли собой (см. [101]) несущественное обобщение классов типа Т из [95].

Достаточно подробное доказательство своей теоремы И. Розенберг опубликовал [113] в 1970 г.; на русском языке несколько усовершенствованное изложение этого результата дано в книге [101].

Алгебраическая трактовка вопросов выразимости для функциональных систем была первоначально представлена в работах А. В. Кузнецова [46, 47] и А. И. Мальцева [59, 62], обратившего внимание исследователей (в 1966 г.) на важность изучения так называемых итеративных алгебр Поста, связанных с замкнутыми классами в системах {Рк, С) при алгебраическом представлении операции суперпозиции.

Проблема описания замкнутых классов в Р% при к > 3 является принципиально более сложной, чем в Р2, ибо в [к > 3), как было установлено Ю. И. Яновым и А. А. Мучником [103], есть классы, не имеющие базисов, а также классы с бесконечными базисами, что влечет за собой континуальную мощность структуры включений замкнутых классов в Рк ■

В силу этого многие исследователи занимались изучением отдельных семейств замкнутых классов в Рк и соответствующих решеток, выделяя такие свойства, которые либо допускают достаточно хорошую характеризацию рассматриваемых семейств классов, либо имеют теоретический и практический интерес [2, 3, 8, 24-27, 48, 49, 66, 68, 69, 71, 72, 74, 80,89, 90, 111,116]. Укажем также некоторые работы, посвященные нахождению базисов и практически полезных полных систем в разнообразных замкнутых классах в Рк, и работы об удобных для приложений формульных представлениях функций из Рк [19, 20, 23, 25, 60,117, 121-123,125]. Здесь стоит отметить, что формульные представления позволяют получать и обосновывать эквивалентные соотношения между элементами функциональных систем (функциями и операциями), выявлять полные системы в соответствующих классах функций и формул, находить и описывать замкнутые классы (используя, например, множества функций, входящих в формульные представления), оценивать число замкнутых классов, обладающих теми или иными выделенными свойствами, и число функций в исследуемых классах, описывать алгоритмы вычисления значений функций, предлагать конкретные методы синтеза соответствующих устройств (например, схем из функциональных элементов), оценивать сложность и надежность предложенных реализаций функций (по сложности и надежности элементов, из которых построены устройства, реализующие данные функции).

В 60-х годах началось исследование частичных функциональных систем {Рк,С}, где Рк — множество функций на Еь (всюду и не всюду

определенных). Этой проблематике посвящены, например, работы [51, 52, 82, 87, 88].

В конце 50-х —начале 60-х годов внимание исследователей было также обращено на изучение счетнозначной логики [9-13, 15, 70, 97], или, говоря иначе, функциональной системы (РШ,С), где Рш — множество всех функций, определенных на множестве Еш ={0,1,..., г,...}, и ее «частичного» расширения {РШ,С) и различных подсистем в (РШ,С), в частности, предельных логик [14, 96, 97], примитивно рекурсивных, общерекурсивных и частично рекурсивных функциональных систем [37, 77].

Эти изыскания были инициированы работами С. В. Яблонского [96, 97], А. В. Кузнецова [70] и А. И. Мальцева [58]. Результаты исследований, затрагивающих эту проблематику, отражены в работах [4, 5, 16-18, 28, 35, 36, 40-42, 48, 49, 56, 64, 65, 67, 76, 78, 80, 81, 83-85 92, 114, 115, 118].

Работы автора, составляющие основу данного доклада, связаны с исследованием свойств диаграмм включений замкнутых классов в функциональных системах {Рт, С), где тп = 2,3,... и т = Н0. Все эти работы объединены неким общим взглядом на проблематику полноты для дискретных функциональных систем (и даже — для произвольных универсальных алгебр). Опишем его, используя язык функциональных систем.

Проблема полноты для функциональной системы Ф = (К. О) состоит не только в выявлении принципиальной возможности реализации (выразимости) любой функции из Р через какие-то функции из заданной совокупности функций С Р, но и в указании (очерчивании) тех средств, которые необходимо (или достаточно) использовать при конструировании функций. В частности, описание формульных реализаций (их вида), имеющих определенное строение или определенную сложность, понимаемую в каком-либо смысле.

В дальнейшем мы иногда вместо термина «полная система» применяем термин «полпое множество».

Для сравнения выразительных возможностей, предоставляемых разными полными в Р (относительно совокупности операций П) множествами, можно привлекать свойства или характеристики диаграммы включений, образуемой всеми замкнутыми классами, порождаемыми подмножествами рассматриваемого полного в Р множества Р'. Обозначим эту диаграмму включений через С(Р'). Она является ча-

стично упорядоченным множеством относительно теоретико-множественного включения и, если предполагать, что в ней всегда содержится пустой замкнутый класс 0, представляет собой нижнюю полурешетку (но решеткой может и не быть). Задача исследования таких диаграмм включений с позиций теории решеток — особая проблема.

Диаграмма включений £(-Р) всей системы Ф несет в себе достаточно полную информацию о порождающих возможностях разнообразных подмножеств /<" множества 1<\ а значит, и каждой подсистемы Ф' = (Р',С1) системы Ф.

Рассматривая конкретное полное в Р подмножество Р', мы, естественно, не можем получить полную информацию о диаграмме £^) по £(/'"), но все же имеем возможность как-то характеризовать диаграмму С(Р) и описывать какие-то свойства системы Ф, оценивать сложность строения ее элементов, формировать разнообразные условия полноты для нее.

Сравнение разных полных в Р множеств можно осуществлять, например, следующим образом. Пусть ^ и Р2 — два полных множества в Р. Полагаем, что ¡'\ (-Р\ не сильнее Р2), если £(-Р\) С £(/'2). Отношение =<: является предпорядком (т.е. рефлексивно и транзитивно). На множестве Т — {-Р1'} всех полных в Р его подмпожеств естественным образом вводится отношение эквивалентности разбивающее Т на классы эквивалентных полных в Р множеств: к, Р-л тогда и только тогда, когда Р± ^ и Рч ^ Р\ ■ Элементы фактор-множества Т/ и взаимно однозначно соответствуют множеству разных диаграмм включений {£(/")}, где F/ пробегает некоторую совокупность Р, состоящую из разных представителей классов эквивалентности множества Т, определяемых отношением и.

Если мы хотим получить достаточно подробную информацию о диаграмме включений £{Р), используя не всю диаграмму, а только некую собственную часть ее, то можно попытаться выделить подходящие полные множества в Р1, обладающие приемлемыми свойствами. Например, построить некоторую (возможно, бесконечную) совокупность полных в Р множеств {/''1,..., удовлетворяющую условию:

I

все преднолньге классы из диаграммы £(/'') содержатся в и £(/'',)■

! = 1

Тогда, если для £(^) справедливо утверждение, что всякий замкнутый класс в ней расширяется до предполного, мы получим обычный (классический) критерий полноты, подобный сформулированному вы-

ше при описании результатов о полноте для систем (Рк, С) (см. также [98, 100, 101]).

Один из методов поиска подходящих полных множеств в Р состоит в конструировании формульных представлений (реализаций) для функций множества Р и при этом вполне возможно, что удобных формульных реализаций для «обозрения» существенной части полных множеств в Р понадобится несколько. Например, для функциональной системы (Рт, С) (или, говоря короче, для алгебры логики Р->), чтобы выявить все предполпые в Ро классы, можно использовать следующие три полные в Р? множества: {0, ху, х(&у®1}, {1, хУу, х®у} и {0,1 ,х,ху © хг ф уг], причем ни одно из них выбросить нельзя, но при этом почти все замкнутые классы из диаграммы включений Поста -С(Рг) останутся не выявленными. Для получения достаточно мощного семейства замкнутых классов из С(Р^) можно взять, на-

оо

пример, полное в Р2 множество {0.1, х(у V г)} и У (Лп(£"+1)}, где

п-1

п + 1

^(ё"*1^ V • ■ • ^¿-1^1+1 ■ ■ хп.

¿=1

Может оказаться желательным найти сравнительно простое полное в Г множество К' такое, что С(Р') = £(Р). Назовем его исчерпывающим для Г (или Ф). Если Р' удовлетворяет дополнительному условию: никакое его собственное подмножество Р" исчерпывающим тля Р не является, то множество Р' естественно называть неизбыточ-чым (или неприводимым) исчерпывающим множеством для Р. Возни-<ают вопросы о существовании таких множеств, их числе, об их связи ; неприводимыми порождающими (полными) множествами для Р и т.д.

В Ръ неизбыточным исчерпывающим множеством является, например, множество {0,1, г, ж, ху, х V у, ху, х V у, х{уУ г), х V уг, х(у VI), х V

оо

/г,хфуфг,/12(х1,х2,хз)}и и {Лп(х"+1),/г;(ж"+1)}, где /г* — функ-

п=3

чия, двойственная к функции Нп. Нетрудно доказать, что в Рк (при ; ^ 2) множество всех неизбыточных исчерпывающих систем конти-1уалыю.

Для обозрения и сравнения диаграмм из совокупности {£(Р')} и /становления различий между замкнутыми классами, входящими в шх, нужно уметь «отделять» любой класс К у из С(Р') от всякого фугого класса К2 (из £(Р') или из £(Р")). Это можно осуществить,

указав «отделяющее» свойство q, присущее функциям из А'] (и сохраняемое при проведении преобразований, допустимых в данной функциональной системе Ф), но не присущее хотя бы одной функции из класса К2, т.е. если А'(<?) — класс всех функций из Р, обладающих свойством q, то должны быть справедливы соотношения: А'1 С А'(4) и К2\К(я) Ф ф.

Возникает, естественно, задача поиска таких свойств. Их можно находить, например, исследуя строение функций из классов К]_ и К2 или анализируя строение формул, реализующих функции из класса А'х. Скажем, рассматривая класс всех неконстантных монотонных функций в Р2, можно использовать тот факт, что сокращенная дизъюнктивная нормальная форма любой такой функции (и только таких функций) не содержит отрицаний переменных.

Имея конкретные формульные реализации (одну или несколько), построенные с использованием полного в Р множества Р", мы получаем принципиальную возможность описать диаграмму включений £(Р'), выявить в ней такие совокупности замкнутых классов, которые можно обозреть и применять для формирования каких-то условий полноты. Полные множества в Г можно использовать и для получения оценок сложности диаграммы С(Р). Например, если ^^ — полное в Р множество, то разбиваем его на попарно не пересекающиеся подмножества Р\,...,Рт такие, что замкнутые классы вида [А{ и ... и , где Р{ С А, (г = 1,..., т), расширяются до разных классов, удовлетворяющих каким-то дополнительным условиям, например, являются предполпыми классами в £(А).

Метод построения гиперконтинуального семейства прсдполных классов в счетнозначной логике Рш, предложенный автором в [11, 12], реализует как раз этот прием и был приспособлен [18] для получения нового гииерконтинуалыюго семейства предполных классов в Рш (см. п. 3.2).

В свете описанного общего взгляда на проблематику полноты дадим некоторые пояснения к результатам, включенным в наш доклад.

В п. 1.1 рассматривается задача описания фрагмента диаграммы С(ЯЯрт), состоящего из замкнутых классов, содержащих класс полиномов Ро1р.. Нами было построено [25] достаточно естественное полное множество в 9Лрг и, опираясь на него, мы описали некоторую совокупность замкнутых классов, доказав [27], что все они разные. Для обоснования этого факта были найдены свойства Я,- и Н[ (именно

этот этап исследования был сложным). Свойства Я,- нужны т> случае, когда р ^ 3, а в случае р = 2 необходимо добавить свойства Я;. Эти свойства отделяют построенные замкнутые классы друг от друга.

В п. 1.2 приведено описание некоторого формульного представления для класса системы Р^, состоящего из функций, самодвойственных относительно подстановки в(ж) ф. х. (Наиболее трудным этапом исследования было построение функции Ф.) Используя это представление, можно описать фрагменты диаграмм С^ь^х))) в случаях, когда подстановка «(х) отлична от единичной и не является циклом. Выбор именно классов Zt:{s{x)) связан с тем обстоятельством, что, во-первых, среди них немало предполных в Рк классов [38, 95, 100, 101], а во-вторых, они связаны со специальным весьма интересным семейством универсальных алгебр, так называемыми однородными алгебрами [68].

Заметим, что нами получены [100, 101] и иные формульные представления — для функций из предполных классов семейства {//(/?)} (класс 11 (Б) состоит из всех функций, сохраняющих нетривиальное разбиение Б множества Еь) и семейства {Т(£)} (класс Т(£) состоит из всех функций, сохраняющих непустое собственное подмножество £ множества £к), а также полных в Рк систем, почти целиком состоящих (кроме одной функции) из функций, принадлежащих какому-либо предполному классу Мг (в нем содержатся только все такие функции, которые монотонны относительно частичного порядка г, заданного на Ек и имеющего наибольший и наименьший элементы).

В п. 2.1 описан результат, связанный с получением характериза-ции замкнутых классов Р^ (г = 1, 2,..., 8 и у, = 2,3,...), образующих счетнобесконечные цепочки в диаграмме включений Поста. Исполь-

оо

зуя полное в классе множество Я = {ху}и и {/гп(хп+1)} и найден-

п=2

ные нами [23] рекуррентные формульные представления для функций из классов ^ (/( 2), можно дать достаточно простое доказательство конечной порождаемое™ классов Р£ (см. также [19, 20]) и полностью описать образуемую ими цепочку в диаграмме £(Рг)- Описание других бесконечных цепочек диаграммы Поста, состоящих из классов Р-1 (¿ = 1,2,..., 8), можно получить с помощью принципа двойственности и добавления к множеству Я константы 0 и функций х(у\/г) и ху (см. [19, 20]).

При построении формульных реализаций функций и конструиро-

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

В п. 2.2 изложены результаты, относящиеся к выявлению (при проведении операции отождествления переменных) одновременного сохранения булевой функцией следующей совокупности свойств — нелинейность (¿), немонотонность (М), несамодвойственность (5) и существенная зависимость от всех оставшихся переменных (Ф). Получен [22] алгоритм, названный «последовательным отождествлением с возвратом», который позволяет для функций, существенно зависящих от всех входящих в них п ^ 7 переменных, находить допустимую для отождествления пару переменных. Оказалось, что допустимая пара переменных всегда существует, если число существенных переменных у функции равно 4 или не меньше 6. Однако, среди функций, существенно зависящих от 5 переменных, имеется ровно 1790 «исключительных» функций, у которых допустимых пар нет. Этот результат был весьма неожиданным, так как проведенными ранее исследованиями (ссылки на соответствующие работы даны в статье [22]) было установлено, что если у булевой функции не менее 4 существенных переменных, то допустимые пары найдутся для каждого из следующих наборов свойств: (Ь, Ф), (Ь, М, Ф) и (£, 5, Ф).

Раздел 3 содержит изложение результатов, относящихся к харак-теризации диаграмм £(РШ) и С(РШ).

Исследование вопросов полноты в счетнозначной логике Рш и частичной счетнозяачной логике Рш осложняется тем обстоятельством, что мощности диаграмм £(РШ) и £(РШ) гиперконтинуальные (а для систем Рт и Рт, где т > Ко, они равны В [12] было устано-

влено, что в Рш гиперконтинуальна также мощность множества всех предполных классов. Используя этот результат, В. А. Соколов [83] доказал аналогичное утверждение для системы Ри.

Естественно возникает вопрос о мощностной характеризации собственных подсистем из систем Ри и Рш и различных совокупностей замкнутых классов из диаграмм £(РШ) и £(РШ).

В п. 3.2 приведены утверждения, обосновывающие следующий ре-

зультат: мощность множества всех предполных классов, не содержащих Сш,в диаграмме С(РШ) гиперконтинуальна (здесь Сш — континуальное множество всех обобщенных констант, т. е. одноместных функций, каждая из которых принимает конечное число разных значений). При получении этого результата был использован разработанный автором прием, описанный нами выше (он базируется на специальном разбиении подходящего полного в Рш множества) и реализованный ранее в работах [11, 12].

Этот результат показывает, что гиперконтинуальности множества предполных классов избежать не удается и при удалении континуальных подмножеств из некоторых полных систем в Ры.

В п. 3.3 излагаются утверждения, связанные с установлением того факта, что в каждом слое диаграммы £(РШ), отстоящем от Ры на конечном расстоянии, существует замкнутый класс, имеющий гиперконтинуальное множество предполных в нем классов. Все эти классы строятся как классы, сохраняющие подходящие множества одноместных функций. Описание этих множеств функций осуществляется с использованием специальных разбиений множества Еш и множества последовательностей, составленных из элементов множества Еы и удовлетворяющих условию: если число содержится в последовательности, то оно стоит в пей только на конечном числе мест.

Заметим, что и в п. 3.2 при построении требуемой полной системы применяется некоторое разбиение множества Еш и множество всех последовательностей, составленных из элементов множества Еы.

В п. 3.4 приведены все три класса типа Слунецкого, содержащиеся в диаграмме С(РШ). Они построены тоже как классы сохранения подходящих множеств, состоящих из всех одноместных функций и специально выделенных двуместных функций.

При рассмотрении счетнобесконечных замкнутых классов в £(РШ) представляют интерес такие классы, которые можно толковать как системы, моделирующие любую ¿-значную логику (к ^ 2), а именно, содержащие гомоморфные прообразы этих логик. Оценивая эту совокупность классов (их называют предельными логиками), С. В. Яблонский установил [96], что даже если потребовать попарной неизоморфности предельных логик, состоящее из них максимальное по мощности множество континуально. Нами доказано [14], что континуальным является и максимальное по мощности множество конечно порожденных попарно не изоморфпых предельных логик. В п. 3.1 приведены

утверждения, связанные с обоснованием этого результата. Дальнейшие изыскания, выполненные Я. Деметровичем [36], показали, что континуальности избежать не удается и при других естественных требованиях, накладываемых на отношения между предельными логиками.

Заметим, что при построении соответствующих предельных логик в п. 3.1 нами привлекается некое разбиение множества и множество так называемых быстро растущих последовательностей, составленных из элементов множества Еш.

Итак, все результаты автора, включенные в доклад, выявляют ряд таких свойств диаграмм £(-Рг), £(Рк), <С(РШ), и соответствую-

щих им функциональных систем Р2, Рк, Puji Рш у которые связаны с мощностной характеризацией их (оценивались мощности фрагментов диаграмм) и с использованием формульных представлений для входящих в указанные системы функций (с последующим приложением полученных представлений к описанию множеств замкнутых классов из этих диаграмм).

Если говорить кратко, результаты, содержащиеся в докладе, таковы.

1) Дано несколько формульных представлений для некоторых замкнутых классов функциональных систем {Рк,С), к > 3, и (Р^,С).

Именно:

а) Формульное представление для функций класса УЯк, где к = рт, р — простое число и г > 2, состоящего из функций, сохраняющих сравнение по каждому модулю d. — ps, s = 1,..., г — 1, (разд. 1, п. 1.1).

б) Формульное представление для функций из Р*, самодвойственных относительно подстановки з(г) ф. х множества Ек (разд. 1, п. 1.2).

в) Рекуррентное формульное представление для монотонных булевых функций, входящих в замкнутые классы Рд' из бесконечных цепочек диаграммы включений Поста (разд. 2, п. 2.1).

2) Приведено описание некоторых решеток замкнутых классов в {Рк, С), к = рг, включающих класс полиномов; выявлено отличие случая р = 2 от случаев, когда р > 3; указаны ширина и высота этих решеток и число элементов в них; сформулированы некоторые необходимые условия полиномиальности функций из класса fMpr (разд. 1, п. 1.1).

3) Найдены все булевы функции, существенно зависящие пе менее чем от 4-х аргументов и не сохраняющие при проведении опе-

рации отождествления переменных в них следующую совокупность неитеративных свойств — нелинейность, несамодвойственпость, немонотонность и существенную зависимость от всех своих аргументов. Таких функций оказалось ровно 1790 и все они зависят существенно от пяти переменных (разд. 2, п. 2.1).

4) Установлена континуальность множества предельных логик, обладающих конечным базисом (разд. 3, п. 3.1).

5) Дано обоснование гиперконтинуальности множества предпол-ных классов счетнозначной логики, не содержащих обобщенных констант (разд. 3, п. 3.2).

6) Установлено, что для каждого натурального числа / > 2 в структуре включений замкнутых классов счетнозначной логики: Рш существует класс высоты / (причем дается конструктивное описание каждого такого класса), содержащий гиперконтинуальное множество классов высоты / + 1.

7) Показано, что в частичной счетнозначной логике Ри] существует ровно три класса типа Слупецкого, и приведено описание этих классов.

Использовались следующие приемы:

а) проводился поиск подходящих формульных представлений, базирующийся на характеризации свойств функций, входящих в исследуемые замкнутые классы;

б) осуществлялись поиск и описание совокупностей функций, классы сохранения которых обладают нужными свойствами, и при этом использовались соответствующим образом подобранные системы подмножеств натурального ряда;

в) проводилось выявление независимости функций из исследуемых полных систем, для чего привлекались (искались) свойства, сохраняемые этими функциями, и осуществлялось «погружение» исследуемого класса в класс, являющийся элементом некоторого семейства замкнутых классов, состоящего из попарно различных классон, не• содержащихся друг в друге; затем исследовались пересечения классов данного семейства.

Указанные приемы являлись как раз основными методами (подходами), применяемыми нами при решении затрагиваемых в данном докладе задач.

Все результаты, содержащиеся в работах, которые легли в основу доклада, к моменту выхода работ из печати являлись новыми.

Эти работы (экземпляры их помещены в отдельном приложении) носят теоретический характер. Полученные в работах [12-15] результаты оказали влияние на научные изыскания ряда авторов [5, 35, 36, 65, 67, 76, 83, 85, 114]. Результаты работы [23] вместе с работами [19, 20] легли в основу одного из разделов курса «Избранные вопросы дискретной математики», читающегося на кафедре математической кибернетики Московского государственного университета.

Список литературы к докладу состоит из 126 источников.

Результаты автора, отраженные в докладе, содержатся в работах [13-18, 21-27,100, 101] и докладывались на Международном конгрессе математиков в Москве (1966 г.), Третьей Всесоюзной конференции по математической логике в Новосибирске (1974 г.), Четвертой Всесоюзной конференции по математической логике в Кишиневе (1976 г.), Второй Международной конференции по дискретной математике и ее приложениям в Благоевграде (1990 г.), X Международной конференции по теоретической кибернетике в Саратове (1993 г.), XI Международной конференции по теоретической кибернетике в Ульяновске (1996 г.) и на заседаниях семинара «Математические вопросы кибернетики» в МГУ, руководимого членом-коррсспопдентом РАН С. В. Яблонским.

1. Многозначные логики

1.1. Замкнутые классы в Ррт, содержащие полиномы

Полиномиальные функции многозначных логик играют важную роль в теоретических изысканиях и практических приложениях [2, 3, 71, 72, 74, 80, 89, 90, 95, 100, 101, 107]. Поэтому представляет интерес изучение строения совокупности замкнутых классов в Рь, содержащих класс полиномов Polj,. Надструктура класса , состоящего из всех ¿-значных функций, сохраняющих сравнение по каждому собственному делителю числа к, исследовалась, например, в работах [71, 72, 80, 89, 90]. В данном пункте приводится описание результатов, полученных нами [24-27] при изучении решетки (РоЦ,9Jlk) для к = рг, где р — простое число и г > 2. Выбор таких значений к оправдывается тем обстоятельством, что каждому замкнутому классу А из решетки (Polt,9Jlit) взаимно однозначно соответствует (см., например,

[80]) набор (Bi,.. ,,BS) замкнутых классов из решеток (Ро1р>, ЙЛр--(), г = 1,..., s, где pi,..., pj — различные простые числа и г,- >' 1.

В самом деле, пусть к = р^1 .. .рг/. s > 2. Тогда любую функцию /(£") = f{x\,..., хп) £ Рк можно представить в виде

s

! = 1

где к{ € Ек = {0,1,..., к—1}, ki = (modк), <р — функция

Эйлера, /0(5») : ££ ff\xn) = f(xn) (modp?') и сумма и

произведение берутся по модулю к. Далее, если f{xn) G Шк, то

S ¿=1

где х^р £ Ерг, и х^ = Xj (modp^'), j = 1,..., п, а также при /(£"•), € т f(fi(xi,..., rm), ...,/„ (г 1,..., rm)) =

t ^ ■ • ■ • . • • • ■ ЯН*?, • ■ • ■ *£))■

1 = 1

Поэтому, если А — замкнутый класс из ЯЯ^, то ему однозначно соответствует набор замкнутых классов (Biy..., Bs), где В,- С Ш*,, i = 1,..., s, и

Bi = [g{xn)\3f{xn) g А (5(4°, • ■ • ,4°) = • ■ ■. 4i}))} ■

Обратно, набору замкнутых классов (В\,..., Bs), где В,- С (t = 1,..., s) соответствует единственный класс Л С ШЦ, функции которого получаются из функций, принадлежащих классам В\,..., Bs, по формуле (1).

Итак, для описания решетки замкнутых классов (Polt, Шь) достаточно изучить строение решетки (Ро1рг, 9Лрг), где р — простое число иг>2.

Пусть /(£") £ .Ррг. Так как любое число а £ Ерг можно предста-

г-1

вить в виде а = Y2 dtp', где а,- £ Ер, то справедливо разложение i=0

¿=о

где функция (0,-/)(£") = [/(хп)/р'} ~Р [1(хп)/р'+1] осуществляет отображение вида ЕрГ —> Ер. Здесь деление рассматривается в поле С} и [Ь] означает целую часть числа Ь £ С}, а сумма и произведение берутся по модулю к. Далее, пусть

к(п)(хп) = I Р'> есЛИ = (тоар^1),

1 \ 0 в других случаях,

где/ = 0,1,..., г - 1.

Утверждение 1. Если /(£п) 6 5ЭТрг, п > 1, то

/(*")=£ £ ((Шг))-ь\п\х-т).

1=0 г££п

р'+1

Утверждение 2. Если п > 3, то = — ,. ..,

хп-1)>хп) ПРИ всяком г = 0,1,..., г — 1. Из утверждений 1 и 2 вытекает

Утверждение 3. Система А(рг) — {1, х + у, т, ■ у} и и полна в классе ЗЯрг.

Утверждение 4. Если р > 3, то = /г^1) (2р* - Ь.^^)-

—/»¿^(яг)) при всяком г = 0,1,..., г — 1. Учитывая утверждение 4, получаем

г-1

Утверждение 5. Система В(рг) = {1, х + у, х • у} и и Щ '(х)}

»=о

полна в классе ЯПр? при р > 3.

В классе Шрг при р > 2 являются полными также системы А(рГ)\{г ' У} и = Жрг)\{/1о2)(^2)>7 а при р > 3 — системы

В(рг)\{г • у} и В'(р*) = В&)\{к£\х)}.

Исходя из систем А'(рг) и В'(рг), можно указать несколько совокупностей замкнутых классов, принадлежащих решеткам (Ро1рг-,

Пусть р > 3 и г > 2. Рассмотрим следующие замкнутые классы в Ррг:

где ф С {/1...,/т} С {1, ...,г- 1}.

Среди этих классов находятся классы Ро1рг и Шрг, а именно: Ро]рг = Ург(ф) и Шрг = Ург(1,. ,.,г- 1).

Теорема 1. Классы Ур*(1\, ... ,1т) попарно различны и образуют (вместе с классами Ро1рг и Шрг) решетку (по включению), изоморфную решетке всех подмножеств множества {1,..., г — 1}. Ее ширина

^[(г — 1)/2]^, высота равна г — 1 и в лей 2Г_1 элементов.

Для доказательства теоремы 1 вводится свойство Н((рг): функция /(£") е Шрг обладает свойством Я,(рг), если функция (&{/)(тп +р'уп) при всяком наборе т" € является линейной функцией из Рр (т.е. относительно уп 6 Ер). В этом определении р > 2. Множество всех функций, обладающих свойством Щ(рг), обозначается через Р7,(рг).

Теорема 2. Для каждого г = 1,..., г — 1 множество ^¡(р1") является замкнутым классом, включающим класс Ро1рг и содержащимся в классе Шрг.

Следствие. Каждая полиномиальная функция из Ррг обладает лю-

г— 1

бым ИЗ СВОЙСТВ Нг[рг), I — 1, .. ., г — 1, т.е. Ро1рг С р) И^(рГ).

1=1

Теорема 3. Для всякого подмножества Ь — {/ь ..., /т} множества Е'г — {1,. .., г — 1} справедливо включение

ад,...,/„) с П иЦРГ).

1ЕЕ'г\£

(Пересечение, взятое по пустому множеству индексов, совпадает с классом ЯУ1рг.)

Если р~ 2, то для описания решетки замкнутых классов, связанных с системой А'{рг), необходимо ввести еще одно свойство.

Пусть { — фиксированное, 2 ^ г г — 1. Будем говорить, что функция /(ж™) из И^(2Г), п > 1, обладает свойством Н{(2Г), если при всяком т £ Е^,-! сумма

(0.7) (г + 2-1 + Ту,.. .,Г + 2'"1 + 2{у) ©

©(0,7)(т+2\...1г+2'"у)>

где у £ {0,1} и ф — сложение по модулю 2, зависит от переменной у несущественным образом. Множество всех функций из \¥{(2Г), обладающих свойством Н[{2Г), обозначается через И;1'(2Г).

Теорема 4. Для всякого г такого, что 2 ^ г <С г — 1, справедливы включения

г-1

{1,х+у,*-у} и У {Лр}(52)} С [^(2Г)] С

1=1 М'

причем £ [И7(2Г)].

Рассмотрим следующие замкнутые классы в Ргг (г > 3):

... ,/т; «1,..., ег) ~

= [1 ,х+у,х.у, к£\х),..., . ■ •. ,

где ф С {¡г,..., 1т} С {2,..., г - 1}, ф С К... С {1,... ,г - 1} и

{к,-■ -,1т] П{$1, ...,«,} = ф.

Среди этих классов находятся классы РоЬ-- и Ш2г, а именно: Ро12, = У2г(ф;ф) и Ж2г= У2г(ф;1,...,г-1).

Теорема 5. Пусть Ь = {1Х,..., 1т } и 5 = {«1} — подмножества из множеств Е" = {2,..., г — 1} и Е'Т — {1,. .., г — 1} соответственно. Тогда справедливо включение

«0 с П ]у{(2г)п р| [И*(2Г)3-

(Пересечение, взятое по пустому множеству индексов, совпадает с классом £¡12'-.)

Следствие. Разным парам таким, что Ь П 5 = ф, соответ-

ствуют разные классы Уг^Сь ■ • •, 1т', • ■ ■, Учитывая равенство

¿е-ЕЛя

г-1 2'-1

_ 2) + £ £ ~ 20 = ® '

¿=1 /=2 —1

и соотношения

[Я ^(ж) = 1 - х2^1 £ Ро12г и /^(х) $ Ро12г, получаем Ро12'СМ1;^)= [1,Х + У,Х-У,}1[1\Х)\ С

С

Теорема 6. Класс ^>-(1;^) отличен от каждого из классов У2'{Ц Я), где ф С Ь С Е?, ф С 5 С Е'т и Ь П ,5 = ф, и все эти классы образуют решетку (по включению), состоящую из 2 ■ Зг~2 + 1 элемен-

1.2. Классы самодвойственных функций

Интерес, проявляемый к самодвойственным функциям из Рвызван, во-первых, тем обстоятельством, что класс Zk(s(x)), состоящий из всех функций, самодвойственных относительно подстановки s(x) ф. х (заданной на множестве Ек), предполон в Рк, если s(x) разлагается в произведение циклов одинаковой простой длины [95,100, 101] (и только в таких случаях). Кроме того, самодвойственные функции позволяют выделить некоторые классы универсальных алгебр со специальными группами автоморфизмов [68] и предоставляют дополнительные возможности при реализации &-значных функций формулами [111].

Докажем утверждение, дающее описание некоторых систем, полных в классе Zk(s(x)) при s(x) х.

Пусть разложение подстановки s(x) в произведение циклов имеет вид: «(г) — (ть ..., m2)(m3,..., т4)... [m^i-i, ■ ■ ■, m2i). Если функция g(xn) = д{х 1,..., хп) £ Zk(s(x)), п > 2, то она однозначно определяется своими значениями на множестве наборов

что вытекает из равенства з(д(хп)) = <7(5(1:1),.. . ,5(гп)), характеризующего свойство самодвойственности функции д(хп) относительно подстановки «(г). Функцию ¡/(шг,--1, х2,. ■ ■, хп) назовем г-й компонентой функции д(хп) по переменной . Если А — произвольная полная система в Рк, то можно построить суперпозицию Ф,-(х2,.. •,хп) над системой А такую, что ..., хп) = Фг-(х2, ■ ■ ■ ,хп). Ка-

ждую функцию /(х;1,..., Х]т), входящую в суперпозицию Ф,- (здесь {ж^,..., г7г) С {х2,..., жп}), заменим на самодвойственную относительно ¿(х) функцию . .., г;-г), У которой г-я компонента по переменной х\ совпадает с функцией /(х,-,,..Xjr). Получающаяся при этом суперпозиция будет реализовывать самодвойственную отно-

тов, имеющую ширину и высоту 2г — 2.

сительно в(х) функцию х2, ■ ■ ■, хп) такую, что

С,(гтг2!-1, а?2, - • г^п) = $г(х2, ■ ■■,хп) = хъ ■ ■ ., хп).

Следовательно, исходя из системы функций {Р/}, соответствующей (в описанном выше смысле) полной системе Л, можно построить самодвойственные относительно в(а;) функции С»(а; 1, х-2, • ■ ■, хп), г = 1,2,...,/, такие, что С<(т2г_\,х2, ...,хп) = 5(т2,_ 1, х2,. . .,£„)•

Рассмотрим теперь функцию Ф(х,1Д, ■ • ., У1) = Ух'ф1{х)+- ■ ■+У]'ф1{х), где функция ф](х) равна 1 на элементах ..., гп2], образующих

]-та цикл в указанном выше разложении подстановки ¿(ж), и равна О на остальных элементах множества Ек{] — 1,2,...,/); при этом сложение и умножение осуществляются здесь по модулю к. Функция Ф(г, ух,..., у]) самодвойственна относительно Легко видеть, что Ф(г1,С1(ж1,Х2).. .,хп),..., С;(а;1,Х2,.. .,®„)) = д{хих2, . ..,хп).

Итак, справедлива

Теорема 7. Система {Ф(я, уи . .., уг), ги^х, у, г),. .., ич(х,у,г)}, где Ь1{{х, у, г) — произвольная самодвойственная относительно в(х) функция, у которой 1-я компонента по переменной х совпадает с функцией Вебба ь(у,г) = тах(у,г) + 1 (см. [95, 98, 125]), полна в классе

ад*)).

2. Булевы функции

2.1. Рекуррентные формульные представления функций из классов ¡1 = 2,3,...

При обосновании того факта, что каждый замкнутый (относительно операции суперпозиции) класс булевых функций имеет конечный базис (иными словами, конечно порождаем), наибольшие трудности возникают при рассмотрении классов, принадлежащих бесконечным цепочкам диаграммы включений Э. Поста [19, 20, 99, 110]. Нетрудно доказать (см. [19, 20]), что конечная порождаемость произвольного класса, содержащегося в такой цепочке, вытекает из конечной порождаемое™ подходящего класса монотонных функций, лежащего в некоторой из этих цепочек, причем достаточно ограничиться монотонными а функциями, т.е. монотонными функциями, отличными от констант 0 и 1. Соответствующих цепочек две — одна состоит из классов а другая — из классов где ^ = 2,3,....

Напомним, что в класс входят все монотонные булевы «-функции, удовлетворяющие условию (а(последнее означает, что у любых ц наборов, на которых функция обращается в нуль, найдется общая нулевая компонента). Класс является двойственным классу условие, которому удовлетворяют функции из класса РД обозначается через (А11).

Мы приведем формулы для функций из классов > 2), ко-

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

Пусть /(£") — монотонная булева а — функция (п > 3). Она называется одпозубчатой, если с точностью до переименования переменных удовлетворяет следующим условиям: (а) /(£") = 1 при хп > ап = (!», (К, 1!), где 2 > 2, ; + * > 3, Ч + ; + X = щ (б) /(£») =■ 1 при х" = О, I'"'"1), где г > 0; (в) /(х") = 0 в остальных случа-

ях. (Здесь «зубец» задастся набором ап.) Аналогично определяется р-зубчатая функция для р > 2. У р-зубчатой функции ровно р нижних единиц «1,..., &р («зубцов»), каждая из которых имеет не менее двух нулевых компонент, т.е. в качестве «зубцов» берутся только нижние единицы, не принадлежащие одпопулевому слою п-мсриого булева куба.

Одяозубчатую функцию /(хп) описанного нами вида обозначим

Утверждение 6 .Н^п)(х) = ц... ... хд+]-, хч+уН,. ..,хп),

<+1

где Му*+1) = V г/1 •• Уг-1г/»+1 -• -г/(+1-¿=1

Пусть р > 2 и /(£") = — такая р-зубчатая функция, которая ровно на q однонулевых наборах (по переменным хх, ..хд) обращается в 0 и у которой нижние единицы &1,..., йр имеют в точности г общих единичных компонент, отличных от компонент с номерами 1.....д. Будем считать, что номера этих { компонент суть 5 + 1,...,5 +г. Через Н^1 ^ - будем

обозначать фупкцшо, получающуюся из функции ^ от-

брасыванием сомножителя х\ ...хд, стоящего перед соответствующей функцией

Индукцией по числу р > 2 доказывается

Утверждение 7. Описанная выше р-зубчатая функция f(xn) пред-ставима в виде:

XI ■... - Г(,Л,Чр_1 (г4+ь • • . .. ,г„) ,

Применяя утверждение 7, можно следующим образом обосновать конечную порождаемость замкнутых классов (ц > 2). Сначала устанавливаем, что если т > 3, то функция кт(хт+1) порождает произвольную функцию Л4(г*+1) при £ > то + 1. Для этого можно использовать, например, соотношение

Ьт+1(хт+1, у1) = Лт (/гт+;_1(г2, • ■ ■,хт+1, у') , Ьт+1-1(х1,х3,.. ,,хгп+1,у1),..., Ат+/_1(а?1,.. .,хт, у')) ,

где т > 3 и / > 1, истинность которого проверяется непосредственно.

Далее устанавливается справедливость следующих двух утверждений.

Теорема 8. Если /(£" ), п > 2,— монотонная а-функция с / нижними единицами, равная 1 на однонулевых наборах, то найдется ¡о такое, что 2 ^ ¡о

^ I И /(5") е [[/(£") и {х{у V г)>]С<'0+1)], оде квадратные скобки означают замыкание множества, а выражение /ц + 1) указывает на то, что в соответствующем множестве берутся все функции, зависящие не более чем от /о + 1 переменных.

Теорема 9. Любая монотонная булева а-функция /(£"), п > 4, принимающая на всяком однонулевом наборе значение 1 и не порождающая с помощью функции х(у V г) ни одну из функций х V у и ху\хгЧуг, порождает некоторую функцию /г;(х'+1), / > 3, и при этом

Дгп)е[/и].

После этого обоснование конечной порождаемости каждого класса при ц> 3 особых трудностей не вызывает.

2.2. О сохранении неитеративных свойств при отождествлении переменных

Операция отождествления переменных в функциях естественным образом возникает в разнообразных задачах дискретной математики и теории управляющих систем; в частности — при исследовании

простых базисов в Рк(к > 2), при обобщении инвариантных классов С. В. Яблонского, при формульных реализациях булевых функций и построении полных систем в замкнутых классах Поста [19, 20, 99], в задачах проверки и диагностики дискретных устройств при учете функциональных неисправностей.

Для характеризации возможностей операции отождествления переменных на множестве булевых функций полезно выяснить, при каких условиях осуществление этой операции не нарушает те или иные неитеративные свойства (типа нелинейности, немонотонности и т.п.) преобразуемых функций.

Пусть Ь, М и 5 — соответственно классы линейных, монотонных и самодвойственных булевых функций, а Ф — множество всех булевых функций, в каждой из которых есть хотя бы одна фиктивная переменная.

Пусть /(хп) ^ Ф и Ь и М и 5, т.е. существенно зависит от всех п переменных и не является ни линейной, ни монотонной и ни самодвойственной. Существуют ли переменные хг- и х1 (1 г < ] ^ п) такие, что, отождествляя их в функции /(£"), получаем функцию £Фи£иМи5(сп — 1 существенными переменными)? Установлена следующая

Теорема 10. Если п = 4 или п > б и /(£") £ Ф и Ь и М и Б, то найдутся переменные х,- и х, такие, что /\Х{=Х; ^ Ф и X и М и 5.

В то же время доказано

Утверждение. При л = 5 имеется ровно 1790 «исключительных» функций, т.е. зависящих существенно от пяти переменных, не являющихся ни линейными, пи монотонными и ни самодвойственными и таких, что при любом отождествлении в них двух переменных получаются функции, принадлежащие множеству Ф и Ь и М и 5.

Все эти «исключительные» функции являются а-функциями. Если зафиксировать пару наборов значений переменных, обеспечивающую несамодвойственность «исключительной» функции, то число различных «исключительных» функций будет равно 92 (для них построена общая формула). Примерами «исключительных» функций являются Д(х5) = x1x2va:зx4v(x1г;зvx2x4)x5 и /г(55) = х^х2Ухах^х5Ух2{хАхьУ х4х5) V Х1Х3Г4Х5.

3. Счетнозначные логики 3.1. Предельные логики

Понятие предельной логики было определено С. В. Яблонским [96]. Их введение связано с тем обстоятельством, что во многих приложениях приходится рассматривать не всю счетнозначную логику Ри, содержащую, как известно, континуум функций, а только такие ее подмножества, которые являются обобщениями ¿-значных логик Р^ и в тоже время состоят из счетного множества функций. В работе [96] С. В. Яблонский установил, что максимальная мощность множеств попарно неизоморфных предельных логик равна мощности континуума. Нами было доказано [14], чго континуальной является и максимальная мощность множеств попарно неизоморфных предельных логик, обладающих конечным базисом.

Оба эти результата приводят к выводу о невозможности избавиться от континуальности при обобщении ¿-значных логик путем рассмотрения предельных логик без введения существенных ограничений на их структуру, что подтвердилось и дальнейшими исследованиями [35, 36, 56]. Ряд интересных свойств счетных замкнутых классов в Ры представлен в работе [97].

Изложим сейчас результаты, установленные в статье [14].

Говорят, что множество функций Р = {/(ж")} гомоморфно отображается в множество функций С — {<7(2/")}, если

1) существует взаимно однозначное соответствие между множествами переменных {я,-} и {ад},

2) каждой функции / £ Р однозначно отвечает функция } ё б, зависящая от соответствующих переменных,

3) всякой суперпозиции функций над Р, принадлежащей множеству Р, отвечает суперпозиция такого же строения над множеством <?, которая тоже принадлежит (7.

Если при этом отображении гомоморфизм имеет место и в обратную сторону, то множества Р и б называются изоморфными (обоз-иаченис:/' ~ О). Если {/0} есть базис замкнутого класса Р н Р ~ С, то {<7с*} — базис замкнутого класса б = [{#»}], где да <—► /0.

Замкнутый класс А С Рш называется предельной логикой, если:

1) мощность А — счетная,

2) для всякого натурального числа к(к > 2) существует подмножество В* С А, которое гомоморфно отображается па множество всех функций ¿-значной логики .

Примером предельной логики является замыкание множества

{<р(х, у)}, где функция <р(х, у) описывается следующим образом.

00

Разобьем множество Еы — {0,1,2,...}: Еш = и ¿з> где =

1= о

00" + 1)/2,0'0' + 1)/2) + 1, ■ • - , (0" + 1)0' + 2)/2) - 1}. Рассмотрим

функцию у), г = 1,2,..., областью определения которой является множество Еъ х £{, а областью значений — множество £,■:

Г г(г + 1)/2, если г = ((г + 1)(г + 2)/2) - 1 или

П(х,у) = < у=((« + 1)(: + 2)/2)-1,

[ тах(ж, у) + 1 в ином случае. Используя функции ^¿(аг,г/), определяем функцию <р(х,у) 6

{^.•(е1,е2), если (г,у) - (еье2) £ х г'= 1,2,...,

О, если(г,^) = (е1,е2)£ 0(£х£)-

Построение континуального множества попарно неизоморфных предельных логик, обладающих конечным базисом, осуществляется в два этапа.

На первом этапе строится континуальное семейство {Я\} попарно неизоморфных множеств, каждое из которых порождается тремя функциями: Н\ = [уо(аг), д\(х), /г\(х)], где А £ А л А — множество последовательностей специального вида (его описание дано ниже).

Функции до(х) и ^(г) определяются с использованием разбиения множества Еш на подмножества М0 = {0,1, 3,.. ., 2г + 1,...} и М5 = {23,23 • 3,.. •, 28(2г + 1),...}, 5 = 1,2,...:

, . Г е, если х — е 6 Мл, д0(х) = ^

[ 0 в ином случае,

. . ГО, если х = е Е М0 и Мх, 91{х) = | у-и

г'-дгг-ы), если X = 25(2г-1• 1),в> 2 и г > 0.

Функции Ь\(х) определяются следующим образом. Берется множество Л — {А} всех целочисленных монотонных последовательностей

вида X = (/оЛ, • • ■ • •), где 0 = ¡о < ¡1 < ...</; < ... и /¡+1 — {,- > г, г = 0,1, 2,.. .. Эти последовательности называются быстро растущими. Для А £ А полагаем

Г 0, если г = е£ Мо,

м*) - {м<°>°) «= 1,2,3,...,

где через (а, 6) при 0 ^ а < Ь обозначается подстановка множества Еш вида (0, а + 2, а + 3,..., Ь+ 1)(1).. ,(а)(а + 1)(6 + 2)... и (а, о) = (0)(1)(2) ...; здесь запись £\ <—> £2 (£1 и £2 — бесконечные подмножества из Еи) толкуется так: £\ и £4 упорядочены по типу ы отношениями порядка -<1 и <2 соответственно и если — {ец \ е^,..., ¿п , ■ ■.}, вп>? -<| (г = 1,2; т = 0,1, 2,...), то отображается в с™ .

Доказательство попарной неизоморфности множеств Н\1 и Н\2, где Ль Аг 6 Л, опирается на ряд вспомогательных утверждений. Для их формулировки введем следующее обозначение: если N — подстановка множества Еы такая, что Ы(г) = щ, г = 0,1, 2,..., и £ - - бесконечное подмножество из Еы, причем £ = {ео, е\,..., ,...} и < е7-+1, _/' = 0,1, 2,..., то через £ * N будем обозначать множество £ с введенным на нем новым упорядочением: элемент с номером N(1 + 1) считается непосредственно следующим за элементом, имеющим номер N(;). В дальнейшем считаем, что запись д"(х), п > 1, означает д(д .. .д(х)...), где д берется п раз, и д°(х) — х.

Утверждение 8. Пусть /(г) = Ьд'+1(<?Г'(Ла' • • -дТЧКЧд?* (ЛдЧ2)))) ■ ■ ■))' гДе « > 1, ям > 1 и при « > 2 т,- > 1 и П; > 1 и = 2,..., б). Тогда

{«

О, если х — с € и М,-, М-0'0*1 <-С М,-+п.+1-р, *■№,

к

где р* = - «г), £ = 1,..., в; д = тах(0,Рь .. .,р,); г > д0;

Г = 1

^ = ('¡-лЛ'-Х+тМ'«-!-?!. '¡-1+п3-Р1) • ■ ■ С»"-1-р.|'»-1+п,+1-р.) (2)

(обычное произведение подстановок).

Справедливость этого утверждения устанавливается с использованием метода полной индукции по числу е.

Утверждение Э. Если суперпозиция f(x) функций до(х), ffi(x) и h\(x) содержит функцию дп(х), то либо

где so ф 0, si ф 0 и N — подстановка вида (2).

Следствие. Если суперпозиция f(x) функций g0(х), (ц(х) и h\(x) содержит функцию до(х), то /(х) ф дх{г) и /(ж) ф h\(x).

Утверждение 10. Пусть Л —быстро растущая последовательность и /(х) — суперпозиция функций fl^x) и Лд(х), вид которой описан в утверждении 8. Тогда /(х) ф Лд(х).

Следствие. Равенство f(x) = Лл(х), где Л € Л и f(x) — произвольная суперпозиция функций go(x), ffi(x) и h\(x), возможно тогда и только тогда, когда /(х) имеет вид h\(x).

Утверждение 11. Пусть А — быстро растущая последовательность и f(x) — суперпозиция функций дi(x) и Лд(х), вид которой описан в утверждении 8, причем если т1 = 1 и raj = nJ+1 = 0, то s > 1. Тогда /(х) ф ffi(x).

Следствие. Равенство f(x) — gi(x), где /(ж) — произвольная суперпозиция функций gо(х), gi(х) и h\(x), А € Л, возможно тогда и только тогда, когда Дх) имеет вид gj(x).

Утверждение 12. Равенство Дх) = ffo(x), где /(г) — суперпозиция функций 5о(х), <7i(x) и Ад(х), возможно тогда и только тогда, когда /(х) содержит функцию £?о(х).

Из приведенных утверждений вытекает

Теорема 11. Если А — быстро растущая последовательность и и Ы2) — функции из множества Н\ = [3o(x),5i(x), Лл(х)], образующие в нем полную систему, т.е. [£1(х),£2(ж),£з(х)] = ЯЛ) то 6,(х) = h\{p), &a(r) - 31(х) и &3(х) = /(г), где Дх) — суперпозиция, содержащая функцию <7о(х) (здесь индексы ii, г'г, г3 — разные).

Теорема 12. Если Ах и A-j — различные последовательности из множества Л, то HXi не изоморфно Н\2.

Благодаря специальному выбору множества Л, функции ЛдЛх) и h\2(x) при разных последовательностях Ai и А2 «существенно отли-

а) /(х) = О,

либо

б)

чаются друг от друга» на любом множестве Mi, начиная с некоторого М{а, зависящего от выбранных последовательностей Ai и А2.

Достичь «существенного отличия» удалось введением специального, характерного только для данной функции h\(x), упорядочения множества значений, которые эта функция принимает на множестве Mi, i > ¡о- Суперпозиция Л (г), содержащая вхождения функции /¡х, (ж), либо вырождается в тождественный нуль: fi(x) = 0, либо «еще более существенно» (чем h\l(x) от hx2{x)) отличается от суперпозиции /г(х), которая получается из Д(г) заменой каждого вхождения функции h\j(s) на функцию h\,J(x). Выявление указанного отличия функции /i(s) от /з(х) за конечное число итераций осуществляется с помощью функций до(х) и gi(x).

На втором этапе построенные множества Н\ расширяются до предельных логик А\. Ввиду того, что все функции из множества П\ на бесконечном подмножестве А/о множества Еы обращаются в нуль, для сохранения попарной неизоморфности при расширении множеств Н\ до предельных логик А\ поступаем следующим образом: присоединяем к Н\ такую функцию го(х,у), которая, во-первых, обращается в О вне множества (Мо\{0}) х (Мо\{0)), а во-вторых, порождает предельную логику. Функция, удовлетворяющая перечисленным условиям, строится из функции ip(x, у), рассмотренной в примере:

Здесь х—у означает обычную усеченную разность.

"Утверждение 13. Если Л £ А, то Н\ П [и)(г, у)] = (з(г)|р(г) = 0}.

Утверждение 14. Любая суперпозиция функций из А\ = [д0(а;), дх(г), /1х(ж), т(х, у)], где Л £ А, содержащая одновременно функции из Яд и у)], равна тождественно 0.

Следствие. Справедливо равенство Н\ и [ш(ж, у)] — где Л 6 Л.

Теорема 13. Если Л} и — Две разные последовательности из Л, то множества А\1 и Лд, не изоморфны.

Принимая во внимание континуальную мощность множества Л, получаем следующую теорему.

Теорема 14. Максимальная мощность множеств попарно не изоморфных предельных логик, обладающих конечным базисом, равна континууму.

3.2. Гиперконтинуалыюе семейство предиолных классов в не содержащих обобщенных констант

В счетнозначной логике Ры мощность множества всех предполных классов равна мощности гиперконтинуума [11, 12]. При доказательстве этого факта в работе [11] рассматривались такие предполные классы, которые целиком содержат множество Со всех константных функций из Ры. В то же время, если предполный класс в Рш имеет с множеством Со непустое пересечение С'0 / Со, то он есть просто класс сохранения подмпожсства С'0 (см. [9]). Значит, множество всех предполных классов, содержащих только собственные подмножества множества Со, имеет континуальную мощность. Континуальные семейства предполных классов, не содержащих константных функций из Рш, можно построить разнообразными способами [84], причем не используя аксиому выбора.

Мы приведем здесь обоснование того факта, что в Рш мощность множества всех предполных классов, не содержащих константных функций, гиперконтинуальна [18]. На самом деле доказано больше: гиперконтипуальпа мощность множества всех предполных классов, не содержащих множество Сы всех обобщенных констант, т.е. таких одноместных функций из Ры, каждая из которых принимает только конечное число разных значений.

Разобьем множество Еш на бесконечное число бесконечных подмножеств: Еи = U 8Р, где £р = ..., е.[р\...}, £Pl Г\£Р2 - ф Р=о

при pi ф í>2- Затем каждое из множеств £р разобьем следующим образом: £р = {е^} U Q ^ £Р = {<%), ..., е^ ...}.

г=0

Обозначим через Л множество всех бесконечных последовательностей целых неотрицательных чисел. Пусть А = {?о,'ъ • ■ •, 4, • • •} 6 Л. Введем в рассмотрение функцию и(х,у, А), определяемую с помощью функций v>o(®o) = хо, <Pi{xo,Xi) = (®о + ®i)(zo + + 1)/2 + xi,.. .,<pn{xo,xi,.. .,xn-i,x„) = <Pi(<Pn-i(xo,xi,... ,r„_i), х„),...:

если х = i и у = j (i = 0,1,2, ...;;' = 0,1,2,...).

Пользуясь ею, определим функцию д\(х), А £ Л:

ífc(*) = ew<Lx)> если ж = 4?) (Р= 0,1,2,...; ,= 0,1,2,...).

Функция д\(х) — разнозначная и если Ах и А2 — две различные последовательности из Л, то зхДх) Ф ?л2(х).

Пусть Л' — произвольное непустое собственное подмножество из Л. Положим

где Яд' = Сш и(Лд\Л.л<), — множество всех одноместных функций из Рш и

у) = 9(х) ■ - т/1 + х ■ вдЩх) - у\.

Определим еще функцию /<,(х,у). Для этого возьмем некоторую функцию до(х) Е взаимно однозначно отображающую Еш на £0, и функцию 7г(®, у) = 1рх(х, у),

описанную выше. Положим

у0(ж „) _ / 9о(т(х, у)), если (х, у) Е £о х £0, ' \ тах(х, у), если (г, у) £ £0 х £0.

Утверждение 15. Если Л' — произвольное собственное подмножество из Л и Л(х) £Сши (Аа\Ал.), то [ВА, и {/¡(г))] Э

Следствие. Если СА. = ЛЛ- и ВА- и {/0(х, у)}, то [Сл< и {Л(х)}] = Рш при любой функции Цх) Е Си и (-АЛ\АЛ')-

Утверждение 16. Если Л' — произвольное подмножество из Л, то [4/]п4 = 4'-

Индукцией по порядку (рангу) суперпозиции над множеством СА< обосновывается

Теорема 15. Если Дх) е [Сл.1], где Л' — собственное подмножество из Л, то найдется число р0, зависящее от функции /(х), такое, что на множестве и £р функция /(х) либо совпадает с тождествен-

р>ро

ной функцией х, либо совпадает с некоторой суперпозицией функций из множества Лл'.

Следствие. Если Л' — произвольное собственное подмножество из Л, то [СА<] П Ал = Аа, ф Аа.

Принимая во внимание лемму 1 из работы [12], следствие из утверждения 15 и следствие из теоремы 15, заключаем, что замкнутый класс [Сд'] расширяется до некоторого предполного класса КА>, не

содержащего ни одну функцию из подмножества Сш и (/1д\/1Л')> причем К а1 П Лд = АЛ1. Отсюда следует, что при разных собственных подмножествах Л1 и Л2 из Л классы Л'д, и К\2 различны.

Остается учесть тот факт, что множество всех собственных подмножеств множества Л гиперконтинуалыю.

Теорема 16. В Рш мощность множества всех предполных классов, не содержащих множество Сы всех обобщенных констант, равна мощности гиперконтинуума.

3.3. Классы конечной высоты в Рш

Дадим необходимые определения. Через Рт обозначается совокупность всех конечноместных функций, определенных на множестве Ет мощности тп > 2 и принимающих значение из этого же множества. Считаем, что Рт — класс высоты 0. Пусть А — произвольный замкнутый класс из Рт. Будем называть его классом высоты I (I — целое положительное число), если

1) какова бы ни была функция / 6 РпДЛ, класс [А и {/}] имеет высоту п < I — 1,

2) существует такая функция /0 (Е Рт\А, что высота класса [Ли {/}] равна I — 1.

Через обозначается множество бссх классов высоты I в множестве Рт.

Метод доказательства гиперконтинуальности множества Квсех предполных классов в Рш, предложенный в [11], см. также [12], базировался па идеях, почерпнутых из работ Б. Неймана и А. Г. Куроша, посвященных исследованию бесконечных групп. Этот метод, как оказалось, можно использовать при изучении совокупностей замкнутых классов в теории детерминированных и ограниченно детерминированных функций (см. стр. 145 в [45]) и в теории рекурсивных функций [85]. Однако он существенно опирается на аксиому выбора, а достаточно обозримого «конструктивного» доказательства теоремы о ги-перконтинуальносги множества К^ пока не найдено (см. [76]). В то

тЛ')

же время гиперконтинуальные семейства, входящие в множества при / > 2, удалось построить непосредственно — как семейства классов сохранения подходящих подмножеств одноместных функций. Заметим, что каждый из классов высоты / > 2, входящий в построенное

гиперконтинуальное семейство, является предполным в одном и том же классе высоты / — 1.

Приведем описание соответствующих гиперконтинуальных семейств.

Через Л* обозначим множество всех последовательностей Л = (Мь Целых неотрицательных чисел, удовлетворяющих ус-

ловию: любое число из Еш встречается в А не более чем на конечном числе мест. Очевидно, что мощность множества А* континуальна. Последовательности А1 = (110,1ц, ■ ■ ■ ,1и, ■ ■ •) и Аг = ('20,'21, • • ■ ,1ц, ■ - -) из Л* называются квазисовпадающими, если существует г'о такое, что ¡и = Ь; при г > ¿о. Отношение квазисовпадения является отношением эквивалентности и разбивает множество Л* на классы Л* квазисовпа-дающих последовательностей, где /1бМиМ — множество индексов континуальной мощности. Подмножество А„ из Л* обладает факторным свойством, если Л„ = у Л*,гдеМ'—произвольное непустое

нем1

подмножество из М. Мощность множества всех подмножеств из А*, обладающих факторным свойством, гиперкоптипуальпа.

Разобьем множество Еи на бесконечное число бесконечных подмножеств: Еы — У £5, £,1Г\£,2 — ф при ф £, = е^,.. .,

5 = 0

ёг\ ...}. Обозначим это разбиение через О.

Определим функцию е(х,у, А), где А = ■ ••>'»,••■)£

' ], еслих — г, у = у и1( = О, ( + еслиI = г, у = /,• ф йи3 ф т ■ 21, — 1 (т > 1),

£{х,у,л) — ^ (т _ 1). 2'-, еслиг -- г, у = 3, и ф Ои . ; = т ■ 2й - 1 (т > 1).

Исходя из функции е(х, у, А), введем в рассмотрение функцию Д(ж): /*(*) = 4(1,г,А)> если х ~ е["\

Функция /а(х) — разнозначная, и если А; и Аг — различные последовательности из А*, то /аДх) ф /а2(х).

Рассмотрим далее некоторые замкнутые классы из Рш, состоящие из нульместных и одноместных функций.

Класс <Эт состоит из всех одноместных функций, которые выпускают не более конечного числа значений из Еы и имеют не более чем конечное дополнение к объединению всех единичных множеств уровней.

Класс Qs содержит только все константы и все одноместные функции, выпускающие бесконечно много значений из Еи.

Пусть ffi(r) и — функции из Q7. Они называются подоб-

ными относительно разбиения D (обозначение: gi(х) ^ д2(2)), если существует такое s0 > 0, что gi(x) = д2{х) на множестве (J £,.

3>3 о

Возьмем подмножество Л„ из Л*, обладающее факторным свойством, и определим следующие два подмножества из Qr.

Множество Q(D,AU) (или, короче, Q(A„)) состоит из всех таких функций д(х) £ Q7, что существует f\(x), подобная д(х), т.е. f\(x) ^

Множество Q*(D,A„) (или, короче, Q*(A„)) состоит из всех таких функций д(х) £ Qi, которые удовлетворяют условию: каковы бы ни были функции fi(x),..., /р(х) (р > 0), принадлежащие множеству Q(A„), найдутся функции Я(х),..., #(х), f{'(x),..., f'{x) (t > 0, q > 1), также принадлежащие множеству Q(A„), такие, что

5 (Л (-../р(Я(-•■/«*) •••))■ ■ ■))"£'(• ••№•••)■

Положим Q(Л„) = QsliQ*(Av). Справедливы соотношения: Q*(А„) Э Q(A„) и {f{x) = х}, [Q*(A„)] П Р™ = Q*(A»), [<3(Л„)] П - Q(Л„) и Q7\Q(A*) Ф ф.

Затем устанавливаются следующие утверждения.

Утверждение 17. Если ji(x) - д2(х), д\(fi(x)) - ^(ЛС®)) и Л (я), /2ОО € Qr, то Л (г) - /2(х).

Утверждение 18. Функции /(х) = Д(.../р(х) ...) и /'(х) = /[(... f'q(x)...), где fi и f'j принадлежат Q(А*), подобны тогда и только тогда, когда р = q и /,• ~ // при каждом г = 1,..., р.

Следствие. Если /(¡с) £ Q(A*)\Q(A„), то Дх) 0 Q*(A„).

Теорема 17. Если Л„, ф AVi, то <5(AVl) ф Q(А„2).

Через Яд1^ обозначим множество всех функций из Ри, зависящих либо от нулевого числа переменных (нульместньте константы), либо от фиксированной переменной «1.

Пусть Я(А„) = Q(A„) П Hq^ и p(H(Av)) — класс функций из Pw, сохраняющих множество функций Я(Av), т.е. f(x 1,..., х„) £ р(Я(А„)) тогда и только тогда, когда при любых gi,...,yn из Я(Л„) имеем:

Утверждение 19. Класс р(Я(Л„)) содержит квазипеановскую функцию (х + у)(х + у + 1) + 2у.

Теорема 18. р(Я(Л„)) П = Q(A„) С Qv U Q8. Теорема 19. Если ^ Л„2, то p(É(AVl)) ^ р(Я(Л„а)). Утверждение 20. Множество Q(AV) U где д(х) G

PÎl)\(Q7 U Qs), образует полную систему в Ри>

Через Яз обозначается множество (Qy U Qs) П H^. Утверждение 21. Если д(х) е Ç>7\Q(Л1,),то [р(Я(Лу))и{5|(ж)}] = р(Яз), где р(Яз) — класс сохранения множества Яз. Из утверждений 19-21 вытекает Теорема 20. Класс р(Я(Л„)) предполон в р(Я3). Затем устанавливаются следующие две теоремы. Теорема 21. Высота класса р(//(Л1,)) равна 2. Теорема 22. Множество (р(Я(Л„))}, где Л„ пробегает все подмножества множества Л*, обладающие факторным свойством, гиперкон-тинуально.

Тем самым гиперконтинуальное семейство классов высоты 2 построено и все классы из этого семейства содержатся в предполном классе р(Яз).

Далее для каждого I > 3 строится гиперконтинуальное семейство классов высоты I.

I

Берется следующее разбиение множества Еш: Ew = (J Е{, где

1=0

/ > 0 и Ei, ■.., Ei — конечные подмножества. Определяется замкнутый класс G(Ei,..., Ei): если / = 0, то G{E\,..., F,\) = Ри \ а если 1 > 1, то класс G(E 1,..., Ei) состоит из всех функций, зависящих от нулевого числа переменных и совпадающих с элементами подмножества Е\, а также из всех таких одноместных функций, которые удовле-

i

творяют условию: g{Ei) С (J Ej (i — 1,...,/)• Через H(Ei,... ,Ej)

j=i

обозначается пересечение G(Ei, ...,£;) П Рассматриваются

следующие классы сохранения множеств функций: Т(Е\,..., Ei) = р(Н(ЕгЕг)), р{Н3 П Н{ЕХ ,...,£,)) и р(Я( А„) П ЩЕЬ ..., Е,)), и устанавливается ряд свойств этих классов.

Утверждение 22. Функция f(xn) (п > 1) принадлежит классу

та

T(Ei,..., Ei) тогда и только тогда, когда /(Е{ 1 ,...,£,■„) Ç (J Ej, где

;=1

1 < iq < I, g = 1,.. ■ ,п, и m = max(ii,..., in).

Утверждение 23. Для всякого I > 0 справедливо строгое включение: T(Ei, ...,Е,)Э T(EU Ew).

Утверждение 24. Справедливы следующие равенства: р(Я3)пТ(£ь ...,Е,)= р(ЩПН(Е1,..., Е,)),р(Н{А.г))ПТ{Еи ...,£,) = р(Н(А,)Г\ Н(Е1,...,Е1)), р(Я3 Л//(£?!,...,^ПЯ^ = (Зт и <Э8) Л ..., Е,), Р(Я(Л„) П Я(Р,,..., Р,)) П РЬ1) = (5(А„) П С(РХ, ..., £,)•

Индукцией по / доказывается

Теорема 23. Классы Т(Еи ..., Р,), р(Я3 П Я(РЬ ..., Р,)) и р(Й(А„) Л Н(Е\,..., Р;)) имеют высоту /, ! + 1 и / + 2 соответственно.

Затем устанавливается

Теорема 24. Если <Э(Л„,) Л С(РЬ.. ., Е,) ф д(А„а) П в(Е[,..., Е!я), то р(Й(А^) П Я(Рь ..., £,,)) ^ р(Я(Л„а) П Н(Е[,..., Е},)).

После этого легко обосновывается

Теорема 25. Для любого / > 0 существует класс высоты I + 1, содержащий гиперконтинуальное семейство классов высоты 1 + 2.

Она вытекает из теоремы 23 и того факта, что мощность множества всех подмножеств Л„, обладающих факторным свойством, гипер-континуальна.

Класс высоты I + 1 это класс р(Пз П Н{Е\,..., Е{)), а классами высоты I + 2, содержащимися в нем, являются классы р{П(Ау) Г) Н(Е\,..., £()): гДе А" — произвольное подмножество из А*, обладающее факторным свойством.

3.4. Классы типа Слупецкого в Рш

В многозначной логике Рк(к > 3) видное место занимает следующий критерий полноты, называемый критерием Слупецкого [95, 98, 100, 101, 123]: система функций из Р¡¡, содержащая множество С,к = всех функций, зависящих не более чем от одной переменной, полна в Рк тогда и только тогда, когда она содержит функцию, зависящую существенно не менее чем от двух переменных и принимающую все к значений из Ек (так называемую существенную функцию). Теорему, принадлежащую Е. Слупецкому [123], составляет достаточность этого критерия, а необходимость следует из того, что в Рк при к > 2 существует только один предполный класс, содержащий множество Ск, причем при к > 3 этот предполный класс состоит из всех несущественных функций [95].

При обобщении этого критерия на счетнозначную логику [9, 10,12] выяснилось, что в Ри существует ровно два предполных класса типа Слупецкого, т.е. содержащих множество С? = Р^ и Р^. Используя эти два класса, удалось доказать [12], что функция / £ Ры образует

с множеством G полную систему в Рш (или, говоря иначе, является квазипеановской) тогда и только тогда, когда / не принадлежит ни одному из этих классов. Кроме того, в [12] было установлено, что если f(xn) — квазипеановская функция, то любую функцию д(хп) 6 Рш можно представить в виде суперпозиции не выше второго порядка (ранга) относительно /, используя при этом, быть может, еще только функции, зависящие от одной переменной, т.е. в виде:

9{¿n) = Vo \f(<Pi[f(4>u(*i). • • ■ > lM*„))], • ■ •,

Заметим, что аналогичные вопросы рассматривались и для непрерывных функций: А. Н. Колмогоров [43] показал, что любую функцию, непрерывную на единичном евклидовом n-мерном кубе, можно представить в виде:

2п+1 г п

д(хп) - ^ (рт Ефт1(г,) ,

m=i L/=i

где Ifim <= С[0,1] и Фт1 е С[0,1], / = 1,..., п и т = 1,.. .,2га + 1, т.е. в виде конкретной суперпозиции непрерывных функций одного аргумента и сложения (в конструкции А. Н. Колмогорова функции Vw даже не зависят от функции </(£")).

При перенесении теоремы о классах типа Слупецкого со счетно-значной логики Рш на частичную счетнозначную логику Рш В. А. Соколовым [83] было установлено, что в Рш существует не менее двух классов типа Слупецкого. В работе [17] мы доказали, что в Рш таких классов ровно 3. Ниже приводятся соответствующие утверждения, связанные с обоснованием этого факта.

Заметим, что вопросы, относящиеся к квазипеановости функций и классам типа Слупецкого для случая рекурсивных функций рассматривались, например, в [65, 85].

Частичной счетнозначной логикой Ри называется множество всех частичных функций таких, что переменные в них принимают значения из Еш — {0,1,..., ш,...} и если функция /(£") определена на наборе й" значений переменных, то /(а") £ Еш. Подмножество G множества Рш состоит из всех функций, зависящих не более чем от одной переменной.

Пусть М\ и М-2 — подмножества из Рш, удовлетворяющие условиям:

1) любая функция из М\ U М2 зависит либо от нулевого числа переменных, либо от переменных, принадлежащих некоторому подмножеству переменных {hi,«2i • ■ •};

2) если f(ukl,.. .,щр) е М2, то /(umi,..., итр) £ М2, где переменные tijtj,..., икр — различные, а переменные umi,..., unip не обязательно различны.

Говорят, что функция <p(xi,... ,х„) € Pw сохраняет множество М2 па множестве Mi, если f(f\, ■ ■ ■,fn) G М2 при любых функциях /ь ■ • •, /п из Mi. При этом, если функция ip нульместная, то, по определению, она сохраняет множество М2 тогда и только тогда, когда ip G М2. Если функция <р(хп) не удовлетворяет сформулированному условию, то говорят, что она не сохраняет множество М2 на множестве Mi. В случае равенства множеств Mi и М2 говорят просто, что функция сохраняет (не сохраняет) множество Mi.

Множество всех функций из Рш, сохраняющих М, называется классом сохранения множества М и обозначается через р(М).

Через Й обозначим подмножество из Рш, состоящее из всех функций, зависящих либо от нулевого числа переменных, либо от переменных из множества {ui, «г}. Но — подмножество всех одноместных функций из Н.

Положим IIq — II C\G. Пусть Cw — множество всех функций из G, область значений которых либо пуста, либо конечна.

Функция f(x, у) 6 Рш называется функцией 1-го рода, если либо /(/, у) € Сы при любом I, либо /(ж, т) 6 Сы при всяком т (/ и т принадлежат Еш).

Множество всех функций 1-го рода обозначим через Ri и положим Fi = Ri П Я и Ti = Н'0 U Fi-

Утверждение 25. Если функция f(xn), п > 2, не сохраняет множество Ti, то она не сохраняет его и на множестве IIq.

Рассмотрим множество р('1\) — класс сохранения множества Ti. Оно является замкнутым классом, отличным от Pw, и GU R\ С р(Т\).

Теорема 26. Класс p(Ti) является предполным в Рш.

Говорят,что функция /(г, у) £ Рш обладает квазипеановским углом по переменной х (по перемеппой у), если существуют такие функции 9i(x) и д2(х) из G, что f(gi(x+y),g2(y)) (соответственно f{gi{x), д2(х+ у))) является всюду определенной разнозначной функцией.

Функцией 2-го рода называется функция /(х,у) 6 Ри,, не обладающая квазипеановским углом ни по одной из переменных.

Множество всех функций 2-го рода обозначим через &2 и положим Ё2 = к2 П Я и т2 = й'0 и Ё2.

Утверждение 26. Если функция /(ж"), п > 2, не сохраняет множество Т2, то она не сохраняет его и на множестве До-

Возьмем множество р(Т2) — класс сохранения множества Т2. Оно является замкнутый классом, отличным от Ры, и С и Да С р{Т2).

Теорема 27. Класс р(Т2) является предполным в Ры.

Пусть f(x1 у) — всюду определенная функция из Рш. Введем обозначения:

= {е : е € ЕшкЗсЗй{с > ¿к}(с,й) = е)}, = {е : е £ Я„&ЗсЗ«*(с < «*&/(с, Л) = е)}.

Утверждение 27. Пусть /(х,у) — всюду определенная функция из Рш, удовлетворяющая условию: каковы бы ни были всюду определенные функции дх(ж) и д2{х) из (5, всегда где (р{х, у) = /(<71 (х), д2{у)). Тогда в О найдутся строго монотонные функции /н(х) и Ь2{х) такие, что функция f(hl(x),h2(y)) существенно зависит не более чем от одной неременной.

Функция /(х, у) £ Рш называется функцией 3-го рода, если, каковы бы ни были фупкции 31 (г) и д2(х) из множества <5, функция <р(х,у) = /(д1(х), д2(у)) либо не всюду определена, либо всюду определена и удовлетворяет соотношению А^1' П Л^ ф ф.

Множество всех функций 3-го рода обозначим через Яз и положим

= ДзП//иГз = Я4иРз-

С использованием утверждения 27 доказывается

Утверждение 28. Если функция /(¿п), п > 2, не сохраняет множество Тз, то она не сохраняет его и на множестве Но.

Рассмотрим множество р(Тз) — класс сохранения множества Т3. Оно является замкнутым классом, отличным от Рш, и СиЁ3 С р(Т3).

Теорема 28. Класс р(Тз) является предполным в Ры.

Теорема 29. В Ры существуют только три предполных класса, содержащих множество б, а именно классы р(Т;), г = 1,2,3.

Следствие. Система (5и{/} полна в Рш тогда и только тогда, когда

/ £р№.)ир(т2)ир(т3).

Список литературы

1. Автоматы, сб. статей под ред. К. Э. Шеннона и Дж. Маккарти. М.: ИЛ, 1956.

2. Айзенберг H. H , Семйон И. В. Некоторые критерии представимости функций fc-значной логики полиномами по модулю к // В кн.: Многоустойчивые элементы и их применение, Москва, Сов. радио, 1971, с. 84-88.

3. Айзенберг H. Н., Семйон И. В.,Циткин А. И. Полиномиальные представления логических функций / / Автоматика и вычислительная техника, 1971, № 2, с.6-13.

4. Березин С. А. Об алгебрах одноместных примитивно рекурсивных функций с операцией итерации общего вида // Кибернетика, Киев, 1976, № 3, с. 12-18.

5. Березин С. А. О максимальных подалгебрах алгебр рекурсивных функций // Кибернетика, Киев, 1978, № 6, с. 123-125.

6. Боднарчук В. Г., Калужнин JI. А., Котов В. II., Ромов Б. А. Теория Галуа для алгебр Поста // Кибернетика, Киев, 1969, № 3, с. 1-10; № 5, с. 1-9.

7. Буевич В. А. Условия А-полноты для конечных автоматов. М.: Изд-во Моск. гос. ун-та, ч. 1, 1986; ч. 2, 1987.

8. Бурле Г. А. Классы fc-значных логик, содержащие все функции одной переменной // Дискретный анализ, Новосибирск, 1967, вып. 10, с. 3-7.

9. Гаврилов Г. П. О некоторых условиях полноты в счетнознач-ной логике // Доклады АН СССР, 1959, 128, № 1, с. 21-24.

10. Гаврилов Г. П. О квазипеановости функций // Доклады АН СССР, 1964, 156, № 5, с. 1011-1013.

11. Гаврилов Г. П. О мощности множеств замкнутых классов конечной высоты в Р$0 // Доклады АН СССР, 1964, 158, № 3, с. 503-506.

12. Гаврилов Г. П. О функциональной полноте в счетнозначной логике // Проблемы кибернетики, М.: Наука, 1965, вып. 15, с. 5-64.

13. Гаврилов Г. П. О замкнутых классах конечной высоты в счег-нозначной логике // Тезисы кратких научных сообщений Международного конгресса математиков. Секция 13, М., 1966, с. 16.

14. Гаврилов Г. П. О мощности множества предельных логик, обладающих конечным базисом // Проблемы кибернетики, М.: Наука, 1969, вып. 21, с. 115-126.

15. Гаврилов Г. П. Мощность множества классов конечной высоты в счетнозначной логике // Проблемы кибернетики, М.: Наука, 1974, вып. 29, с. 5-26.

16. Гаврилов Г. П. Классы Слупецкого в частичной счетнозначной логике // Третья Всесоюзная конференция по математической логике, 23-27 июня 1974. Тезисы докладов, Институт математики СО АН СССР, Новосибирск, 1974, с. 38.

17. Гаврилов Г. П. Предполные классы частичной счетнозначной логики, содержащие все функции одной переменной // Методы дискретного анализа в теории графов и логических функций, Новосибирск, 1976, вып. 28, с. 12-24.

18. Гаврилов Г. П. Гиперконтинуальность множества замкнутых классов счетнозначной логики, не содержащих констант // Четвертая Всесоюзная конференция по математической логике. Тезисы докладов и сообщений, Кишинев, изд-во «Шти-ипца», 1976, с. 25.

19. Гаврилов Г. П. Индуктивные представления булевых функций и конечная порождаемость классов Поста // Алгебра и логика, Новосибирск, 1984, 23, № 1, с. 3-26.

20. Гаврилов Г. П. Функциональные системы дискретной математики. М.: Изд-во Моск. гос. ун-та, 1985.

21. Гаврилов Г. П. О сохранении неитеративных свойств булевых функций при отождествлении переменных // Вторая конференция по дискретной математике и ее приложениям, Благо-евград, 05-10 июня 1990 г. Тезисы докладов, с. 4-5.

22. Гаврилов Г. П. Сохранение некоторых неитеративных свойств при отождествлении переменных в булевых функциях // Го-дишиик Висши Педагогически институт, Природо-математи-

чески факультет, Математика, кн.2, Благоевград, 1990, с. 1926.

23. Гаврилов Г. П. Формульные реализации функций из бесконечных цепочек классов Поста // Методы и системы технической диагностики, Межвузовский сборник научных трудов, вып. 18, Изд-во Саратовского университета, 1993, с. 44-45.

24. Гаврилов Г. П. О решетке замкнутых классов в содержащих полиномы // Дискретный анализ и исследование операций, Новосибирск, Изд-во Института математики, 1995, 2, № 3, с. 73-74.

25. Гаврилов Г. П. О надструктуре класса полиномов в многозначных логиках // Дискретная математика, М.: Наука, 1996, 8, № 3, с. 90-97.

26. Гаврилов Г. П. О некоторых классах многозначной логики, содержащих полиномы // Проблемы теоретической кибернетики. Тезисы докладов XI Международной конференции, 1014 июня 1996 г., М., 1996, с. 37.

27. Гаврилов Г. П. О замкнутых классах многозначной логики, содержащих класс полиномов // Дискретная математика, М.: Наука, 1997, 9, № 2, с. 12-23.

28. Гаврилов Г. II., Русова О. С. О предполпых классах счетно-значной логики, не имеющих обобщенных констант // Проблемы теоретической кибернетики. Тезисы докладов XI Международной коференции, 10-14 июня 1996 г., М., 1996, с. 38.

29. Глушков В. М. Синтез цифровых автоматов. М.: Физматгиз, 1962.

30. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Языки. Программирование. Киев, «Накова думка», 1978.

31. Голунков Ю. В. Полнота системы микроопераций и сложность микропрограмм // Известия АН СССР. Техническая кибернетика, ч. 1, 1976, № 3, с. 117-123; ч. 2, 1976, № 4, с. 115122.

32. Голунков Ю. В. О полноте операций в системах алгоритмических алгебр // Алгоритмы и автоматы, Казань, Изд-во Казанского университета, 1978, с. 11-53.

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

34. Голунков Ю. В. Полнота по модулю идеала в функциональных системах программного типа // Дискретная математика, М.: Наука, 1990, 2, № 2, с. 112-120.

35. Деметрович Я. О мощностях множеств предполных классов в предельных логиках // Acta Cybernetica, Szeged, 1972, 1, №> 4, с. 233-239.

36. Деметрович Я. О некотрых гомоморфизмах и отношениях для предельных логик // Проблемы кибернетики, М.: Наука, 1975, вып. 30, с. 5-42.

37. Захаров Д. А. Рекурсивные функции. Новосибирск. Изд-во Новосибирского университета, 1970.

38. Захарова Е. Ю., Кудрявцев В. Б., Яблонский С. В. О предполных классах в ¿-значных логиках // Доклады АН СССР, 1969,186, № 3, с. 509-512.

39. Кобринский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. М.: Физматгиз, 1962.

40. Козьминых В. В. Об одноместных примитивно рекурсивных функциях // Алгебра и логика, Новосибирск, 1968, 7, № 1, с. 75-90.

41. Козьминых В. В. О подалгебрах алгебы Р. Робинсона // Алгебра и логика, Новосибирск, 1970, 9, № 6, с. 672-690.

42. Козьминых В. В. О представлении частично рекурсивных функций в виде суперпозиций // Алгебра и логика, Новосибирск, 1972,11, № 3, с. 270-294.

43. Колмогоров А. Н. О представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций одного переменного и сложения // Доклады АН СССР, 1957, 114, № 5, с. 953-956.

44. Кон П. Универсальная алгебра. М.: Мир, 1968.

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

46. Кузнецов А. В. О проблемах тождества и функциональной полноты для алгебраических систем // 'Груды Третьего Вес-союзного математического съезда, М.: Изд-во АН СССР, 1956, т.2, с. 145-146.

47. Кузнецов А. В. Структуры с замыканием и критерии функциональной полноты // Успехи математических наук, 1961, 16, № 2, с. 201-202.

48. Кузнецов А. В. О функциональной выразимости в суперинтуиционистских логиках // Матем. исследования, Кишинев, 1971, VI: 4(22), с. 75-122.

49. Кузнецов А. В., Раца М. Ф. Критерий функциональной полноты в классической логике предикатов первого порядка // Доклады АН СССР, 1979, 249, Л'» 3, с. 540-544.

50. Лисовик Л. П. Алгебры полулинейных преобразователей над размеченными деревьями // Вычислительные системы, 1988, вып. 124, с. 114-143.

51. Ло Чжу Кай Максимальные замкнутые классы в множестве частичных функций многозначной логики // Кибернетический сборник, М.: Мир, 1988, вып. 25, с. 131-141.

52. Ло Чжу Кай Теория полноты для частичных функций многозначной логики // Кибернетический сборник, М.: Мир, 1988, вып. 25, с. 142-161.

53. Лупанов О. Б. Об одном классе схем из функциональных элементов // Проблемы кибернетики, М.: Наука, 1962, вып. 7, с. 61-114.

54. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, М.: Наука, 1963, вып. 10, с. 63-98.

55. Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики, М.: Наука, 1965, вып. 14, с. 31-110.

56. Макаров А. В. О гомоморфизмах функциональных систем многозначных логик // Математические вопросы кибернетики, М.: Наука, 1992, вып. 4, с. 5-29.

57. Мальцев А. И. On the immersion of an algebraic ring into a field // Math. Ann., 1937, 113, p. 686-691.

58. Мальцев А. И. Конструктивные алгебры // Успехи матем. наук, 1961, 16, JV- 3, с. 3-60.

59. Мальцев А. И. Итеративные алгебры и многообразия Поста // Алгебра и логика, Новосибирск, 1966, 5, № 2, с. 10-25.

60. Мальцев А. И. Об одном усилении теорем Слуиецкого и Яблонского // Алгебра и логика, Новосибирс, 1967, 6, № 3, с. 61-74.

61. Мальцев А. И. Алгебраические системы. М.: Наука, 1970.

62. Мальцев А. И. Итеративные алгебры Поста. Новосибирск, 1976.

63. Мартынюк В. В. Исследование некоторых классов в многозначных логиках // Проблемы кибернетики, М.: Наука, 1960, вып. 3, с. 49-60.

64. Марченков С. С. Об одном методе построения максимальных подалгебр в алгебрах общерекурсивных функций // Алгебра и логика, Новосибирс, 1978, 17, № 5, с. 581-595.

65. Марченков С. С. О квазипеановости рекурсивных функций // Проблемы кибернетики, М.: Наука, 1979, вып. 35, с. 199-204.

66. Марченков С. С. О замкнутых классах самодвойственных функций многозначной логики // Проблемы кибернетики, М.: Наука, 1979, вып. 36, с. 5-22.

67. Марченков С. С. О мощности множества предполных классов в некоторых классах функций счетнозначной логики // Проблемы кибернетики, М.: Паука, 1981, вып. 38, с. 109-116.

68. Марченков С. С. Однородные алгебры // Проблемы кибернетики, М.: Наука, 1.982, вып. 39, с. 85-106.

69. Марченков С. С., Деметрович Я., Ханнак Я. О замкнутых классах самодвойственных функций в Р3 // Методы дискретного анализа в решении комбинаторных задач, Новосибирск, 1980, вып. 34, с. 38-73.

70. Математика в СССР за сорок лет, 1917 -1957. М.: Физматгиз, 1959, т.1, с. 13-120.

71. Мещанинов Д. Г. О некоторых свойствах надструктуры класса полиномов в Рк // Математические заметки, 1988, 44, № 5, с. 673-681.

72. Мещанинов Д. Г. Метод построения полиномов для функций ¿-значной логики // Дискретная математика, М.: Наука, 1995, 7, № 3, с. 48-60.

73. Минский М. Вычисления и автоматы. М.: Мир, 1971.

74. Нечаев А.. А. Критерий полноты систем функций р"-значной логики, содержащих операции сложения и умножения по модулю рп // Методы дискретного анализа в решении комбинаторных задач, Новосибирск, 1980, вып. 34, с. 74-89.

75. Новиков П. С. Конструктивная логика с точки зрения классической. М.: Наука, 1977.

76. Перфильева И. Г. Построение гиперконтинуального семейства предполных классов счетнозначной логики // Проблемы кибернетики, М.: Наука, 1979, вып. 35, с. 29-44.

77. Поляков Е. А. Алгебры рекурсивных функций // Алгебра и логика, Новосибирск, 1964, 3, Л'! 1, с. 41-56.

78. Раца М. Ф. Выразимость в исчислениях высказываний. Кишинев, «Штиинца», 1991.

79. Редько В. Н., Никитченко Н. С. Композиционные аспекты программологии, I // Кибернетика, Киев, 1987, № 5, с. 49-56.

80. Ремизов А. Б. О надструктуре замкнутого класса полиномов по модулю к // Дискретная математика, М.: Наука, 1989, 1, № 1, с. 3-15.

81. Розинас М. Г. Алгебра многоместных примитивно рекурсивных функций // Ученые записки Ивановского государственного педагогического института, 1972, 117, с. 95-111.

82. Ромов Б. А. О максимальных подалгебрах алгебры частичных функций многозначной логики // Кибернетика, Киев, 1980, № 1, с. 28- 36.

83. Соколов В. А. Замечания о классе частичных функций счетнозначной логики // Дискретный анализ, Новосибирск, 1971, вып. 19, с. 56-62.

84. Соколов В. А. О максимальных подалгебрах алгебры всех частично рекурсивных функций // Кибернетика, Киев, 1972, № 1, с. 70-73.

85. Соколов В. А. Некоторые свойства алгебры всех частично рекурсивных функций // Матем. исследования, Кишинев, 1972, 7, № 1, с. 133-149.

86. Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы. М.: Наука, 1970.

87. Фрейвалд Р. В. Критерий полноты для частичных функций алгебры логики и многозначной логики // Доклады АН СССР, 1966, 167, № 6, с. 1249-1250.

88. Фрейвалд Р. В. Функциональная полнота для не всюду определенных функций алгебры логики // Дискретный анализ, Новосибирск, 1966, вып. 8, с. 55-68.

89. Черепов А. Н. Описание структуры замкнутых классов в P¡¡, содержащих класс полиномов // Проблемы кибернетики, М.: Наука, 1983, вып. 40, с. 5-18.

90. Черепов А. Н. Надструктура класса сохранения отношений сравнения при к = рт //В кн.: Моделирование и оптимизация вычислительных систем и процессов, Ярославль, Изд-во Ярославского государственного университета, 1988, с. 61-65.

91. Чёрч А. Введение в математическую логику, т.1. М.: ИЛ, 1960.

92. Щеглов А. И. О мощности множества максимальных подалгебр алгебры частично рекурсивных функций // Алгебра и логика, Новосибирск, 1968, 7, № 3, с. 119-121.

93. Яблонский С. В. Функциональные построения в многозначных логиках // Труды Третьего Всесоюзного математического съезда, М.: Изд-во АН СССР, 1956, т.2, с. 71-73; с. 425-431.

94. Яблонский С. В. О классах функций алгебры логики, допускающих простую схемную реализацию // Успехи матем. наук, 1957,12, № 6, с. 189-196.

95. Яблонский C.B. Функциональные построения в fc-значной логике. // Труды Матем. института им. В. А. Стеклова АН СССР, 1958, 51, с. 5-142.

96. Яблонский С. В. О предельных логиках // Доклады АН СССР, 1958, 118, № 4, с. 657-660.

97. Яблонский С. В. О некоторых свойствах счетных замкнутых классов из Рц0 // Доклады АН СССР, 1959, 124, № 5, с. 990993.

98. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.

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

100. Яблонский С. В., Гаврилов Г. ГГ., Набебнн А. А. Анализ и синтез схем в многозначных логиках, ч.1. М.: Изд-во Московского энергетического института, 1989.

101. Яблонский С. В., Гаврилов Г. П., Набебин А. А. Предпол-ные классы в многозначных логиках. М.: Изд-во Московского энергетического института, 1997.

102. Янов Ю. И. О логических схемах алгоритмов // Проблемы кибернетики, М.: Наука, 1958, вып. 1, с. 75-127.

103. Янов Ю. И., Мучник А. А. О существовании fc-значных закну-тых классов, не имеющих конечного базиса // Доклады АН СССР, 1959, 127, № 1, с. 44-46.

104. BirkhoiF G. On the combination of subalgebras // Proc. Cambridge Phil. Soc., 1933, 29, p. 441-464.

105. Birkhoff G. On the structure of abstract algebras // Proc. Cambridge Phil. Soc., 1935, 31, p. 433-454.

106. Higgins P. J. Algebras with a scheme of operators // Math. Nachrichten, 1963, 27, №1-2, p. 115-132.

107. Lo Czu Kai Precompleteness of a set and rings of linear functions // Acta sci. riatur Univ. Jilinensis, 1963, № 2.

108. Mc Kinsey J. С. C. Proof of the independence of primitive symbols of Heytings calculus of propositions // J. Symb. Logic, 1939, 4, p. 155-158.

109. Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math., 1921, 43, № 3, p. 163-185.

110. Post E. L. The two-valued iterative systems of mathematical logic. Princeton, 1941.

111. Rose Â. Self-dual binary and terxiaxy connectives for m-valued propositional calculi // Math. Ann., 1961, 143, p. 448-462.

112. Rosenberg I. G. La structure des fonctions de plusieurs variables sur un ensemble fini // Comptes Rendus Acad. Sei., Paris, 1965, 260, p. 3817-3819.

113. Rosenberg I. G. Uber die funktionale Vollständigkeit in den mehr-vertigen Logiken. Rozpravy Ceskoslovenskê Academie vëd. Rada matematickych apfirodnich vëd. Praha, 1970, Rocnik 80, Sesit 4.

114. Rosenberg I. G. Some maximal closed classes of operations on infinite sets // Math. Ann., 1974, 212, p. 157-164.

115. Rosenberg I. G. Universal algebras with all operations of bounded range // Colloquium Mathematicum, 1974, 30, p. 177-185.

116. Rosser J. В., Turquette A. R. Many-valued logics. Amsterdam, 1952.

117. Rousseau G. Completeness in finite algebras with a single operation // Proc. Amer. Math. Soc., 1967, 18, p. 1009-1113.

118. Salomaa A. Some analogues of ShefFer functions in infinite-valued logics // Acta Philosophice Fennica, 1968,16, p. 227-235.

119. Shannon С. Б. A symbolic analysis of relay and switching circuits // Trans. AIEE, 1938, 57, p. 713-722. (Русский перевод: Шеннон К., Работы по теории информации и кибернетике. М.: ИЛ, 1963.)

120. Shannon С. Б. The synthesis of two-terminal switching circuits // Bell Syst. Techn. J., 1949, 28, 1, p. 59-98. (Русский перевод: Шеннон К., Работы по теории инфоромации и кибернетике. М.: ИЛ, 1963.)

121. Schofield P. Complete subsets of mappings over a finite domain // Proc. Cambridge Phil. Soc., 1966, 62, p. 597-611.

122. Sierpinski W. Sur les fonctions de plusieurs variables // Fundamenta Mathematicae, 1945, 33, p. 169-173.

123. Slupecki J. Kryterium pelnosci wielowartosciowych systemów lo-giki zdari / / Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie, Classe III, 1939, 32, p. 102-109.

124. Tarski A. Der Wahrheitsbegriff in den formalisierten Sprachen // Studia Philos., 1936, 1, p. 261-405.

125. Webb D. Generation of any n-valued logic by one binary operator // Proc. Nat. Acad. Sei., 1935, 21, p. 252-254.

126. Whitehead A. N. A treatise on universal algebra, with applications, I. Cambridge, 1898; reprinted New York, 1960.

Оглавление

Введение..........................................................................................................3

1. Многозначные логики........................................................................16

1.1. Замкнутые классы в Ррг, содержащие полиномы 16

1.2» Классы самодвойственных функций........................21

2. Булевы функции ..................................................................................22

2.1. Рекуррентные формульные представления функций из классов , (г — 2,3,..........................................22

2.2. О сохранении неитеративных свойств при отождествлении переменных..................................................24

3. Счетнозначные логики ......................................................................26

3.1. Предельные логики..........................................................26

3.2 - Гиперкоитинуальное семейство предполных классов в Рш, не содержащих обобщенных констант. 31

3.3. Классы конечной высоты в Рш....................................33

3.4. Классы типа Слупецкого в Рш....................................37

Список литературы....................................................................................41