Решение проблемы r-полноты для автоматов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ .ГОСУДАРСТВИПШЙ У1ШЙРСИТКГ игл. МЗ.ЖШ ЮСОВА

Механико-математический ¡пакультет

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

ЕУИШ Вячеслав Александрович

УДК 519.736

РЕШЕНИЕ ПРОБЛЕМЫ '»ПОЛНОТЫ ДЛЯ АВТОМАТОВ Специальность 01,01.09 - математическая кибернетика

АВТОРЕФЕРАТ

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

Москва - 1992

Работа выполнена на механико-математическом факультете- МГУ

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

профессор Ю.Глухов, доктор физико-математических наук, профессор В.Н.Редько, доктор физико-математических наук, профессор Ю.И.Янов

Ведущая организация - Новосибирский государственный университ

Защита диссертации состоится , 1992 г.

в 16 час. 05 шн. на заседании специализированного Совета Л.053.05.05 при Московском государственном университете им. М.В.Ломоносова по адресу: 119899, ГСП, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08.

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

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

<1$ лллА^ 1992г.

Ученый секретарь специализированного Совета Д.053.05.05 при МГУ доктор физико-математических наук

В.НЛубариков

- (

'! - з -

i* 'ч <•».» »

, î ОЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

I

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

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

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

Для К-значных логик - ф.с.^, основная проблема в теор! итеративных ф.с. - проблема полноты, была решена. Усилиями многих авторов /Е.Пост, С.В.Яблонский, А.В.Кузнецов, А.И.Мальцев, Ло чжу-кай, Н.Розенберг и др./ были последовательно•в явном ви; построены все предполные классы в Р^ , образующие минимальную критериальную систему для распознавания полноты систем функций К-значных логик. Важно отметить, что • для явного задания множе< ва предполиых классов в был использован аппарат сохранения функциями /("-значных логик отношений /предикатов/. Именно на этом пути было проведено завершающее построение множества всех предиолных классов в АГ-злачных логиках /4,6/.

Проблема полноты для ф.с. автоматных функций с конечной п мятью и ограниченным временем вычислений долгое время оставала открытой. В диссертации приводится полное решение этой проблем В качестве исходной модели рассматривается ф.с. ¡о-д. » элемент ми которой являются конечно-автоматные или ограшченно-детерми рованные функции /о.-д. функции/, а операциями - операции супе

позиции и обратной связи.

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

Проблема Т-полноты. Пусть К>-2 • Пусть ~ последо-

вателъностная ф.с., элементами которой язляются о.-д. Функции, а операциями - операций суперпозиции и обратной связи; при этом предполагается, что переменные о.-д. функций, принадлежащих /^я

г-оо ' У'

принимают значение из с« » множества всех бескопечшс последовательностей, составленных из элементов {о,I,..., к-1 }■, Пусть ГС - фиксированное натуральное число, большее или равное единице. Множество Р0~о, называется 'с.-полным, если для любой

о.-д. функции Ро.-д. из о.-д. функций множества ]ТС с помощью операций суперпозиции и обратной связи можно получить о.-д. функцию , совпадающую с на всех наборах, составленных из слов длины ГС . Проблема ^-полноты состоит в описании 'с-полннх подмножеств множества Оу^-д. •

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

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

В /2, 29/ показано, что для решения проблемы' -полноты операция "обратная связь" оказывается несущественной, т.е. в данном случае эта операция выразима через операции суперпозицш Отсюда следует, что проблема полноты в К-значных логиках является частным случаем проблемы ^-полноты при А. . Вместе с тем, при Х-^О. существует принципиальное различие между ф.с., элементами которой являются функции К-значных логик, с одной стороны, и.отображения, осуществляемые о.-д. функциями на словг длины , с другой. Множество всех детерминированных отображен!

рассматриваемых на словах длины , порождает специальное залпа

'с

тое подмножество в К-значной логике, существенно зависящее от двух параметров - параметра К и параметра 'с . Используя есте< венную аналогию между проблемой И-полиоты и проблемой полнот] в конечнопорождеиных замкнутых классах К -значной логики, мо; но ввести понятие ^с-нредполного класса и показать, что всякое множество о.-д. функций является 1>полным тогда и только тог; когда оно целиком не содержится ни в одном из -предполных классов: совокупность 'с-предполных классов конечна, может бьт описана эффективно и образует минимальную ^-критериальную систему; при этом множество 4. -предполных классов изоморфно множеству предполных классов в К-значных логиках. Таким образом для любого 1 существуют алгоритмы для распрзнавашя 'С-по. ноты конечных множеств о.-д. функций. Также, как и в К-значны: логиках, каждый из этих алгоритмов может быть задан с использованием эффективно описываемых 'С-критериальных систем, а наилу шин из них получается на пути явного описания множества исех ^

преднолннх. классов.

Развитие теории итеративных ф.с. шло но пути изучения конкретных моделей ф.с, Е 1921г. Е.Постом была полностью описана структура замкнутых классов а двузначной логике. Это описание, изложенное в виде монографии в 1941 году, по-существу эквивалентно решению проблемы полноты для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции /5/. Интерес к изучению итеративных ф.с. особенно возрос в начале 50-х годов в связи с появлением ЭВМ и необходимостью синтеза сложных кибернетических устройств. В Т954 году СМЗ.Ябчоиским /-.'/ била решена проблема полноты в трехзначной логике. Поолс появления работы /3/ усилия многих авторов были сосредоточены на решении проблемы полноты в произвольных К-значных логиках /см. I и цитированную там литературу/. Начиная с 60-х годов наряду с К-зпачпыш логиками стали интенсивно изучаться итеративные ф.с., здепьпташ которых являются автоматные отображения /I, 3,10,11/, функции счетнозначных логик /12,13/. Позже появились работы, связанные с изучением итеративных ф.с., содержащих в качестве элементов вычислимые функции /7.1 А,'¡5/, программы и схемы программ /16,17/.

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

В наиболее обшей постновкв проблема полноты для о.-д, функций изучалась в работах 13.1;.Кудрявцева /I/ и М.И.Кратко /II/.

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

ся конечнопоровденной /1,2/ и, также как в К-значных логиках, множество всех предполных в ^о-^, классов образует минимальную критериальную систему. Отсюда следует, что в принципе критерий полноты в 9 может быть сформулирован в терминах предполных классов. Однако, как показано В.Б.Кудрявцевым, мощность множест ва предполных в ^.-д. классов равна континууму и, таким образом, эффективного критерия полноты для о.-д. функций не существует. О этим согласуется результат М.И.Кратко, установившего отсутств: алгоритма распознавания полноты конечных систем о.-д.функций.

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

В 1964 году В.Б.Кудрявцев в качестве одной из наиболее важ ных и естественных можификаций проблемы полноты в ^о-д. предлож рассматривать проблему 'с-полноты. Эта проблема, как отмечено выше, допускает эффективное решение, для всякого 'сЪА. сущест вует алгоритм распознавания 'С-полноты конечных систем о.-д. фу ций, и каждую функцию, принадлежащую любой последовательности© ф.с., можно аппроксимировать отображениями, осуществляемы™ о.-функциями на словах длины 'С .

Изложение части результатов по проблеме ^--полноты, связан ных с исследованием базисных ^-полных систем о.-д. функций, со держится в /2/. Проблема 'С -полноты для некоторых специальных систем о.-д. функций со специальным набором операций рассматрив

лась в работах Ф.Гечега, Б.Тальхаима, М.Пэака, 3.Ёжика, Г.Хорвата, Р.Дёмёши, Б.Имреха, И.Вираха и других авторов /19,20,21,22,' 23,24,25,26/.

С проблемой ^-полноты тесно связана Проблема А-полноты /аппрокеимационнои полноты/. Множество п называется А-полным, если для любого 'с >1. это множество является 'С-полннм. Проблема А-полноты состоит в описании А-полных подмножеств множества

Проблема А-полноты исследовалась в работах /27,29,30.31/. Оказалось, что эта проблема алгоритмически неразрешима. Тем не менее критерий А-полноты может быть сформулирован в терминах А-предполных классов, число А-предполных классов счётно, множество А-предполных классов рекурсивно перачислимо, и каждый А-нредпол-ный класс может быть описан эффективно. Белее того, каадий предполныи класс является А-предполным классом к наоборот: для любого А-предполного класса существует ^С^А. такое, что этот А-предполный класс в то же время и 'с-предполон. Отсюда следует, что проблема элективного описания А-предполных классов сводится к проблеме эффективного описания 'с-предполных классов для всех

Это позволяет вести поиск и находить примеры содержательных подклассов множества конечных систем о.-д. функций, для которых существует алгоритм для распознавания А-полноты /31/. В /30, 31/ дано явное описание множества всех А-предполных /и, следовательно, Т-предполных/ классов в двузначном случае и устакошюпа асимптотика их числа при Т-> «>0 . Там же на примере решения проблемы гС-полноты для множеств, содержащих все одноместные о.-Д. функции, проиллюстрировано существенное различие между проблемой полноты в конечнозначных логиках и проблемой ^полноты для о.-д. функций.

Цель работ». Для любых К^Ч Дать явное в терминах

сохранения отношений описание множества всех 'С-предполных классов и тем самым решить проблему 'С-полноты для автоматов.

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

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

Методы исследования. Для решения проблемы '»полноты для ав томатов использован аппарат сохранения функциями отношений /предикатов/. Аналогичный подход оказался весьма эффективным при опи еэшш множества нреднолных классов в К-значных'логиках. Однако значительно более сложная структура автоматных отображений по сравнению с функциями К-значных логик во многом усложняет задачу и приводит к необходимости разработки новых методов для её решения. Каждое отношение, класс сохранения которого является rt предполным, при уде не просто совокупность наборов элемен-

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

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

тическом центре им. С.Банаха в Варшаве, на международных конференциях в Германия, Словении, а такте на Кубе.

Структура и объем работы. Диссертация состоит из введения, одиннадцати параграфов и списка литературы. Библиография включает 84 наименования, в том числе 14 работ автора по теме диссертации. Полный объем диссертаций - 329 страниц машинописного тек,ста.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Основным результатом диссертации является явное описание семи семейств отношений - семейств ïE^fv1, ifcC'vi

11 Доказательство Теорем 5.1, 5.2, 5.3, 5.4 /§5/. Приведем здесь описание указанных семейств и формулировки Теорем 5.1, 5.2, 5.3. 5.4. Заметим, что проблема гС-иолпоты для о.-д. функций и проблема t-полноты для произвольных детерминированных функций эквиваленты: при этом операция "обратная связь" элиминируется. Поэтому в диссертации проблема t-полноты решается в функциональной системе Fy, ', элементами которой являются детерминированные функции, а в качестве операции используются только операции суперпозиции.

Пусть /О 2, Ек=7 о, 4.,,,.. ^-i}, Е";< - множество слов

