Итеративные алгебры, близкие к транзитивным тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

МАЛЬЦЕВ ИВАН АНАТОЛЬЕВИЧ

ИТЕРАТИВНЫЕ АЛГЕБРЫ, БЛИЗКИЕ К ТРАНЗИТИВНЫМ

01.01.06 - математическая логика, алгебра и теория чисел

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

НОВОСИБИРСК • 2004

Работа выполнена в Институте математики им. С. Л. Соболева Сибирского отделения РАН.

Официальные оппоненты:

доктор физико-математических наук, профессор О. М. Касим-Заде доктор физико-математических наук, профессор А. Г. Пинус доктор физико-математических наук, профессор В. И. Хомич

Ведущая организация: Уральский государственный университет имени А. М. Горького

Защита состоится " 23 " сентября 2004 г. в 14 часов на заседании диссертационного совета Д 003.015.02 в Институте математики им. С.Л.Соболева СО РАН по адресу: 630090, Новосибирск, проспект Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Института математики СО РАН

Автореферат разослан 2004 г.

Ученый секретарь диссертационного совета к.ф.-м.н.

А. Н. Ряскин

Суперпозиция, то есть замена одной из переменных функции также функцией; является одним из простых и естественных способов получения новых функций из уже имеющихся. Возникающая в результате суперпозиций функция называется сложной. Одни свойства исходных функций наследуются сложной функцией, другие же не сохраняются. Например, при суперпозиции возрастающих функций получается также возрастающая функция. Закономерный интерес вызывает вопрос, можно ли всякую функцию, обладающую каким-то заданным свойством, получить при помощи суперпозиций из функций, обладающих тем же свойством, но зависящих от меньшего числа переменных. В качестве свойства обычно выбирается непрерывность, дифференцируемость и т.п.

Упомянем лишь некоторые результаты в указанном направлении, полученные отечественными математиками А. Г. Витушкиным, А. Н. Колмогоровым и В. И. Арнольдом. Если натуральные числа- удовлетворяют неравенству

то, как доказал. А. Г. Витушкин [2], существует зависящаяот переменных раз дифференцируемая функция, которую нельзя получить суперпозициями из раз дифференцируемых функций, зависящих от переменных. А. Н. Колмогоров [24] и В. И. Арнольд [1] доказали, что каждая вещественная непрерывная функция представима в виде суперпозиции, непрерывных функций, зависящих от двух переменных. Любую непрерывную функцию от нескольких переменных можно получить при помощи суперпозиций из функции х+у и непрерывных функций; зависящих от одного аргумента (Колмогоров, [25]).

В приведенных выше примерах решаемые задачи можно

сформулировать следующим образом.

» ;

Каким-то способом заданы два множества функций М\ и Л/г. Можно ли каждую функцию из множества М\ получить суперпозициями функций, принадлежащих множеству М2?

К этой задаче близка следующая.

3aдан класс функцию К. Описать все функции, которые можно получить суперпозициями функций, принадлежащих К.

Функции, получаемые при помощи суперпозиции из функций класса К, образуют множество [К], называемое замыканием класса К. Класс К называется порождающим для своего замыкания. Если К ={Щ, то класс [К] называется замкнутым. Описание множества [Мг] ведет к решению первой из указанных выше задач: функции из множества М\ можно получить суперпозициями функций, принадлежащих множеству Мг тогда и только тогда, когда множество является подмножеством замыкания множества М?. Однако решение первой задачи может и не зависеть от решения второй.

Задача описания замыкания множества функций М имеет смысл только при существенных ограничениях на входящие в М функции. Одним из таких ограничений является фиксирование числа элементов в множестве, на котором определены функции из М. Э. Постом [34, 35] описаны все замкнутые классы функций, определенных на множестве из двух элементов. По включению эти классы образуют решетку, называемую решеткой Поста. На множестве из трех элементов имеется континуум замкнутых классов [49], образующие решетку очень сложного строения, поэтому приходится дополнительно ограничивать множество изучаемых классов.

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

исчислениях. Формулам при таких интерпретациях отвечают сложные функции, принадлежащие замкнутым классам, порождаемым этими операциями: Особое внимание привлекала проблема полноты: найти условия, необходимые и достаточные для того, чтобы система функций, определенных наконечном множестве, порождала замкнутый класс, содержащий все функции, определенные на этом множестве. Как уже говорилось, проблема полноты в классе всех функций, определенных на множестве из двух элементов, была решена Э. Постом. Задача оказалась намного сложнее в случае, когда функции определены на множестве, содержащем более двух элементов. Одну из первых работ в этом направлении опубликовал в 1939 г. Я. Слупецкий [44]. Он доказал, что каждая полная система функций должна содержать существенно многоместную функцию, принимающую все возможные значения. Такую функцию принято называть функцией Слупецкого. В 1954 г. С. В. Яблонский [47, 48] решил проблему полноты для случая, когда функции определены на множестве из трех элементов. Затем в течение 10 лет появилось много работ, в которых указывались достаточные условия полноты системы функций. Окончательно проблема полноты была решена И. Розенбергом [41] в 1965 году.

Стоит отметить, что упомянутую ранее теорему А. Н. Колмогорова [25] о том, что функция х+у вместе со всеми непрерывными одноместными функциями порождает все одноместные функции, можно рассматривать в качестве аналога теоремы Слупецкого. Любую непрерывную функцию от нескольких переменных можно получить при помощи суперпозиций из функции и непрерывных функций, зависящих от

одного аргумента (Колмогоров, [25]). Определенные топологические аналоги теоремы Колмогорова были позже найдены А. А. Мальцевым [27].

В теории универсальных алгебр важную роль играют классы функций, замкнутые относительно суперпозиций и содержащие все проекции, то есть функции вида е"(х1,..., Хп) = х^. Эти классы называются клонами. Две универсальные алгебры с одинаковыми носителями называются рационально эквивалентными, если множества их основных операций порождают один и тот же клон. Ввиду этого описание с точностью до рациональной эквивалентности различных универсальных алгебр, определенных на каком-то множестве, сводится к описанию всех клонов на этом множестве.

Клоны можно рассматривать как алгебры, например, как содержащие функцию еКжъХг) = предитеративные алгебры, введенные А. И: Мальцевым [29]. Предитеративны-ми алгебрами называются подалгебры предитеративной алгебры. Поста О а = типа (1,1,1.2), в которой О а — множество всех функций, определенных на множестве А. Операции Д,* при.п > Г определены следующим образом:

Если функция f унарная, то = г/ = А/ = /. Операция * определена так:

В совокупности операции заменяют суперпози-

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

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

Тождество £ ~ ¿' называется гипертождеством алгебры А, если f = V тождественно выполняется в А при любой замене символов операций, входящих в термы Ь и термальными функциями алгебры А соответствующей арности. Тождества в клонах называются клоповыми тождествами. Клоповые тождества алгебры Т(А) соответствуют гипертождествам алгебры А [45].

Следующий пример [11] показывает, что гипертождества могут применяться в теории логических сетей. Если

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

g

g 1 >

1 >

1

можно заменить элементом

какой бы не была функция д, поскольку

Р{х,Р{х,Р{хуу)))ъР{х,у)

является гипертождеством алгебры {{0,1}; ЛГ).

Гипертождества позволяют кратко формулировать признаки полноты системы функций [23]. Например, система булевых функций Я полна тогда и только тогда, когда равен-

« F(F(x,x),F(y,y))

не является гинертождеством алгебры

Обзор основных результатов, вошедших в диссертацию. . • • •

Для любого множества функций Р С Ок через п Е

