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

ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова»

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

дг»

Родин Александр Алексеевич О Р-МНОЖЕСТВАХ АВТОМАТНЫХ ФУНКЦИЙ 01.01.09 — дискретная математика и математическая кибернетика

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

11 АПР 2014

МОСКВА 2014

005547364

005547364

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

Научный руководитель: доктор физико-математических наук,

профессор Буевич Вячеслав Александрович

Официальные оппоненты: Чечкин Александр Витальевич,

доктор физико-математических наук, профессор (ФГБОУ ВПО "Финансовый университет при Правительстве Российской Федерации")

Карташов Сергей Иванович,

кандидат физико-математических наук, доцент (ФГБОУ ВПО "Московский государственный университет приборостроения и информатики")

Ведущая организация: ФГБОУ ВПО "Национальный иссле-

довательский университет "МЭИ"

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

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВПО "Московский государственный университет имени М.В. Ломоносова" (Москва, Ломоносовский проспект, д. 27, сектор А, 8 этаж).

Автореферат разослан 30 апреля 2014 г.

Ученый секретарь диссертационного совета Д.501.001.84, созданного на базе ФГБОУ ВПО МГУ, доктор физико-математических наук,

профессор Иванов Александр Олегович

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

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

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

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

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

Важнейшим примером истинностных и последовательностных функциональных систем являются к—значная логика, с одной стороны, и функциональная система автоматных функций, с другой. Для к—значных логик (функциональная система основная проблема в теории итеративных функциональных систем — проблема полноты, была решена. В 1921 г. Э. Постом была полностью описана структура замкнутых классов в двузначной логике. Это описание, изложенное в виде монографии в 1941 году3, по существу эквивалентно решению проблемы полноты для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции. Для произвольного к > 3 усилиями многих авторов ( С.В. Яблонский4, А.В. Куз-

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

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

'Post Е. The two-valued iterative systems of mathematical Logic. Princeton Univ. Press, Princeton, 1941.

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

нецов5, И. Розенберг6, В.А. Буевич 7 и др.) в терминах сохранения отношений (предикатов) были последовательно в явном виде построены все предполные классы в Pfc, образующие минимальную критериальную систему для распознавания полноты систем функций &-значной логики. Т.е.. произвольное множество функций к—значной логики M является полным тогда и только тогда, когда M целиком не содержится ни в одном из предполных в Рк классов.

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

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

1. Функциональная система "суперпозиция" (Pk)zl

2. Функциональная система "композиция" (Рк)к■

Множество функций, определяемых в функциональных системах (Pk)z и (Рк)к, совпадает с множеством Рк, Операциями в (Рк)к являются операции суперпозиции и обратной связи, а в (Pk)s — только операции суперпозиции.

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

При изучении проблемы полноты в {Рк)у. и (Рк)к фундаментальный результат был получен В.Б. Кудрявцевым. Известно, что функциональная система (Рк)к является конечнопорожденной и, также как в fc-значных логиках, множество всех предполных классов образует минимальную критери-

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

»Rosenberg J. La structure des fonctions de plusiers variables sur un ensemble fini. Comptes Rendus Acad. Sei. Paris, 1965 №260, c.3817-3819.

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

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

альную систему. Отсюда следует, что в принципе критерий полноты в (Рк)к может быть сформулирован в терминах предполных классов. Однако, в 19G3 году В.Б. Кудрявцев показал9, что мощность множества предполных классов в (Pk)z и (Рк)к равна континууму, и, следовательно, алгебраический подход не дает эффективного критерия полноты. С этим согласуется результат М.И. Кратко, установившего10 в 19G4 году отсутствие алгоритма распознавания полноты конечных систем о.-д. функций.

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

Отрицательные, с точки зрения эффективности, результаты по проблеме полноты для о.-д. функций в общем случае привели к тому, что различные авторы11,12,13'14'15'16,17 рассматривали некоторые модификации этой проблемы. Одни из них возникают на пути сужения класса систем, исследуемых на полноты, другие — на пути моделирования отдельных свойств о.-д. функций.

В предлагаемой диссертации вводятся и рассматриваются Р—множества о.-д. функций (термин предложен В.Б. Кудрявцевым). Известно, что каждая о.-д. функция однозначно определяется своим множеством состояний Q = {<7ь ■■• 1 Qm}, функцией перехода ф и множеством функций к—значной логики Fi, ... ,Fm, реализующихся в состояниях {qi, ... ,qm} соответственно7.

Пусть D — произвольный замкнутый класс в Р*. Р—множество, порож-

9 Кудрявцев В.Б. О мощности множеств предполных классов некоторых функциональных систем, связанных с автоматами. М.: ДАН СССР, 1963, т.151, №3.

"Кратко М.И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов. М.: ДАН СССР, 1964, т.155, Jf«l.

"Алешин C.B. Über ein Vollstänig klits kriterium für Automatenabbildungen beruglich der Superposition. Rostoker Math. Kolloq. (1977) 5, 119-132.

"Бабин Д. H. Разрешимый случай задачи о полноте автоматных функций. Москва, Дискретная математика, 1992. Т. 4, вып. 4. с. 41-56.

13Бабин Д. Н. О классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты // Доклады Академии наук. ЯМ. Т. 367. 1999. С. 439-441.

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

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

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

"Часовских А. А. О полноте в классе линейных автоматов. Математические вопросы кибернетики. Вып. 3. 1995, с. 140-166.

денное классом D — это множество всех ограниченно-детерминированных функций, в каждом состоянии которых реализуется функция к—значной логики. принадлежащая D. Будем обозначать такое Р—множество через Рд. Нетрудно видеть, что Рд замкнуто как в (Pk)z, так и в (Рк)к■ Заметим, что если D содержит все функции к—значной логики, то Р—множество Рд совпадает с множеством всех о.-д. функций, если D = {0,1,..., к — 1}. то с качестве Р—множества получим все автоматы Мура, если к = 2, D^ = {0,1. х, х], то Р—множество совпадает с множеством о.-д. функций, в каждом состоянии которых реализуется некоторая функция алгебры логики (а.-л.), зависящая не более, чем от одной переменной.

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

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

ТЕОРЕМА 1.1. Пусть D С Рк и D = [D]. Тогда множество предполных классов в (Рк)к, содержащих Рд, континуально и множество предполных классов в (Pk)z, содержащих Рд, также континуально.

Пусть D — произвольный замкнутый класс в Рк, содержащий тождественную функцию, а По — континуальная система всех предполных классов в {Pk)z, каждый из которых содержит Рд. Нетрудно показать, что существует такая о.-д. функция U g Рк, что [Рд U {Î7}] = Рк. Поэтому любое неполное множество о.-д. функций М, содержащее Рд, расширяется до предполного в (Рк)х- Следовательно, для того, чтобы множество M было полным, необходимо и достаточно, чтобы его подмножество M \ Рд не содержалось ни в одном предполном классе системы Пд.

В диссертации рассматривается случай к = 2. Это объясняется тем, что любой класс из структуры замкнутых классов Поста18 имеет конечный базис и, как легко видеть, при к = 2 всякое Р—множество образует рекурсивное подмножество множества всех о.-д. функций.

Пусть D — произвольный замкнутый класс функций алгебры логики. Пусть Пд — совокупность всех множеств о.-д. функций, содержащих Р—множество Рд, и таких, что для любого M G Г2д множество M \ Рд — конечно. Очевидно, что система По образует критериальную систему для распознавания полноты множеств, принадлежащих Пд. Из теоремы 1.1 следует, что это множество континуально. Возникает вопрос: существует ли алгоритм распозна-

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

вания полноты произвольного множества М. принадлежащего Пд? Важно отметить, что если такой алгоритм существует, то этот алгоритм должен устанавливать, содержится ли конечное множество М \ Рд в одном из пред-полных классов системы Па и, тем самым, давать ответ, является ли полным множество М.

В диссертации найдены случаи, в которых подобный алгоритм существует, имеет место:

ТЕОРЕМА 2.4. Если Б С Рг,-0 = [О] и Б содержит тождественную функцию а.-л. и одну из констант, то в (Р2)е существует алгоритм распознавания полноты систем из

Доказательство этой теоремы конструктивно, т.е. алгоритм для каждого Б явно указывается в тексте диссертации. Из теоремы 2.4 следует, что в отличие от общего случая (В.Б. Кудрявцев, М.И. Кратко) существуют примеры таких множеств о.-д. функций, для которых, несмотря на наличие континуальных критериальных систем, существуют алгоритмы для распознавания полноты.

Заметим, что справедлива также

ТЕОРЕМА 2.14. Если Б С Р2, Б = {0,1}, то не существует алгоритма распознавания полноты систем из £1°.

На рис. 1 жирными точками отмечены те классы Б из структуры замкнутых классов Поста, для которых построен алгоритм распознавания полноты множеств из

Также в работе рассматривается вопрос существования базиса в произвольном Р-множестве. Получены следующие результаты:

ТЕОРЕМА 3.1. Пусть Б С Р2,£> = [Б] и {0,1,1} С Б. Тогда в (Р|,)Е существует полная система, не содержащая базиса.

ТЕОРЕМА 3.2. Пусть Б С Р2, Б = [£>] и {0,1,а:} С Б. Тогда в (Р£)2 существует базис.

ТЕОРЕМА 3.3. Пусть Б С Р2, Б = [Я] и {х,ж} С Б. Тогда в (Р£)е существует полная система, не содержащая базиса.

ТЕОРЕМА 3.4. Пусть Б С Р2, Б = [Б] и {я, 5} С Б. Тогда в (Р£)Е существует базис. Методы исследования

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

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

Апробация работы

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

• Кафедральный семинар кафедры МаТИС механико-математического факультета МГУ имени М.В. Ломоносова «Теория автоматов» под руководством академика, проф., д.ф.-м.н. В.Б. Кудрявцева (2012 г.)

• Международная конференция «Современные проблемы математики и их приложений» посвященная 70-летию академика В. А. Садовничего (Москва, 30 марта — 2 апреля 2009 г.)

• X Международный семинар «Дискретная математика и ее приложения» (Москва, 1—6 февраля 2010 г.)

• X международная конференция «Интеллектуальные системы и компьютерные науки» (Москва, 5—10 декабря 2011 г.)

• Международная конференция студентов, аспирантов и молодых ученых «Ломоносов» (Москва, 9—13 апреля 2012 г.)

• XI Международный семинар «Дискретная математика и ее приложения» (Москва, 18—23 июня 2012 г.)

• Также результаты диссертации докладывались на следующих семинарах механико-математического факультета МГУ имени М.В. Ломоносова: на семинаре «Дискретный анализ» под руководством проф., д.ф.-м.н. С. В. Алешина, проф., д.ф.-м.н. В. А. Буевича, с.н.с., к.ф.-м.н. М. В. Носова (2007— 2012 г.), на семинаре «Замкнутые классы булевых функций » под руководством проф., д.ф.-м.н. А. Б. Угольникова (2010 г.).

Публикации

Основные результаты диссертации опубликовано в восьми работах {1-8], в том числе работы [1-4] в изданиях из Перечня ВАК. Структура и объем диссертации

Диссертация состоит из введения, трех глав и списка литературы. Объем диссертации 91 страница. Список литературы содержит 43 наименования.

Содержание работы

Во введении описана предметная область и история вопроса, даны основные используемые определения, сформулированы результаты диссертации.

Пусть к > 2, обозначим через Рк множество всех ограниченно-детерминированных функций (автоматных отображений), входные и выходные переменные которых определены на множестве бесконечных последовательностей, составленных из Е^, где = {0,... ,к-1}.

Будем считать, что на множестве Рк определены операции суперпозиции и обратной связи. В работе будут рассматриваться две функциональные системы — "суперпозиция" и "композиция" (присутствуют операции суперпозиции и обратной связи). Пусть М С Рк. Замыкание множества М С Рк относительно операций суперпозиции обозначим через [М], а замыкание относительно суперпозиции и обратной связи — через [М]к- Функциональную систему "суперпозиция" над множеством Рк обозначим через [Рк)у., а функциональную систему "композиция" — через (Рк)к■

Множество N С Рк называется предполным классом в (Рк)ъ, если [ДО] ф Рк, но для любой о.-д. функции / ^ Аг, [./V и {/}] = Рк. Аналогично определяются предполные классы в (Р^)д-.

Пусть ¡{х\,... ,хп) — о.-д. функция из Рк, задаваемая системой канонических уравнений

9(1) = 9о, <?(£ + !) = <р(*1 (<),■•■ ,хп(г),ч{г)), у(г) = ф(х 1(1),... ,х„(0,а(4)), где <2 = {>7о, ... , др} — множество ее состояний, а до — ее начальное состояние. Функцию к—значной логики, реализуемую в состоянии дг, обозначим через Р,,.

Пусть £ > 1, Е\~ множество слов длины ¿, составленных из Пусть г,] е {0,1,...,р}. Будем считать, что состояние является ¿-достижимым из состояния qj, если найдутся такие аь аг,..., ап 6 Е1к, что ц>(ау,... , ап, = <?;. Состояние <7; достижимо из состояния если ¿-достижимо из qj для некоторого ¿. Будем считать, что состояния д, и связны друг с другом, если состояние <7; достижимо из с^ и наоборот. При этом необязательно, чтобы 9. Ф Чу

Пусть Б — некоторое замкнутое множество функций значной логики. Тогда множество всех о.-д. функций из Рк, таких, что каждая из функций РЧо,Р^,,... , Р^ принадлежит множеству О, обозначим через Рд. Это множество называем Р-множеством, порожденным классом Б. Нетрудно видеть, что Рд — замкнутое множество как в (Рк)к, так и в (Рк)■£.

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

ТЕОРЕМА 1.1. Пусть Б С Рк и Б = [О]. Тогда множество предполных классов а (Рк)к, содержащих Рк}, континуально и множество предполных классов в (Рк)т:, содержащих Рр, также континуально.

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

системы используется (Р2)е-

Пусть £> — произвольный замкнутый класс алгебры-логики. Пусть — совокупность всех подмножеств М множества Р2 , содержащих Р—множество Рд и таких, что множество М \ Рд конечно.

Для каждого Б рассматривается задача о существовании алгоритма распознавания полноты множеств, принадлежащих совокупности Пв. Любая система М из содержит Р}} и конечное множество о.-д. функций, не принадлежащих Р^. По этой конечной добавке искомый алгоритм должен определить, полна система М или нет. Ясно, что наличие алгоритма должно зависеть от порождающего множества О. Во второй главе рассмотрены несколько возможных вариантов.