длины "Ь, составленных из элементов Еь . Каждое такое слово будем

-Ут °°

представлять в виде CL- (РМ)1 • • Cf-WJ . Пусть EL-- U Eif . Очевидно можно считать, что переменные д. функции, принадлежащих fj^, принимают значения чз множества ЕГ^ . На множества f^, ' обычным образом вводятся операции суперпозиции, а также понятия замыкания подмножеств относительно этих операций.

Пусть t^d,* Д. функции j-far» I ,Хги; из R^.' на-

зываются ^-эквивалентными, если для любого набора J

элементов из

r„)cin.J совпадаете Cji^dy/^fc). Пусть

- 12 -

Рр . Множество 74, называется /^-полным, если для любой д. функции Рд. в замыкании множества Ж содержится д. функция, ^-эквивалентная . Множество ТС^Рд. называется предполным классом, если УС не является 'С-полным, но для любо: д. функции Рд, /ТС множество Ж 'С-лолно.

Пусть А. , Т= ("¿Л/-"/ - произвольный набор поло-

Г—гр г—

жительных целых чисел, и с^^с^ ЬХс^ , Любое непустое под множество Е^ называется отношением, заданным на Е^Г, а число Р - арностью этого отношения. Д. функция /-(Х-1/'"; Хи,) из сохраняет отношение R , если для любой совокупности

(Я^.I"'I)/'" I Фаг"! наборов из £ набор

("сК^Г''/ С1лЬ ''' > '"' > )) также принадлежит . Множес во всех д. функций, сохраняющих отношение /\ , обозначим через

и№)/§1/.

Пусть . Определим функциюЭГ, отображающую множество

ф Е* т 1°>1г- } • пусть ^^ -¿=

Тогда:

Ща*,^)-о , если

Щ^а^)- I ¿^-Ь-1) .если