К, обозначим множество всех функций из Р, зависящих ровно от п переменных, через рМ — множество всех функций из .Р, принимающих не более п значений, через рМ — множество всех функций из Р, принимающих ровно п значений. Отметим, что множество Л1) относительно операции * является полугруппой. Порождаемую множеством. АМ подалгебру алгебры "Ра, образованную всеми существенно одноместными функциями из обозначим через Полугруппа одноместных функций называется в раз транзитивной, если для любых попарно различных чисел а,1,...,а3 и любых чисел в ней найдется такая функция что Да») = Ьг, г = 17в.

Итеративная алгебра называется клеточной (А. И. Мальцев [31]), если она состоит из всех существенно одноместных функций и всех существенно многоместных функций, принимающих не более в значений. Клеточная алгебра имеет вид 'Ри "Р^ и далее иногда будет обозначаться через 1А3. Основной клеткой клеточной алгебры называется подалгебра ■р^, образованная всеми функциями; принимающих не более 5 значений.

А. И. Мальцевым [29] доказана структурная теорема, обобщающая известные теоремы Слупецкого [44] и С. В. Яблонского [48]. Опуская особые случаи, ее можно сформулировать следующим образом.

Итеративная алгебра, порождаемая всеми функциями э раз транзитивной полугруппы вместе с существенно многоместной функцией /, принимающей т значений, содержит клетку "Р^ и все функции, значения которых принадлежат множеству значений функции f, если 2 < т < в-Ъ 1.

В диссертации изучаются итеративные алгебры с 5 раз транзитивными основаниями, и обобщения таких алгебр. Однако в ряде случаев, например в четвертой главе, исследуемые алгебры не укладываются в указанные границы, поскольку некоторые утверждения носят общий характер. Для рассматриваемых алгебр строятся порождающие системы и находятся условия полноты систем функций. Для ряда изучаемых алгебр описываются решетки подалгебр. Описываются конгруэнции и образуемые ими решетки, а также группы автоморфизмов. Описываются алгебры многообразий, порождаемых универсальными алгебрами, клоны которых близки к транзитивным. Рассматривается проблема разделения клонов при помощи гипертождеств. Для произведений итеративных алгебр доказывается аналог структурной теоремы А. И. Мальцева.

Глава 1. Первые два параграфа носит вводный характер. В нем приводятся определения; соглашения и точные формулировки утверждений из работ других авторов, необходимые в дальнейшем. Многие из них уже приведены выше. Далее нам потребуется следующие определения.

Функции, представимые в виде /о(/1(^1) Ф Ф /п(#п)), где п > 1, значения одноместных функций. Л,...,/« принадлежат множеству {0,1}, сложение ведется по модулю 2, а одноместная функция /о может принимать любые значения, называются квазилинейными. Итеративная алгебра, состоящая из квазилинейных функций, будет обозначаться через С.. Ввиду ее свойств она также считается клеточной. Ее основной клеткой является алгебра

Параграф 1.3 содержит ряд структурных теорем и следствия из них. Утверждение 1.3.1 дополняет приведенную выше теорему А. И. Мальцева следующим образом.

Если Л содержит два раза транзитивную полугруппу О и не квазилинейную функцию, принимающую два значения, то Аэгр.

Если алгебра Л>при кг > 3 содержит полугруппу а также существенно многоместную квазилинейную функцию, то Л

Известная теорема Саломаа [43] утверждает, что при к > 4 множество функций^^^ вместе с любой существенно многоместной функцией; принимающей Означений, порождает Систему порождающих какой итеративной алгебры мы получим, присоединив к функциям из существен-

но многоместную функцию, принимающую менее к значений? Теорема 1.3.9 утверждает, что если к > 3 и добавляемая функция не квазилинейная, то получится система порождающих некоторой клеточной подалгебры.

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

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

В параграфе 1.5 рассматриваются максимальные подалгебры клеток и клеточных алгебр. Теорема 1.5.1 показывает, что задача описания всех максимальных подалгебр алгебр

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

ьСи Т{ка}иг11)[к-2}*и<т%, р«1л£н*-1>уиМ? (г е 4),

где „М^ — максимальная подгруппа группы о^. Следствием этой теоремы является описание подалгебр Фраттини алгебр С, 142, • • • > Ык-х. Так, подалгеброй'Фраттини указанной выше алгебры 1Аа является алгебра ¿Ги'Р^"1^'?^1^*-2^, где £ — селекторная подалгебра алгебры "Рк (подалгебра, порождаемая функцией

В том же параграфе описываются два класса максимальных подалгебр клеток алгебры причем оказывается, что пересечение всех- построенных- максимальных подалгебр алгебры при 2 ^ й < к пусто. Доказывается, что подалгеброй Фраттини алгебры С^ является алгебра р],1'.

Пример, построенный Ю. И. Яновым и А. А. Мучником [49], показывает, что уже у алгебры имеется континуум подалгебр, а потому столько же подалгебр есть у каждой клеточной подалгебры, отличной от В разделе 1.6 доказывается, что мощность множества всех подалгебр алгебры £{2}

счётна. В алгебре

£{2}

имеются бесконечнопорожденные подалгебры, но нет подалгебр с бесконечным базисом.

11

Глава 2. Эта глава целиком посвящена описанию под-клонов клона Бурле над множеством из трех элементов. Указанный клон состоит из существенно одноместных функций; и функций вида

fo(fi{xi).+ -r + fn(xn)),'

где значения одноместных функций fi,...,fn принадлежат множеству '{0,1}, сложение ведется подмодулю 2, а функция /о может принимать любые значения. Клон Бурле является наименьшим среди клонов, содержащих все одноместные функции и хотя бы одну существенно многоместную функцию. Хотя он содержит счетное число подклонов, образуемая этими подклонами решетка значительно сложнее решетки Поста. Здесь исследованы лишь подклоны, состоящие из функций, значения которых принадлежат либо множеству либо множеству Удалось нарисовать граф решетки подклонов клона образованного функциями со значениями в множестве *{0j 1}, (рис. 1). Приводятся таблицы с указанием состава клонов, системы порождающих. Многочисленные диаграммы помогают уяснить взаимное расположение клонов в решетке всех подклонов клона Бурле. Исследование выполнено совместно с Я. Деметровичем [5] - [9].

Глава 3. Конгруэнции на подалгебрах алгебр Поста впервые изучались Л. И. Мальцевыми работе [29]. Им было отмечено, что, если исключить тривиальные случаи, на каждой подалгебре алгебры Vk имеется три конгруэнции: Kq, совпадающая с отношением равенства, совпадающая с тождественно истинным отношением, и /са, определяемая следующим образом: функции тогда и только тогда конгруэнтны, когда они зависят от одинакового числа переменных. В дальнейшем эти три конгруэнции будут называться тривиальными. В той же работе найдено условие, достаточное для того, чтобы все конгруэнции на какой-либо подалгебре алгебры являлись тривиальными; в частности,

оказалось, что тривиальны все конгруэнции на самой алгебре

V*

Упомянутое условие не выполняется ни для клеток алгебры Тк, ни для клеточных подалгебр. В параграфе 3.1 доказывается, что при А; > 2 на подал: VР е -ются лишь тривиальные конгруэнции, а на С^ есть лишь одна нетривиальная конгруэнция. В разделе 3.2 показывается, что тривиальными являются также все конгруэнции на любой подалгебре Л'алгебры»'^•удовлетворяющей условию "Рк^ 2 Л. Э '«5>{я} где ¿»^ — некоторая специальная подалгебра алгебры В параграфе 2:3 указывается достаточное условие, при котором решетка конгруэнций на подалгебре содержащей лишь существенно одноместные функции, легко строится, если известна решетка конгруэнции на полугруппе Этому условию удовлетворяют основания всех клеточных подалгебр. Затем; используя описание решетки конгруэнции на полугруппе "Р^, приведенное в [28], строятся решетки конгруэнции на подалгебрах

Пусть , образованную всеми

функциями из Т'ач значения которых принадлежат D, назовём простой, или элементарной квазиклеткой над множеством В; множество В назовем определяющим для./С/>. Квазиклеткой называется подалгебра алгебры являющаяся объединением произвольного множества простых квазиклеток. Клетки являются частным случаем квазиклеток. Изучение свойств квазиклеток и их подалгебр проводится в параграфе 3.5. Оказывается, что эти свойства можно увязать с изоморфными вложениями алгебры описанны-

ми А. И. Мальцевым [29]: Ранее свойства простых квазиклеток конечного ранга исследовались Д. Лау [26]. Она нашла все конгруэнции на подалгебрах простых квазиклеток. Часть этих конгруэнции имеет весьма регулярное строение. Назовем их 5 -конгруэнциями.

Пусть а — взаимно однозначное отображение множества А в множество В, С — образ множества А, /3 — отображение множества В на С, оставляющее элементы множества С неподвижными. Каждой функции /(х\,... ,хп) из подалгебры алгебры сопоставим функцию' из следующим образом:

Отображен/я1 а : / —> и 7 : / —> faß %вл?но¥о^)изоморфиз-мами алгебру А в алгебрuJPc и Vb соответственно. Обозначим через С иаВ^&Ьы' мгеЙр^^^й'^тих'Изоморфизмах. Алгебра В называется проективным расширением алгебры С.

