О полноте и A-полноте S-множеств детерминированных функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

Подколзина Мария Александровна

О ПОЛНОТЕ И А-ПОЛНОТЕ Э-МНОЖЕСТВ ДЕТЕРМИНИРОВАННЫХ ФУНКЦИЙ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

О 3 ОЕЗ 2011

Москва - 2011

4853774

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

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор фнз.-мат. наук, профессор Буевич Вячеслав Александрович; доктор физ.-мат. наук, профессор Угольников Александр Борисович; кандидат физ.-мат. наук, доцент Карташов Сергей Иванович Вычислительный центр имени А.А.Дородницына РАН

Защита диссертации состоится 18 февраля 2011 г., в 16ч. 45 м. на заседании диссертационного совета Д 501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж)

Автореферат разослан 18 января 2011 г.

Ученый секретарь

диссертационного совета Д 501.001.84 доктор физико-математических наук, профессор

А.О. Иванов

Общая характеристика работы

Актуальность темы

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

Центральное место среди функциональных систем принадлежит итеративным функциональным системам, представляющим собой множество дискретных функций с операциями итерации — суперпозиции, обратной связи, а также их модификациями.1'2

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

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

Развитие теории итеративных функциональных систем шло по пути изучения конкретных моделей функциональных систем. В 1921 году Е. Постом была полностью описана структура замкнутых классов в двузначной логике. В 1954 году C.B. Яблонским3 была решена проблема полноты в трехзначной логике. После появления этой работы C.B. Яблонского усилия многих авторов были сосредоточены на решении проблемы полноты в произвольных fc-значиых логиках.

Это объясняется прежде всего тем, что, во-первых, в большинстве реальных моделей истинностных функциональных систем функции, как правило, коиечнозначны и, во-вторых, любая функция в каждой истинностной функциональной системе аппроксимируется функциями к-значных логик путем увеличения числа к. Критерий полноты в ï\ может быть сформулирован с использованием понятия предполпого класса.

В уже упоминавшихся работах Е. Поста4 и С.В.Яблонского решение задач о полноте в двузначной и трехзначной логиках как раз и было

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

2Ма1ьцов А.И. Итеративные алгебры Яостд-Новоснбирск, Нзд-во СО АНСССГ, 1976

3 Яблонский C.B. Функциональные построения в к-значных логиках. Труды математического