а^; = -Ь .если о*.(±).

На множестве Е^ определим отношение предпорядка " ^ ". Пусть А= (^Г'Ч^Ц^^Г-/^)- элементы из В^} Л'%А > если для любых С,^ из ^ЗГСО-о, • Пусть

/\- / • • • /^ ~ произвольный элемент из Ег^Г. Множество всех Д

из Е/^7 таких, что

АЧА

, назовем ^множеством, задаваемым элементом Д . Для обозначения ^множеств будем использовать символ . Любое Эр-множество разбивается на два подмножества: Д^ - множество всех максимальных по предпорядку

» ^ " элементов из А , и Д^ - множество всех оставшихся элементов. Таким образом, при /г.-4 Д = р . Нетрудно видеть, что для любых С, I из -1: значение ЗГС^'.си) не зависит от выбора элемента из Д. ' . Поэтому число ЗТ^ос," с^-)

обозначим через ^д^л/^ I ^Г-множество Д назовем приведенным, если для любых таких, что Сф^ , ^Дд [¿,4 О. Будем

считать, что всякое ^-множество удовлетворяет следующему свойству:

для любых ¿,¿1 £ из , если , то

е} Ж^&С.Ь/] (¿>¿7

Пусть Д?г • Подстановку ^ чисел & назовем Д-подстановкой, если для любого элемента (Л^.,-.изД набор («ОД//' • также принадлежит Д . Пусть ¡3^:1.., Множество {С^г-у

элементов из ¿^ ' назовем Д-совместимым, если существует совокупность Д-под-становок (Гк/ • / «У^ такая, что для любых ^ из

6, ^ т -¡Л,Я} имеет место соотношение о и в (-■ ,

Пусть Д . Отношение назовем Д-рефлексивным,

если

, и Д-симметричным, если для любых («<»;■••¡^Ю из и Д-подстановки

I "'./ также при-

надлежит ^ . Пусть Д -приведенное 9/чдаожество. Отношение £сД назовем Д-элементарным, если это отношение Д-реф-лексивно, Д-симметрично, а множество Д//? Д-совместимо. Пусть /? - Д- элементарное отношение. Легко убедиться в том, что существуют множества

таете, что справедливо следующее:

а/ если набор слов (Я^.,не принадлежит отношению

- 14 -

то для некоторой ¿^-подстановки X

имеет

6/ Д.Ш1 любых C,j ИЗ -{Лг" I У, ^ ^ ' а' е

место неравенство

^LChjX^í^oJ)'

Пусть R - Д- элементарное отношение, произвольным элемент из "•/ «J . Определим подано-

C^A),Qr (А) множества tic-:

C¿ (Д j тогда и только тогда, когда существует о/ё" ^ j Cl'tyc) = и любой элемент

жсства

■j А принадлежит R, , если

такое, что

HJ

(Д) тогда н только тогда, когда в Д/R существу ет элемент такой, что

Пусть J\ >, ¿_ . R-^J" - произвольная система

Д-элементарных отношений. Систему отношений назовем Т1-совместимой, если для любых

мно

жестсо (А) отлично от множества . Систем отношений назовем "jV-совместимой, если для любых

множества

одн

временно либо пусты, либо не пусты, причем, если

то для всякого существует J такое, чт

■if Ре И).

Семейство отношений ^к(^) . Пусть t Д - приве

денное ЗГ-множество арности Отношение принадлеж

семейству (Д] , если для некоторого у^ ^ Л. отношение представило как пересечение /\.-элементарных отношений /

система отношений -[Rf- •■/ R-^J- является г7~7-совместш/юй, совместимой, для люинх oG-{d.r..lfLJl A^AIR^ множество Q^t.04

не пусто и справедливо следующее.

Пусть ¡7^:1 , числа принадлежат множеству

У-Г",/}, А!>4) " произвольный ¡га-

бор элементов из множеств соответственно.

Пусть

Тогда, если

то имеет место соотношение л

Семейство отношений ¿ТсО*^ - суть объединение семейств взятое по всем приведенным 5Г-мпохествзм Д & , где У ^^¿^•'•гЩ^таши, что с/.

Пусть- Д-элементарное отношение. Пусть ,

Через ¿£>(/4,) обозначим подмножество , совпадающее с

, если Ог

не пусто, и совпадающее с

(/V в противном случае.

Семейство отношений

. Пусть , Л

- приведенное ^-множество арности . Отношение /\СД принадлежит семейству (Д] , если для некоторого уЧ отношение представимо как пересечение /\-элементарных отношений система отношений / является '"/"'-совместимой, IV-совместимой, для любого Дбг Д ¡^ множества (А/, (А) пусты, существует .по крайней мере одно С такое, что множество (^¿(А) пусто, и справедливо следующее.

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

Й-..,/}, Г»* АШг-Л) - произвольный па-

бор эдаментов из множеств Д//?^-*-,,. , Д 2. соответственно. Пусть

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

- 16 -

Тсада, если числа попарно различны, то

Семейство отношений

й - суть объединение семейств

, взятое по веем приведенным ЗГ-множествам Д С ^ , гдвТ= С**/'"№),; ) Щ € таким, что

^СА)^/ • Ф при , еслж К>2. , при,

если 2..

Семейство отношений . Пусть КЬ 2. , Д - приве-

денное ^множество арности . Отношение принадле-

жит семейству Т)^ [А) , если для некоторого уЧ ^ 4 отношение представило как пересечение Д-элементарных отношений

, система отношений является Т-сов

мостимой, ""[//"^"-совместимой, для любого

множества

ПУ°™. ПРИ дай всякого ¿£-¡/¡-4^}

множество С^±{А) не пусто и справедливо следующее:

а/ Пусть , числа ¿¿¡••■¡ё^ принадлежат множеству

{¿г-.АЬ ^ с^г-Аь^А^^гЛ) - наб°рэлементоБ из

множеств Д/Я^'"/ соответственно такой, что для любых

из ЭК&ОлМ . пусть

и имеют место соотношения ^

Тогда существуют из •[¿¡•■■/У? такие, что

2},.,.множество .., А^} является Д-сов-

местимым и

«/цсЛ^.т™, ^'ПКФ/-

Семейство отношений РК - суть объединение семейств £)|<(Л),

взятое по всем приведенным ЯчиножестБам ~ Е^Г , где

Т- таким, что

'Ък(!с}=^ при , всшК>9. , при , если

Пусть К» ,ГГ7- (-Ь ¡Ь), А | А-ь - 3= множество

такое, что Л^ (.4,2)-£.

- Семейство отношений при любых .

Отношение ¡^^Мк^) тогда и только тогда, когда С Д ^, Ь <^

совпадает с некоторым отношением частичного порядка, онределен-г—'Т7

ннм на и ГиЛбКлцКш в точности К жнимнльнкх и К максимальных элементов.

Семейство отношений

при любых К¿-2

Отношение тогда и только тогда, когда /уСД^£ < 'с,

существует подстановка , определенная на ЕГ^ и разлагающаяся в произведение циклов одинаковой простой длины р Ъ , график которой совпадает с К » т.е. для любого если (сцОг,^ /? , то а^^

Пусть ~Ь>> - совокупность всех отображений множества

Ё^в множество подстановок /перестановок/, определенных на Е^. Подстановку, которую отображение

ставит в соответствие элементу ЕЕ^ , обозначим . Через Я-*^ обозначим подмножество , состоящее из всех отображений ^Р таких, что для любых СЬ-^1 из Е^' совпадает с Но,' , если Ж^^о!) ^ 4. Пусть /V? - подмножество Е^^ ,

состоящее из всех Стаких, что для-любых из

4 . Пусть /ч ~р'71', где р - простое число, и 0- = - абелева группа, в которой каждый не-

нулевой элемент имеет порядок р . Семейство отношений

для любого

- 18 -

если /<= р^, где р - простое число, Пг^-А.). Отношение

тогда и только тогда, когда для некоторого ^С спра

ведливо следующее:

а/ Пустьк'=:'Р^/3>2. Тогда £СА4 ; элемент ОЧ^/^ из принадлежит /\ , если

и не принадлежит ^ в противном случае;

б/ Пусть К-2!п'. Тогда ; элемент

из д^4 принадлежит , если

ы^сц/,

и не принадлежит в противном случае.

Заметим, что совпа-

дают соответственно с семействами отношений & » с

помощью которых описываются все предполные классы в К-значных логиках /1,4,6/. ^

Пусть.Т7^ Аь^ ^К; ^-множество такое,

что

Семейство отношений ~У/< РФ (1^-Ос) ф $ при любых , Отношение тогда и только тогда, когда/^СД^

и справедливо следующее: Р^^Ц/ 113 Ал^ принадлежит £ если С^= , и не принадлежит в противном случае;

существует ^6гтакое, что любой элемент Сиз ^ принадлежит , если для некоторого С^бгЕ^

, и не принадлежит в противном случае. Пусть К>>0. , ~ объединение семейств отно-

шений

Теорема 5.1. Пусть К <>.2 » • Произвольное

тожество 01,— /^является, ^-полным тогда и только тогда, когда не сохраняет ни одного отношения из ,

т.е. ЖфиСЯ).