Пусть D С А, В — подалгебра алгебры Vd и /Сд — квазиклетка алгебры Vai имеющая определяющее множество D. Подалгебру алгебры JCu, образованную такими функциями /, из Va, что /t f D 6 В, назовём вполне ограниченным расширением алгебры В в Va- Будем писать А>> В, если- Аяъ-ляется вполне ограниченным расширением алгебры В.

Обозначим через А(А) объединение множеств значений всех функций, принадлежащих подалгебре А' итеративной алгебры Va- Алгебру А f А{А) назовём ядром алгебры А. Ядро алгебры Л'назовём отделимым, если оно не совпадает с А. Мощность множества А \ А(А) назовём индексом алгебры

В параграфе 3.5 описан ряд свойств ^-конгруэнций. Центральным результатом является следующая теорема.

Пусть подалгебра А алгебры Va является вполне ограниченным расширением алгебры В, S = {Д|/ G 1} —совокупность попарно различных подмножеств множества А(А), Ds = U,<=/Д, >cs — S-конгруэнция на А. Алгебра A/xs изоморфна такой подалгебре С алгебры А, которая является

15

проективным расширением алгебры С>В. Если множество А конечно, то индекс алгебры С строго меньше индекса алгебры Л. Если каждое множество Л» содержит лишь один элемент, то алгебра С' имеет индекс \А \ (Л(Л) и Дэ)|.

В разделе 3.6 рассматриваются итеративные алгебры произвольного ранга. А. И. Мальцев [29] разделил все автоморфизмы таких алгебр на внутренние и внешние. Он установил, что внутренними являются все автоморфизмы любой итеративной алгебры, содержащей все функции, принимающие некоторое фиксированное значение о/, как только значение любой ее переменной равно и потому группа автоморфизмов такой алгебры вложима в группу В параграфе 3.6 доказывается, что внутренними являются все автоморфизмы итеративной алгебры, содержащей все константы, и потому ее группа автоморфизмов также вложима в ет*.. Это в частности означает, что внутренними являются все автоморфизмы клеток и клеточных алгебр. . .

В параграфе 3.7 устанавливаются некоторые связи между квазиклетками и универсальными алгебрами, у которых клон, порождаемый основными операциями, получается пополнением квазиклетки всеми проекциями. Описываются многообразия, порождаемые такими алгебрами. Тем самым обобщаются результаты, полученные ранее Б. Венглоржем [3] и И. Розенбергом [42].

Глава 4. Тождества алгебр функций являются формулами языка второго порядка (гипертождествами). Естественным образом возникает следующий вопрос: верно ли, что клоны однозначно определяются множествами своих гипертождеств? Обсуждению этой проблемы посвящены три параграфа этой главы.

Если рассматривать клоны функций, определенных на множестве, содержащем более двух элементов, то ответ в общем случае будет отрицательным. Однако булевы клоны одно-

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

Пусть С и С — два таких булевых клона, что С не изоморфен никакому подклону клона С. Тогда С можно отделить от С' гипертождествами.

В этом смысле булевы клоны можно разделить гипертождествами. Доказательство указанного выше утверждения приведено в разделе 4.3. Оно опубликовано в работе [10], написанной совместно с К. Денеке. Отметим, что в статье [11], написанной в соавторстве с К. Денеке и М. Решке, приведено конструктивное доказательство с указанием разделяющих гипертождеств.

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

В последнем параграфе исследуется следующая проблема: можно ли отделить квазиклетки от других подалгебр алгебры Т*л при помощи гипертождеств? Для | А | = 3 положительный ответ был найден совместно с Д. Швайгер-том [18]. Точнее говоря, сформулированы условия, необходимые и достаточные для того, чтобы подалгебра алгебры, Т>з являлась квазиклеткой. Ниже указаны такие условия для рассмотренных случаев.

Пусть через в обозначено функциональное тождество

Через Л обозначим функциональное тождество

А(А(А(А(х, х)), А(А(х, х), А(х, х))),

А(А(А(у, у), А (у, у)), А(А(у, у), А(у, у)))) = — А(А(А(А(аг, х)), А(А(у, у), А(у, у))),<

А(А(А(х, х), А(х, х)), А(А(у;у)/А(у, у»)).

Через П обозначим формулу,

У<рУфУ,у[{(рф1рф^3фф ~ (рф(рфу<рф) V = (рф(р)].

Подалгебра Л ^ VI совпадает с квазиклеткой /С{од} < VI тогда и только тогда, когда одновременно выполняются следующие условия:

1) Никакая функция из А'не принимает значение 2;

дМ'^е?

Подалгебра А ^ VI совпадает с квазиклеткой /С{од} и тогда и только тогда, когда одновременно выполняются следующие условия:

Подалгебра Л1^ совпадает с квазиклеткой

/Сод и /Со,2 и 1^1,2

тогда и только тогда, когда одновременно выполняются следующие условия:

Глава 5. Пусть Пс^ = ^М х ••• х Рдт — множество всевозможных последовательностей

(/1(2-1» • • • ) ^п)) • • • ) (/т(^1) • * • ) ^п))>

в которых /, £ Рл, Каждую такую последовательность можно рассматривать как функцию определенную на множестве А = А\ х х'Ат. Очевидным образом на Пс ^а, можно определить операции г, Д, V, *. Например,

Алгебра Тки.,кт — (Пс ^Ао С)г) V, *} называется согласованным (с числом переменных у функций, принадлежащих носителям сомножителей) произведением алгебр "Ра,- В универсальной алгебре этому понятию соответствует определенное В. Наркевичем [4] неиндексированное произведение алгебр. Различные свойства согласованных произведений исследовались Б. А. Ромовым[36] - [40], В. А. Таймановым [46], С. С. Марченковым [32, 33).

Пятая глава диссертации делится на два параграфа. Параграф 5.1 содержит теорему, обобщающую структурная теорему А. И. Мальцева [30](с дополнениями, описанными в первой главе) на произведения итеративных алгебр. Она опубликована в статье [21], написанной совместно с Б. Г. Тугыл-баевой. Результаты параграфа 5.2 опубликованы в [22].