Данная глава состоит из шести параграфов. В первом параграфе даны необходимые определения.

Пусть f(x1,... , хп) ~ о.д. функция из Рк, где <3 — {?0,91,... , qp} — множество ее состояний, а до — ее начальное состояние.

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

Если Рдг является линейной функцией алгебры-логики, состояние ^ будем называть линейным, иначе — нелинейным.

Если Ръ является монотонной функцией алгебры-логики, состояние будем называть монотонным, иначе — немонотонным.

Подмножество К С О будем называть компонентой связности, если:

1) Для любых € АГ, и связны друг с другом.

2) Если 6 К и существует состояние ^ 6 <3, такое что дг и связны, то е К.

Рассмотрим произвольное состояние ч функции /, принадлежащее какой-либо компоненте связности К. Для этого состояния определим множество А{д) <= {Е\)п, где п - число переменных, от которых зависит функция /:

(«1,... , а„) € Ф). ф(а.\,... , ап, д) е К

Т.е. А(д) — это множество наборов слов длины 1, по которым из состояния д достижимы только состояния, принадлежащие той же компоненте связности, что и д.

Пусть

9\(уи- ,Ут),- ,9п{уи— 1 Ут)

функции а.-л. Через 5(<71,... , дп) будем обозначать множество двоичных наборов