Теорема 5.2. Пусть /<)>.2 , ^^ 4. , Ж. - произвольный. ^-предполный класс е Тогда существует отношение такое, что

Теорема 5.3. Пусть К>/0. . А • Класс сохранения любого отношения £\ изТх/кС'С^ является ^-предполним.

Теорема 5.4. Пусть /^->2 . • Пусть отношения

принадлежат . Тогда справедливо следующее,

а/ Пусть /? , /ч' принадлежат различным семействам из множества ССМОЙС73 МкМ, Тогда иСУФгЖ')}

б/ Пусть ^ , принадлежат объединению семейств

, причем . Тогда

в/ Пусть , принадлежат объединению семейств ,

ШЪкМ и имеюг разную арность. Тогда О^Фу

г/ Пусть £\ , Я принадлежат одному из семейств ■^(ъ) , ^С'сУ и имеют одинаковую арность Тогда

равенство

равносильно существованию подстановки ¿Г числа ( Я- такой, что для любого элемента (Ядун.,«-/^ из

>'"> принадлежит , для любого элемента(О^.^а^

из (а^у у.... СЬ^1^)) принадлежит ;

д/ Пусть , ' принадлежат семейству ^ы^Х) . Тогда равенство

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

Остановимся на содержании параграфов диссертации. В первом параграфе вводятся основные понятия и определения, необходимые для дальнейшего - понятия ^-полного множества, /Ь-крятериальной системы, гС-предиолного класса и т.п. Результат

второго параграфа носит- общий характер: показано, что для любого система, состоящая из классов сохранения всех отношений -множеств упорядоченных наборов слов, длина каждого из которых не превосходит t, является fc-крлтериальн ой. Множество ^.-предполных классов изоморфно множеству предполных классов в Р^ / /<-знач-ных логиках/. Поэтому решение задачи об 4,-полноте эквивалентно решению задачи о полноте в . Известно, что множество всех пред полных классов в Р^ совпадает с классами сохранения отношений /предикатов/ из некоторой совокупности отношений, которая распадается на шесть семейств - семейства^tjfyМ,fc /1,4,6/. В параграфе третьем приводится описание этих семейств. По сравнению с /1,4,6/ описание семействti, Q несколько иное. Вводятся понятия "^-элементарных, ¿/-элементарных a D-элементарных отношений. Показано, что каждое отношение из семейств"*^ íj и*Ь может быть представлено как пересечение ^-элементарных, ¿/-элементарных и 7)-элементарных отношений соответственно: при этом семейство D расширяется до семейства отношений^ . Множество всех отображений, осуществляемых детерминированными функциями на словах