Пусть кг ^ 3 при г = 1,т, а, 6 М, 5г > 2, А — подалгебра алгебры "Р/^, ,кт> содержащая такую функцию / = (/ь • • •) /т)), что /, для любого г — \,т является существенно многоместной функцией, принимающей либо либо 1 значение, ^ - множество всех функций из Рк,, все значения которых содержатся в множестве /г(£*,)• Пусть далее Нг — б\ раз транзитивная подполугруппа полугруппы Р^К если ^ 4, либо полугруппы если я, € {2,3}

и /г — не квазилинейная функция, и Нг = если функ-

ция /, 6 Р^ квазилинейная. Если Лсодержит все функции

19

из множества II — Н\ х ... х Нш, то Л принадлежат все функции из произведения В\ х ... х Вт, где Вг может совпадать либо с Тг, если /, принимает в, + 1 значение и содержит тождественную функцию е}(х) = х, либо £Щ, если /, б либо с если /, £ £<2>.

Слова «может совпадать» в заключительной части формулировки теоремы указывают на то, что в некоторых случаях произведение В\ х... х Вт может быть составлено несколькими способами и каждый раз будет получено множество функций, принадлежащих Л, причем разные варианты произведений могут давать несовпадающие множества функций. Так, если /, $ С^, /, принимает в, + 1 значение и Нх содержит тождественную функцию, то в качестве Вг можно взять либо множество либо множество ,

В приведенной выше теореме существенную роль играют произведения Н\ х ... х Нт транзитивных п о л у г р у ЙЛ-П о -скольку существенные переменные в разных сомножителях могут иметь различные индексы, такие произведепия следует считать существенно многоместными функциями. Такая точка зрения подтверждается например утверждением 5.2.3, доказываемым в параграфе 5.2. Существенно одноместными являются произведения одноместных функций, у которых индексы существенных переменных, если таковые имеются, совпадают. В связи с этим случай, когда известно, что алгебра содержит все такие произведения и еще какую-либо функцию, не совпадает с уже рассмотренным, и является интересным. Теорема 5.2.4 также является аналогом упоминавшейся выше структурной теоремы А. И. Мальцева, хотя требования, накладываемые на множества одноместных функций в сомножителях, приближают ее к теоремам Слупецкого и С. В. Яблонского.

Если подалгебра Л алгебры содерэюит все функ-

ции, принадлежащие

множеству

кт, и такую функ-

цию f = (fi, • • ■, fm)> что для каждого г = 1 ,ш функция fi € принимает 2 значений, и ее единственная

существенная переменная имеет индекс, отличающийся от индексов существенных переменных всех остальных проекций функции f, то А содержит все функции из произведения х ... х Аут' •

Напомним, что подалгебра Слупецкого является единственной максимальной подалгеброй алгебры Vk, содержащей все функции из V^K Она образована всеми существенно одноместными функциями из Vk и всеми существенно многоместными функциями, принимающими не более к — 1 значений; Следуя С. С. Марченкову [33], присвоим это название максимальным подалгебрам алгебры Vki...km, содержащим все функции из U^ кт. Последняя теорема позволяет описать все подалгебры Слупецкого в произведениях итеративных алгебр: ^ ^ ^

и % — подалгебра Слупецкого алгебры является единственной подалгеброй Слупецкого алгебры Vkx...km, если ki > 3 для каждого i Е (1,.. . ¡т}.: J

Все вошедшие в диссертацию результаты опубликованы в [5]- [22]. Они докладывались на семинарах в институте математики СО PAH, Новосибирском и Московском государственных университетах, а также на международных конференциях в России, Австрии, Венгрии, Германии, Китае, Югославии, и Японию Статьи [5] - [9] написаны в неразделимом соавторстве с Я. Деметровичем, работа [10] - в неразделимом соавторстве с К. Денеке, работа [11] - в неразделимом соавторстве с К. Денеке и М. Решке, статья [18]- в неразделимом соавторстве с Д. Швайгертом; статья [21] - в неразделимом соавторстве с Б. Г. Тугылбаевой;

Литература

[1] Арнольд В. И. О функциях трех переменных // ДАН СССР. 1957. Т. 114, № 4. С. 679-681. -

[2] Витушкин А. Г. О многомерных вариациях // М.: Гос. издат. технико-теоретич. литературы. 1955.

[3] Wgglorz В.- A representation theorem for Post-like algebras / Colloq. math. 1970. V. 30, №1. P. 35-39.

[4] Goetz A. A generalization of the notion of direct product of universal algebra // Colloq. Math. 1971. V. 22. P. 167-176.

[5] Demetrovics J., Malcev I. A. On the depth of infinitely generated subalgebras of Post's iterative algebra P3 // Coll. math. soc. Janos Bolyai. Szeged, 1983. V. 43. P. 85-96.

[6] Деметрович Я., Мальцев И. А. О существенно минимальных ТС-клонах па трехэлементном множестве // МТА SZTAKI Kozl. 1984: № 32. С. 115-151.

[7] Demetrovics J., Malcev I. A. Essentially minimal TC-clones on three-element base set // C.R. Math. Rep. Acad. Sci. Canada. 1986. V. 8, № 3. P. 191-196.

[8] Деметрович Я., Мальцев И. А. О строении клона Бур-ле на трехэлементном множестве // Acta cybernetica. 1989. V. 9, № 1. P. 1-25.

[9] Demetrovics J., Malcev I. A. Essentially minimal TC-clones on three-element base set // The nineteenth int. symp. on multiple-valued logic. Guangzhou, China. 1989. P. 220-227.

[10] Денеке К., Мальцев И. А. Разделение клонов гипертождествами // Сиб. мат. журн. 1994. Т. 35, № 2. С. 310-316.

[11] Денеке К., Мальцев И. А., Решке М. О разделимости клопов гипертождествами // Сиб. мат. жури. 1995. Т. 36, № 5. С. 1050-1066.

[12] Мальцев И. А., Некоторые свойства клеточных подалгебр алгебра Поста и их основных клеток // Алгебра и логика. 1972. Вып. 11. № 5. С. 571-587. :

[13] Мальцев И. А. Конгруэнции и автоморфизмы на клетках алгебр Поста// Алгебра и логика. 1972. Вып. 11, № 6. С. 666-672.

[14] Мальцев И. А. Некоторые свойства клеток алгебр Поста. // Дискретный анализ. 1973: № 23. С. 24-31.

[15] Мальцев И. А. О конгруэнциях на подалгебрах итеративных алгебр Поста. // Дискретный анализ. 1976. № 29. С. 40-52.'

[16] Мальцев И. А. Гомоморфизмы вполне ограниченных расширений итеративных алгебр Поста // Rostock.'Math. Kolloq. 1979. № 11. P. 85-92.

[17] Мальцев И. А. Инварианты квазиклеток итеративных алгебр Поста//Сиб: мат.журн. 1985. Т. 26, № 1. С. 220223.

[18] Мальцев И. А., Швайгерт Д. Гипертождества QZ-алебр // Сиб. мат. журн. 1989. Т. 30, № 6. С. 132-139.

[19] Malcev I. Graduated products of Post algebras // Note on multiple-valued logic. 1995. V. 18, № 13. P. 1-4.

23

[20] Malcev I. Coordinated products of iterative algebras // Proc. VIII int. conf. on logic and comp. sci. Novi Sad, Yugoslavia. 1997. P. 1-2.

[21] Мальцев И. А., Тугылбаева Б. Г. Произведения umepa-тивных алгебр // Сиб. мат. журн. 1999. Т. 40, №1. С. 102-112.

