Содержание
1 Основные понятия и результаты.............................. 10
2 Отношения; тупиковые и приведенные отношения............... 16
3 Понятие 7г-множества. Д-рефлексииные отношения............. 19
4 Семейства отношений Gi(A:,r), N\(k,r), V^(A,г), Ь\(к,т)}
Qo(k,T),Q1(k,r),Q2(k,r)................................... 25
5 S-тупиковые отношения. S-критериальность S-гупиковых
отношений................................................. 30
6 Критерий полноты в Р*. S-критериальные системы в Р*. . 39
7 Семейства отношений {Z(k, 1), /3(&, 1),
D(M), L(k,l), N(k,l)}..................................... 43
8 S-нредполиота S-миожеств, принадлежащих классам сохранения отношений из объединения семейств Z{k. 1), N{k) 1),
D(k, 1), L(k, 1) и I(k, 1)................................ 51
9 Семейства отношений Z(k) т), D(h, г), N(k, т), I(k, г), L(k, т)
и V(k.r). Доказательство теорем 1.4 - 1.7................. 59
10 О числе S-предполных классов в функциональной системе
Р1........................................................ 67
11 О полноте в Р£ и А-иолиоте S-множеств детерминирован-
ных функций, содержащих все одноместные детерминированные S-функции..................................... 69
12 Об алгоритмической разрешимости задачи об А-полноте
для систем ограниченно-детерминированных функций, содержащих все одноместные S-o.-д функции.............. 79
(к/
Введение
Одной из важных проблем, рассматриваемых в дискретной математике и математической кибернетике, является проблема полноты для разных функциональных систем. Функциональная система представляет собой множество функций и множество операций над этими функциями. Проблема полноты для функциональных систем состоит в описании всех таких подмножеств функций, используя которые с помощью операций функциональной системы можно выразить все принадлежащие функциональной системе функции.
С точки зрения алгебры функциональные системы могут рассматриваться как вариант универсальных алгебр [1]. Существенной особенностью функциональных систем, выделяющей их из общего класса универсальных алгебр, является содержательная связь функциональных систем с реальными кибернетическими моделями управляющих систем и отражение важнейших характеристик таких моделей: функционирования, правил построения более сложных систем из заданных, описания функционирования более сложных систем по функционированию его компонент.
Центральное место среди функциональных систем принадлежит итеративным функциональным системам, представляющим собой множество дискретных функций с операциями итерации — суперпозиции, обратной связи, а также их модификациями |2,3). Развитие теории итеративных функциональных систем шло по пути изучения конкретных моделей функциональных систем. В 1921 году Е.Постом была полностью описана структура замкнутых классов в двузначной логике — это описание, изложенное в монографии в 1941 году, по существу эквивалентно решению проблемы полноты для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции [4,5,6]. Интерес к изучению итеративных функциональных систем особенно возрос в начале 50-х годов прошлого века в связи с появлением ЭВМ и необходимостью синтеза сложных кибернетических устройств. В 1954 году С.В.Яблонским [7] была решена проблема полноты в трехзначной логике. После появления работы |7] усилия многих авторов были сосредоточены на решении проблемы полноты в произвольных Ахзначных логиках. Начиная с 60-х годов прошлого века наряду с Ахзначными логиками стали интенсивно изучаться итеративные функциональные системы, элементами которых являются автоматные отображения [8,9], функции счетнозначных логик [11,12|. Позже появились работы, связанные с изучением итеративных функциональных систем, содержащих в качестве элементов вычислимые функции [12,15], программы и схемы программ [13,16].
2
Изучение конкретных и важных с точки зрения приложений моделей итеративных функциональных систем позволило накопить опыт в их исследованиях, отточить и разнообразить проблематику. Возник ряд задач, примыкающих к задаче о полноте, таких как существование и оценка сложности алгоритмов распознавания полноты конечных систем, исследование базисов, гомоморфизмов и конгруэнций, сравнения операций в функциональных системах и т.п. [17,18,19,20].
Как показано в [2] итеративные функциональные системы могут быть разделены на два типа: истинностные функциональные системы и последовательностные функциональные системы. В первом случае функции, принадлежащие функциональной системе, вычисляются без использования, а во втором — с использованием ’’памяти”.
Среди всех истинностных функциональных систем центральное место занимает функциональная система Рк, состоящая из функций к-значной логики и операций суперпозиции над ними. Это объясняется прежде всего тем, что, во-первых, в большинство реальных моделей истинностных функциональных систем функции, как правило, коиечпозначны и, во-вторых, любая функция в каждой истинностной функциональной системе аппроксимируется функциями к-значных логик путем увеличения числа к. Критерии полноты в Рк могут быть сформулированы с использованием понятия критериальной системы. Система замкнутых подмножеств множества Р/: образует критериальную систему в Р/:, если из непринадлежности произвольного множества функций &-зпачной логики к каждому из подмножеств данной системы следует его полнота. Тривиальным примером критериальной в Рк системы является множество всех собственных замкнутых подмножеств множества Рк- Однако мощность этой критериальной системы континуальна и с ее помощью нельзя получить эффективный Критерий ПОЛНОТЫ в Рк [21]. Вместе с тем, в функциональной системе Рк существуют конечные полные системы, и любое замкнутое подмножество множества Рк расширяется до предполного в Рк класса (максимальной подалгебры), причем для любого к > 2 число предполных в Рк классов конечно. Нетрудно видеть, что всякий нредполиый класс принадлежит любой критериальной системе, а множество всех предполных классов образует минимальную критериальную систему в Рк. Таким образом, из явного описания множества всех предполных классов следует эффективный и наилучший в определенном смысле алгоритм для распознавания полноты произвольных конечных систем функций к-значной логики. В уже упоминавшихся работах Е.Поста и С.В.Яблонского [4,7] решение задач о полноте в двузначной и трехзначной логиках как раз и было достигнуто путем явного описания множества предполных классов; при этом оказалось, что в Р2 пять, а в Р$ восемнадцать таких классов. Проблема явного
3
описания множества предполных классов в Р* для любого к > 4 долгое время оставалась открытой и оказалась довольно сложной. В 1964 году А.И.Мальцев исследовал задачу о полноте в четырехзначной логиках. С.В.Яблонским [7], А.В.Кузнецовым [21]. В.В.Мартышоком [22],
Ло Чжу Каем, Пан Юн-цзе. Ван Сяо-хао. Лю Сюй-хуа [23,24,25,26],
Е.В.Захаровой [27|, И.Розенбергом [28] были последовательно в явном виде построены все предполные классы в к-значпых логиках (см. также [29]). Важно отметить, что в этих работах использован аппарат сохранения функциями fc-значных логик отношений (предикатов), впервые введенный A.B.Кузнецовым. Именно на этом пути 14.Розенбергом было проведено завершающее построение множества всех предполных классов в fc-значных логиках, а С.В.Яблонским, Е.Ю.Захаровой и В.Б.Кудрявцевым получена асимптотика их числа [30].
Наиболее важной последовательностной функциональной системой, как в теоретическом плане, так и с точки зрения приложений, является функциональная система Р, содержащая в качестве элементов ограниченно-детерминированные функции (о.-д. функции), а в качестве операций — операции суперпозиции и обратной связи. Множество всех о.-д. функций совпадает с множеством всех конечно-автоматных отображений. Поэтому каждая о.-д. функция может быть ’’вычислена” с помощью некоторого конечного автомата, имеет ’’память”, ее ’’функционирование” происходит во времени, и задача о полноте в функциональной системе Р в большей степени, чем в истинностных функциональных системах, отражает реальную ситуацию, возникающую при синтезе сложных кибернетических устройств.
В наиболее общей постановке задача о полноте для о.-д. функций изучалась в работах В.Б.Кудрявцева [31] и М.И.Кратко [32]. Как показано в [32] не существует алгоритма для распознавания полноты конечных множеств о.-д. функций. Вместе с тем, функциональная система Р является конечнонорождепиой [2] и совокупность предполных классов образует минимальную критериальную систему в Р. Поэтому возникает вопрос: какова мощность множества предполных классов в Р. В [31] (см. также ]33]) установлено, что эта мощность равна континууму.
Негативные с точки зрения эффективности результаты по задаче о полноте для о.-д. функций в общем случае привели к тому, что различные авторы рассматривали некоторые частные постановки этой задачи. Одни из них возникают на пути сужения класса систем, исследуемых на полноту, другие — на пути моделирования отдельных свойств о.-д. функций.
Задача о полноте для систем о.-д. функций, содержащих полную истинностную подсистему (т.е. все о.-д. функции с одним состоянием) рассматривалась в работе А.А.Летичсвского [34]. Им был получен эффек-
4
тивкый алгоритм распознавания полноты конечных систем с указанными свойствами в классе отображений, осуществляемых автоматами Мура. Д.Н. Бабин усилил этот результат, распространив его на случай, когда наряду с полной истинностной подсистемой исследуемая на полноту система содержит произвольное конечное множество о.-д. функций. Кроме того, Д.Н. Бабиным полностью описаны все случаи существования алгоритмов распознавания полноты систем о-д.функций, содержащих истинностные подсистемы, образующие базисы в произвольных замкнутых классах булевых функций из диаграммы Е.Поста (см. [35] и цитируемую там литературу).
Одной из основных характеристик поведения автоматов (о.-д.функций) является возможность с их помощью представлять регулярные события [36]. Множество Ш С Р называется К-полным (Клини-полным), если для всякого регулярного события из о.-д.функций множества можно получить о.-д.функцию, представляющую это событие. В общем случае (Ю.Даесоу [37]) ситуация, возникающая при изучении задачи о К-иолноте аналогична той, которая возникает при исследовании задачи о полноте: существует континуум предполных классов и не существует алгоритма для распознавания К-полноты конечных систем о.-д.функций.
С точки зрения приложений важным подклассом Р является множество Ь — отображений, осуществляемых так называемыми линейными автоматами. Задача о полноте в этом множестве рассматривалась
А.А.Часовских [38]. В частности, А.А.Часовских установлено, что хотя в Ь счетное число предполных классов, существует' алгоритм распознавания полноты конечных систем о.-д. функций из Ь.
Большой, главным образом, теоретический интерес представляет исследование последовательностной функциональной системы, которая отличается от Р тем, что в ней к о.-д.функциям могут применяться только операции суперпозиции. Эта функциональная система изучалась в работах С.В.Алешина и Д.Н.Бабина [39,40,41]. Нетрудно показать [42], что изъятие такой сильной ’’автоматной” операции, как обратная связь, приводит к тому, что в рассматриваемой функциональной системе нет конечных полных систем. Однако ее элементы — о.-д. функции, достаточно ’’сложны” и обладают интересными имитационными свойствами. Легко видеть, что множество всех одноместных о.-д.функций замкнуто относительно операции суперпозиции и образует полугруппу. Вместе с тем, множество всех взаимно-однозначных одноместных о.-д.функций образует группу, которая, как показал С.В.Алешин [43], содержит бесконечную, периодическую и конечнопорожденную подгруппу. Вопрос о существовании таких групп составляет содержание известной ослабленной проблемы Бернсайда [44]. Указанная подгруппа порождается явно всего двумя элементами, представляющими собой о.-д.функции с семью и
5
тремя состояниями. Как отмечено выше, в множестве всех о.-д.функций не существует конечных полных систем, если пользоваться только операциями суперпозиции. Поэтом}^ естественно возникает следующая важная проблема (аналог 13 проблемы Д.Гильберта): можно ли для всякого п > 3 любую п-местную о.-д.функцию представить в виде суперпозиции (тг — 1)-местных. Оказалось, что эта проблема решается положительно. Более того, в [41| показано, что любую о.-д.функцию можно выразить через суперпозицию одноместных о.-д.функций и единственной двухместной о.-д.функции, которая имеет одно состояние и образует полную истинностную систему.
Кроме функциональных систем, содержащих в качестве элементов
о.-д. функции, рассматривались также последовательностные функциональные системы, элементами которых являются детерминированные функции (д.функции), а операциями — те же операции суперпозиции и обратной связи. В этой функциональной системе любое полное множество континуально и, как установлено В.Б.Кудрявцевым |2], существует гиперконтинуум предполных классов. С.С.Марченковым показано, что для любого п > 2 существуют д.функции от п переменных, которые нельзя представить через суперпозицию д.функций от меньшего числа переменных [45].
Анализ содержательных моделей последовательностных функциональных систем показывает, что решение задачи о полноте в этих системах наталкивается на трудности недостаточной эффективности. Исключение составляет функциональная система функций с задержками, которая занимает промежуточное положение между конечнозначными логиками и автоматными отображениями (В.Б.Кудрявцев [8,9|). Однако элементы этой системы представляют собой лишь весьма частный случай о.-д.функций, а используемые в ней операции синхронной суперпозиции значительно "слабее” операций суперпозиции и обратной связи. Таким образом, возникает необходимость в разработке принципиально иных подходов к исследованию задачи о полноте в последовательностных функциональных системах.
В силу своего определения о.-д.функции являются бесконечными и даже континуальными функциями. Таким образом, предполагается, что вычисляющий любую о.-д.функцию автомат "работает” бесконечно долго. Однако с точки зрения приложений совершенно очевидно, что каждое реальное кибернетическое устройство (в том числе, автомат) по истечении некоторого конечного промежутка времени прекращает свою "работу", т.е. либо становится ненужным, либо переводится в начальное состояние. В связи с этим естественно возникает
Задача о полноте в последовательностной функциональной системе Р£.
Пусть к > 2, г > 1. Элементами функциональной системы яв-
б
- Киев+380960830922