t

длины f , порождает некоторое замкнутое подмножество в К-значно] логике. Оказывается, что это подмножество суть пересечение (fC-Aj-го замкнутого масса в P^/t, каждый из которых сохраняет некоторое отношение из семейства Т).

В параграфе четвертом определяется важное для всего дальней' шего изложения понятие ЗГняножества. Для придания геометрической наглядности этому понятию из множества всех ЭР-множеств выделяет' ся совокупность SJP-множеств П . Для обозначения Эр-множеств используется символ А .

В пятом параграфе приводятся формулировки основных результа тов диссертации /Теоремы 5.1, 5.2, Ь.о, 5.4/. Дано явное описапи

семи семейств отношении - , $*(*:}, ^кМ^Х.),

классы сохранения которых в точности совпадают с множеством всех 'С-предполных классов; при этом сшейства^С^^С^.^ОУ^^Л^сф ^(^овпадают соответственно с семействами X, /Ь" /§3/.

Важные понятия тупиковое™, приведенности, Д-рефлексивиос-ти, Д-симметричности отношений, а также ^Т^гундаментов, С-фундаментов ЭГ-множеств и отношений определится в параграфе шестом. С их помощью из множества всех отношений выделяются пять

_ А Л

семейств - семейства £1</С);^ • Затем с использованием понятия /\-симметричиого ядра из семейства ^ выделено подсемейство Сг, . Показано, что классы сохранения отношений, нринад-' лежащих объединению семейств ПРП некотором