[22] Malcev I. Slupecki subalgebras in coordinated products of iterative algebras// Multi. val. logic. 2000. V. 5. P. 1-13.

[23] Denecke K., Poeschel R. The characterization of primal algebras by hyperidentities // Contributions to general algebra 6. Wienna: Hoelder-Pichler-Tempsky, 1988. Bd 6. S. 67-68. .

[24] Колмогоров А. Н. О представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных // ДАН. СССР. 1956. Т. 108. № 2. С. 179-182.

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

[26] Lau D. Kongruenzen auf gewissen Teilklassen von .Pk,i // Rostock, math, kolloq. 1977. № 3. S.. 37-43.

[27] Мальцев А. А. Топологический вариант теоремы Слу-пецкого для некоторых компактов// ДАН СССР. 1969. Т. 188. № 1. С. 33-36.

[28] Мальцев А. И. Симметрические группоиды // Мат. сб. 1952. Т. 31, вып. 1. С. 136-151.

[29] Мальцев А. И. Итеративные алгебры и многообразия Поста//Алгебра и логика. 1966. Вып. 5, № 2. С. 5-24.

24

[30] Мальцев А. И. Об одном усилении теорем Слупецкого и Яблонского // Алгебра и логика. 1967. Вып. 6, № 3. С. 61-75.

[31] Мальцев А. И. Итеративные алгебры Поста. - Новосибирск: Новосиб. гос. ун-т, 1976.

[32] Марченков С. С. О полноте в системе Рз х // Дискретная математика. 1992. Т. 4, № 1. С. 126-145.

[33] Марченков С. С. О классах Слупецкого в системах Pk х //. ДйЁ^ретная математика. 1992. Т. 4, № 3. С135-

148.

[34] Post E. Introduction to a general thery of elementary propositions II Amer. J: Math. 1921. V. 43. P.f 163-185.

[35] Post E. Two-valued iterative systems of mathematical logic. - Princeton Univ. Press., 1941.

[36] Ромов Б. А. Алгоритм решения проблемы полноты в классе векторных функциональных систем // Математические модели сложных систем. - Киев: ИК АН УССР, 1973. С. 151-155.

[37] Ромов Б. А. О решетке подалгебр прямых произведений алгебр Поста конечной степени // Математические модели сложных систем. - Киев: ИК'АН УССР. 1973. С. 156-168.

[38] Ромов Б. А. О полноте на квадрате функций алгебры логики и в системе Р& х Pi //Кибернетика, 1987. Т. 4. С. 9-14.

[39] Ромов Б. А. Об одной серии максимальных подалгебр прямых произведений алгебр конечнозначных логик // Кибернетика, 1989. Т. 3.С. 11-16.

[40] Ромов Б. JI. О функциональной полноте в системе Р2 х

F* //Кибернетика, 1991. Т.1. С. 1-8.

[41] Rosenberg I. G. La structure des fonctions de plusieurs

variables sur un ensemble fini// C.R.,Acad. Sci. Paris. Ser. A,B. 1965. V. 260. P. 3817-3819.

[42] Rosenberg I. G. Universal algebras with all operations of

boundid range // Colloq. math. 1974. V. 30, № 2. P. 177185.

[43] Salomaa A. On basic groups for the set of functions over

a finite domain // Ann. Acad. Sci. Fennicae. A. 1. 1963. №338. P. 3-15.

[44] Slupecki J. Kriterium pelnosci wielowartosciowich systemow

logiki zdan // Comptes Rendus des Seances de la Societe des Sciences et des Letters de Varsovie, Cl III. 1939. V. 32. P. 102-128.

[45] Taylor W. Hyperidentities and hypervarieties //

Aequationes Math. 1981. V. 23, № 1. P. 30-49.

[46] Тайманов В. А. О декартовых степенях Р2 // Доклады АН СССР, 1983. Т. 270, № 6. С. 1327-1330.

[47] Яблонский С. В. О функциональной полноте в трехзначном исчислении // ДАН СССР. 1954. Т. 95, № 6. С. 1152-1156."

[48] Яблонский С. В. Функциональные построения в k-

значной логике. - В кн.: Труды МИ АН СССР. - М.: Изд-во АН СССР, 1958. Т. 51. С. 5-142.

[49] Янов Ю. И., Мучник А. А. О существовании k-значных замкнутых классов, не имеющих конечного базиса //

Докл. АН СССР, 1959. Т. 127, № 1. С. 44-46.

МАЛЬЦЕВ Иван Анатольевич Итеративные алгебры, близкие к транзитивным

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

Подписано в печать 11.06.04. Формат 60x84 1/16. Печать офсетная. Усл. печ. л 1,5. Уч.-изд. л. 1,5. Тираж 100 экз. Заказ №42.

Отпечатано на полиграфическом участке ИМ СО РАН, пр. Академика Коптюга, 4, 630090 Новосибирск, Россия.

04

- 1 4850

! Г

v^'i

Введение

0.1 О суперпозициях функций .I

0.2 Обзор основных результатов .уш

1 Клетки и клеточные алгебры

1.1 Итеративные алгебры.

1.2 Транзитивные полугруппы.

1.3 Структурные свойства.

1.4 Свойства базисов.

1.5 Максимальные подалгебры.

1.6 Число подалгебр.

2 Решетка подклонов клона Бурле

2.1 Строение нижней части решетки.

2.2 Решетка подклонов клона 2о.

2.3 Клоны типов «ТС, 2/С, ^/С, «ТС при /С <

2.4 Другие подклоны клона ^и^, порождаемые с помощью унарных функций из .'.

2.5 Подклоны клона Ео и ¿2, порождаемые с помощью многоместных функций из

3 Гомоморфизмы

3.1 Конгруэнции на клетках.

3.2 Конгруэнции на некоторых подалгебрах клеток

3.3 Гомоморфизмы итеративных алгебр и свойства оснований этих алгебр.

3.4 Конгруэнции на клеточных подалгебрах.

3.5 Гомоморфизмы вполне ограниченных расширений итеративных алгебр

3.6 Автоморфизмы.

3.7 Инварианты.

4 Гипертождества

4.1 О разделении клонов гипертождествами.

4.2 Гиперподстановки.

4.3 Некоторые приложения.

4.4 Выделение гипертождествами квазиклеток.

5 Согласованные произведения

5.1 Транзитивные полугруппы в произведениях итеративных алгебр.

5.2 Теорема Слупецкого.

0.1 О суперпозициях функций

Суперпозиция, то есть замена одной из переменных функции также функцией, является одним из простых и естественных способов получения новых функций из уже имеющихся. Возникающая в результате суперпозиций функция называется сложной. Одни свойства исходных функций наследуются сложной функцией, другие же не сохраняются. Например, при суперпозиции возрастающих функций получается также возрастающая функция. Закономерный интерес вызывает вопрос, можно ли всякую функцию, обладающую каким-то заданным свойством, получить при помощи суперпозиций из функций, обладающих тем же свойством, но зависящих от меньшего числа переменных. В качестве свойства обычно выбирается непрерывность, дифференцируемость и т. п.

Упомянем лишь некоторые результаты в указанном направлении, полученные отечественными математиками А. Г. Витушкиным, А. Н. Колмогоровым и В. И. Арнольдом. Если натуральные числа га, п, гах, п\ удовлетворяют неравенству га т1 — > —, п П\ то, как доказал А. Г. Витушкин [9], существует зависящая от га переменных п раз дифференцируемая функция, которую нельзя получить суперпозициями из щ раз дифференцируемых функций, зависящих от Шх переменных. А. Н. Колмогоров [32] и В. И. Арнольд [1] доказали, что каждая вещественная непрерывная функция представима в виде суперпозиции непрерывных функций, зависящих от двух переменных. Любую непрерывную функцию от нескольких переменных можно получить при помощи суперпозиций из функции х-\-у и непрерывных функций, зависящих от одного аргумента (Колмогоров, [33]).