института им. В.А. Стеклова АН СССР, 1958, [.51, с.5-142

'Post Е. Two-valued iterative systems of mathematical logic. Pririsrorl, [O il

достигнуто путем явного описания множества предполных классов; при этом оказалось, что в А пять, а в Рц восемнадцать таких классов. Проблема явного описания множества предполных классов в P¡¿ для любого к > 4 долгое время оставалась открытой и оказалась довольно сложной. В 1964 году А.И.Мальцев исследовал задачу о полноте в четырехзначной логике. С.В.Яблонским, А.В.Кузнецовым,0 В.В.Мартынюком,6 JIo Чжу Каем,7'8 Паи Юн-цзе,9 Ban Сяо-хао,10 Лю Сюй-хуа, Е.В. Захаровой,11 И.Розепбергом12 были последовательно в явном виде построены все пред-полные классы в ¿-значных логиках. Важно отметить, что в этих работах использован аппарат сохранения функциями fc-значных логик отношений (предикатов), впервые введенный А.В.Кузнецовым. Именно на этом пути И.Розепбергом было проведено завершающее построение множества всех предполных классов в fc-значных логиках, а С.В.Яблонским, Е.Ю.Захаровой и В.Б.Кудрявцевым13 получена асимптотика их числа.

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

-но-детермипированпые функции (о.-д. функции), а в качестве операций — операции суперпозиции и обратной связи.

В наиболее общей постановке задача о полноте для о.-д. функций изучалась в работах В.Б.Кудрявцева14и М.И.Кратко.13 Как показано в вышеупомянутой работе М.И.Кратко не существует алгоритма для распознавания полноты конечных множеств о.-д. функций. Вместе с тем, функциональная система Р является конечнопорожденнон и совокуп-

^ Кузнецов A.D. Математика в СССР за сорок лет. Москва, 1959, т.1, с.102-115 сМартыиюк В.В Исследование некоторых классов функций в многозначных логиках. Проблемы кибернетики, вып.З, Москва, Паука, 19G0, с.49-60

' Ло Чжу Kaff, Лю Сюй-хуа. Предполние классы, определяемые бинаршлми отношениями в многозначных логиках. Acta Sei. natur. Univ. Yilinensis, 19G3, v.4

8Ло Чжу Кай. Прсдполные классы, определяемые нормальными k-арными отношениями о к-значной логике. Acta Sei. natur. Univ. Yilinensis, 1964, v.3

9 Пан Юн-цзе. Один разрешающий метод для отыскания всех предпатых классов в многозначных логиках. А с t.a Sei. natur. Univ. Yilinensis, 1962, v. 2

10Ван Сяо-хао Теория структур функций с отсутствием значений и фрикций без отсутствия значений. Acta Sei. natur. Univ. Yilinensis, 1963, v.2

"Захарова Е.Ю. Критерий полноты систем функций в Рк- Проблемы кибернетики, вып. 18, М., 1967, с.5-10

I2Rosenberg Y. Uber die functionate Vollständigkeit in den mehi~we.rt.igen Logiken. Praha, Rozpravi Ceskoslovenska Aeodemie Ved. v. 80, ЛЧ, p. 3-93,1970

13Захарова Е.Ю., Кудрявцев В.Б., Яблонский C.B. О предполных классах о к-значньег логиках. ДАН СССР, т. 136, №, стр.509-512, 1969

ИКудрявцев В.Б. О мощности множеств предполных множеств некоторых функциональных сист&ч, связанных с автоматами. Проблемы кибернетики, вьгп. 13, Москва, Наука, 1965, с.45-74 '"Кратко М.И. Алгоритмическая нер&)реыимость распознавания полноты для конечных автоматов ДАН СССР, 1964, т.155, №1, с.35-37

ность прсдполных классов образует минимальную критериальную систему в Р. Поэтому возникает вопрос: какова мощность множества пред-полпых классов в Р. В.Б.Кудрявцевым установлено, что эта мощность равна континууму.

В силу своего определения о.-д.функции являются бесконечными и даже континуальными функциями. Таким образом, предполагается, что вычисляющий любую о.-д.функцию автомат "работает" бесконечно долго. Однако с точки зрения приложений совершенно очевидно, что каждое реальное кибернетическое устройство (в том числе, автомат) но истечении некоторого конечного промежутка времени прекращает свою "работу'', т.е. либо становится ненужным, либо переводится в начальное, состояние. В связи с этим естественно возникает

Задача о полноте в последовательностпой функциональной системе PJ..

Пусть к > 2, г > 1. Элементами функциональной системы Р£ являются детерминированные функции, переменные которых принимают значения из ££ — множества всех слов длины т, составленных из букв алфавита Ек = {0,1,..., к — 1}. В качестве операций в функциональной системе PJ. рассматриваются операции суперпозиции и обратной связи. Заметим, что любая функция из Р£ может быть "вычислена" конечным автоматом за первые г тактов его работы.

Известно,10 что для решения задачи о полноте в Р[ операция "обратная связь" оказывается несущественной, т.е. в данном случае эта операция выразима через операции суперпозиции. Отсюда легко следует, что задача о полноте в копечнозпачпых логиках — одна из основных задач в теории истиностных функциональных систем, эквивалентна задаче о полноте в Pj., т.е. при т = 1. Вместе с тем, при т > 2 существует принципиальное различие между функциональной системой, элементами которой являются функции fc-зпачных логик, и функциональной системой РЦ. Множество всех детерминированных отображений, рассматриваемых на словах длины т, порождает специальное замкнутое подмножество в &т-зиачиых логиках, существенно зависящее от двух параметров — параметра к и параметра т. Используя естественную аналогию между задачей полноты в Р£и в конечнопорожденных замкнутых классах копечнозпачпых логик, можно ввести понятие предполного класса в PI и показать, что всякое множество является полным в Р(Г тогда и только тогда, когда оно целиком не содержится пи в одном из прсдполных в PJ. классов; совокупность прсдполных классов в Р[ конечна, может быть описана эффективно и образует минимальную критериальную систему для распознавания полноты систем функций из Р([; при этом множество

iu Кудрявцев В.Б., Алешнн C.B., Подколзнн A.C. Введение в теорию автоматов. Москва, Наука,

1983. "

предполных классов в Р^ совпадает с множеством прсдполных классов в Рк. Таким образом, в отличие от задачи о полпотс в Р для любых к > 2, т > 1 существует алгоритм для распознавания полноты в произвольных конечных множеств д.функций. Так же, как в &-значных логиках, каждый из этих алгоритмов может быть задан с использованием эффективно описываемых критериальных систем, а наилучший из них получается на пути явного описания всех предполных классов в

В общем случае для любых к > 2, т > 1 задача о полноте в РкГ решена В.А.Буевичем.17'18'19,20 В терминах сохранения отношений описаны псе предполаые классы в Р[. Однако это описание оказалось довольно сложным. В частности, отношения, классы сохранения которых совпадают с предполными в Р£ классами, могут иметь любую арность от 1 до кт, а их число даже при малых к к т очень велико. В связи с этим естественной представляется задача об исследовании на полноту систем детерминированных функций, которые обладали бы некоторыми наперед заданными, но вместе с тем достаточно общими свойствами.

Диссертация посвящена рассмотрению задачи о полноте в так называемых Б-множеств, состоящих только из Э-функций — детерминированных функций, вычисляемых конечными автоматами, в каждом состоянии которых реализуется функция ¿-значной логики, принимающая все к значений. Легко видеть, что для любой функции /(а^,.... хп) из Р£ существует Б-функция д{х\,... ,хп,хп+1), также принадлежащая РЦ такая, что

/(хь ...,хп)= д{х ь ...,хп, хп).

По аналогии с общим случаем в диссертации введено понятие ¡3-предполного класса и показано, что произвольное Э-мпожество Ш С Р[ является полным в тогда и только тогда, когда ЯЛ не содержится ни в одном из Б-предполных в классов. Таким образом, возникает задача об описании множества всех Б-предполных в Р{. классов. Отметим, что эта задача в случае, когда г = 1, т.е. в Ахзпачных логиках, решена В.Б.Кудрявцевым.21

В диссертации с использованием аппарата сохранения отношений для любых к > 2, г > 1 представлено описание всех Б-предполных классов в Р£. Оказалось, что совокупность отношений, классы сохранения

пБуевич В.А. О т-полноте а класса автоматных отображений. Докл. АН СССР, 1980, Т. 252, .V' 5, с. 221-224)

18Буевич В.А, У&ювия А-полноты для конечных автоматов, ч.1 Москва., Изд-во МГУ, 1986

19Буевич В.А. Условия Л-па-июгпи (?лл конечных автоматов, ч.2 Москва, Изд-во МГУ, 1987

2нБуевпч В.А. О г- полноте в классе детерминированных- функций Докл. РАН, т.326, Л*!3, стр.399403, 1992

-'Кудрявцев В.Б. О свойствах .Ч-счппем функций к-зна*аюй логики. Е1ск1гошзс1ю 1пГог1паиоп8\'г;гугЬ(:кип^ ипс1 КуЬепюик. Е1К 9,1/2, с.8-105, 1973

которых совпадают с S-прсдполными, расподастся на шесть семейств — семейства Z{k,r), D(k.r), N(k,r), 1(к,т), Ь(к,т) и V(k,r). Семейство Z(k,r) состоит из унарных отношений, отношения, принадлежащие семействам D(k,r), N(k,r), 1(к.,т)и V(k,r) бинарны, а отношения, принадлежащие семейству L(k. т) имеют арность, равную четырем. При этом семейства Z(k, 1), D(k, 1), N(k, 1), I(k, 1) н L(k, 1) совпадают с теми, которые описаны в работе Кудрявцева В.Б. "О свойствах S-систем функций k-значной логики". Заметим, что каждый S-нредполньгй в PJ. класс является в то же время одним из предполных классов в однако описание S-нреднолных классов значительно проще, чем описаиие всех предполных классов в Р£, полученное В.А.Буевичем.

С задачей полноты в Р[ тесно связана задача об А-полноте в Р. Учитывая детерминированность функций из Р можно, очевидно, считать, что для всякого г > 1 эти функции определены также па всех наборах слов длины т. Пусть г > 1. О.-д.функция д(х\,... ,хп) и о.-д.функция f(x\,..., хп) являются г-эквивалентнымн, если для любого набора слов (аь ..., ап), каждое из которых имеет длину т. выполнено равенство g(ai...., а„) = /(аь •.., ап). Множества 11 и 91' из Р называются т-эквивалснтиыми, если для любой о.-д.функции }{х\,...,хп) из

в 91' существует r-эквивалентная ей о.-д.функция J'(xi,... ,хп) и наоборот. Подобным образом определяется и т-эквивалентность множеств ЯЛ из Р и Ш' нз PJ.. Множество 91 С Р называется А-полным, если для любого т > 1 замыкание множества ОТ т-эквивалентно Р[. Известно, что в общем случае не существует алгоритма для распознавания А-полноты конечных систем о.-д.функций. Поэтому представляет интерес поиск такого алгоритма для систем о.-д.функций, обладающих некоторыми наперед заданными свойствами.

Диссертация состоит из введения и двенадцати параграфов. В $$ 19 для любых к > 2, г > 1 дано полное решение задачи о S-полноте в Р1 — с использованием аппарата сохранения отношений описано множество всех S-предполпых в классов. Совокупность отношений, классы сохранения которых совпадают с S-прсдполными в классами разбивается на шесть семейств — семейства Z(k,T), D(k, т), iV(fc.r), 1(к, т), L(k,r)nV{k,T).

В $10 диссертации для любого к >2 представлена ассимптотика числа S-предполных классов при т, стремящемся к бесконечности.

В $11 диссертации для любых к > 2, т > 1 рассматривается задача, аналогичная классической задаче Слупецкого-Яблонского-Саломаа22'23,24

2гЯблонскнй C.B. Введение в àucKpcimtyio математику., Москва, Наука. 1986

23Slupeski Y. Kryterium jletnosci wielowartosciowych systemow loyici zdan. Comptes rendus des .seanse-s de la Société des Sciences et des Lettres de Varsovie, 102-109, 1939 2iSalomaa A. On basis giviips for the set of functions over a finite domain. Ann.Acad. Sci. Finnicae,

для ft-значных логик. Пусть S(.P¿"(1)) — множество всех S-функций из Р[, существенно зависящих только от одной переменной. Пусть — совокупность всех S-мпожеств ЯЯ таких, что S(P¿-(1)) С 9Л. Возникает вопрос: каковой должна быть минимальная критериальная система для распознавания полноты S-множсств, принадлежащих В терминах сохранения отношений эта критериальная система описапа. Очевидно, она состоит из тех и только тех S-предполиых в Р[ классов, которые содержат все одноместные S-функций из Щ.

Пусть / — произвольная о.-д.функция из Р. О.-д.функция / называется S-o.-д.функцией, если для любого т > 1 о.-д.фупкция / т-эквивалентпа некоторой S-функции из P¡.. По аналогии с предыдущим вводится понятие S-множества о.-д.функций. Пусть S(P( 1)) — S-миожсство о.-д.фупкций, зависящих от одной переменной. В $11 показано, что существует алгоритм для распознавания А-полноты S-множеств 971 таких, что 5(Р(1)) С Ш и 9Л \ 5(Р(1)) < оо.

В $12 диссертации при к = 2 задача об A-полноте обобщается гга случай, когда множество ЯЯ, содержащее в качестве подмножества множество S(P( 1)) состоит из произвольных о.-д.фупкций (не обязательно S-o.-д.функций). Показано, что и в этом случае задача об А-полното является алгоритмически разрешимой.

Цель работы

1) Для любых к > 2, т > 1 представить эффективное описание всех S-прсдполиых классов в функциональной системе

2) Получить ассимптотику числа S-прсдполных в РЦ классов при фиксированном к и при г, стремящемся к бесконечности.

3) Изучить вопрос о существовании алгоритма для распознавания А-полпоты S-множсств, содержащих все одноместные S-o.-д.функции.

4) Изучить вопрос о существовании алгоритма для распознавания A-полноты произвольных множеств о.-д.функций, содержащих все одноместные S-o.-д.функции.

Основные методы исследования

В диссертации используются методы дискретной математики и комбинаторного анализа.

Науная новизна

Результаты работы являются новыми и состоят в следующем:

1) С использованием аппарата сохранения отношений для любых к > 2, г > 1 полностью описано множество всех S-ирсдполных в Р]. классов. Множество отношений, классы сохранения которых совпадают с S-редполными распадается на шесть семейств - семейства Z(k, г), D{k, т), N(k.r), 1(к,т), Ь(к,т) и У(к.т).

Ser А 338, 1-15, 19G3

2) При произвольном, но фиксированном к > 2 установлено асимптотическое поведение числа 5-прсдполных классов при г стремящемся к бесконечности.

3) Для любых к > 2, т > 1 из множества всех отношений, описывающих Я-прсдполпыс в классы, выделены те отношения, классам сохранения которых принадлежат всс одноместные 5-функцин. На этом основании для любого к >2 указан алгоритм распознавания А-полноты ¿"-множеств, содерхащих всс й'-о.-д. функции, зависящие от одной переменной.

4) При к = 2 решена задача о существовании алгоритма для распознавания А-полноты произвольных систем о.-д. функций, содержащих все одноместные 5-о.-д. функции.

Теоретическая и практическая ценность

Диссертация носит теоретический характер.

Апробация результатов

Результаты диссертации докладывались автором на семинарах механнко-матсматичсского факультета МГУ им. Ломоносова:

- семинаре "Дискретный анализ" под руководством д.ф.-м.н, проф. С.В.Алешина, д.ф.-м.н, проф. В.А.Бусвича, к.ф.м.н, с.н.с. Носова М.В.;

- семинаре 'Теория автоматов" под руководством д.ф.-м.н, проф. В.Б. Кудрявцева;

- семинаре "Математические вопросы кибернетики" под руководством д.ф.-м.н, проф. О.М.Касим-Заде;

- семинаре "Функции многозначной логики и смежные вопросы" под руководством д.ф.-м.н, проф. А.Б.Уголыгакова.

А также на семинаре под руководством член-корр. РАН К.В.Рудакова в Вычислительном центре РАН и на следующих научных семинарах и конференциях:

- международной конференции "Интеллектуальные системы и компьютерные науки" ((Москва, МГУ им.Ломоносова, 2006);

- 9 международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О.Б.Лупанова (Москва, МГУ им.Ломоносова, 2007);

- международной конференции "Современные проблемы математики, механики и их приложений", посвященной 70-летию ректора МГУ академика В.А.Садовпичсго (Москва, МГУ им.Ломоносова, 2009);

- международных научных конференциях студентов, аспирантов и молодых ученых "Ломоносов" (Москва, МГУ им. Ломоносова, 2007, 2008, 2009 и 2010 гг.);

- научных конференциях "Ломоносовские чтения" (Москва, МГУ им.Ломоносова, 2007, 2008 и 2009 гг.);

Публикации

Основные результаты диссертации опубликованы в работах автора, список которых приведен в конце автореферата [1] — [7].

Структура и объем диссертации

Диссертация состоит из введения, 12 параграфов и списка литературы. Полный объем диссертации - 92 страницы, список цитируемой литературы содержит 61 наименование.

Краткое содержание работы

Пусть к > 2, т > 1, Ek = {0,1,..., к— 1}. Пусть Щ — множество всех слов длины г, составленных из элементов Ек• Произвольный элемент а, принадлежащий множеству Щ будем обозначать следующим образом: а = (о(1),..., а(т)). Пусть х, Х\,..., у, у\,... — переменные, принимающие значения из Етк. Всякую такую переменную (например, х) представим в виде х = (ж(1),. ■ ■ ,х(т)). Для любого t (1 < t < т) на множестве El введем отношение ^эквивалентности. Элементы ai и аг из El назовем i-эквивалентыми (oi аг), если ai(l) = а2(1),.. ■, oi(i) = аг(£).

Определение Пусть п > 1. Через Е1(п) обозначим множество

El х ... х Wk/

п

Пусть к > 2,т > 1. Функция f(xi,... ,хп), отображающая множество Е1(п) в El называется детерминированной (д.функцией), если для всякого t (1 < t < т) и для любой пары (ai,... ,ап).{а\,... ,а'п) наборов алиментов из El такой, что aj а[.....ап а!п, /(ai.....ап)

/(«',-• -"«'J-

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

Пусть — множество всех д.функций, зависящих от переменных, которые принимают значения из множества Етк. Будем считать, что на множестве задана операция суперпозиции. Пусть 971 С PJ,. Замыкание множества 9Л относительно этой операции обозначим [ЯЯ].

Определение Пусть к > 2, т > 1, Ш С Рк. Множество ЗЯ называется полным в Рк, если [ЯЛ] =

Известно,20 что для любых к > 2, т > 1 существуют конечные системы, полные в PJ..

В качестве примера такой полной системы будем рассматривать систему, состоящую из двух д.функций: д.фуикции д(х) — "задержки" и д.функции h(x 1,хг) — "штриха Шсффера".

Д. функция д{х) = у такова, что j/(l) = 1 и для любого t (1 < t < т — 1) y(t) = min{xi(t), X2(t)} 4-1 (modk).

25Гаврилов Г.П О функциональной полноте в счетгию-значшй логике. Проблемы кибернетики, вып. 15, Мжква, Наука, 1965, с.5-61

Определение Пусть к > 2, г > 1. Пусть D = {9ЛЬ ШТ2., • - ■ } - некоторая система подмножеств множества PJ.. Система D называется критериальной, если справедливо оле,'1ующее: множество ОТ С PJ. является полным в РдГ тогда и только тогда, когда ОТ не содержится целиком ни в одном из множеств системы D.

Из общих алгебраических соображений следует, что минимальной критериальной системой в Р£ является множество, состоящее из пред-полных классов в РЦ.

Определение Пусть к > 2. т > 1. Замкнутое множество 91 С Р[ называется преднолным классом в Р£, если 91 не является полным, но для любой д.функции f $ <ft замыкание множества U {/} совпадает с

П-

Имеет место 26'2''28

Теорема 1.1. Пусть к > 2, т > 1. Множество ОТ С Р£ является полным в тогда и только тогда, когда ОТ не принадлежит целиком ни одному из предполных в Pj. классов, причем число предполных классов в Р[ конечно.

Определение Пусть к > 2, т > 1. Пусть h > 1, Т = (ti,...,th) — произвольный набор положительных целых чисел такой,что max{£i,..., th) < т. Пусть El = El1 х ... х E[h. Произвольное непустое множество

h

R С Е% называется отношением, заданным на Е^, а число h — арпостыо этого отношения.

Определение Пусть к > 2, г > 1. Д.функция f(xi,...,xn) из Р£ сохраняет отношение R С если для любой совокупности (о},... ,al), ■ ■ • ЛаТ. • • •. ah) элементов из R набор (f(a\...., aj),..., f(a\,..., a£)) также принадлежит R. Множество ОТ С сохраняет отношение R, если каждая д.функция из ОТ сохраняет это отношение.

Множество всех д.функции, сохраняющих некоторое отношение II обозначим через U(R). Нетрудно видеть, что для любого R множество U(R) замкнуто.

Можно показать 26>27>28 что справедлива

Теорема 1.2. Пусть к > 2, г > 1. Для того, чтобы произвольное множество д.фуикций 2ЛС Pt; было полным в Р£ необходимо и достаточно, чтобы для любых h > 1, Т = (ti,..., th), R С Е^ таких, что max{£i,..., £/,} < т и U{R) не является полным в PJ., в ОТ содержалась д.функция, не сохраняющая отношения R.

Прежде, чем приступить к доказательству теоремы 1.2., введем нско-

2<iKoti П. Универсальная длгеб/м.Москва, Мнр, 19G8

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

2вМальцев А.И. Итеративные алгебры Поста. Новосибирск, Цзд-во СО АНСССР, 1976

торые понятия и докажем две леммы. Рассмотрим два семейства отношений — семейство Р\ и семейство Р-1-

Семейство Р(. Пусть Т\ = т х ... х т, А\ £ причем Ах —

кт

некоторый набор, содержащий все элементы множества Енекоторым образом упорядоченные. Пусть А\ = (01,..., ар)- Рассмотрим набор А = (йь ..., а*г) из такой, что для любого г (1 < г < кт) = д{а{). Отношение Л принадлежит семейству Р\ тогда и только тогда, когда Я является подмножеством Е^1, содержит элемент А\, но не содержит элемента А. Очевидно, для любого И из Р\ {/(й) Ф Р£.

Семейство Р>. Пусть В = ((6ц, Ьи), (Ь/^п-, ^к2т 2)) ~ набор, содержащий все элементы множества Е¡Г х Щ, некоторым образом упорядоченные. ПуСТЬ Т2 = Г X ... X Г, = (6ц, . . . , 6*;2п)> В2 = (¿12, • • • ; 6а;2г2).

Очевидно, В\ е Ё£2, В2 £ Е^2. Рассмотрим набор Б3 = (Ъ\,... такой, что для любого г (1 < г < к'1т) 6, = /¿(¿>г 1.6,2). Отношение Д прннадлжеит семейству Р2 тогда и только тогда, когда К является подмножеством Е^2, содержит элементы В\ и по не содержит элемента Д). Очевидно, для любого И из Р2 ¿/(Я) ф Р1Г.

В терминах сохранения отношений для любого к > 2 описаны 29 все предполные классы в Р£ при г = 1, т. е. в А, а в [1-4] в тех же терминах описаны все предполные классы в Щ для любых к > 2,т > 1. Следует отметить, что описание в общем случае является довольно сложным. Поэтому возникает вопрос об исследовании па полноту в Р£ систем, обладающих некоторыми наперд заданными, но в то же время достаточно общими свойствами.

Определение Пусть к > 2, г > 1. Пусть }{х\,...,хп) 6 РЦ. Д. функцию /(х{,..., хп) назов(!м Э-функцией, если в любом состоянии вычисляющего ее автомата реализуется функция /с-значной логики, не выпускающая ни одного значения из множества Е

Очевидно, д.фупкцня /г(х 1,0:2) является Б-фупкцией, а д.функция д(х) таковой не является.

Определение Пусть Ш С Р^. Множество Ш назовем Э-множеством, если любая д.функция из 9Я является Б-функцией.

Легко убедиться в том, что существуют {-¡-множества, образующие полные системы в Р£ и состоящие из конечного числа Б-функций.

Например, таковой является система, состоящая из Б-функции /1(2:1, Х2) и Б-функции д(х1,х2) = у такой, что у( 1) = 1, если 24(1) = 12(1) и у{ 1) = 2:1(1), если ц(1) ф 2:2(1); уЦ) = хх(г - 1), если ж:(1) = х2(1),...,

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

X\[t — 1) = z2(t — 1); X\(t) = X2(£); y(t) = X\(t), если существует t' < t такое, что xi(t') ф X2(i) (1 < i < r — 1).

Пусп. ОТ С Pf, причем ОТ, вообще говоря, не является S-мпожеством. Через 5(£/(ОТ)) обозначим подмножество ОТ, содержащее все S-функции из Ш1.

Определение Пусть к > 2. т > 1. Пусть D = {OTj, ОТ2, ■ • ■} — некоторая система подмножеств множества Р£. Систему D назовем S-крите-риальпой, если справедливо следующее: S-множество ОТ С PJ. является полным в Р1 тогда и только тогда, когда ОТ целиком не содержится пи в одном из множеств системы D.

Очевидно, любая критериальная система является также и S-критс-риальной. Однако обратное не верно. Пусть {9Ti,..., 9Im} — совокупность предполных классов в Р£. Тогда множество {S(9ti),..., S(9Tm)} образуют S-критериальную систему в РкГ.

Определение Пусть к > 2, г > 1. S-множество С Р£ называется S-прсдполным классом в PJ., если ОТ не является полным в Р[. по для любой S-функции f П замыкание множества 91U {/} совпадает с

Легко убедиться в том, что множество всех S-предполных классов в Рявляется подмножеством множества {¿'(•Jti)...., S(9Tm)}, но ис совпадает с ним.

Теорема 1.3. Пусть к > 2, т > 1. Любая S-критсриальпая система в в качестве своего подмножества содержит множество всех S-предполных классов. Пусть D = {ОТьОТг ...} — такая система. Множество ОТ; (г > 1) является S-иредполным классом в Р£ тогда и только тогда, когда для любого j > 1, j ф г ,ОТ; ОТ

Теорема 1.4. Пусть к > 2, т > 1. S-множество ЯЛ С PJ. является полным в Р£ тогда и только тогда, когда ОТ не принадлежит целиком ни одному из S-предполных классов.

Множество всех S-предполных классов в терминах сохранения отношений для всякого к >2 при т = 1 описано. 30,31 Интерес представляет аналогичное описание для любых к > 2, т > 1.

Рассмотрим шесть семейств отношении — семейства Z(k, т), D(k, т), N(k.T),I(k,T),L(k,T)nV(k,T).

Семейство Z(k,r) (Z(k,r) ф 0 для любых к > 2, т > 1. Унарное отношение 7? принадлежит семейству Z(k, т) тогда и только тогда, когда для некоторого t (1 <t < т) R С причем при т > 2, t > 2 имеет место следующее: для любого a £ E^-.a = (а(1),..., a(t — 1)) существуют a(t) е Ек, a'(t) € Ек такие, что a{t) ф a'(t), (а(1),..., a(t - 1 ),a(i))

30Кудрявцев В.Б. Теорема полноты д.гя одного класса автоматов без обратных связей. ДАН СССР, I960, т. 132, Л>2, с.272-274

31Гавршюв Г.П. О функциональной полноте в счетно-значной логике. Проблемы кибернетики,вып. 15, Москва, Наука, 19G5, с.5-64

и

принадлежит, а (а(1), ...,a(t — 1), o'(i)) не принадлежит R.

Семейство D(k,r) (D(k,T) ф 0 для любых к > 3, г > 1. Бинарное отношение R принадлежит семейству D(k,r) тогда и только тогда, когда для некоторого t (1 < t < т) R С Ек(2). R является определенным на Ек отношением эквивалентности, причем имеет место следующее. Существует принадлежащий R набор (а 1,02) такой, что ai(l) = 02(1),..., ai(t — 1) = ai(t — 1). Кроме того, для любого а £ Ef. существует а' £ El такое, что a(t) ф a'(t), набор (a, а') не принадлежит R и при г > 2, t > 2 a(l) = a'(l),..., a(t - 1) = a'{t - 1).

Семейство N(k, r) (N(k, г) ф 0 для любых к > 2, г > 1. Бинарное отношение R принадлежит семейству N(k, т) тогда и только тогда, когда для некоторого t (1 < t < т) R С Ек(2), существует определенная на Ек подстановка <хд, разлагающаяся в произведение циклов одинаковой простой длины р > 2, график которой совпадает c. R, причем, если т > 2, £ > 2 и набор (ai,a2) принадлежит R, то ai(l) = о2( 1), ■. •, «i(i — 1) = a2(t— 1). Таким образом, для любого a £ 0"д(а)) 6 Ли для всякого набора (аь аг) из R а,2 = cr^(ai).

Пусть к > 2. т > 1. Пусть Е — множество всех подстановок (перестановок), определенных на Е^- Пусть ( € {1,..., т} и Ф( — совокупность отображений множества Е*к в Е такая, что при t = 1 для любых <р € Фг, a 6 Ек, а' £ = <р{а'), а при г > 2, t > 2 для любых у? € Ф(,

a 6 a' € Е{ <р(а) = yj(a'), если a(l) = а'(1), ...,a(t- 1) = а'(£ - 1). Подстановку, которую отображение <р £ Ф1 ставит в соответствие элементу а £ Ек обозначим через <Jv(ay

Семейство 1(к,т) (1(к,т) ф 0 для любых к > 5, г > 1. Пусть /г > 5, m > 1. к = hm. Бинарное отношение /i принадлежит подсемейству lh{k,r) семейства отношений 1{к,т) если для некоторых t (1 < t < т), ip £ <&t имеет место следующее: R С Е\{2), набор (аьаг) принадлежит R тогда и только тогда, когда для любого г (1 < г < тп) г-ые компоненты чисел (T[f(a.i){0'i{t)),&<p{al){(i2{t)) при разложении их по степеням числа h различны, причем при г > 2, t > 2 aj(l) = 02(1),..., ai{t — 1) = — 1). Семейство отношений 1(к,т) есть объединение семейств 1/,(к, г), взятое по всем h > 5, таким, что hm = к, m > 1.

Пусть к = рт. где р — простое число, р > 2, m > 1. Пусть G = {Ек, ©) — произвольная элементарная абелева р-группа. В каждой такой группе всякий ненулевой элемент имеет порядок р. Пусть т > 1.

Семейство L(k. т) (L(k, т) ф 0 для любого т > 1, если /с = //", где р — простое число, р > 2, m > 1. Отношение R, арность которого равна четырем, принадлежит семейству Ь{к,т), если для некоторых t (1 < t < т) ip £ Фг имеет место следующее: R С Ек(4), набор (01,02,03^4) принадлежит R тогда и только тогда, когда a^ai)(ai(t)) Фс^а,)^^)) — <т?(а1)(аз(*)) ® ^(ooia-iiOJj причем при г > 2, t > 2 ai(l) = a2(l) =

а3(1) = а4(1), • • •, ai(t - 1) = a2{t - 1) = a3(t - 1) = a4(i - 1).

Заметим, что семейства отношений Z(k.r). D(fc. т), N(k,r), 1{к,т) и L(k. т) совпадают с семействами отношений, с помощью которых 30,31 описываются все S-предполные классы в fc-зиачных логиках.

Семейство V(k, т) (V(k, г) ф 0 для любых к > 2, т > 2. Бинарное отношение Я принадлежит семейству V(k, т), если для некоторых t (t < т), ^ € имеет место следующее: Я С ££(2), набор (ai,a2) принадлежит Я тогда и только тогда, когда либо ai(t — 1) = а2(£ — 1), ai(i) = а2(£), либо ai(i — 1) ф а2(£ — 1) и существует а 6 Е^ такое, что ai(t) = ст^(а1)(а), a2(t) = а^(а2)(а), причем при т > 3, t > 3 ai(l) = a2(l),...,a1(i-2) = a2(i-2).

Пусть к > 2, т > 1, т) — объединение семейств Z(k, т), D(k, г), A'(fc, г), т), L(k, т) и V(jfc: г).

В диссертации доказываются

Теорема 1.4. Пусть к > 2, г > 1. Произвольное S-множество ЯЛ С

является полным тогда и только тогда, когда ЯЛ не сохраняет ни одного отношения Я из W(k,r).

Теорема 1.5. Пусть к > 2, т > 1. Пусть 91 — произвольный S-предполный класс в Тогда существует отношение Я 6 W(k, т) такое, что 01 = S(U(R)).

Теорема 1.6. Пусть к > 2, т > 1. Пусть R € W(k, т). Тогда множество S(U(R)) образует S-прсдполный класс в PJ..

Теорема 1.7. Пусть к > 2, т > 1. Имеет место следующее

а) Пусть R 6 W(k. т), R! е т)\Д'(А:, г), Я ^ Л'. Тогда S{U(R)) ф S(U(R'))

б) Пусть Я € N{k.T), Я' € N{k,r). Тогда равенсто S(U(R)) = S(U(R')) равносильно тому, что одна из подстановок ctr и ац>, графики которых образуют отношения Я и Я' соответственно, является степенью другой.

Определение Пусть к > 2, т > 1, р(к.т) — число ¿ьпредполных в Р(к, т) классов.

Имеет место

Теорема 1.8. Пусть т —> оо. Тогда

р(2, г) ~ 3 • 22 , р(3, т) ~ 3 • б3*', р(4, г) ~ 244'1.

а, если к > 5, то р(к, т) ~ (р + 2)(/с!)*:Г \

Пусть N(2,t), L2(2, г), ¿з(3, т), ¿4(4, г), Iiik.r) — семейства отношений, таких, что класс сохранения любого отношения из этих семейств содержит все одноместные S-o.-д функции. Пусть Wi(k,r) — объединение этих семейств.

Пусть М — множество всех таких систем S-o.-д.функций ЯЛ из Р, что S(P(1)) С ЯЛ и множество ЯЛ \ S(P(1)) конечно.

Теорема 1.9. Пусть к > 2. Произвольное множество о.д. функций ЯЛ, принадлежащее совокупности S-множеств М, является А-полным тогда и только тогда, когда для любого т > 1 ЯЛ не сохраняет ни одного отношения из Wi(k,r)

Теорема 1.10 Пусть к > 2. Существует алгоритм для распознавания А-полноты произвольных систем о.-д.функций, принадлежащих множеству А/.

Пусть к — 2. Пусть N — множество всех систем 91 из Р, состоящее из произвольных о.-д.функций, таких что S(P( 1)) С 91 и множество ЭТ\5(Р(1)) конечно.

Теорема 1.11. Существует алгоритм для распознавания А-полноты систем о.-д. функций, принадлежащих множеству N.

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

Публикации автора по теме диссертации

[1] Буевич В.А., Подколзина М.А. Задача о полноте S-множеств детерминированных функций // Вестник Московского Университета. Серия 1. Математика. Механика., 2008, № 5, с. 57-59. (Подколзиной М.А. принадлежат теоремы 3, 4 и доказательство некоторых вспомогательных утверждений в теоремах 1, 2)

[2] Подколзина М.А. О числе S-предполных классов в функциональной системе Pj,. Вестник Московского Университета. Серия 1. Математика. Механика., 2008, № 6, с. 43-45

[3] Подколзина М.А. О полноте и А-полноте S-множеств детерминированных функций, содержащих все одноместные детерминированные S-функции Дискретная математика, том 21, вып.2, М., 2009, с. 75-88

[4] Буевич В.А., Подколзина М.А. Критерий полноты S-множеств детерминированных функций. Математические вопросы кибернетики.16, Москва. Физматлит, 191-238, 2007 (Подколзиной М.А. принадлежат результаты, изложенные в параграфах 4 (утверждения 7-14), 5, 6, 7, 8)

[5| Буевич В.А., Подколзина М.А. О полноте S-множеств детерминированных функций. Тезисы докладов 9 Международного семинара "Дискретная математика и ее приложения", Москва, 2007, с. 152-155

[6] Подколзина М.А. Об одной системе конечных множеств автоматных отображений, для которой задача об А-полноте алгоритмически разрешима. Тезисы докладов 9 Международного семинара "Дискретная математика и се приложения", Москва, 2007, с.175-176

[7] Подколзииа М.А. К задаче о полноте в-множеств детерминированных функций тезисы докладов международной конференции "Современные проблемы математики, механики и их приложений", Москва, 2009, с.370

Подписано в печать 17.01.2011 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 100 экз. Заказ № 1074 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

1 Основные понятия и результаты.

2 Отношения; тупиковые и приведенные отношения.

3 Понятие 7г-множества. Д-рефлексивные отношения.

4 Семейства отношений Gi(k,r), Ni(k,r), V\(к, г), Li(fc,r), Qo(*,T),Qi(A,T),Q2(fc,T).

5 S-тупиковые отношения. S-критериальность S-тупиковых отношений.

6 Критерий полноты в Р^. S-критериальные системы в Pk.

7 Семейства отношений {Z(k: 1), /3(к, 1),

D(k,l), L(k, 1), N{k, 1)}.

8 S-предполнота S-множеств, принадлежащих классам сохранения отношений из объединения семейств Z(k, 1), N(k, 1), D(k,l),L(k,l)nI(k,l).

9 Семейства отношений Z(k,r), D(k, г), N(k, т), I(к, т), г) и V(k, т). Доказательство теорем 1.4-1.7.

10 О числе S-предполных классов в функциональной системе

11 О полноте вР^и А-полноте S-множеств детерминированных функций, содержащих все одноместные детерминированные S-функции.

12 Об алгоритмической разрешимости задачи об А-полноте для систем ограниченно-детерминированных функций, содержащих все одноместные S-o.-д функции.

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

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

Центральное место среди функциональных систем принадлежит итеративным функциональным системам, представляющим собой множество дискретных функций с операциями итерации — суперпозиции, обратной связи, а также их модификациями [2,3]. Развитие теории итеративных функциональных систем шло по пути изучения конкретных моделей функциональных систем. В 1921 году Е.Постом была полностью описана структура замкнутых классов в двузначной логике — это описание, изложенное в монографии в 1941 году, по существу эквивалентно решению проблемы полноты для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции [4,5,6]. Интерес к изучению итеративных функциональных систем особенно возрос в начале 50-х годов прошлого века в связи с появлением ЭВМ и необходимостью синтеза сложных кибернетических устройств. В 1954 году С.В.Яблонским [7] была решена проблема полноты в трехзначной логике. После появления работы [7] усилия многих авторов были сосредоточены на решении проблемы полноты в произвольных к-значных логиках. Начиная с 60-х годов прошлого века наряду с &-значными логиками стали интенсивно изучаться итеративные функциональные системы, элементами которых являются автоматные отображения [8,9], функции счетнозначных логик [11,12]. Позже появились работы, связанные с изучением итеративных функциональных систем, содержащих в качестве элементов вычислимые функции [12,15], программы и схемы программ [13,16].

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

Как показано в [2] итеративные функциональные системы могут быть разделены на два типа: истинностные функциональные системы и после-довательностные функциональные системы. В первом случае функции, принадлежащие функциональной системе, вычисляются без использования, а во втором — с использованием "памяти".

Среди всех истинностных функциональных систем центральное место занимает функциональная система Р&, состоящая из функций к-значной логики и операций суперпозиции над ними. Это объясняется прежде всего тем, что, во-первых, в большинстве реальных моделей истинностных функциональных систем функции, как правило, конечнознач-ны и, во-вторых, любая функция в каждой истинностной функциональной системе аппроксимируется функциями /г-значных логик путем увеличения числа к. Критерии полноты в Р^ могут быть сформулированы с использованием понятия критериальной системы. Система замкнутых подмножеств множества Р/. образует критериальную систему в Р&, если из непринадлежности произвольного множества функций &-зиачной логики к каждому из подмножеств данной системы следует его полнота. Тривиальным примером критериальной в Р& системы является множество всех собственных замкнутых подмножеств множества Р&. Однако мощность этой критериальной системы континуальна и с ее помощью нельзя получить эффективный критерий полноты в Р^ [21]. Вместе с тем, в функциональной системе Р& существуют конечные полные системы, и любое замкнутое подмножество множества Р& расширяется до предполного в Р% класса (максимальной подалгебры), причем для любого к > 2 число предполиых в Р^ классов конечно. Нетрудно видеть, что всякий предполный класс принадлежит любой критериальной системе, а множество всех предполных классов образует минимальную критериальную систему в Р^. Таким образом, из явного описания множества всех предполных классов следует эффективный и наилучший в определенном смысле алгоритм для распознавания полноты произвольных конечных систем функций &-значной логики. В уже упоминавшихся работах Е.Поста и С.В.Яблонского [4,7] решение задач о полноте в двузначной и трехзначной логиках как раз и было достигнуто путем явного описания множества предполных классов; при этом оказалось, что в Р2 пять, а в Р3 восемнадцать таких классов. Проблема явного описания множества предполных классов в Р& для любого к > 4 долгое время оставалась открытой и оказалась довольно сложной. В 1964 году А.И.Мальцев исследовал задачу о полноте в четырехзначной логиках. С.В.Яблонским [7], А.В.Кузнецовым [21], В.В.Мартышоком [22], JIo Чжу Каем, Пан Юн-цзе, Ван Сяо-хао, Лю Сюй-хуа [23,24,25,26], Е.В.Захаровой [27], И.Розенбергом [28] были последовательно в явном виде построены все предполные классы в &-значных логиках (см. также [29]). Важно отметить, что в этих работах использован аппарат сохранения функциями &-значных логик отношений (предикатов), впервые введенный А.В.Кузнецовым. Именно на этом пути И.Розенбергом было проведено завершающее построение множества всех предполных классов в &-значных логиках, а С.В.Яблонским, Е.Ю.Захаровой и В.Б.Кудрявцевым получена асимптотика их числа [30].

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

В наиболее общей постановке задача о полноте для о.-д. функций изучалась в работах В.Б.Кудрявцева [31] и М.И.Кратко [32]. Как показано в

32] не существует алгоритма для распознавания полноты конечных множеств о.-д. функций. Вместе с тем, функциональная система Р является конечнопорожденной [2] и совокупность предполных классов образует минимальную критериальную систему в Р. Поэтому возникает вопрос: какова мощность множества предполных классов в Р. В [31] (см. также

33]) установлено, что эта мощность равна континууму.

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

Задача о полноте для систем о.-д. функций, содержащих полную истинностную подсистему (т.е. все о.-д. функции с одним состоянием) рассматривалась в работе А.А.Летичевского [34]. Им был получен эффективный алгоритм распознавания полноты конечных систем с указанными свойствами в классе отображений, осуществляемых автоматами Мура. Д.Н. Бабин усилил этот результат, распространив его на случай, когда наряду с полной истинностной подсистемой исследуемая на полноту система содержит произвольное конечное множество о.-д. функций. Кроме того, Д.Н. Бабиным полностью описаны все случаи существования алгоритмов распознавания полноты систем о.-д.функций, содержащих истинностные подсистемы, образующие базисы в произвольных замкнутых классах булевых функций из диаграммы Е.Поста (см. [35] и цитируемую там литературу).

Одной из основных характеристик поведения автоматов (о.-д.функций) является возможность с их помощью представлять регулярные события [36]. Множество Ш1 С Р называется К-полным (Клини-полным), если для всякого регулярного события из о.-д.функций множества можно получить о.-д.функцию, представляющую это событие. В общем случае (Ю.Дассоу [37]) ситуация, возникающая при изучении задачи о Неполноте аналогична той, которая возникает при исследовании задачи о полноте: существует континуум предполных классов и не существует алгоритма для распознавания К-полноты конечных систем о.-д.функций.

С точки зрения приложений важным подклассом Р является множество Ь — отображений, осуществляемых так называемыми линейными автоматами. Задача о полноте в этом множестве рассматривалась А.А.Часовских [38]. В частности, А.А.Часовских установлено, что хотя в Ь счетное число предполных классов, существует алгоритм распознавания полноты конечных систем о.-д. функций из Ь.

Большой, главным образом, теоретический интерес представляет исследование последовательностной функциональной системы, которая отличается от Р тем, что в ней к о.-д.функциям могут применяться только операции суперпозиции. Эта функциональная система изучалась в работах С.В.Алешина и Д.Н.Бабина [39,40,41]. Нетрудно показать [42], что изъятие такой сильной "автоматной" операции, как обратная связь, приводит к тому, что в рассматриваемой функциональной системе нет конечных полных систем. Однако ее элементы — о.-д. функции, достаточно "сложны" и обладают интересными имитационными свойствами. Легко видеть, что множество всех одноместных о.-д.функций замкнуто относительно операции суперпозиции и образует полугруппу. Вместе с тем, множество всех взаимно-однозначных одноместных о.-д.функций образует группу, которая, как показал С.В.Алешин [43], содержит бесконечную, периодическую и конечнопорожденную подгруппу. Вопрос о существовании таких групп составляет содержание известной ослабленной проблемы Бернсайда [44]. Указанная подгруппа порождается явно всего двумя элементами, представляющими собой о.-д.функции с семью и тремя состояниями. Как отмечено выше, в множестве всех о.-д.функций не существует конечных полных систем, если пользоваться только операциями суперпозиции. Поэтому естественно возникает следующая важная проблема (аналог 13 проблемы Д.Гильберта): можно ли для всякого п > 3 любую п-местную о.-д.функцию представить в виде суперпозиции (тг — 1)-местных. Оказалось, что эта проблема решается положительно. Более того, в [41] показано, что любую о.-д.функцию можно выразить через суперпозицию одноместных о.-д.функций и единственной двухместной о.-д.функции, которая имеет одно состояние и образует полную истинностную систему.

Кроме функциональных систем, содержащих в качестве элементов о.-д. функции, рассматривались также последовательностные функциональные системы, элементами которых являются детерминированные функции (д.функции), а операциями — те же операции суперпозиции и обратной связи. В этой функциональной системе любое полное множество континуально и, как установлено В.Б.Кудрявцевым [2], существует гиперконтинуум предполных классов. С.С.Марченковым показано, что для любого п > 2 существуют д.функции от п переменных, которые нельзя представить через суперпозицию д.функций от меньшего числа переменных [45].

Анализ содержательных моделей последовательностных функциональных систем показывает, что решение задачи о полноте в этих системах наталкивается на трудности недостаточной эффективности. Исключение составляет функциональная система функций с задержками, которая занимает промежуточное положение между конечнозначными логиками и автоматными отображениями (В.Б.Кудрявцев [8,9]). Однако элементы этой системы представляют собой лишь весьма частный случай о.-д.функций, а используемые в ней операции синхронной суперпозиции значительно "слабее" операций суперпозиции и обратной связи. Таким образом, возникает необходимость в разработке принципиально иных подходов к исследованию задачи о полноте в последовательностных функциональных системах.

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

Задача о полноте в последовательностной функциональной системе •

Пусть к > 2, г > 1. Элементами функциональной системы являются детерминированные функции, переменные которых принимают значения из Е]. — множества всех слов длины т, составленных из букв алфавита Еь = {0,1,., к — 1}. В качестве операций в функциональной системе Р£ рассматриваются операции суперпозиции и обратной связи. Заметим, что любая функция из Р£ может быть "вычислена" конечным автоматом за первые т тактов его работы. Нетрудно видеть также, что для любого т > 1 множество всех о.-д.функций естественным образом гомоморфно отображениям на множество д.функций из

Как было замечено выше, ключевое значение, занимаемое конечнознач-ными логиками всех истиностных функциональных систем, объясняется тем, что каждую функцию, принадлежащую истиностным функциональным системам, можно аппроксимировать функциями конечнозначных логик. Вместе с тем, всякую функцию с "памятью", т.е. функцию, принадлежащую последовательностным функциональным системам, можно аппроксимировать д.функциями из Р£, причем это достигается путем увеличения не только числа к, как в истиностных функциональных системах, но и числа т. Таким образом, исходя из произвольного полного подмножества д.функций из Р£} любую функцию с "памятью" с некоторой степенью точности можно представить в виде схемы, состоящей из элементов этого подмножества.

В [36] показано, что для решения задачи о полноте в Р£ операция "обратная связь" оказывается несущественной, т.е. в данном случае эта операция выразима через операции суперпозиции. Отсюда легко следует, что задача о полноте в конечнозначных логиках — одна из основных задач в теории истиностных функциональных систем, эквивалентна задаче о полноте в т.е. при г = 1. Вместе с тем, при г > 2 существует принципиальное различие между функциональной системой, элементами которой являются функции &-значных логик, и функциональной системой Р£. Множество всех детерминированных отображений, рассматриваемых на словах длины т, порождает специальное замкнутое подмножество в &т-значных логиках, существенно зависящее от двух параметров — параметра к и параметра т. Используя естественную аналогию между задачей полноты в Р£и в конечнопорожденных замкнутых классах конечнозначных логик, можно ввести понятие предполного класса в Р£ и показать, что всякое множество является полным в Р^" тогда и только тогда, когда оно целиком не содержится ни в одном из предполных в Р£ классов; совокупность предполных классов в Р£ конечна, может быть описана эффективно и образует минимальную критериальную систему для распознавания полноты систем функций из Р£; при этом множество предполных классов в Р£ изоморфно некоторому подмножеству предполных классов в Р£. Таким образом, в отличие от задачи о полноте в Р для любых к > 2, г > 1 существует алгоритм для распознавания пол ноты в PI произвольных конечных множеств д.функций. Также как в fc-значных логиках, каждый из этих алгоритмов может быть задан с использованием эффективно описываемых критериальных систем, а наилучший из них получается на пути явного описания всех предполных классов в Р£.

В общем случае для любых к > 2, т > 1 задача о полноте в PJ. решена В.А.Буевичем в [46,47,48,49]. В терминах сохранения отношений описаны все предполные классы в Р£. Однако это описание оказалось довольно сложным. В частности, отношения, классы сохранения которых совпадают с предполными в Р£ классами, могут иметь любую арность от 1 до fcr, а их число даже при малых кит очень велико. В связи с этим естественной представляется задача об исследовании на полноту систем детерминированных функций, которые обладали бы некоторыми наперед заданными, но вместе с тем достаточно общими свойствами.

Настоящая диссертация посвящена рассмотрению задачи о полноте в Р£ так называемых S-множеств, состоящих только из S-функций — детерминированных функций, вычисляемых конечными автоматами, в каждом состоянии которых реализуется функция /г-значной логики, принимающая все к значений. Легко видеть, что для любой функции , жп) из Р£ существует S-функция д(хi,., хП1 xn+i), также принадлежащая PJ. такая, что f(x\, • • • 1 %п) = • • • 1 Яти

По аналогии с общим случаем в диссертации введено понятие S-предполного класса и показано, что произвольное S-множество 9R С Р£ является полным в PJ тогда и только тогда, когда 971 не содержится ни в одном из S-предполных в PJ. классов. Таким образом, возникает задача об описании множества всех S-предполных в PJ. классов. Отметим, что задача в случае, когда т = 1, т.е. в к-значных логиках решена В.Б.Кудрявцевым [50].

В диссертации с использованием аппарата сохранения отношений для любых к > 2, т > 1 представлено описание всех S-предполных классов в Р^. Оказалось, что совокупность отношений, классы сохранения которых совпадают с S-предполными, распадается на шесть семейств — семейства Z(k,r), D(k, г), N(k, г), I(k: г), L(k,r) и V(k,r). Семейство Z(k,r) состоит из унарных отношений, отношения, принадлежащие семействам D(k, г), N(k, г), 1{к, г)и V(k, т) бинарны, а отношения, принадлежащие семейству L(k, т) имеют арность, равную четырем. При этом семейства Z(k, 1), D(k, 1), N(k, 1), I(к, 1) и L(k, 1) совпадают с теми, которые описаны в [50]. Заметим, что каждый S-предполный в PJ. класс является в то же время одним из предполных классов в PZ", однако описание Sпредполных классов значительно проще, чем описание всех предполных классов в полученное в [46,47,48,49].

С задачей полноты в тесно связана задача об А-полноте в -Ро.д. [36,50]. Учитывая детерминированность функций из -Ро.д. можно, очевидно, считать, что для всякого т > 1 эти функции определены также на всех наборах слов длины Пусть т > 1. О.-д.функция д(х1,., хп) и д.функция /(жх,., хп) являются т-эквивалентными, если для любого набора слов (а^ . ,ап), каждое из которых имеет длину г, выполнено равенство д{а\,., ап) = /(аь ., ап). Подобным образом определяется т-эквивалентность множеств из -Ро.д. и из Р^. Множество 91 С Ро.д. называется А-полным, если для любого т > 1 замыкание множества ОХ т-эквивалентно Р£. Известно, [50] что в общем случае не существует алгоритма для распознавания А-полноты конечных систем о.-д.функций. Поэтому представляет интерес поиск такого алгоритма для систем о.-д.функций, обладающих некоторыми наперед заданными свойствами.

Диссертация состоит из введения и двенадцати параграфов. В $$ 19 для любых к > 2, т > 1 дано полное решение задачи о Б-полноте в Щ — с использованием аппарата сохранения отношений описано множество всех Э-предполных в Р£ классов. Совокупность отношений, классы сохранения которых совпадают с Э-предполными в Р£ классами разбивается на шесть семейств — семейства Z(k,т), г), т), /(&,т), Ь(к,т) и У(к,т).

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

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

3. Мальцев А.И. Итеративные алгебры Поста // Новосибирск, Изд-во СО АНСССР, 1976

4. Post Е. Two-valued iterative systems of mathematical logic // Prinston, 1941

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

6. Угольников А.Б. Классы Поста // Москва, Изд-во Центра прикладных исследований при мех.-мат. МГУ, 2008, 64 стр.

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

8. Кудрявцев В.Б. Вопросы полноты для автоматов // ДАН СССР, 1960, т.130, №6, с.1189-1192

9. Кудрявцев Б.£>.Теорема полноты для одного класса автоматов без обратных связей // ДАН СССР, 1960, т.132, №2, с.272-274

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

11. Деметрович Я.О мощности множеств преклассов в предельных логиках // Acta Cybernetika, 1972, t.l, Fase.4, Szeged, s.233-239

12. Лавров И.А. Использование арифметических прогрессий к-го порядка для построения базисов алгебры примитивно-рекурсивных функций // ДАН СССР, 1967, т. 172, "2, с.279-282

13. Редько В.Н. Основания композиционного программирования// Программирование, 1979, №3, с.9-19

14. Глушков В.М. О полноте системопераций в электронных вычислительных машинах // Кибернетика, Киев, 1968, №2, с.1-15

15. Голунков Ю.В. К теории систем алгоритмических алгебр // ДАН СССР, 1977, т.232, №4, с.749-752

16. Тайманов В.А. О функциональных системах к-значной логики с операциями замыкания программного типа // ДАН СССР, 1984, т.286, №6, с.1307-1310

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

18. Алексеев В. Б. О полупростых базисах fc-значной логики // Мат.заметки, 1985, т.38, М, с.44-46

19. Марченков С. С. Существование базисов по суперпозиции в счетных примитивно-рекурсивных замкнутых классах //Мат.заметки, 1986,т.39, №2, с. 268-276

20. Горлов B.B. О замкнутых классах Ахзначной логики, все конгруэнции которых тривиальны // Мат. заметки, 1977, №4, с.499-509

21. Кузнецов A.B. Математика в СССР за сорок лет // Москва, 1959, т. 1, $13, с.102-115

22. Мартынюк В. В Исследование некоторых классов функций в многозначных логиках //В кн. "Проблемы кибернетики", вып.З, Москва, Наука, 1960, с.49-60

23. JIo Чжу Кай, Лю Сюй-хуа Предполные классы, определяемые ьинарными отношениями в многозначных логиках // Acta Sei. natur. Univ. Yilinensis, 1963, v.4

24. Пан Юн-цзе Один разрешающий метод для отыскания всех пред-полных классов в многозначных логиках // Acta Sei. natur. Univ. Yilinensis,1962, v.2

25. Захарова Е.Ю. Критерий полноты систем функций в // В кн. "Проблемы кибернетики", вып. 18, Москва, 1967, с.5-10

26. Rosenberg Y. Uber die functionale Vollständigkeit in den mehrwertigen Logiken. Praha, Rozpravi Ceskoslovenska Acodemie Ved. v. 80, №4, p. 393,1970

27. Буевич В. А. Вариант доказательства критерия полноты для функций к-значной логики. Москва, Дискретная математика, т.8., вып.4, стр. 11-36, 1996

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

29. Кудрявцев В.Б. О мощности множеств предполных множеств некоторых функциональных систем, связанных с автоматами // В кн. "Проблемы кибернетики", вып. 13, Москва, Наука, 1965, с.45-74

30. Кратко М.И. Алгоритмическая неразрешимость распознавания полноты для конечных автоматов // ДАН СССР, 1964, т.155, №1, с.35-37

31. Родин A.A. О предполных классах в множестве автоматных отображений // Материалы конференции "Современные проблемы математики, механики и их приложений", Москва, 2009, с. 372

32. Лебичевский A.A. Условия полноты в классе автоматов Мура // В кн. Материалы научных семинаров по теоритическим и прикладным вопросам кибернетики, вып.2, Киев, 1963

33. Бабин Д.Н. Классификация автоматных базисов Поста по разрешимости свойств полноты и А-полноты // Москва, изд-во МГУ, 2009, 111 стр.

34. Кудрявцев В.Б., Алешин С.В., Водколзин A.C. Введение в теорию автоматов // Москва, Наука, 1985.

35. Dassow У Ein modifizierter Vollstandig-keiin einer Algebra von Automatenabbildungen // Dissertation Doctor B.Rostock Universität, 1978

36. Часовских A.A. О полноте в классе линейных автоматов //В кн. Математические вопросы кибернетики. Вып.З, Москва, Наука, 1991, с.140-166

37. Алешин С. В. О суперпозициях автоматных отображений // Кибернетика, Киев, 1975, с.29-34

38. Алешин С. В. Об отсутствии базисов в некоторых классах инициальных автоматов //В кн. Проблемы кибернетики, вып. 22, Москва, Наука, 1970, с.67-75

39. Бабин Д.В. О полноте двухместных о.-д.функций относительно суперпозиции // Москва, Дискретная математика, 1989, т.1, вып.4, с.86-91

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

41. Алешин С. В. Конечные автоматы и проблема Бернсайда в периодических группах // Москва, Мат. заметки, 1972, вып.З, с.319-328

42. Карганов М.И., Мерзляков Ю.И. Основы теории групп //Москва, Наука, 1982, 214 стр.

43. Марченков С. С. Об одном методе анализа суперпозиций непре-рывныфункций //В кн. Проблемы кибернетики, вып.37, Москва, Наука, 1985, с. 5-18

44. Буевич В.А. О т-полиоте в классе автоматных отображений. Докл. АН СССР 1980. - Т. 252, № 5 - с. 221-224.

45. Буевич В.А. Условия А-полноты для конечных автоматов, ч.1 Москва, Изд-во МГУ, 1986

46. Буевич В.А. Условия А-полноты для конечных автоматов, ч.2 Москва, Изд-во МГУ, 1987

47. Буевич В.А. О т- полноте в классе детерминированных функций Докл. РАН, т.326, №3, стр.399-403, 1992

48. Кудрявцев В.Б. О свойствах S-систем функций k-значной логики. Elektronische Informationsverarbeitung und Kybernetik. EIK 9,1/2, стр. 8105, 1973

49. Буевич В.А. Об алгоритмической неразрешимости распознавания А-полноты для ограниченно-детерминированных функций //Математические заметки. 6, Москва, 687-697, 1972

50. Буевич В.А., Клиндукова Т.Э. О существовании алгоритма для распознавания A-полноты систем, содержащих все одноместные ограниченно-детерминированные функции //Математические вопросы кибернетики.8, Москва, Наука, 289-297, 1999.

51. Slupeski Y. Kryterium petnosci wielowartosciowych systemow logici zdan // Comptes rendus des seanses de la Société des Sciences et des Lettres de Varsovie, 102-109, 1939

52. Salomaa A. On basis groups for the set of functions over a finite domain //Ann.Acad. Sci. Finnicae, Ser A 338, 1-15, 1963

53. Буевич В.А., Подколзииа M.А. Критерий полноты S-множеств детерминированных функций. //Математические вопросы кибернетики, 16, Москва, Физматлит, 191-238, 2007

54. Буевич В.А., Подколзина М.А. Задача о полноте S-множеств детерминированных функций // Вестник Московского университетата. Сер.1. Математика. Механика., 2008, № 5, с. 57-59

55. Буевич В.А., Подколзина М.А. О полноте S-множеств детерминированных функций // тезисы докладов 9 Междунар. семинара "Дискретная математика и ее приложения", Москва, 2007

56. Подколзина М.А. О числе S-предполных классов в функциональной системе //Вестник Московского университета. Сер.1. Математика. Механика., 2008, № 6, с. 43-45

57. Подколзина М.А. К задаче о полноте S-множеств детерминированных функций // тез. докл. между.конференции "Современные проблемы математики, механики и их приложений", Москва, 2009, с. 370-371

58. Подколзина М.А. О полноте и А-полноте S-множеств детерминированных функций, содержащих все одноместные детерминированные S-функции // Дискретная математика, том 21, вып.2, Москва, 2009, с. 75-88