естественном ограничении на-длину слов образуют ^Г-критериальпую

А

систему /Теорема 6.2/; при этом любое отношение из семопствЦгу, , А 'У-

Vи является подмножеством некоторого УРмножества. В параграфах седьмом, восьмом, девятом и десятом происходит последовательное выделение из объединения семейств отношений , и подсемейств таких, что для любого отношения

К 4 А А А А

^ , принадлежащего объединению семейств^ д^Д^Т^С?^ в этих подсемействах всегда найдется отношение Я' , масс сохранения которого содержит в себе класс сохранения отношения

Параграф седьмой состоит из нескольких частей. В п.1 этого параграфа рассматриваются вопросы, связанные с сохранением функциями |<-значных логик упорядоченных наборов отношений, определяются понятия ^-существенной переменной, Л-существенной и р-существенней функций ^-зпачных логик. В пп. 2,3 вводятся понятия класса ^.-эквивалентности, СО-фундаментов элементов множеств, ЗГ-множеств и отношений, с использованием которых доказываются ваглие Теорема 7.1 и Теорема 7.2. Для придания большей

наглядности понятию СО -фундамента из совокупности ^множеств /---*

П /§4/ выделяется подмножество Г] • В п.4 даны определение свойства отношений, описание подсемейств ^т« и М семейства отнс тений а также подсемейства ^ семейства отношений ¡С^ .