В приведенных выше примерах решаемые задачи можно сформулировать следующим образом.

Каким-то способом заданы два множества функций М\ и Мъ- Можно ли каждую функцию из множества М\ получить суперпозициями функций, принадлежащих множеству М2 ?

К этой задаче близка следующая.

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

Функции, получаемые при помощи суперпозиции из функций класса К, образуют множество [К], называемое замыканием класса К. Класс К называется порождающим для своего замыкания. Если К = [К], то класс [К] называется замкнутым. Описание множества [М2] ведет к решению первой из указанных выше задач: функции из множества М\ можно получить суперпозициями функций, принадлежащих множеству Мг тогда и только тогда, когда множество М\ является подмножеством замыкания множества Мг. Однако решение первой задачи может и не зависеть от решения второй.

Рис. 1. Решетка Поста.

Задача описания замыкания множества функций М имеет смысл только при существенных ограничениях на входящие в М функции. Одним из таких ограничений является фиксирование числа элементов в множестве, на котором определены функции из М. Э. Постом [60, 61] описаны все замкнутые классы функций, определенных на множестве из двух элементов. По включению эти классы образуют решетку, изображенную на рисунке 1, называемую решеткой Поста.

На множестве из трех элементов имеется континуум замкнутых классов ([97]), образующие решетку очень сложного строения, поэтому приходится дополнительно ограничивать множество изучаемых классов.

Замкнутые классы функций и свойства порождающих их систем изучались во многих работах по математической логике, поскольку операции, определенные на конечном множестве, используются при интерпретации связок в различных исчислениях. Формулам при таких интерпретациях отвечают сложные функции, принадлежащие замкнутым классам, порождаемым этими операциями. Особое внимание привлекала проблема полноты: найти условия, необходимые и достаточные для того, чтобы система функций, определенных на конечном множестве, порождала замкнутый класс, содержащий все функции, определенные на этом множестве. Как уже говорилось, проблема полноты в классе всех функций, определенных на множестве из двух элементов, была решена Э. Постом. Задача оказалась намного сложнее в случае, когда функции определены на множестве, содержащем более двух элементов. Одну из первых работ в этом направлении опубликовал в 1939 г. Я. Слупецкий [83]. Он доказал, что каждая полная система функций должна содержать существенно многоместную функцию, принимающую все возможные значения. Такую функцию принято называть функцией Слупецкого. В 1954 г. С. В. Яблонский [92, 93] решил проблему полноты для случая, когда функции определены на множестве из трех элементов. Затем в течение 10 лет появилось много работ, в которых указывались достаточные условия полноты системы функций. Окончательно проблема полноты была решена И. Розенбергом [66] в 1965 году.

Стоит отметить, что упомянутую ранее теорему А. Н. Колмогорова [33] о том, что функция х -\-у вместе со всеми непрерывными одноместными функциями порождает все непрерывные функции, можно рассматривать в качество аналога теоремы Слупецкого. Определенные топологические аналоги теоремы Колмогорова были позже найдены А. А. Мальцевым [301.

В теории универсальных алгебр важную роль играют классы функций, замкнутых относительно суперпозиций и содержащие все проекции, то есть функции вида е]'(х\,., х„) = Х\. Эти классы называются клопами. Две алгебры А1 = (А/; Fl) и А2 = (А/; /^2) одинаковыми носителями называются рационально эквивалентными, если множества их основных операций порождают один и тот же клон. Ввиду этого описание с точностью до рациональной эквивалентности различных универсальных алгебр, определенных на каком-то множестве, сводится к описанию всех клонов на этом множестве.