,0т))} С (Е*)",

где объединение берется по всем (ßi,... ,ßm) из (Е¡)т.

Состояние q будем называть локально нелинейным, если найдутся линейные функции а.-л.

gi(yu- ,ут),— ,дп{уи— -.Ут)-, такие что S(gu... ,дп) С A(q) и F^g^yi,... ,ут),... ,дп{уь... ,ут)) является нелинейной функцией а.-л. Все остальные состояния назовем локально линейными. Заметим, что если состояние не принадлежит никакой компоненте связности, то оно локально линейно.

Подобным образом определяются локально существенные и локально немонотонные состояния.

Обозначим через Q^(t) подмножество Qf, состоящее из всех состояний, f-достижимых из начального состояния о.-д. функции /. Пусть

М = Pl[j{Mxi,...,xn) ,..., fm(xь...,х„)},

QM{T) = <3'»(T) U ... U Qfm{T). Рассмотрим последовательность множеств

(QM(0), QM(1), QM(2)...}.

Несложно видеть, что данная последовательность периодична. Пусть sM длина цикла этой последовательности, а Тм — длина предпериода. Тогда для системы М определим множества состояний

С? = Qu(TM+i),i = 1,2,... ,5м.

Пусть т — произвольное натуральное число. О.-д. функции д(хi, ... ,хп) и h(x\, ... ,хп) являются r-эквивалентными, если значения функций / и h совпадают на всех словах длины т. Множество М С Рк является т-полным, если для любой о.-д. функции f(xi, ... ,хп) 6 Рк существует такая функция fM(xi, ... ,xn),fM е [М], что / и fM r-эквивалентны. Множество М С Рк называется А-полным, если оно т-полно для любого натурального г. Также будем говорить, что / € А[М] (А-замыкание), если для любого натурального г существует функция fM 6 [М\ такая, что fM г-эквивалентна /.

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

ТЕОРЕМА 2.2. Пусть

D= {0,1,х},М = Р^У{/1(х1,... ,хп) ,..., /т(хъ... ,

Система М полна тогда и только тогда, когда она А-полна и в каждом из множеств С;4, i — 1,2,... , sM содержится хотя бы одно локально нелинейное, локально существенное и локально немонотонное состояние.

Пусть теперь О — произвольный замкнутый класс а.-л., содержащий множество {0,1, х} и

М = РЬ[]{Мхи-- ,Хп) 1т{х1,- ,1,0)-

Во множестве V могут содержаться нелинейные, немонотонные и существенные функции а.-л. Определим о.-д. функцию /¿(О). Если в £) содержится какая-либо нелинейная функция а.-л. Т7!, то — функция с одним со-

стоянием, в котором реализуется /*}. В противном случай, - функция с

одним состоянием, в котором реализуется константа 0. Аналогичным образом определим о.-д. функции /м(-О) и /.,(!)). Пусть

м' = РЪ СКЛ^Ь ...,!„),..., /т(и,... , хп} и {/Ь(Д)} и ШО)} и {/«(Я)}.

Нетрудно видеть, что [М] = [М1]. Для системы М' справедливо следующее утверждение.

ТЕОРЕМА 2.3. Пусть Б Э {0,1,х},

М'^РЬиШхи... ,хп) ,..., /т(хи-,1„)}и{Л(Д)}и{Л(0)}и{/ир)}.

Система М' полна тогда и только тогда, когда она А-полна и в каждом из множеств С^', г — 1,2,... , вм' содержится хотя бы одно локально нелинейное, локально существенное и локально немонотонное состояние.

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

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

М = Р^УШх„... ,хп) ,..., /т(хь... ,зг„)}.

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

Константную о.-д. функцию, выход которой не зависит от входных переменных и является периодической последовательностью будем обозначать через pip2--.pi{с\С2---Се), где pip2--.pi — предпериод, а с^.-.сц — период (не обязательно простой) выходной последовательности. Например, тождественную единицу в этих терминах можно обозначить через (1) или (11) или 1(11).

Пусть В С ЕГ'. Обозначим через Гт{Щ множество всех бесконечных последовательностей, представимых в виде аЬгДе о. € , Ь е В.

Пусть [Гх(Л)"] множество бесконечных последовательностей. Будем считать, что 7 6 |Тг(5)] тогда и только тогда, когда существует 7' £ Гт(В) такая, что 7 и 7' различаются не более чем в конечном числе разрядов.

Выберем некоторое множество двоичных наборов А = {аь... ,ат} О. Е?2". Построим ориентированный граф С?д(Л) с пометками на ребрах, вершинами которого являются состояния из множества С}*, принадлежащие функции /;. Пусть 1},р £ С}1 П В (? /¡(Л) существует ребро, ведущее издвр если и только если существуют {0Ъ... , /Зп} Е А такие, что ^''(Л. ••■ ,Рп,я) = Р-Припишем этому ребру пометку ... , /3„, д), т.е. тот набор который яв-

ляется выходом функции /;. находящейся в состоянии q, на входных наборах 01,... ,/?„. Таким образом, в графе могут быть кратные ребра и петли. Очевидно, что граф конечен, поэтому в нем можно найти все простые циклы за конечное число операций. Зафиксируем двоичные наборы, приписанные ребрам, которые входят хотя бы в один простой цикл и обозначим их множество через //¡(Л) — образ набора А относительно функции /¿.

Множество наборов А С будем называть 0-полным, если для любых а, ¡5 £ таких, что а > 0 и а € А выполнено /3 6 А.

Теперь можно сформулировать основную теорему параграфа.

ТЕОРЕМА 2.6. Пусть М = РЫ}{А(хь... ,*„) ,..., /т(хь... ,*„)}• Тогда М содержит тождественную единицу если и только если (1) 6 А[М] и для любого 0-полного А С Е\ существует г 6 {1,... , т} такое, что

Эта теорема является эффективным критерием распознавания полноты в данном случае. Ее следствием является следующее утверждение.

ТЕОРЕМА 2.4. Пусть порождающее множество И содержит тождественную функцию а.-л. и одну из констант. Тогда существует эффективный критерий распознавания полноты систем из £1°.

Стоит отметить, что существование алгоритма распознавания полноты в случае, когда Б = {0,1,х,х} следует из результата С.В. Алешина10 .

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

Пусть Пв(/) — совокупность всех подмножеств М множества Р, содержащих и о.-д. функцию /, таких, что множество М \ 0.° конечно.

Пусть о.-д. функции С0(х),С1(а;) — нулевая и единичная задержка соответственно. Обозначим С = (Со(а;),С^ж)}.

и

Доказаны следующие утверждения.

ТЕОРЕМА 2.10. Пусть множество В содержит тождественную функцию а.-л. Тогда существует эффективный критерий распознавания полноты систем из ОР(С). где С — произвольная константная о.-д. функция.

ТЕОРЕМА 2.12. Пусть множество В содержит, тождественную функцию а.-л. Тогда существует эффективный критерий распознавания полноты систем из П°{д), где д принадлежит множеству С.

Доказательство каждой из этих двух теорем также конструктивно. Алгоритмы распознавания полноты приведены в тексте этого параграфа.

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

ТЕОРЕМА 2.14. Пусть В\ = {0,1}. Не существует алгоритма распознавания полноты систем из

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

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

ТЕОРЕМА 3.1. Пусть В С Р2)А = [В] и {0,1,х} С В. Тогда в (Р£)Е существует полная система, не содержащая базиса.

ТЕОРЕМА 3.2. Пусть 0СР2,0 = [О] и {0,1, я} С В. Тогда в (Р£)Е существует базис.

ТЕОРЕМА 3.3. Пусть В С Р2,В = [В] и {х,х} С В. Тогда в (Р£)Е существует полная система, не содержащая базиса.

ТЕОРЕМА 3.4. Пусть О С Р2,С = [В] и {х,х} С В. Тогда в (Р£)Е существует базис.

Доказательство каждой из теорем третьей главы также конструктивно. Соответствующие примеры приведены в тексте диссертации.

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

Рис. X: Разрешимые случаи на решетке Поста

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

[1] Родин А. А. О континуальности множества, специальных предполных классов во множестве автоматных отображений. Интеллектуальные системы. (2012) 16, 329-334.

[2] Родин А. А. О некоторых свойствах Р—множеств ограниченно-детерминированных функций. Вестник Московского университета. Сер. 1, Математика. Механика. 2013. №1. С. 51-53.

[3] Родин А. А. Критерий полноты некоторых систем, содержащих Р-множества о.-д. функций. Дискретная математика, 25:1 (2013), 76-89.

[4| Родин А. А. Базисы в Р—множествах. Интеллектуальные системы. (2013) 17, 380-392.

[5] Родин А. А. О предполных классах во множестве автоматных отображений // Современные проблемы математики и их приложений. Материалы конференции, посвященной 70-летию академика В. А. Садовничего. - М.: Изд-во МГУ, 2009 - С.372.

[6] Родин А. А. О существовании алгоритмов для распознавания полноты систем о.-д. функций из множества АГ0 // Материалы X Международного семинара Дискретная математика и ее приложения -М.: Изд-во МГУ, 2010 - С.421.

[7] Родин А. А. Критерий полноты некоторых бесконечных систем во множестве автоматных отображений // Материалы X международной конференции «Интеллектуальные системы и компьютерные науки» (2011, Москва).

[8] Родин А. А. Эффективный критерий А-выразимости для систем, содержащих Р-множества // Тезисы докладов международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2012» (2012, Москва).

Подписано в печать:

21.03.2014

Заказ № 9430 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ФГБОУ ВПО «Московский государственный университет имени

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

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

Родин Александр Алексеевич О Р-множествах автоматных функций

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

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

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

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

профессор В. А. Буевич

МОСКВА - 2013

Содержание

Стр.

ВВЕДЕНИЕ 4

Глава 1. О континуальности числа предполных классов, содержащих

Р—множество 14

1.1. Доказательство теоремы 1.1......................................................14

Глава 2. Алгоритмы распознавания полноты систем, содержащих

Р—множества 19

2.1. Принятые обозначения............................................................20

2.2. Порождающее множество содержит тождественную функцию и обе константы ..............................................................................26

2.2.1. Проверка эффективности условий теоремы 2.1..............................26

2.2.2. Доказательство теоремы 2.1....................................................32

2.2.3. Следствия из теоремы 2.1 ......................................................39

2.3. Порождающее множество содержит тождественную функцию и одну из констант ............................................................................42

2.4. Порождающее множество содержит тождественную функцию.......48

2.4.1. Критерий А-полноты............................................................48

2.4.2. Система М содержит константную функцию................................53

2.4.3. Система М содержит функцию задержки....................................56

2.5. Порождающее множество не содержит тождественную функцию............65

2.6. Эффективный критерий А-выразимости для систем, содержащих

Р—множества......................................................................70

Глава 3. Полные системы в Р—множествах 73

3.1. Порождающее множество содержит обе константы............................73

3.2. Порождающее множество содержит тождественную функцию и отрицание 80

СПИСОК ЛИТЕРАТУРЫ 88

ВВЕДЕНИЕ

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

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

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

Важнейшим примером истинностных и последовательностных ф.с. являются к—значная логика с одной стороны и ф.с. автоматных функций с другой. Для к—значных логик (ф.с. основная проблема в теории итеративных ф.с. — проблема полноты, была решена. В 1921 г. Э. Постом была полностью описана структура замкнутых классов в двузначной логике. Это описание, изложенное в виде монографии в 1941 году [4], по существу эквивалентно решению проблемы полноты для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции. Для произвольного к > 3 усилиями многих авторов ( C.B. Яблон-

ский [32], A.B. Кузнецов [24], И. Розенберг [5] и др.) в терминах сохранения отношений (предикатов) были последовательно в явном виде построены все предполные классы в Рк, образующие минимальную критериальную систему для распознавания полноты систем функций к—значной логики. Т.е., произвольное множество функций к—значной логики М является полным тогда и только тогда, когда М целиком не содержится ни в одном из предполных в классов.

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

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

1. Функциональная система "суперпозиция" (Рк)е;

2. Функциональная система "композиция" (Рк)к■

Множество функций, определяемых в ф.с. (Pk)z и (Рк)к, совпадает с множеством Рк. Операциями в ф.с. (Рк)к являются операции суперпозиции и обратной связи, а в (Рк)ъ — только операции суперпозиции.

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

При изучении проблемы полноты в ф.с. (Рк)е и (Рк)к фундаментальный результат был получен В.Б. Кудрявцевым. Известно, что ф.с. (Рк)к является конечнопо-

рожденной и, также как в к—значных логиках, множество всех предполных классов образует минимальную критериальную систему. Отсюда следует, что в принципе критерий полноты в (Рк)к может быть сформулирован в терминах предполных классов. Однако, в 1963 году В.Б. Кудрявцев показал [20], что мощность множества предполных классов в (Рк)ъ и {Рк)к равна континууму, и, следовательно, алгоритмический подход не дает эффективного критерия полноты. С этим согласуется результат М.И. Кратко, установившего [18] в 1964 году отсутствие алгоритма распознавания полноты конечных систем о.-д. функций.

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

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

В реальности никакое вычислительное устройство не может работать бесконечно долго, рано или поздно оно должно остановиться. Поэтому представляет интерес о моделировании поведения автоматной функции на конечном отрезке времени. Отсюда естественным образом возникает понятие т-полноты [13]. Множество о.-д. функций М является т-полным, если для любой о.-д. функции / существует такая функция /м 6 [М], что значения функций / и /м совпадают на всех наборах данных длины т. В [14] показано, что множество т-предполных классов конечно, может быть эффективно описано и образует т-критериальную систему. Таким образом, проблема т-полноты разрешима для любого натурального т.

С понятием т-полноты связано понятие А-полноты. Множество о.-д. функций М

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

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

Другие алгоритмически разрешимые случаи могут встретиться при наложении дополнительных условий на рассматриваемые системы. В 1992 году Д.Н. Бабин показал, что существует алгоритм распознавания полноты конечных систем, содержащих все булевы функции [9]. Отсюда естественным образом возникает задача о распознавании полноты систем, содержащих произвольный класс Поста. Все классы Поста разделяются на две части. Для одних задача о полноте алгоритмически разрешима, для классов из другой части — неразрешима. Установить такую классификацию классов Поста также удалось Д.Н. Бабину [10].

В предлагаемой диссертации вводятся и рассматриваются Р—множества о.-д. функций (термин предложен В.Б. Кудрявцевым). Известно, что каждая о.-д. функция однозначно определяется своим множеством состояний Q = {qi, ... , qm}, функцией перехода ф и множеством функций к—значной логики Fi, ... , Fm, реализующихся в состояниях {qi, ... , qm} соответственно [22].

Пусть D — произвольный замкнутый класс в Рк- Р—множество, порожденное классом D — это множество всех ограниченно-детерминированных функций, в каж-

дом состоянии которых реализуется функция к—значной логики, принадлежащая О. Будем обозначать такое Р—множество через Рр. Нетрудно видеть, что Рр замкнуто как в (Рк)так и в (Рк)к■ К примеру, если взять к = 2, £>1 = {0,1}, то в качестве Р—множества получим все автоматы Мура. Если взять к = 2, £)2 = {0,получим множество о.-д. функций, в каждом состоянии которых реализуется функция а.-л., зависящая не более, чем от одной переменной. Заметим, что любой класс Поста имеет конечный базис, поэтому при к = 2 любое Р—множество образует рекурсивное подмножество множества всех о.-д. функций, однако, при к > 3 это, вообще говоря, не так.

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

Основные понятия и определения

Пусть к > 2, обозначим через Рк множество всех ограниченно-детерминированных функций (автоматных отображений), входные и выходные переменные которых определены на множестве бесконечных последовательностей, составленных из Ек,гдеЕк = {0,... ,к-1}.

Будем считать, что на множестве Рк определены операции суперпозиции и обратной связи. В работе будут рассматриваться две функциональные системы — "суперпозиция" и "композиция" (присутствуют операции суперпозиции и обратной связи). Пусть М С Рк. Замыкание множества М С Рк относительно операций суперпозиции обозначим через [М], а замыкание относительно суперпозиции и обратной связи — через [М]к- Функциональную систему "суперпозиция" над множеством Рк обозначим через (Р%, а ф.с. "композиция" — через (Рк)к■

Множество N С Рк называется предполным классом в (Рк)я, если [/V] ф Рк, но для любой о.-д. функции / ^ N. [Ы и {/}] = Рк. Аналогично определяются предпол-ные классы в {Рк)ц-

Пусть /(.Г1,... , хп) - о.д. функция из Рь, задаваемая системой канонических уравнений:

9(0) = 9о,

у(г) = ф{хг(Ь),... , хп{р), д(г)),

где — {до, да,... , др} - множество ее состояний, а до - ее начальное состояние. Функцию к—значной логики, реализуемую в состоянии дг обозначим через Е(]г.

Пусть I > I, Е'к~ множество слов длины составленных из Пусть г,] £ {0,1, ...,р}. Будем считать, что состояние дг является ¿-достижимым из состояния д3, если найдутся такие а^ а2,..., оп € Е1к, что (р(п,г,... , ап, д3) = дг. Состояние дг достижимо из состояния д}, если дг ¿-достижимо из д3 для некоторого £. Будем считать, что состояния дг и д3 связны друг с другом, если состояние дг достижимо из д3 и наоборот. При этом необязательно, чтобы дг ф дГ

Пусть Б — некоторое замкнутое множество функций А;—значной логики. Тогда множество всех о.-д. функций из Рк, таких, что каждая из функций Едо,ЕЯ1,... , ЕПр принадлежит множеству обозначим через Это множество называем Р-множеством, порожденным классом В. Нетрудно видеть, что Рр — замкнутое множество как в (Рк)к, так и в (Рк)т,-

Замечание. Рассмотрим Р—множество Рр, порожденное незамкнутым множеством к—значной логики И с [В]. Тогда Рр также окажется незамкнутым множеством в Рк. Нетрудно видеть, что замыкание множества Рр в обоих функциональных системах совпадает с Ркщ. Поэтому, наибольший интерес представляют Р—множества, порожденные замкнутыми классами к—значной логики.

Введем понятие А-полноты [11]. Пусть т — произвольное натуральное число. О.-д. функции д(х\. ... , хп) и ... ,хп) являются г-эквивалентными, если значения

функций / и /г совпадают на всех словах длины т. Множество М С Рк является т-полным, если для любой о.-д. функции /(х\, ... , хп) € Рк существует такая функция

fM(xi, ... ,xn),fM G [M], что / и fM т-эквивалентны. Множество M Ç Pk называется А-полным, если оно т-полно для любого натурального т. Также будем говорить, что / G А[М] (А-замыкание), если для любого натурального г существует функция /м G [M] такая, что fM т-эквивалентна /.

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

В первой главе решается вопрос о количестве предполных классов, содержащих определенное Р—множество, и доказывается следующее утверждение. Теорема 0.1. Пусть D с Рк и D = [D]. Тогда множество предполных классов в (Рк)к, содержащих Рр, континуально и множество предполных классов в (Pk)s, содержащих Рр, также континуально.

Вторая глава посвящена вопросам существования алгоритмов распознавания полноты систем, содержащих Р—множества. В качестве исследуемой функциональной системы выбирается (P2)v. Пусть к = 2, D — произвольный замкнутый класс алгебры-логики. Пусть VlD — совокупность всех подмножеств M множества Р (о.-д. функции), содержащих Р-множество Рр и таких, что M \ Ро конечно. Рассматривается задача о существовании алгоритма распознавания полноты систем из Q.D относительно операций суперпозиции.

Получены следующие результаты. Теорема 0.2. Если D С P2,D = [D] и D содержит тождественную функцию а.-л. и одну из констант, то в (P2)s существует алгоритм распознавания полноты систем из

Доказательство теоремы конструктивно, т.е. алгоритм для каждого D указан в явном виде.

При D = {0,1, х, ¿с} этот результат был получен C.B. Алешиным в 1977 году [8].

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

Пусть — совокупность всех подмножеств М множества Р, содержащих

и о.-д. функцию /, таких, что множество М \ конечно.

Пусть о.-д. функции Сд(х), С\{х) — нулевая и единичная задержка соответственно. Обозначим С = {С?о(а;), С^ж)} .

Теорема 0.3. Пусть множество И содержит тождественную функцию а.-л. Тогда в (Р2)ц существует алгоритм распознавания полноты систем из ОР{С), где С — константная о.-д. функция.

Теорема 0.4. Пусть множество И содержит тождественную функцию а.-л. Тогда в (Р2)т, существует алгоритм распознавания полноты систем из ОР(д), где д принадлежит множеству

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

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

Если £> = {0} или £> = {1}, то не существует полных в (Р2)е систем из 0,°, следовательно об алгоритме распознавания полноты говорить бессмысленно.

Пусть О = {0,1}. Тогда полные системы в существуют, но вместе с тем справедлива следующая теорема.

Теорема 0.5. Пусть множество И = {0,1}. Тогда в (Р2)2 не существует эффективного критерия распознавания полноты систем из £1°.

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

Теорема 0.6. Пусть 0,1 £ Г>. Тогда в (Ро)е существует полная система, не содержащая базиса.

Теорема О.Т. Пусть 0,1 е И. Тогда в (-Рд)е существует базис.

решетке Поста

Теорема 0.8. Пусть порождающее множество D содержит тождественную функцию а.-л. и отрицание. Тогда в существует полная система, не содер-

жащая базиса.

Теорема 0.9. Пусть порождающее множество D �