'Рг'

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

/-О

отношенийН^З^Х)^.вводятся понятия Д ¿-элемента]:

А

них, Д-однородных отношений, а также понятие 0)-представления отношений. Показано, что любое отношение из семейств Н^ , ,Т^к мокет быть представлено как пересечение Д^элементарных и Д-однородных отношений.

В параграфе девятом рассматриваются некоторые свойства отношений из семейств 1 . . Вводятся понятия -совместимо го множества, Д,-элементарного отношения, ^-представления, представления и "£) -представления отношений. Из семейств ,

выделены отношения, которые могут быть представлены в виде пересечения Д-элементарных отношений, обладают ¿^-свойством,

¿/-свойством, гу, ц) -свойством, "ь- свойством, (р,2/-сзойством,

свойством. Показано, что множество всех таких отношений з точном совпадает с объединением семейств/§5/. Для этого в начале параграфа доказано несколько вспомогательных лемм, связанных со свойствами систем отношений из семейств"^Т) /§3/.

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

В параграфе одиннадцатом доказывается 'С-предполкота классо! сохранения любых отношений, принадлежащих семействамЧ^О^),

- 23 -

М^ (ъ)приводятся условия совпадения классов сохранения отношений из различных семейств.

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

ЛИТЕРАТУРА

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