Клоны можно рассматривать как алгебры, например, как содержащие функцию е\{х\,Х2) нредитеративные алгебры, введенные А. И. Мальцевым |41|. Предитера,тивным,и алгебрами называются подалгебры прсОи-теративной алгебры Поста О а = {О а', С г? А? *) тина (1,1,1.2), в которой Оа ~ множество всех операций, определенных на множестве А. Определения операций т, Д, * приведены в разделе 1.1. В совокупности они заменяют суперпозицию, которая не является алгебраической операцией. Поскольку элементами носителей иредитеративных алгебр являются функции, гомоморфизмы таких алгебр бывают двух видов: сохраняющие арность функций и не сохраняющие арности. Отвечающие им конгруэнции соответственно называются подарностными и внеарност-ными. Сохраняющий арность гомоморфизм клона, отображающий каждую проекцию е" одного клона в такую же проекцию е" другого клона называется клоповым.

Обозначим через Т(А) клон, порождаемый основными операциями алгебры А, а через Var А многообразие, порождаемое алгеброй А. Взаимосвязь между клоновыми изоморфизмами клонов Т{ А) и Т'(В) и строением многообразий Var А и Var В найдена А. И. Мальцевым [41]. Фактически им была доказана более сильная теорема, так как утверждение остается верным, если в формулировке и в доказательстве вместо изоморфизмов говорить о клоновых гомоморфизмах. Эта теорема осталась незамеченной и затем была заново открыта в работах ряда авторов (см., например, [71], иное доказательство приведено в [23]). Утверждение, о котором идет речь, можно сформулировать следующим образом.

Возьмем два непустых множества А и А'. Пусть А = (A; {/^j-iej) — некоторая алгебра, а С' — какой-то клон функций, определенных на множестве А'. Клоповый гомоморфизм кр : Т(А) —* С', отображающий Т( А) на С', существует тогда и только тогда, когда существует такое отображение <р' : Т(А) —* С', что алгебра А' = (А'\ (у?'(//1)ге/) принадлежит многообразию Var А (и С = Т{А')).

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

Тождество t ~ t' называется гипертождеством алгебры А, если t = t' тождественно выполняется в А при любой замене символов oneраций, входящих в термы £ и £', термальными функциями алгебры А соответствующей арности. Тождества в клонах называются клоповыми тождествами. Клоновые тождества алгебры Т(А) соответствуют гипертождествам алгебры А [84].

Следующие примеры [24] показывают, что тождества и гипертождества могут применяться в теории логических сетей. Изобразим логический элемент с двумя входами и одним выходом, реализующий конъюнкцию, следующим образом:

- к

->

Тогда сложная составная переключающая схема может быть заменена этим элементом в любом месте сети, так как х&,{х&,{х&,у)) = х&,у тождественно выполняется в двухэлементной булевой алгебре (0,1; &, -/V) (а потому и в любой булевой алгебре). Если является произвольным переключающим элементом с двумя входами и одним выходом, реализующим какую-то бинарную булеву функцию д(х,у), то составную переключающую схему можно заменить элементом

-> g

-> какой бы не была функция д, поскольку

F(x,F(x,F(x,y)))*sF(x,y) является гипертождеством алгебры (0,1;&, N).

Гипертождества позволяют кратко формулировать признаки полноты системы функций. Например, система булевых функций S полна тогда и только тогда, когда равенство

F(F(x, у), F(x, у))) « F(F(:г, х), F(y, у)) не является гипертождеством алгебры (0,1; S).

0.2 Обзор основных результатов

Для любого множества функций F С Ok через п € N,, обозначим множество всех функций из F, зависящих ровно от п переменных, через — множество всех функций из F, принимающих не более п значений, через F^ — множество всех функций из F, принимающих ровно п значений. Отметим, что множество относительно операции * является полугруппой. Порождаемую множеством подалгебру алгебры Va, образованную всеми существенно одноместными функциями из А, обозначим через Полугруппа одноместных функций называется s раз транзитивной, если для любых попарно различных чисел ai,., ая и любых чисел Ъ\,., bs в ней найдется такая функция /, что f(a¡) = bh i - М.

Итеративная алгебра называется клеточной (А. И. Мальцев |43|), если она состоит из всех существенно одноместных функций и всех существенно многоместных функций, принимающих не более s значений. Клеточная алгебра имеет вид U V^ и далее часто будет обозначаться через Us. Подалгебра образованная всеми функциями, принимающих не более s значений,называется ее основной клеткой.

А. И. Мальцевым [41] доказана структурная теорема, обобщающая известные теоремы Слупецкого [83] и С. В. Яблонского [93|. Опуская особые случаи, ее можно сформулировать следующим образом.

Итеративная алгебра, порождаемая функциями из s раз транзитивной полугруппы вместе с существенно ■мпого.местпой (функцией f, принимающей т значений, codepoicum клетку v]?'^ и все функции, значения которых принадлежат множеству значений функции f, если 2 < m < s +1.

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

1. Арнольд В. И. О функциях трех переменных // ДАН СССР, 1957, т. 114, №, с. 679-681.

2. Bagyinszki J., Demetrovics J. The lattice of linear classes in prime-valued logics ¡I Discrete mathematics, Banach center publ. Warsaw. 1982. V. 7. P. 105-123.

3. Байрамов P. А. О предикатной характеризуемости подалгебр многозначной логики II Изв. АН АзССР. Сер. физ.-техн. и мат. наук. 1969. т. С. 100-104.

4. Berman J., McKenzie. Clones satisfying the term condition // Discrete math. 1984. V. 52. P. 7-29.

5. Birkhoff G. Lattice Theory // Amer. Math. Soc. Colloq. Pub. 25, 1948. (Русский перевод: Биркгоф Г. Теория структур. 11 ИЛ., М.: 1952.)

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

7. Webb D. Generation of any n-valued logic by one binary operator // Proc. Nat. Acad. Sci. 1935. V. 21. P. 252-254.

8. W§glorz В. A representation theorem for Post-like algebras // Colloq. math. 1970. V. 30, №1. P. 35-39.

9. Витушкин А. Г. О многомерных вариациях // M.: Гос. издат. технико-теоретич. литературы. 1955.

10. Goetz A. On weak isomorphisms and weak homomorphisms of abstract algebras // Coll. Math. 1966. V. 14. P. 163-167.

11. Goetz A. A generalization of the notion of direct product of universal algebra // Colloq. Math. 1971. V. 22. P. 167-176.

12. Горлов В. В. О конгруэнциях на замкнутых классах Поста // Мат. заметки. 1973. Т. 13, вып. 5. С. 725-734.

13. Demetrovics J., Malcev I. A. On the depth of infinitely generated subalgebras of Post's iterative algebra Pz // Coll. math. soc. Janos Bolyai. Szeged, 1983. V. 43. P. 85-96.

14. Деметрович Я., Мальцев И. А. О существенно минимальных ТС-клонах на трехэлементном множестве // МТА SZTAKI Kozl. 1984. №32. С. 115-151.

15. Demetrovics J., Malcev I. A. Essentially minimal TC-clones on three-element base set // C.R. Math. Rep. Acad. Sci. Canada. 1986. V. 8, №3. P. 191-196.

16. Деметрович Я., Мальцев И. А. О строении клона Бурле на трехэлементном множестве // Институт математики СО АН СССР. Препринт №1, Новосибирск, 1987.

17. Деметрович Я., Мальцев И. А. О строении клона Бурле на трехэлементном множестве // Acta cybernetica. 1989. V. 9, №1. P. 1-25.

18. Demetrovics J., Malcev I. A. Essentially minimal TC-clones on three-element base set // The nineteenth int. symp. on multiple-valued logic. Guangzhou, China. 1989. P.220-227.

19. Denecke K. Boolean clones and hyperidentities in universal algebras // Universal and applied algebra. Proc. of the 5th universa algebra sympos. Turawa, Poland, 1988.

20. Denecke K. On varieties generated by Boolean clones. Potsdam, 1991. (Preprint).

21. Denecke K., Lau D., Poeschel R., Schweigert D. Hyperidentities, hyperequational classes and clone congruences. Contributions to General Algebra N 7, Verlag Hoelder-Pichler-Tempsky. Wien, 1991, Verlag BG Teubner, Stuttgart.

22. Денеке К., Мальцев И. А. Разделение клонов гипертождествами // Сиб. мат. журн. 1994. Т. 35, №2. С. 310-316.

23. Денеке К., Мальцев И. А., Решке М. О разделимости клонов гипертождествами // Сиб. мат. журн. 1995. Т. 36, №5. С. 1050-1066.

24. Denecke К., Poeschel R. The characterization of primal algebras by hyperidentities // Contributions to general algebra 6. Wienna: Hoelder-Pichler-Tempsky, 1988. Bd 6. S. 67-68.

25. Denecke K., Reichel M. Funktionalgleichungen in zweiwertigen Logiken // Wiss. Z. Padagog. Hochsch. "Karl Libknecht" Potsdam. 1988. Bd 32, №3. S. 603-606.

26. Denecke K., Schweigert D. Hyperidentities and completeness properties of finite algebras // Preprint, 1986.

27. Denecke K., Wismath S. L. Hyperidentities and clones // Amsterdam: Gordon & Breach Publ., 2000.

28. Epstein G. The lattice theory of Post algebras // Trans. Amer. Math. Soc. 1960. 95, №. 300-317.

29. Ермолаева H. M., Мучник А. А. Функционально замкнутые четырехзначные расширения алгебры Буля и соответствующие логики // Исследования по неклассическим логикам и теории множеств. -Москва: Наука, 1979. С. 298-315.

30. Keisel Н. J. Limit ultrapowers // Trans. Amer. Math. Soc. 1963. V. 107. P. 382-497.

31. Колмогоров А. H. О представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных // ДАН СССР, 1956, т. 108, №2, с. 179-182.

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

33. Lampe W. A. Abstract 777Т-А120. // Notices Amer. Math. Soc. 1977. №24. A-371.

34. Lau D. Prävollständige Klassen von Pkj // EIK. 1975. №11. S. 624-626.

35. Lau D. Kongruenzen auf gewissen Teilklassen von Pk,i // Rostock, math, kolloq. 1977. №3. S. 37-43.

36. Lau D. Klassen quasilinearen Funktionen von Pz // Rostock, math, kolloq. 1985. №28. S. 33-45.

37. McKenzie R. N., Taylor W. Interpretations of module varieties //J-Algebra. 1990. V. 135, №2. P. 456-493.

38. Мальцев А. А. Топологический вариант теоремы Слупецкого для некоторых компактов // ДАН СССР. 1969. Т. 188, №1. 33-36.

39. Мальцев А. И. Симметрические группоиды // Мат. сб. 1952. Т. 31, вып. 1. С. 136-151.

40. Мальцев А. И. Итеративные алгебры и многообразия Поста // Алгебра и логика. 1966. Вып. 5, №2. С. 5-24.

41. Мальцев А. И. Об одном усилении теорем Слупецкого и Яблонского // Алгебра и логика. 1967. Вып. б, №3. С. 61-75.

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

43. Мальцев И. А. Некоторые свойства клеточных подалгебр алгебр Поста и их основных клеток // Алгебра и логика. 1972. Вып. 11, №5. С. 571-587.

44. Мальцев И. А. Конгруэнции и автоморфизмы на клетках алгебр Поста // Алгебра и логика. 1972. Вып. 11, №6. С. 666-672.

45. Мальцев И. А. Некоторые свойства клеток алгебр Поста. // Дискретный анализ. 1973. №23. С. 24-31.

46. Мальцев И. А. О конгруэнциях на подалгебрах итеративных алгебр Поста. // Дискретный анализ. 1976. №29. С. 40-52.

47. Мальцев И. А. Гомоморфизмы вполне ограниченных расширений итеративных алгебр Поста // Rostock. Math. Kolloq. 1979. №11. P. 85-92.

48. Мальцев И. А. Инварианты квазиклеток итеративных алгебр Поста // Сиб. мат. журн. 1985. Т. 26, №1. С. 220-223.

49. Мальцев И. А., Швайгерт Д. Гипертождества QZ-алебр // Сиб. мат. журн. 1989. Т. 30, №6. С. 132-139.

50. Malcev I. Graduated products of Post algebras // Note on multiple-valued logic. 1995. V. 18, №13. P. 1-4.

51. Malcev I. Coordinated products of iterative algebras // Proc. VIII int. conf. on logic and сотр. sci. Novi Sad, Yugoslavia. 1997. P.1-2.

52. Мальцев И. А., Тугылбаева Б. Г. Произведения итеративных алгебр // Сиб. мат. журн. 1999. Т. 40, №1. С. 102-112.

53. Malcev I. Slupecki subalgebras in coordinated products of iterative algebras // Multi. val. logic. 2000. V. 5, pp. 1-13.

54. Марченков С. С. О замкнутых классах квазилинейных функций в Р3 // Препринт №17 ИПМ АН СССР. 1986.

55. Марченков С. С. О полноте в системе Р3 х Рз // Дискретная математика. 1992. Т. 4, т. С. 126-145.

56. Марченков С. С. О классах Слупецкого в системах Р& х . х Рк // Дискретная математика. 1992. Т. 4, №3. С. 135-148.

57. Machida Н. Toward a classification of minimal closed sets in 3-valued logic // Proc. 12th int. symp. on multiple-valued logic. Paris, 1982. P. 313-317.

58. Poeschel R., Kaluznin L. A. Funktionen und Relationenalgebren // Berlin: Deutscher Verlag der Wissenschaften, 1979.

59. Post E. Introduction to a general thery of elementary propositions / / Amer. J. Math. 1921. V. 43. P. 163-185.

60. Post E. Two-valued iterative systems of mathematical logic. Princeton Univ. Press., 1941.

61. Reichel М., Schweigert D., Simovici D. A. A completeness criterion by functional equations // Proc. 17th int. symp. on multiple-valued logic. Boston, 1987. P. 2-4.

62. Reichel M. Hyperidentitäten in zweielementigen Algebren // Diplomarbeit PH Potsdam, 1988.

63. Reschke M., Denecke К. Ein neuer Beweis für die Ergebnisse von E. L. Post über abgeschlossene Klassen Boolescher Funktionen // J. Inform. Process. Cybernet. 1989. V. 25, N 7. P. 361-380.

64. Reschke M., Lueders O., Denecke K. Kongruenzdistributiviaet, Kongruenzvertauschbarkeit und Kongruenzmodularität zweielemetiger Algebren // J. Inform. Process. Cybernet. 1988. V. 24, №1/2. P. 6578.

65. Rosenberg I. G. La structure des fonctions de plusieurs variables sur un ensemble fini. // C.R. Acad. Sei. Paris. Ser. A,B. 1965. V. 260. P. 3817-3819.

66. Rosenberg I. G. Uber die funktionale Vollständigkeit in dem mehrvertigen Logiken von mehreren Verändlichen auf endlichen Mengen // Rozpravy Cs. Akademie Ved, Ser. Math. Nat. Sei. 1970. V. 80. P. 3-93.

67. Rosenberg I. G. Strongly rigid relations // Rocky mountains j. of math. 1973. JV®3. P. 631-639.

68. Rosenberg I. G. Universal algebras with all operations of boundid range // Colloq. math. 1974. V. 30, №. P. 177-185.

69. Rosenberg I. G. Clones containing the direct square of a primal algebra. // Proc. of the 12 int. symposium on multiple-valued logic. CNAM, Paris. 1982. P. 30-34.

70. Rosenberg I. G. Mal'cev algebras for universal algebra terms. Berlin: Springer, 1990. (Lecture Notes in Comput. Sci.).

71. Rosenblum P. C. Post algebras. 1. Postulates and general theory. // Amer. j. math. 1942. V. 64, m. P. 35-39.

72. Ромов Б. А. Алгоритм решения проблемы полноты в классе векторных функциональных систем // Математические модели сложных систем. Киев: ИК АН УССР, 1973. С. 151-155.

73. Ромов Б. А. О решетке подалгебр прямых произведений алгебр Поста конечной степени // Математические модели сложных систем. Киев: ИК АН УССР. 1973. С. 156-168.

74. Ромов Б. А. О полноте на квадрате функций алгебры логики и в системе Pk х Pi // Кибернетика, 1987. Т. 4. С. 9-14.

75. Ромов Б. А. Об одной серии максимальных подалгебр прямых произведений алгебр конечнозначных логик // Кибернетика, 1989. Т. 3. С. 11-16.

76. Ромов Б. А. О функциональной полноте в системе Р2 х Рк // Кибернетика, 1991. Т. 1. С. 1-8.

77. Salomaa A. On basic groups for the set of functions over a finite domain // Ann. Acad. Sci. Fennicae. A. 1. 1963. №338. P. 3-15.

78. Salomaa A. On infinitely generated sets of operations in finite algebras // Ann. Univ. Turkuensis. 1964. V. 74. P. 1-13.

79. Scendrei A. On closed sets of linear operations over a finite set of square-free cardinality // EIK. 1978. V. 14. P. 547.

80. Scendrei A. Clones in universal algebra // Montreal: Les presses de l'universite de Montreal, 1986.

81. Slupecki J. Kriterium pelnosci uuielowartosciowich systemow logiki zdan // Comptes Rendus des Seances de la Société des Sciences et des Letters de Varsovie, Cl III. 1939. V. 32. P. 102-128.

82. Taylor W. Hyperidentities and hypervarieties // Aequationes Math. 1981. V. 23, №1. P. 30-49.

83. Taylor W. Some applications of the term condition // Algebra universalis. 1982. V. 14. P. 11-24.

84. Тайманов В. А. О декартовых степенях Р2 // Доклады АН СССР, 1983. Т. 270, № 6. С. 1327-1330.

85. Traczyk T. Axiomes and some properties of Post algebras // Colloq. Math. 1963. V. 10. P. 193-209.

86. Schweigert D. Clones of term functions of lattices and abelian groups 11 Algebra universalis. 1985. V. 20. P. 27-33.

87. Schweigert D. Hyperidentities and clone congvruences // Proc. Mal'cev-conference. Novosibirsk, 1989.

88. Schreier I. Uber Abbildungen einer abstrakten Menge auf ihre Teilmengen // Fundamenta Mathematicae, 1937, V. 28, P. 261-264.

89. Csakany B. All minimal clones on the three-element set // Acta Cybernetika. 1983. V. 6. P. 227?

90. Яблонский С. В. О функциональной полноте в трехзначном исчислении // ДАН СССР. 1954. Т. 95, Ж. С. 1152-1156.

91. Яблонский С. В. Функциональные построения в k-значной логике. В кн.: Труды МИ АН СССР. - М.: Изд-во АН СССР, 1958. Т. 51. С. 5-142.

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

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

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