Содержание к диссертации
Введение
Глава 1. Оператор FE-замыкания в счетнозначной логике 19
1.1 Основные понятия и терминология 20
1.2 Операторы FE-замыкания и HG-замыкания 22
1.3 Принцип сопряженности для оператора FE-замыкания 26
1.4 FE-замыкание множеств типа {0, х + 1} 31
1.5 FE-замыкание множеств, содержащих характеристические функции 34
1.6 Язык FE-замыкания с логическими связками 38
Глава 2. Оценки числа FE-замкнутых и FE-предполных классов 44
2.1 FE-замкнутые классы 44
2.2 FE-предполные классы 48
Глава 3. Сложность проблемы выполнимости систем функцио нальных уравнений 54
3.1 Неразрешимость проблемы выполнимости 55
3.2 Проблема выполнимости и класс Пі 59
3.3 Все решения системы функциональных уравнений 67
Заключение 69
Список литературы
- Операторы FE-замыкания и HG-замыкания
- FE-замыкание множеств, содержащих характеристические функции
- FE-предполные классы
- Проблема выполнимости и класс Пі
Введение к работе
Актуальность темы диссертации.
Уравнение — одно из самых распространенных понятий в математике, уступающее по частоте использования, возможно, лишь понятию функции.
По отношению к основным (предметным) переменным все уравнения можно условно разделить на две группы: к первой группе относятся уравнения, в которых разыскиваются значения неизвестных предметных переменных (линейные, алгебраические, матричные и другие уравнения), во вторую группу входят функциональные уравнения, в которых неизвестными являются функции от предметных переменных, и наряду с предметными переменными в них присутствуют известные функциональные константы.
Функциональное уравнение — это один из самых распространенных способов задания функций в математике, оно выражает связь между значением функции в одной или нескольких точках с ее значениями в других точках. Предметные переменные в функциональных уравнениях указывают на универсальный характер этих связей и всегда находятся под действием кванторов общности (т.е. уравнение должно оставаться верным при любых значениях входящих в него предметых переменных).
Функциональные уравнения представляют собой весьма общий класс уравнений, ими, по существу, являются дифференциальные уравнения, интегральные уравнения, уравнения конечных разностных схем и ряд других, хотя само название «функциональные уравнения» к уравнениям этих типов обычно не относят. Решениями функциональных уравнений могут быть как конкретные функции, так и множества функций, зависящие от некоторых параметров, в частности, от функций, определяемых этими же уравнениями. Несколько функциональных уравнений можно объединить в систему функциональных уравнений. Решением системы считается набор функций, являющийся решением каждого уравнения.
В целом можно сказать, что функциональные уравнения применяются практически во всех разделах математики: от теории множеств и общей (универсальной) алгебры до сугубо прикладных направлений математической физики. Особенно часто системы функциональных уравнений используются в разделах математики, включающих теории функций той или иной природы. Для специальных нужд в различных областях знаний формулируются функциональные уравнения и системы функциональных уравнений, исследуются вопросы о существовании решения вообще, а также о существовании решения, удовлетворяющего заданным свойствам, или о единственности решения, или о свойствах множества решений. Приведем некоторые примеры.
Одними из простейших функциональных уравнений являются функциональные уравнения Коши: f{x + у) = fix) + f(y) (этому уравнению удовлетворяют все линейные однородные функции f(x) = С х) и f(x + y) = f(x)f(y) (этому уравнению удовлетворяют все показательные функции fix) = Сх), где С — произвольная константа.
К функциональным уравнениям также относятся многочисленные рекуррентные соотношения, которые содержат неизвестные функции от целочисленных переменных и оператор сдвига. Пример подобного соотношения: f(n) = f(n -1) + f(n — 2).
Хорошо известные законы коммутативности и ассоциативности также можно рассматривать как функциональные уравнения. В привычной записи эти законы выглядят следующим образом:
X о у = у о х, (х о у) о z = X о (у о z),
где о — символ некоторой бинарной операции. Однако, если представить эту операцию в виде f(x,y), то получатся как раз функциональные уравнения:
f(%, У) = f(y,x), f(f(x,y),z) = f(x,f(y,z)).
Решениями данных функциональных уравнений будут совокупности всех коммутативных или ассоциативных функций.
Еще несколько простейших, хорошо известных примеров из математического анализа: периодические функции с периодом Т — это функции, удовлетворяющие функциональному уравнению f(x + Т) = f(x), четные функции — уравнению f(x) = f(—x), нечетные функции — уравнению f(x) = —f(—x).
Обратимся к примерам из дискретной математики. В теории булевых функций и теории функций многозначной логики функциональные уравнения представлены достаточно широко. Все линейные булевы функции, зависящие от п переменных, могут быть определены как решения функционального уравнения
у{хі Єуі,... ,хпфуп) 0(/?(О,... ,0) = ір(хі,...,хп) ip(yi,... ,уп),
где 0 и суть заданные функциональные константы нуль и сложение по модулю два. Все самодвойственные булевы функции от п переменных — это решения функционального уравнения
ір(хі,... ,хп) = ф(хі,... ,хп).
Само задание булевой функции f(x\,... ,хп) табличным способом есть ни что иное, как система функциональных уравнений, состоящая из 2п уравнений с функциональными константами 0 и 1 и одной функциональной переменной — определяемой функцией /.
Если обратитвся к математической кибернетике, то можно увидетв, что целые теории строятся и развиваются на базе подходящих языков функциональнвіх уравнений.
Так, например, действие операции суперпозиции (на множестве функций любой природы) может бытв представлено в виде функционалвного уравнения
ір[Х\, . . . , Хп) J [fi[Xi, . . . , Хр) , . . . , Jmy^li ) Жр))-,
где f,fi,...,fm — функциональные константы.
Действие оператора примитивной рекурсии может быть выражено в виде системы функциональных уравнений
tp(xx,... ,жга_і,0) = fi(xi,... ,xn-i), <р(х1,... ,Xn_i,Xn + 1) = f2(xi,... ,хп,<р(х1,... ,xn)) с функциональными константами 0, х + 1,/1,/2-
Более того, одним из первых определений рекурсивной функции в теории алгоритмов явилось эрбран-геделевское определение, основанное на решениях систем функциональных уравнений специального вида.
Системы канонических уравнений в теории автоматов представляют собой основной инструмент как для задания и изучения собственно конечно-автоматных функций, так и для исследования разнообразных их обобщений. Как правило, эти системы канонических уравнений имеют вид
y{t) = f(xi(t),...,xn(t),qi(t- I),---, qr(t- 1)),
Qi(t) = 0і(жі(і),...,жга(і),ді(і- I),---,qr(t- 1)),
<
Qr(t) =gr(x1(t),...,xn(t),q1(t- 1),...,qr(t- 1)),
k ^(0) = ... = ^(0) = 0,
где f,gi,... ,gr — (булевы) функциональные константы.
Несмотря на то, что в теории булевых функций и теории функций многозначной логики имеется большое число примеров функциональных уравнений, систематическое исследование функциональных булевых уравнений и функциональных уравнений многозначной логики началось сравнительно недавно.
В данном направлении можно отметить несколько результатов о функциональных уравнениях, рассматриваемых на множестве булевых функций: О. Ekin, S. Foldes, P. L. Hammer, L. Hellerstein опубликовали ряд работ, в которых авторы вывели уравнения, задающие множества рефлексивных, полярных, супермодулярных, субмодулярных, билинейных, квадратичных и принадлежащих классам Хорна булевых функций, а также доказали критерий задания класса булевых функций функциональным уравнением.
Также необходимо обратить внимание на работы С.С. Марченкова и B.C. Федоровой, в которых функциональные уравнения рассматриваются на множестве функций многозначной логики. В данных работах, в частности, полностью решены вопросы о выразимости одних функций через другие с помощью систем функциональных уравнений (в другой терминологии — описание всех классов функций многозначной логики, замкнутых относительно систем функциональных уравнений), а также о сложности решения проблемы выполнимости для систем функциональных уравнений.
В счетнозначной логике системы функциональных уравнений уже использовались (однако в иной постановке) в теории алгоритмов и продемонстрировали часть своих возможностей.
Функциональные уравнения являются удобным средством для задания оператора замыкания. Изучению оператора замыкания, базирующегося на системах функциональных уравнений (коротко — оператор FE-замыкания), в данной работе уделяется особое внимание. Рассмотрение различных операторов замыкания помогает разбивать все множество функций на замкнутые классы. Подобная классификация позволяет выделять свойства отдельных множеств функций, а также исследовать вопросы о выразимости одних множеств функций через другие.
Исследования в данном направлении начались в работах Э. Поста с описания счетной решетки всех замкнутых относительно суперпозиции классов булевых функций. Логичным продолжением и обобщением подобных исследований является изучение замыкания относительно суперпозиции на множестве функций многозначной логики. Однако в случае функций многозначной логики мощность множества всех замкнутых классов континуальна. Этот факт значительно ограничивает возможности получения некоторого полного описания, поэтому во многих работах исследуются лишь отдельные фрагменты решетки. Чаще всего рассматриваются все замкнутые (либо предполные) классы, содержащие некоторое множество функций, представляющих наибольший интерес.
В случае многозначной логики для создания решетки замкнутых классов простой структуры вводятся более «сильные» операторы замыкания, такие, как оператор параметрического замыкания, оператор позитивного замыкания, оператор lL-замыкания. Действие этих «сильных» операторов замыкания, как правило, начинается с исследования случая булевых функций. Исследования в данном направлении актуальны и в последнее время.
В данной диссертации исследуются функциональные уравнения счетнозначной логики и оператор замыкания, основанный на системах функциональных уравнений. Сам термин «счетнозначная логика» предложен СВ. Яблонским для обозначения функциональной
системы с операцией суперпозиции, функции которой заданы на множестве натуральных чисел. Получение первых нетривиальных результатов в счетнозначной логике потребовало привлечения теоретико-множественных конструкций большой технической сложности. В этом направлении следует выделить работы Г.П. Гаврилова и С.С. Марченкова, в которых исследуются вопросы полноты и выразимости относительно операции суперпозиции. Следует также отметить, что в настоящее время исследований по счетнозначной логике проводится крайне мало, что, вероятно, связано с тем, что мощность множества предполных относительно суперпозиции классов функций счетнозначной логики гиперконтинуальна.
Таким образом, в исследовании класса функций счетнозначной логики (например, посредством подходящих операторов замыкания) имеются лишь первоначальные результаты, которые связаны с операцией суперпозиции и которые пока не получили дальнейшего развития.
Как и в случае многозначной логики, в случае счетнозначной логики вводятся другие, отличные от суперпозиции, операции. Подобные операции чаще всего используются вместе с операцией суперпозиции, причем рассматриваются замыкания лишь некоторых множеств функций. Самыми простыми примерами могут служить множество примитивно-рекурсивных функций, которое получаются в результате замыкания системы функций {0, ж + 1,1к(х\,... ,хп)} с помощью операций суперпозиции и примитивной рекурсии, и множество частично-рекурсивных функций, которое получаются также из системы {0, ж + l,Ifr(xi,... ,хп)} в результате замыкания по суперпозиции, примитивной рекурсии и минимизации. Также отметим счетное семейство классов Гжегорчика , S1, Є2 ..., порождаемых операциями суперпозиции и ограниченной рекурсии из множеств вида {0,ж + l,I%(xi,... ,xn),fk}, где {fk(x\,X2)} — специальным образом выбранная последовательность монотонных примитивно-рекурсивных функций. Эти классы образуют возрастающую иерархию множества всех примитивно-рекурсивных функций.
Также следует привести пример, в котором в качестве исходных функций рассматривается множество функций {х + 1, Ik(x\,..., хп), х—у}. Если в качестве порождающих операций взять операции суперпозиции и ограниченного суммирования, то образуется класс функций, элементарных по Сколему, а если добавить операцию ограниченного мультиплицирования, то получится класс функций, элементарных по Кальмару. Вопрос о порождении различных подмножеств множества рекурсивных функций актуален и в настоящее время.
Изучение структуры множества рекурсивных функций, не принадлежащих классу примитивно-рекурсивных, началось с примера В. Аккермана функции, являющейся всюду определенной и вычислимой, но не примитивно-рекурсивной. Дальнейшее развитие
это иследование получило в работе Р. Петер, в которой она изучала счетную иерархию вложенных классов, определяемых рекурсиями различных ступеней.
Обращаясь к примеру замыкания относительно систем функциональных уравнений, следует отметить, что еще в середине 1930-х годов Ж.Эрбран и К.Гедель предложили одну из первых формализации понятия алгоритмически вычислимой функции — формализацию, основанную на логическом выводе из системы функциональных уравнений. Однако, несмотря на схожесть формулировок этого исследования с темой данной работы, такая формализация пригодна лишь для построений алгоритмического характера и почти не связана с определимостью функций, базирующейся на решениях систем функциональных уравнений.
Отметим, что в большинстве случаев (в том числе, для описанных выше примеров) исследуемые множества функций счетнозначной логики не выходят за пределы множества рекурсивных (вычислимых) функций. Следует еще обратить внимание на то, что в вопросах классификации функций счетнозначной логики (в терминах, например, графиков функций), можно применять различные типы алгоримической сводимости (т-сводимость, табличную сводимость, сводимость по Тьюрингу, сводимость по перечислимости и др.), что приводит к разнообразным по объему и свойствам классификациям. В этом же русле находятся классификации, основанные на классах арифметической иерархии Клини-Мостовского и аналитической иерархии Клини.
В диссертации в силу больших выразительных возможностей оператора FE-замыкания (в частности из-за того, что множество рекурсивных функций не является FE-замкнутым) приходится рассматривать классы функций счетнозначной логики, далеко выходящие за пределы класса вычислимых функций (и даже класса функций, арифметических по Клини-Мостовскому).
Цель работы — изучить свойства и выразительные способности оператора замыкания, базирующегося на системах функциональных уравнений, а также исследовать проблему выполнимости функциональных систем для случая функций счетнозначной логики.
Основные результаты диссертации:
Доказано, что для всякого общерекурсивного оператора Ф(/і,..., fm) найдется такая система уравнений с функциональными константами 0,х + 1 и f\,..., fm, которая для любого выбора функциональных констант f\,..., fm определяет (по выделенной функциональной переменной) функцию Ф(/і,..., fm).
Установлено, что FE-замыкание систем, подобных системе {0, ж+1} , а также каждой из систем {х<}> {х<}> {х>}? {х>}? совпадает с классом | аналитической иерархии
Клини.
Исследована сложность проблемы выполнимости для систем функциональных уравнений над множествами {p(x,y,z)} и {р(х,у, z),a\,... ,a,k}, где р — тернарный дискриминатор, a 1,..., — константы. Доказано, что данная проблема алгоритмически неразрешима и принадлежит классу Пі арифметической иерархии Клини-Мостовского.
Получены оценки мощности множеств FE-замкнутых и FE-предполных классов. Доказано, что мощность семейства всех FE-замкнутых классов гиперконтинуальна, а семейства всех FE-предполных классов — не менее чем континуальна.
Научная новизна. В общей постановке системы функциональных уравнений и оператор замыкания, базирующийся на системах функциональных уравнений, исследовались для случая булевых функций и функций многозначной логики. В случае функций счетнозначной логики системы функциональных уравнений использовались только для определения некоторых операций и при решении конкретных задач. В данной работе системы функциональных уравнений счетнозначной логики впервые исследуются с самых общих позиций. В частности, находятся важнейшие характеристики оператора FE-замыкания и устанавливается алгоритмическая сложность проблемы выполнимости для систем функциональных уравнений. Все результаты диссертации являются новыми.
Методы исследования. В работе используются методы теории алгоритмов, теории функциональных систем, математической логики и теории множеств.
Теоретическая и практическая значимость. Результаты диссертации могут быть использованы для поиска решений некоторых систем функциональных уранений счетнозначной логики, а также в исследовании вопросов функциональной выразимости в счетнозначной логике.
Апробация работы и список публикаций. Результаты диссертации опубликованы в рецензируемых журналах из перечня ВАК (работы [1-4]) и в сборнике тезисов конференции (работа [5]). Результаты диссертации получены автором самостоятельно, некоторые из них — в соавторстве с научным руководителем. Результаты диссертации излагались на конференции «Ломоносовские чтения» в 2013 и 2014 г., на конференции «Тихоновские чтения» в 2014 г., докладывались на семинаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета ВМК МГУ и на семинаре лаборатории ПОИС факультета компьютерных наук ВШЭ.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Общий объем работы составляет 77 страниц. Список ли-
Операторы FE-замыкания и HG-замыкания
Также необходимо обратить внимание на работы С.С. Марченкова и В. С. Федоровой [19, 32-34], в которых функциональные уравнения рассматриваются на множестве функций многозначной логики. В данных работах, в частности, полностью решены вопросы о выразимости одних функций через другие с помощью систем функциональных уравнений (в другой терминологии — описание всех классов функций многозначной логики, замкнутых относительно систем функциональных уравнений), а также о сложности решения проблемы выполнимости для систем функциональных уравнений.
В счетнозначной логике системы функциональных уравнений уже использовались (однако в иной постановке) в теории алгоритмов и продемонстрировали часть своих возможностей.
Функциональные уравнения являются удобным средством для задания оператора замыкания. Изучению оператора замыкания, базирующегося на системах функциональных уравнений (коротко — оператор FE-замыкания), в данной работе уделяется особое внимание. Рассмотрение различных операторов замыкания помогает разбивать все множество функций на замкнутые классы. Подобная классификация позволяет выделять свойства отдельных множеств функций, а также исследовать вопросы о выразимости одних множеств функций через другие.
Исследования в данном направлении начались в работах Э. Поста [57-58] с описания счетной решетки всех замкнутых относительно суперпозиции классов булевых функций. Логичным продолжением и обобщением подобных исследований является изучение замыкания относительно суперпозиции на множестве функций многозначной логики. Однако в случае многозначной логики мощность множества всех замкнутых относительно суперпозиции классов континуальна (следует из работы [43]). Этот факт значительно ограничивает возможности получения некоторого полного описания, поэтому во многих работах исследуются лишь отдельные фрагменты решетки. Чаще всего рассматриваются все замкнутые (либо предполные) классы, содержащие некоторое множество функций, представляющих наибольший интерес. Например, в работе [29] описаны все классы, содержащие тернарный дискриминатор, в работе [36] — все предполные классы, содержащие класс полиномов, а в работе [59] — все минимальные классы, включающие в себя целиком множество селекторных функций.
В случае многозначной логики для создания решетки замкнутых классов простой структуры вводятся более «сильные» операторы замыкания, такие, как оператор параметрического замыкания (см., например, [8]), оператор позитивного замыкания (см., например, [27] ), оператор lL-замыкания (см., например, [24, 30]). Действие этих «сильных» операторов замыкания, как правило, начинается с исследования случая булевых функций (см. [25]). Исследования в данном направлении актуальны и в последнее время. К примеру, в работе [1] рассматривается замыкание относительно операции расширенной суперпозиции, в работе [38] исследуется замыкание относительно суперпозиции и перестановки с множеством наборов специального вида, в работе [35] рассматриваются классы функций, допускающих неявное представление над некоторой системой функций.
В данной диссертации исследуются функциональные уравнения счет-нозначной логики и оператор замыкания, основанный на системах функциональных уравнений. Сам термин «счетнозначная логика» предложен СВ. Яблонским (см. [40-41]) для обозначения функциональной системы с операцией суперпозиции, функции которой заданы на множестве натуральных чисел. Получение первых нетривиальных результатов в счетнозначной логике потребовало привлечения теоретико-множественных конструкций большой технической сложности. В этом направлении следует выделить работы Г.П. Гаврилова (см. [5-6]) и С.С. Марченкова (см. [17]), в которых исследуются вопросы полноты и выразимости относительно операции суперпозиции. Следует также отметить, что в настоящее время исследований по счетнознач-ной логике проводится крайне мало, что, вероятно, отчасти связано с тем, что мощность множества предполных относительно суперпозиции классов функций счетнозначной логики гиперконтинуальна (см. [17]), а, как сказано выше, даже континуальная мощность существенно ограничивает круг подобных исследований. Таким образом, в исследовании класса функций счетнозначной логики (например, посредством подходящих операторов замыкания) имеются лишь первоначальные результаты, которые связаны с операцией суперпозиции, и которые пока не получили дальнейшего развития.
Как и в случае многозначной логики, в случае счетнозначной логики вводятся другие, отличные от суперпозиции, операции. Подобные операции чаще всего используются вместе с операцией суперпозиции, причем рассматриваются замыкания лишь некоторых множеств функций. Самыми простыми примерами могут служить множество примитивно-рекурсивных функций, которое получаются в результате замыкания системы функций {О, ж + 1,1 (х\,.. . ,хп)} с помощью операций суперпозиции и примитивной рекурсии, и множество частично-рекурсивных функций, которое получаются также из системы {0, ж + 1,1%(хі,... , хп)} в результате замыкания по суперпозиции, примитивной рекурсии и минимизации (см., например, [52]). Также отметим счетное семейство классов Гжегорчика , , ... (см. [7, 28]), порождаемых операциями суперпозиции и ограниченной рекурсии из множеств вида {0, х + 1,/ (жі,.. . ,жп),/&}, где {fk(%ii%2)} специальным образом выбранная последовательность монотонных примитивно- рекурсивных функций. Эти классы образуют возрастающую иерархию множества всех примитивно-рекурсивных функций.
FE-замыкание множеств, содержащих характеристические функции
Однородность приведенных функций можно установить как непосредственно с использованием исходных определений, так и с учетом того, что значениями данных функций являются значения переменных, которые выбираются в соответствии с отношением равенства/неравенства между переменными.
Для большинства изучаемых операторов замыкания, действующих на множествах булевых функций, функций многозначной логики или функций счет-нозначной логики, рассматривается принцип сопряженности, являющийся одной из важнейших характеристик оператора замыкания. Ниже в тексте устанавливается истинность принципа сопряженности для оператора FE-замыкания.
"Утверждение 1. (принцип сопряженности для FE-замыкания). Пусть система функциональных уравнений над множеством функций {/i,..., fs} определяет функцию f и тг — перестановка на множестве N. Тогда система уравнений S71", полученная из системы S заменой каждой функциональной константы fi, соответствующей функциональной константой f[, определяет функцию р.
В полученной системе заменим все вхождения функциональных констант 0,0Ъ , 0/, /ъ Л на функциональные констаны (f ,(j\,..., gf, /f,..., /s\ Из принципа двойственности для оператора суперпозиции (см. [42]) следует, что после подобной замены полученные равенства также останутся тождествами.
Следовательно, набор функций gf,...,gf будет являться решением системы S71". Единственность решения по главной функциональной переменной системы S71" будет следовать из единственности решения по главной функциональной переменной системы в системе S, так как можно с помощью перестановки 7Г перейти от системы S71" к системе S. Утверждение доказано.
Однородные функции играют важную роль в универсальной алгебре и теории функций многозначной логики. В связи с этим интерес представляют FE-замкнутые классы, включающие однородные функции. Так, к примеру, в работе [18] исследуются похожие вопросы для случая оператора замыкания по суперпозиции. Выясним, какие нетривиальные (неселекторные) однородные функции могут содержать FE-замкнутые классы.
В работе [18] установлено, что класс Н порождается (в смысле операции суперпозиции) тернарным дискриминатором р. Кроме того, в [18] доказано, что любой замкнутый (относительно суперпозиции) класс функций из Н, отличный от класса селекторных функций, содержит либо функцию i, либо какую-нибудь функций 1п. Поэтому теорема 2 будет доказана, если мы установим, что каждая из функций d, ln FE-порождает функцию р.
Начнем с функции d. Рассмотрим систему функциональных уравнений (р(х,х,у)=у, (р(х,у,х)=х, (р(х,у,у) = х, (p(x,y,d(x,y,z)) = x. Первые три уравнения этой системы правильно определяют функцию р на всех наборах, содержащих не более двух различных значений. Четвертое уравнение определяет функциюр, в частности, на наборах (ж, у, z), где х у. Отметим, что четвертое уравнение согласовано с первыми тремя на наборах, содержащих не более двух значений.
Покажем далее, что функция /з FE-порождает функцию d. Соответствующая система функциональных уравнений имеет следующий вид: (р(х,х,у) = х, (р(х,у,х) = х, р(х,у,у) = у, k(x,(p(x,y,z),z) = z, h(y, p(x,y,z),z) = z. Первые три уравнения данной системы правильно определяют функцию d на всех наборах, содержащих не более двух различных значений. Остальные два уравнения обеспечивают равенство d(x,y,z) = z на наборах, состоящих из трех различных значений. Нетрудно также убедиться, что последние два уравнения согласованы с первыми тремя уравнениями на наборах, содержащих не более двух различных значений.
FE-предполные классы
Классом Пі арифметической иерархии Клини-Мостовского (см. [37], глава 15) называется класс всех отношений, которые представимы в виде (Ужі)...(Ужт)Я(жі,...,жт,2/і,... ,у/), где R(xi,...,xm,yu...,yi) — рекурсивное отношение.
Пусть — произвольная система функциональных уравнений над множеством {р\. По системе S эффективным образом будем строить дерево А (вообще говоря, бесконечное), все вершины которого имеют конечную степень. В каждой вершине дерева А, за исключением его корня, для всякой функциональной переменной (/, входящей в систему S, будут определяться в конечном числе точек значения соответствующей функции fi. Некоторые ветви дерева А в процессе построения будут отсекаться (точнее, будут целиком отсекаться некоторые поддеревья, «растущие» из вершин дерева А). Мы покажем, что система уравнений выполнима тогда и только тогда, когда в данном дереве А имеется хотя бы одна бесконечная ветвь. Существование бесконечной ветви в дереве А будет выражено формулой класса Пі.
Пусть х\,...,хп — все предметные переменные, входящие в систему S. Зафиксируем вычислимую «канторовскую» нумерацию множества 7Vn, в которой нулевой набор имеет номер 0, а далее номера присваиваются последовательно в «блоках», состоящих из всех наборов с заданной суммой координат (см., например, [16], глава 4). Набор с номером к в этой нумерации будем обозначать через х&. Отметим, что в наборе х& все компоненты не превосходят величины к. Выделим в системе S все вхождения функциональных переменных и обозначим их (/9,..., (рт (одна и та же функциональная переменная может входит в уравнения системы несколько раз).
Опишем первый шаг в построении дерева А — определение вершин первого яруса (вершины, связанные ребрами с корнем дерева). Рассмотрим набор хо и придадим всем предметным переменным х\,...,хп системы значение 0. Далее, каждому вхождению функциональной переменной в систему «придадим» одно из значений 0,1,.. . ,ш. Отметим, что при фиксировании набора хо для «означивания» всех термов системы (включая термы вида p(t\ t2its)) достаточно значений из множества {0,1,... , т}.
Всего имеется (т + 1)т таких присвоений, этим присвоениям будут отвечать в дереве А (т + 1)т вершин первого яруса. Как видно, в результате одного присвоения каждая функция fi (отвечающая функциональной переменной (fii) будет определена в конечном числе точек. В самом деле, если в систему S входит терм вида (fii(xj1, ...,2 ), то функция fi будет определена на нулевом наборе. Если же в систему входит терм вида (fii(ti,.. . ,ts), где t\,... , ts — термы, и в результате присвоения термы t\,... , ts получили значения 2i,.. . , as, то функция fi получит значение на наборе ( 2i,.. . , as). (Мы не рассматриваем отдельно термы, которые начинаются символом функциональной константы р, поскольку вычисление значений таких термов проводится очевидным образом.)
При выполнении присвоений следует соблюдать следующее естественное условие: если для нескольких различных вхождений одной и той же функциональной переменной (fi в результате присвоения определяются значения функции fi на одном и том же наборе, то эти значения должны быть равны.
Для каждого присвоения проверяем, может ли оно обеспечить истинность всех равенств системы (напомним, что на первом шаге всем предметным пере менным присвоено значение 0). Если возникло противоречие, то прекращаем дальнейшее построение дерева А из данной вершины. Если же противоречивых равенств из системы не получено, то фиксируем значения, присвоенные функциональным переменным на рассматриваемых наборах (т.е. фактически значения функций fi), и переходим к построению вершин второго яруса.
Предположим, что мы уже определили все вершины к-го яруса дерева А (все те вершины, к которым в построенном фрагменте дерева А ведут из корня пути длины к). Будем также считать, что на всех вершинах дерева с 1-го по к-й ярусы в операциях присвоения были использованы числа только из множества {0,1,..., к(т + 1) — 1}. Кроме того, предполагаем, что в результате предыдущих присвоений в каждой из построенных вершин дерева А соответствующие функции fi уже корректно определены на некоторых наборах из декартовых степеней множества {0,1,..., к(т + 1) — 1}.
На всех вершинах {к + 1)-го яруса будем рассматривать набор х&, все компоненты которого не превосходят к. Выберем в к-м ярусе вершину v. Присвоим переменным х\,... , хп соответствующие значения из наборах . Будем далее присваивать всем вхождениям (/?,..., (рт функциональных переменных независимым образом всевозможные значения из множества {0,1,.. . , (к + 1)(ш + 1) — 1}. При этом присвоения должны быть корректными (см. шаг 1 в построения дерева А) и согласованными с уже имеющимися в вершине v значениями функций f\. Образуется не более (& + l)m(m + l)m вершин (& + 1)-го яруса, которые будут соединены в дереве А ребрами с вершиной v. Как и на шаге 1, для всякого присвоения осуществляем проверку выполнимости всех равенств системы S. В случае невыполнения какого-либо из равенств системы (с присвоенными значениями) обрываем построение дерева А в соответствующей вершине. В противном случае рассматриваем набор x +i и переходим к построению яруса к + 2. Нетрудно видеть, что процесс построения дерева А является полностью эффективным: существует алгоритм, который по «координате» произвольной вершины дерева А определяет, является ли данная вершина «концевой», а если нет, то вычисляет значения функций fi во всех рассматриваемых точках.
Предположим теперь, что в дереве А имеется бесконечная ветвь В. Проходя по всем вершинам ветви , мы сможем для любой функциональной переменной (fii системы корректно определить значения соответствующей функции f на некотором множестве точек F{. При этом, как легко понять, набор функций fi будет удовлетворять системе уравнений S. Единственная возникающая здесь проблема состоит в том, что множество Fi не обязано быть полным (т.е. совпадать с надлежащей декартовой степенью множества N). Иными словами, определяемые на ветви В функции fi будут, вообще говоря, частичными. Эту проблему можно легко решить, если заметить, что полученная система функций fi удовлетворяет системе уравнений при всех значениях предметных переменных. Это означает, в частности, что наборы, не входящие в множество Fi, в данном решении системы уравнений вообще не используются. Поэтому на них значения функции fi можно определить произвольным образом.
Обратно, предположим, что система уравнений имеет решение. Покажем, что в этом случае в дереве А существует хотя бы одна бесконечная ветвь.
Пусть tp\,.. . ,tp\ — все функциональные переменные системы уравнений S, а набор функций (/і, ,//) из Рдг удовлетворяет системе S. Рассмотрим сначала нулевой набор значений переменных х\,.. . ,хп. Если заменить в системе S все предметные переменные значением 0 и затем рассматривать последовательно все термы системы S, содержащие функциональные переменные, то с использованием функций /і,... , // можно для всех вхождений ip ,... , Lpm функциональных переменных в систему найти соответствующие значения 2i,... , ат (это, разумеется, значения функций /і,... , //, вычисленные на тех наборах, которые имплицируются в системе S равенствами = 0). Отметим, что в последовательности а\,... , ат некоторые значения могут совпадать.
Проблема выполнимости и класс Пі
Аналогично теореме 14 по системе S эффективным образом будем строить бесконечное дерево А, все вершины которого имеют конечную степень. Повторим построение дерева из теоремы 14, модифицируя некоторые моменты.
На первом шаге в построении дерева А, как и ренее, рассмотрим набор хо и придадим всем предметным переменным х\,... ,хп системы значение 0. Далее, каждому вхождению функциональной переменной в систему придадим одно из значений 0,1,..., т или значение из множества { 2i,... , а&}. Отметим, что при фиксировании набора хо для «означивания» всех термов системы (включая термы вида p(ti,t2, 3)) достаточно значений из множества {0,1,... ,m, 2i,... ,dk}.
Всего имеется конечное число таких присвоений и, как и ранее, этим присвоениям будет отвечать в дереве А также конечное число вершин первого яруса. На вершинах последующих ярусов будем присваивать всем вхождениям if1,... , ifm функциональных переменных независимым образом всевозможные значения из множества, определенного в теореме 14, а также значения из множества { 2i,... , а&}. В остальном целиком повторяем алгоритм построения дерева А из теоремы 14. Нетрудно заметить, что такие модификации не влияют на эффективность процесса построения дерева А.
Итак, можно утверждать, что полученная в результате подобных посто-рений система функций будет являться решением системы S, а также то, что в случае существования решения системы в дереве А на некоторой бесконечной ветви будет получено множество также являющееся решением системы S. Чтобы в этом убедиться, необходимо просто повторить соответствующую часть доказательства теоремы 14, заменяя произвольную перестановку на перестановку с неподвижными точками От,.. . , (ik- Тем самым мы показали, что, модифицируя построение дерева А из теоремы 14 указанным образом для случая систем функциональных уравнений над {р(х,у, z),a\,... , 2/г}, мы получим метод того же порядка сложности, что и метод построения дерева А из теоремы 14. Тем самым получаем, что множество всех выполнимых систем функциональных уравнений над {р(х, у, z),a\,.. . , (ik} также является m-полным множеством в классе Пі иерархии Клини-Мостовского. Следствие доказано.
Проанализируем доказательство теоремы 14. Пусть ( i,... , (рг — все функциональные переменные системы уравнений S. И пусть В — бесконечная ветвь в дереве А, которая определяет решение (/i,... , fr) (вообще говоря, частичное) системы уравнений S. При построении дерева А некоторым термам вида (fii(ai,... , ащ), где 2i,... , ащ Є TV, присваиваются значения из N. Для каждой переменной (fii выделим все те наборы ал,а 2,..., на которых термам (fiifaij) будут присвоены значения из N. Это множество, вообще говоря, не совпадает с множеством всех наборов из Nni.
Отметим следующее обстоятельство: поскольку система S состоит только из равенств термов, при получении решения (/i,... , fr) важными являются не сами значения функций fi на наборах вида а , а лишь соотношения равенства/неравенства между значениями функций на этих наборах и значениями термов-переменных и термов, начинающихся символами функциональных констант. Иными словами, если при определении решения (/i,... , fr) мы изменим значения функций на упомянутых наборах, но сохраним отношения равенства/неравенства между перечисленными значениями термов, то вновь получим решение системы уравнений S. Фактически именно это преобразо вание мы проделали во второй части доказательства теоремы 14.
Мы хотим далее сосредоточиться только на значениях термов вида (/ (а ). Для этого зафиксируем нумерацию (с основанием N) всех пар термов вида где при і = I должно быть j = т. Обозначим через [5 = /Зорі двоичную последовательность, в которой / = 1 в том и только том случае, когда в паре термов (7) с номером t значения термов совпадают. Пусть Fp обозначает множество всех наборов функций (gi,... , дг), где функции д и fi зависят от одного и того же числа переменных, 1 і г и двоичная последовательность, построенная для набора функций (gi,... ,дг), совпадает с последовательностью (3. Очевидно, что набор функций (/i,... , fr) принадлежит множеству Fp, и этому множеству принадлежат все решения системы S, «подобные» решению (/i,. .. , fr) . Множество Fp мы рассматриваем как «накрывающее» множество для всех решений системы S, «подобных» решению (/i,.. . , fr) (и определяемых бесконечной ветвью В).
Проведенные выше рассуждения приводят к следующему утверждению -следствию из теоремы 14.
Следствие 11. Множество всех решений ситемы функциональных уравнений над {р(х, у, z)} содержится внутри объединения всех множеств Fp, где последовательности [5 построены для различных бесконечных ветвей дерева А. Заключение
На защиту выносятся следующие результаты: 1. Доказано, что для всякого общерекурсивного оператора Ф(/і,...,/т) найдется такая система уравнений (в формализме FE) с функциональными константами 0, ж+1 и /і,... , /m, которая для любого выбора функциональных констант /i,... , /т определяет (по своей главной функциональной Переменной) фуНКЦИЮ Ф(/і, , fm). 2. Доказано, что FE-замыкание систем, подобных системе {0, ж + 1} , а также каждой из систем {% }, {% }, {х }; {х }) совпадает с классом S} аналитической иерархии Клини. 3. Доказано, что проблема выполнимости для систем функциональных уравнений над множествами {p(x}y}z)} и {р(х,у, z), 2i,..., а }, где ai,...,dk — константы, алгоритмически неразрешима и принадлежит классу Пі арифметической иерархии Клини-Мостовского. 4. Доказано, что мощность семейства всех FE-замкнутых классов гипер-континуальна, а семейства всех FE-предполных классов — не менее чем континуальна.
Дальнейшие исследования могут быть продолжены по трем основным направлениям: изучение FE-замыканий множеств функций, отличных от рассмотренных, а также их обобщений; исследование фрагментов решетки замкнутых классов, порожденных оператором FE-замыкания; определение сложности проблемы выполнимости для систем, отличных от рассмотренных.
Особенно интересны вопросы о расположении класса Н однородных функций в решетке замкнутых классов, порожденных оператором FE-замыкания, об обобщении результатов, полученных для рассмотренных характеристических функций предикатов сравнения, на случай характеристических функций произвольных отношений эквивалентности и отношений частичного порядка, об обобщении выводов о сложности задачи выполнимости для систем функциональных уравнений в зависимости от множества заданных функциональных констант.