2. Кудрявцев В.Б., Алешин С.В., Подколэин А.С. Ввсдтме в теорию автоматов. - М., Наука, IS85, 318 с. /библиография - 87 наименований/.

3. Яблонский С.Б. Функциональные построения в К-зн£1Чной логике. -В кн. Труды матем. ин-та им. В.А.Стоклова, т.51, Изд-во АЛ СССР, 1958, с. 5-142 /библиография - 59 наименований/4, fioaenberg J. Uber dl<5 functionale Vollatandigkeit in den

mehrwertigen Logjken. - Praha, Hoxpravy Ceskoslovenake Academie Ved.1970,v.80, N 4,p.3-93 /библиография - SO наименований/.

5. Post K. Two-valued iterative systems of mathematical logic.-Prinaton, 1|}41.

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

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

8. Кузнецов А.В. Математика в СССР за сорок лет. - М., 1959, т.1, §13, с. I02-II5.

9. Nozaki A. Realisation des fonotion3 definies dans un ensemble fini a I'aide dea organes elementairs d'eiitrec-aortie // Proc.

- 24 -

Japan.Acad.-1970, Suppl.-V.46, No.6.-P.478-482.

10. Летнчевскиы A.A. Условия полноты в шассе автоматов Мура.

Б кн.: Материалы научных семинаров по теоретическим и прикладным вопросам кибернетики, вып. 2, Клев, 1963.

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

с• 35-J7.

12. Яблоиский C.B. О предельных логиках. - ДАН СССР, 1958, т.118 М, с. 657-660.

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

14. Захаров Д.А. Рекурсивные функции.Новосибирск, Изд-во НГУ, 1970, 199 с.

lb. Лавров И.А. Использование арифметических прогрессий К.--ого порядка для построения базисов алгебры примитивно рекурсивнь функций. - ДАН СССР, 1967, т. 172, Ш, с. 279-282. 16„ Глушков В.М. О полноте систем операций в электронных вычисли тельных машинах. - Кибернетика, Киев, 1968, JJ2, с. 1-5.

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

18. Daasow Y. Ein modifizierter Vollstandigkeitabegriff in einei Algebra von Automatenabbildungen: Oiaaertation Doctor В., Rostock, Universität, 1978.

19. Gecseg F. On R-producta oí automata, I-III, // Studia Sei. Math.Hung. 1.-1966.-P.437-441, 443-447; 2.-1967--P.163-166.

20. Gecaeg F., Peak J. Algebraic theory of automata.-Budapest, Academia! Kiado, 1972.

21. Тальхамм Б. О критерии полноты тина Слуцецкого для стабильных автоматов. - В кн. Методы и систем» технической диагностики. Вып. 2, Саратов, 1980.

22. Irarsh В. Oil finite nilpotent automata // Acta Cybernetika.-t.5, Szeged, s.281-293. 1981.

23. Esik Z., Horvath G. The ^^producta is homomori'icail.y General. - Papiers of automata theory, Budapest, 1983-

24. Domosi P. On coacade products of standart automata.-Budape3t, 1984.

25. Gecseg F. Product ci automats. -И«г11п, Acadfimy Verlag, 1906.-P.108.

26. Balk Z., Viregh I. On product of automata with idenfily Ц Acta Cybernetioa.-T.7, Szeged, a.299-311, 1986.

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

-■ Математ. заметки, вып. 6, с. 687-697, 1972.

Литература по теме диссертации

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

29. Буевич В.А. Критерий А-полноты для автоматов в терминах А-Предлолннх классов. - Banach Center publication, РВД, Warsaw, я.53-63, 1982.

30. Буевич В.А. Условия А-лолногу для конечных автоматов, часть

1-ая. - М., Кзд-во МГУ, 1985, 104 с.

31. Буевич В.А. Условия А-полноты для конечных автоматов, часть

2-ая. - М., Изд-во МГУ, 1987, 109 с.

'62. Буевич В.А. Критерий ^-полноты для автоматов с К-значным алфавитом. - Ш., Изд-во ШМШ РАН, 1992, 2G с.