Системы функциональных уравнений счетнозначной логики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Калинина Инна Сергеевна

Системы функциональных уравнений счетнозначной логики

Специальность 01.01.09 — дискретная математика и математическая кибернетика

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

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

5 АВГ 2015

Москва - 2015

005571311

005571311

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

Марченков Сергей Серафимович,

доктор физико-математических наук, профессор кафедры математической кибернетики факультета вычислительной математики и кибернетики федерального государственного бюджетного образовательного учреждения высшего образования «Московский государственнный университет имени М. В. Ломоносова». Соколов Валерий Анатольевич, доктор физико-математических наук, профессор, заведующий кафедрой теоретической информатики факультета информатики и вычислительной техники федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Ярославский государственный университет им. П. Г. Демидова» Мещанинов Дмитрий Германович, кандидат физико-математических наук, доцент кафедры математического моделирования института автоматики и вычислительной техники федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский университет «МЭИ»

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Казанский (Приволжский) федеральный университет»

Защита состоится 25 сентября в 11 час. 00 мин. на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М. В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, д. 1, стр. 52, факультет ВМК, аудитория 685.

С диссертацией можно ознакомиться в Научной библиотеке Московского государственного университета имени М. В. Ломоносова по адресу: 119192, Москва, Ломоносовский проспект, д. 27, а также на официальном сайте факультета ВМК МГУ https://cs.msu.ru в разделе «Диссертации».

Автореферат разослан < ^ СаР _2015 г.

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

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

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

Официальные оппоненты:

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

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

Актуальность темы диссертации.

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

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

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

Функциональные уравнепия представляют собой весьма общий класс уравнений, пми, по существу, являются дифференциальные уравнения, интегральные уравнения, уравнения конечных разностных схем и ряд других, хотя само название •«функциональные уравнения» к уравнениям этих типов обычпо не относят. Решениями функциональных уравнений могут быть как конкретные функции, так и множества функций, зависящие от некоторых параметров, в частности, от функций, определяемых этими же уравнениями. Несколько функциональных уравнений можно объединить в систему функциональных уравнений. Решением системы считается набор функций, являющийся решением каждого уравнения.

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

Одними из простейших функциональных уравнений являются функциональные уравнения Коши: f(x + у) = f(x) + f(y) (этому уравнению удовлетворяют все линейные однородные функции f(x) = С-х) и f(x + y) = f(x)f(y) (этому уравнению удовлетворяют все показательные функции f(x) = Сх), где С — произвольная константа.

К функциональным уравнениям также относятся многочисленные рекуррентные соотношения, которые содержат неизвестные функции от целочисленных переменных и оператор сдвига. Пример подобного соотношения: /(n) = f(n — 1) 4- f{n — 2).

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

х о у = у о х, (х о у) о z = х о (у о г),

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

f{x,y) = f(v,x), f{f(x,y),z)=f(xj(y,z)).

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

Еще несколько простейших, хорошо известных примеров из математического анализа: периодические функции с периодом Т — это функции, удовлетворяющие функциональному уравнению f{x + Т) = f(x), четные функции — уравнению f(x) = f(-x), нечетные функции — уравнению f(x) = —f(—x).

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

V(®i © Уъ • • •© Уп) © V(0, • ■ ■. 0) = 4>{хи..., хп) ® ... ,уп),

где 0 и ф суть заданные функциональные константы нуль и сложение по модулю два. Все самодвойственные булевы функции от п переменных — это решения функционального уравнения

<р(х 1,..., s„) = ■ • •, хп).

Само задание булевой функции }(х\,... ,х„) табличным способом есть ни что иное, как система функциональных уравнений, состоящая из 2" уравнений с функциональными константами 0 и 1 и одной функциональной переменной — определяемой функцией /.

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

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

<р(х 1, ...,!„) = /(/1(2:1, ...,хр),.. .,/т{хи... ,хр)),

где /, /1,... , /т — функциональные копстанты.

Действие оператора примитивной рекурсии может быть выражено в виде системы функциональных уравнений

<р(х 1, . . . .Жп-ьО) = /1(^1, • - ■ ,Хп-1), <р(хг,.. .,хп-1,хп + 1) = Мх1,...,хп,Ч>(х1,-..,хп)) с функциональными константами 0, х + 1, /1, /2.

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

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

' г/№ = /(*1 (<)-••■ ,*»(*). 41 -1), ■•• М* -1)),

<?!(*) = 51(21(<), • • • , 51 (* - 1), • • • , 9г(< - 1)),

qr(t) = <?r(zi(i).....xn{t),qi{t - 1),... ,qr(t - 1)),

. <?i(0) = ... = ?r(0) = 0, где f,g\,... ,gr — (булевы) функциональные константы.

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

В данном направлении можно отметить несколько результатов о функциональных уравнениях, рассматриваемых на множестве булевых функций: О. Ekin, S. Foldes, P. L. Hammer, L. Hellerstein опубликовали ряд работ, в которых авторы вывели уравнения, задающие множества рефлексивных, полярных, супермодулярных, субмодулярных, билинейных, квадратичных и принадлежащих классам Хорна булевых функций, а также доказали критерий задания класса булевых функций функциональным уравнением.

з

Также необходимо обратить внимание на работы С.С. Марченкова и B.C. Федоровой, в которых функциональные уравнения рассматриваются на множестве функций многозначной логики. В данных работах, в частности, полностью решены вопросы о выразимости одних функций через другие с помощью систем функциональных уравнений (в другой терминологии — описание всех классов функций многозначной логики, замкнутых относительно систем функциональных уравнений), а также о сложности решения проблемы выполнимости для систем функциональных уравнений.

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

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

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

В случае мпогозначной логики для создания решетки замкнутых классов простой структуры вводятся более «сильные» операторы замыкания, такие, как оператор параметрического замыкания, оператор позитивного замыкания, оператор lL-замыкания. Действие этих «сильных» операторов замыкания, как правило, начинается с исследования случая булевых функций. Исследования в данном направлении актуальны и в последнее время.

В данной диссертации исследуются функциональные уравнения счетнозначной логики и оператор замыкания, основанный па системах функциональных уравнений. Сам термин «счетнозначная логика» предложен C.B. Яблонским для обозначения функциональной

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

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

Как и в случае многозначной логики, в случае счетнозначной логики вводятся другие, отличные от суперпозиции, операции. Подобные операции чаще всего используют^ ся вместе с операцией суперпозиции, причем рассматриваются замыкания лишь некоторых множеств функций. Самыми простым примерами могут служить множество примитивно-рекурсивных функций, которое получаются в результате замыкания системы функций {0, х + 1,/£(хъ... ,£„)} с помощью операций суперпозиции и примитивной рекурсии, и множество частично-рекурсивных функций, которое получаются также из системы {0, х+ 1,1£(хг,..., хп)} в результате замыкания по суперпозиции, примитивной рекурсии и минимизации. Также отметим счетное семейство классов Гжегорчика £°, Е1, £2..., порождаемых операциями суперпозиции и ограниченной рекурсии из множеств вида {0,х + 1,1Л(хи...,£„),/*}, где {/к{х1,хг)} — специальным образом выбранная последовательность монотонных примитивно-рекурсивных функций. Эти классы образуют возрастающую иерархию множества всех примитивно-рекурсивных функций.

Также следует привести пример, в котором в качестве исходных функций рассматривается множество функций {х + 1,1£(хь..., х„),х-у}. Если в качестве порождающих операций взять операции суперпозиции н ограниченного суммирования, то образуется класс функций, элементарных по Сколему, а если добавить операцию ограниченного мультиплицирования, то получится класс функций, элементарных по Кальмару. Вопрос о порождении различных подмножеств множества рекурсивных функций актуален и в настоящее время.

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

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

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

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

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

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

Основные результаты диссертации:

• Доказано, что для всякого общерекурсивного оператора Ф(Д,..., /т) найдется такая система уравнений с функциональными константами 0,2 + 1 и Л,...,/*», которая для любого выбора функциональных констант Л,..., /т определяет (по выделенной функциональной переменной) функцию Ф(Д,..., /т)-

• Установлено, что РЕ-замыкание систем, подобных системе {0,2+1} , а также каждой из систем {х<}| {х<}> {Х>}, {х>}| совпадает с классом Е| алалитической иерархии

б

Клшш.'

• Исследована сложность проблемы выполнимости для систем функциональных уравнений над множествами {р(х,у,2)} и (р(г,у,г),аи...,ак}, где р — тернарный дискриминатор, 01,...,ац — константы. Доказано, что данная проблема алгоритмически неразрешима и принадлежит классу П1 арифметической иерархии Клини-Мостовского.

• Получены оценки мощности множеств РЕ-замкнутых и РЕ-предполных классов. Доказано, что мощность семейства всех РЕ-замкнутых классов гиперконтинуальна, а семейства всех РЕ-предполных классов — не менее чем континуальна.

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

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

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

Апробация работы и список публикаций. Результаты диссертации опубликованы в рецензируемых журналах из перечня ВАК (работы [1-4]) и в сборнике тезисов конференции (работа [5]). Результаты диссертации получены автором самостоятельно, некоторые из них — в соавторстве с научным руководителем. Результаты диссертации излагались на конференции «Ломоносовские чтения» в 2013 и 2014 г., на конференции «Тихоновские чтения» в 2014 г., докладывались па семинаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета ВМК МГУ и на семинаре лаборатории ПОИС факультета компьютерных наук ВШЭ.

Структура п объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Общий объем работы составляет 77 страниц. Список ли-

тературы состоит из 60 наименований. Содержание работы

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

Глава 1 посвящена оператору РЕ-замыкания и состоит из 6 параграфов. Результаты данной главы опубликованы в работах [1-2, 4]. В первом параграфе вводятся базовые определения, используемые в дальнейшем изложении. В параграфе 2 определяется оператор замыкания, основанный на формализме Эрбрана-Гёделя (оператор НС-замыкания), и доказывается теорема: для всякого общерекурсивного оператора Ф(Д,..., /т) найдется такая система уравнений (в формализме РЕ) с функциональными константами 0,1+1 и

Д...../т, которая для любого выбора функциональных констант Д,..., /т определяет

(по своей главной функциональной переменной) функцию Ф(Д,.. .,/„>)• В третьем параг графе доказывается принцип сопряженности для оператора РЕ-замыкания, формулируются важные следствия из него и доказывается теорема о том, что любой РЕ-замкнутый класс, содержащий нетривиальную однородную функцию, целиком включает класс Н однородных функций.

В четвертом параграфе доказывается теорема о том, что класс отношений ЕРЕ, определимых в формализме РЕ, совпадает с классом Е^ аналитической иерархии Клини. Кроме того, устанавливается справедливость теоремы о том, что замыкания систем функций, подобных системе {0,2 + 1}, дают класс Е}, в следствии из этой теоремы доказывается, что замыкания систем, подобных системе {я + 1}, также дают класс Е^.

В пятом параграфе исследуются системы, содержащие характеристические функции хорошо известных бинарных отношений. Доказывается, что РЕ-замыкание каждого из множеств функций {х<}> {х<} совпадает с классом Е}, а РЕ-замыкание множества функций {0,1, х=} совпадает с РЕ-замыканием множества функций {х=}, содержит класс Н однородных функций, включается в класс функций Е* и не совпадает с классом Е*.

В шестом параграфе расширяются выразительные возможности языка РЕ-замыкания путем добавления логических связок. Доказываются равенства РЕ&у[01 = РЕ[р], [0] = РЕ[р] и РЕ&~[0] = РЕ[р], где р — тернарный дискриминатор. Также доказываются утверждения о том, что классы РЕьУ[тах(а;, т/)] и РЕь-/[тш(х,у)] совпадав ют с классом Е*. Устанавливается справедливость теоремы: РЕ-замыкание множества

{р(х, у, г), Ох,..., о*}, где а\,..., а* — константы, совпадает с классом всех функций, самосопряженных относительно любых перестановок с неподвижными точками ах,..., а*. Выводится следствие из этой теоремы: РЕ-замыкание множества {х=} совпадает с классом всех функций, самосопряженных относительно любых перестановок с неподвижными точками 0,1.

Пусть N = {0,1,...} — расширенный натуральный ряд, Рц — множество всех функций на N (множество функций счетнозначной логики). Если <3 С Рц и п > 1, то через <9^"' обозначаем множество всех функций из С}, зависящих от п переменных.

Предполагаем, что каждая функция из Рн имеет индивидуальное обозначение. Для обозначения п-местпых функций из Рм используем символы /и \ которые называем функциональными константами. Наряду с функциональными константами рассматриваем функциональные переменные со значениями в области Р^К Кроме функциональных переменных используем обычные предметные переменные х^, • • • с областью значений N.

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

Пусть С Рн. Определим понятие терма над С}. Всякая предметная переменная есть терм над <3. Если ¿1,..., £„ — термы над <3, — функциональная константа, служащая обозначением функции из <3, — функциональная переменная, то выражения

.....1п)

суть термы над С}.

Равенством над <2 называем любое выражение вида ¿1 = ¿2, где ¿1, ¿2 — термы над С). Равенства пад <3 считаем также функциональными уравнениями над О- Пусть ..., р'СГ'1 — все функциональные переменные, входящие в уравнение ^ = ¿2- Решением уравнения ¿1 = 42 называем систему {/д1',...,функций пз Рм, которая после замены каждой переменной соответствующей функциональной константой превращает уравнение ¿1 = в тождество (относительно всех входящих в уравнение предметных переменных). Если 2 — конечная система уравнений, то решением системы уравнений 2 называем систему функций из Рн, которая является решением каждого уравнения, входящего в систему 5.

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

S. Пусть ipY* — главная функциональная переменная системы уравнений S и Q С Говорим, что множество функций Q определяется системой уравнений S, если Q является множеством всех тех n-местных функций, которые входят а решения системы S в качестве компоненты.по переменной v5!"'-

Пусть Q С PN. Замыканием множества Q относительно систем функциональных уравнений (коротко: FE-замыкалием) называем множество всех функций из Рц, которые определяются как одноэлементные множества системами функциональных уравнений пад Q. FE-замыкание множества Q обозначаем через FE[Q]. Множество Q называем FE-замкнутъш, если Q =FE[Q],

Для любого множества Q (в том числе при Q = 0) множеству FE[Q] принадлежат все селекторные функции и множество FE[Q] замкнуто относительно операции суперпозиции.

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

Язык оператора HG-замыкания совпадает с языком оператора FE-замыкания. То же самое относится к понятиям терма и равенства (уравнения). Пусть t\, — термы. Частным случаем равенства ti = ¿2 называем любое равенство вида t[ = t'2, где выражения f^t^ получаются из термов ii,ta подстановкой вместо всех предметных переменных некоторых элементов из N. При этом все вхождения одной и той же предметной переменной в термы ti,t2 замещаются одним и тем же элементом из N.

Пусть Н — конечная система равенств. Последовательность равенств Ei,.. .,Е„ не содержащих предметных переменных, называется выводом из системы равенств Е, если каждое равенство Ei этой последовательности удовлетворяет одному из следующих условий:

1) Ei есть частный случай одного из равенств системы S;

2) для некоторого j < i равенство Ei получается из равенства Ej заменой выражения вида /(п)(о 1, • • • I »л) элементом о, где а — /(п)(аь... ,а„);

3) для некоторых j,l < г равенство Et получается из равенства Ej заменой выражения вида ...,Оп) элементом а, при этом равенство Et имеет вид о = •••>°п)-

Будем говорить, что равенство Е, не содержащее предметных переменных, выводимо из системы равенств Н, если существует вывод из системы равенств S, который содержит

Е в качестве одного из равенств. Систему равенств Е называем корректной, если из нее невозможно вывести два равенства вида

а = уг(п)(01,...,ап)> & = ¥>(п)(а1.....а„),

где афЪ.

Пусть <3 С Рц, 3 — корректная система равенств над С}, — функциональная переменная, входящая в 2. Говорим, что (частичная) функция д(хи • • • ,хп) определяется системой равенств 2 по функциональной переменной <р, если для любого набора (ах.....а„)

равенство • • • I °п) = а выводимо из системы равенств 2 в том и только том случае,

когда 5(ах,..., а„) = а. Множество всех функций, определяемых системой равенств 2 над <3, обозначим через 2(ф). Положим

НвДО = У 5(3),

где объединение берется по всем корректным системам равенств 2 над С}. Множество называем ЯС-замыканием множества С}. Отметим, что в теории алгоритмов преимущественно рассматривается множество 1Ю[{0,з: + 1}], которое в этом случае совпадает с классом всех частично рекурсивных функций. Однако в формализме Эрбрана-Гёделя, как и в любом другом формализме рекурсивных функций, можно определять не только частично рекурсивные функции, но и частично рекурсивные, рекурсивные и общерекурсивные операторы.

Чтобы задать в формализме НО общерекурсивный оператор Ф(/х(п1\... ,/тт)) на множестве Р^ х... х следует рассмотреть систему равенств 2, которая помимо функциональных констант 0,2 + 1 содержит также функциональные константы ..., {т (которые в данном случае играют роль функциональных переменных оператора Ф) и некоторые функциональные переменные .. .,<Рк- В случае выполпепия равенства

система равенств 2 должна корректно определять (по главной функциональной переменной) функцию /через функции ...,/Й1™'.

Теорема 1. Для всякого общерекурсивного оператора Ф(/ъ • • • ,/т) найдется такая система уравнений (в формализме РЕ) с функциональными константами 0, х + 1 "

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

(по своей главной функциональной переменной) функцию Ф(/х,..., /т).

Пусть /(жх,...,хп) е Рц, 7г — перестановка на множестве N и 7Г-1 — перестановка,

обратная к перестановке тт. Функция

Г {хг, ...,хп) = я-ЧАФг), • • •. Фп)))

называется сопряженной с функцией / с помощью перестановки п. Если / = /*, то функция / носит название самосопряженной с помощью перестановки 7Г. Множество всех функций из Рм: самосопряженных с помощью перестановки тг, обозначим через Множество 5, замкнуто относительно суперпозиции. Положим

Я = р|5.

где пересечение рассматривается по всем перестановкам 7г на множестве N. Функции из множества Я назваются однородными функциями. Пусть

, . , если х = у, р[х,-

I *

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

Функция p{x,y,z), называемая тернарным дискриминатором, является однородной и порождает по суперпозиции весь класс Н.

Утверждение 1. (принцип сопряженности для FE-замыкания). Пусть система Н функциональных уравнений над множеством функций {Д,..., /,} определяет функцию fun — перестановка на множестве N. Тогда система уравнений Н", полученная из системы S заменой каждой функциональной константы Д, 1 < г < s, соответствующей функциональной константой ff, определяет функцию f.

Следствие 1. Для любой перестановки п класс SV является FE-замкнутым.

Следствие 2. Класс Н однородных функций ЯП-замкнут.

Следствие 3. Пусть все функции из множества {Д,..., /,} являются самосопряженными относительно любой перестановки тг из группы G. Тогда множество решений {¡?ь • • ■ 19if ■} любой системы уравнений над множеством функциональных констант {Д,..., /,} замкнуто относительно перехода gt —> g*.

Теорема 2. Любой FE-замкнутый класс, содержащий нетривиальную однородную функцию, целиком включает класс Н однородных функций.

К проблеме построения FE-замыкания довольно близко примыкают вопросы выразимости отношений в языке функциональных уравнений. Будем рассматривать функциональные уравнения над множеством функциональных констант {0, х +1}. Тогда, согласно теореме 1, всякий общерекурсивный оператор (в частности, всякую общерекурсивную

функцию) можно определить подходящей системой функциональных уравнений. Однако с помощью функциональных уравнений можно определять и отношения Я на множествах вида Р^х ... х Рхт\ Именно, рассмотрим систему функциональных уравнений 5 с функциональными переменными

„(ш) ИЫ „("»+0 м(п™,+,)

VI > • ■ • I 'Ртп > У?т+1 » • " ' > Гтп+1 >

из которых переменные <р[П1\..., будем считать «главными» переменными. Будем далее считать, что система Е определяет отношение Я на множестве Р^11' х.. .х , если для любого набора функций (/[П1\.. .,/^Г1) из х ... х Р^"0 найдется такой набор функций . • •, из р'£™+1) х ... х р£ь"+,), что при замене функциональных

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

константами /1с"1),..., /^Г"' полученная система равенств будет тождественно истинной (относительно всех входящих в систему предметных переменных) в том и только том случае, когда отношение Я истинно на наборе (/^К ■ ■ •, /т™ )■

Обозначим через БРЕ класс всех отношений (на декартовых произведениях множеств вида Рр?'), которые определяются в указанном выше смысле системами функциональных уравнений над тожеством функциональных констант {0, х + 1}.

Класс Е} аналитической иерархии Клшш определяется как класс всех отношений, пред-ставимых в форме

(3/т+1) . .. (3/т+,)0Лс1) ... (VХ*)Я(/г...../т, /т+1, ■ • • . /т+1, ХХ,. . ., Хк),

где

Л е ...../те Р/Г\ /т+1 6 Р}Г+1\ ■ ■ ■, /шн е

и Я — рекурсивное отношение па множестве

Р^П1) X ... X X Р£™+0 X ... X X

Определения классов ИРЕ и Е} имеют довольно много общего. Это подтверждает следующая

Теорема 3. Классы отношений Ш^Е и Е} совпадают.

В дальнейшем Е} рассматривается также как класс всех функций, графики которых принадлежат классу отношений ЕЦ.

Следствие 4. РЕ-замыкание системы {х + 1} совпадает с классом Е}.

Теорема 4. Пусть а € N и /(х) — такая функция из класса Е£, что {/"(в) : п = 1,2,...} = N \ {а}. Тогда РЕ-замыкакие множества {а, /(ж)} совпадает с классом Е^.

Замечание 1. По аналогии со следствием 4 из теоремы 3, в указанной системе можно оставить лишь функцию /.

Исходя из теорем 3 и 4, можно сделать некоторые выводы о выразительной способности оператора РЕ-замыкания: оператор РЕ-замыкания является очень «сильным» оператором замыкания, так как даже замыкание такого простого множества, как {х +1} (и подобных ему множеств), совпадает с классом функций, лежащим далеко за пределами множества вычислимых функций. В частности, теорема 3 также показывает, что класс рекурсивных функций не является РЕ-замкнутым.

Характеристической функцией отношения р{х\,...,х„) назовем функцию х(®1 > • • •, хп), которая принимает лишь значения 0 и 1, причем значение 1 — только на наборах, удовлетворяющих отношению р. Характеристические функции отношений XI = х?, хг < х2, хх < х2 обозначим соответственно х=, Х<> Х<-

Теорема 5. 'РЕ-замыкание каждого из множеств фунщий {0,1,Х<Ь {0,1,Х<} совпадает с классом Е^.

Следствие 5. ¥Е-замыкание каждого из множеств функций {х<}. {х<} совпадает с классом Е}.

Замечание 2. Данное следствие также остается верным для систем {%>}, {х>}> содержащих характеристические функции предикатов х\> х2 и Х\> х2 соответственно.

Теорема 6. РЕ-залшкание множества функций {0,1, х=} содержит класс Н однородных функций, лежит внутри класса и не совпадает с

Замечание 3. РЕ -замыкание множества функций {0,1,х=} совпадает с РЕ-замыканием множества {х=}-

Расширим логические возможности языка РЕ: будем вносить в язык РЕ некоторое множество М логических связок. Полученный в результате язык обозначим через РЕ^. Формулы языка FE^í образуем из элементарных формул (равенств термов) с помощью логических операций из множества М.

Теорема 7. Имеет место равенство РЕьу[0] = РЕ[р].

Следствие 6. Имеют место равенства РЕ&-*[0] = РЕ[р] и РЕ&~[0] = РЕ[р].

Теорема 8. Класс РЕ&у[и1ах(1,у)] совпадают с классом Е^ аналитической иерархии Кли-ни.

Следствие 7. Класс у)] совпадает с классом Е}.

Наряду с простым сравнением операторов FE-замыкания с логическими связками и без них теорема 7 создает удобный аппарат для дальнейших исследований FE-замыканий (без логических связок) различных систем. А именно, при доказательстве утверждений удобно перейти к FE-замыканию с логическими связками и оперировать уже не функциональными уравнениями, а формулами. Таким образом этот метод используется при доказательстве многих утверждений, сформулированных в данной диссертации.

Теорема 9. FE-замыкание множества {р(х, у, z), 01,..., а*}, где ai,..., ak~ константы, совпадает с классом всех функций, самосопряженных относительно любых перестановок с неподвижными точками aj,..., а*.

Следствие 8. FE-замыкание множества {%=} совпадает с классом всех функций, самосопряженных относительно любых перестановок с неподвижными точками 0,1.

В главе 2 исследуются FE-замкнутые и FE-предполные классы. Глава состоит из двух параграфов. Результаты данной главы опубликованы в работах [2,4]. В первом параграфе доказывается несколько вспомогательных утверждений и основная теорема о том, что мощность множества FE-замкнутых классов гиперконтинуальна. Во втором параграфе рассматриваются FE-предполпые классы. Демонстрируется, как некоторые FE-замкнутые классы можно расширить до FE-предполных. Доказывается теорема о том, что мощность множества FE-предполных классов не менее чем континуальна.

Пусть M есть произвольное подмножество из N. Обозначим через С{М) множество всех функций /, которые являются самосопряженными относительно любых перестановок, тождественных на N \ M и произвольных на М. Если F - некоторая совокупность подмножеств множества N, то пусть

C{F) = U mef

Далее будем рассматривать не произвольные совокупности множеств, а только те, которые являются фильтрами. Фильтром (на N) назовем совокупность F подмножеств множества N, удовлетворяющую двум условиям:

1. Если Mi, М2 £ F, то Mi ПМ2е F.

2. Если Mi € F и Mi С Мг, то M2eF.

Утверждение 2. Для любого фильтра F множество H однородных функций содержится в C(F).

Утверждение 3. Для любого фильтра F класс C(F) является FE-замкнутым классом.

Утверждение 4. Для любого фильтра Р, не содержащего одноэлементных множеств, множество С(Р) отлично от множества Рн-

Фильтр называется главным, если он состоит из всех надмножеств некоторого множества (случаи множеств 0 и N не исключаются).

Утверждение 5. Если и Р2 — два различных неглавных фильтра, то ОД ф С(Я,).

Теорема 10. Мощность семейства всех РЕ-замкнутых классов гиперконтинуальна.

Класс функций С} назовем РЕ-предполным, если он РЕ-замкпут, отличен от Рц и при добавлении любой функции из Рк\(2 образует систему, ИЗ-полную в классе Рм.

Теорема 11. Если фильтр Р не содержит одноэлементных множеств, но содержит можество с бесконечным дополнением, то РЕ-замкнутый класс функций С(Р) можно расширить до РЕ-предполного класса.

Разобьем множество N на счетное число попарно не пересекающихся неупорядоченых пар (¿1,12). Пусть ж — перестановка на Лг, которая переставляет местами элементы ¿1 и ¿2 каждой пары. Обозначим через П множество всех таких перестановок 7г. Множество П континуально по построению. Обозначим через Б* класс всех функций, самосопряженных относительно перестановки 7г из П .

Лемма 2. Для любой перестановки тг 6 П класс Бж РЕ-предполон в Рдг.

Теорема 12. Мощность семейства РЕ-предполных классов не менее чем континуальна.

Глава 3 состоит из трех параграфов. В ней изучается вопрос о сложности проблемы выполнимости систем функциональных уравнений. Результаты данной главы опубликованы в работах [3, 5]. В первом параграфе доказывается теорема о том, что проблема выполнимости систем функциональных уравнений над множеством {р(х, у, г)} алгоритмически неразрешима. Во втором параграфе доказывается теорема о том, что проблема выполнимости для систем функциональных уравнений пад множеством {р(х,у, г)} принадлежит классу П1 арифметической иерархии Клини-Мостовского. В качестве следствий из теоремы выводятся утверждения, говорящие, что множества всех выполнимых систем функциональных уравнений над множествами {р(х,у, г)} и {р(х, у, г), аг,..., а*}, где 01,..., — константы, являются т-полными множествами в классе П1 арифметической иерархии Клини-Мостовского. В третьем параграфе исследуется множество всех решений системы функциональных уравнений над множеством {р(х,у,г)}. Доказывается, что множество

всех решений системы функциональных уравнений над {р(£, у, 2)} содержится внутри объединения всех множеств вида Ре, где последовательности /3 построены для различных бесконечных ветвей дерева решений Д.

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

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

Теорема 14. Проблема выполнимости для систем функциональных уравнений над множеством {р(х,у,г)} принадлежит классу Щ арифметической иерархии Клини-Мостповского.

Множество А те-сводится к множеству В, если существует такая общерекурсивная функция /(.т), что произвольное х принадлежит множеству А тогда и только тогда, когда f(x) принадлежит множеству В. Множество А из класса К называется т-полным в классе К, если к нему т-сводимо любое множество из класса К.

Следствие 9. Множество всех выполнимых систем функциональных уравнений над {р(:г, у, г)} является т-полным множеством в классе Щ иерархии Клини-Мостовского.

Следствие 10. Множество всех выполнимых систем функциональных уравнений над [р{х,у, г), 01,..., а*}, где а.!,...., а^ — константы, является т-полным множеством в классе Щ иерархии Клини-Мостовского.

Поиск решения системы функциональных уравнений над множествами {р{х,у,г)} и {р(х, у, г),а 1,..., а*}, где а1:... ,ак — константы осуществляется путем построения дерева решений Д . При этом процесс построения дерева Д является эффективным: существует алгоритм, который по «координате» произвольной вершины дерева Д определяет, является ли данная вершина «концевой», а если пет, то вычисляет значения функций во всех рассматриваемых точках. Если система уравнений Е имеет решение, то в дереве Д существует хотя бы одна бесконечная ветвь.

Проблема существования бесконечной ветви в дереве Д выражается формулой вида (ук)Щк), где Л — рекурсивное отношение, то есть принадлежит классу Щ арифметической иерархии Клини-Мостовского.

Пусть 1ри...,ч)Т — все функциональные переменные системы Е. Зафиксируем нумерацию всех пар термов вида где а, В — наборы элементов из N. Выберем

решение {/i,.--,/r} системы 2 и обозначим через ß = ßoßi ■ ■ ■ последовательность из символов 0,1, —, в которой ßt = 1 (соответ. О или -), если для терма с номером t верно Л(5) = Л© (соответ. /¿(а) ^ /,(6) или одно из значений /¡(а), /-,(6) не определено).

В процессе построения дерева решений Д для системы 2 последовательность /3 можно определить для любой бесконечной ветви дерева Д.

Пусть Ре — множество всех наборов функций (fli,... ,дг), Для которых последовательность ^8', определенная для данного набора функций, совпадает с последовательностью ß (всюду, кроме пропусков).

Следствие И. Множество всех решений системы функциональных уравнений над {p(x,y,z)} содержится внутри объединения всех множеств Fß, где последовательности ß построены для решений различных бесконечных ветвей дерева Д.

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

Список публикаций

1. Марченков С.С., Калинина И.С. Оператор FE-замыкания в счетнозначпой логике // Вестник Московского университета. Серия 15. Вычислит, матем. и кибернет. 2013. № 3. С. 42-47.

2. Калинина И.С. О действии оператора FE-замыкания на множестве функций счет-нозначной логики // Вестник Московского университета. Серия 15. Вычислит, матем. и кибернет. 2014. № 3. С. 46-51.

3. Калинина И.С., Марченков С.С. О сложности проблемы выполнимости для систем функциональных уравнений счетнозначной логики // Известия вузов. Математика. 2015. № 8. С. 25-32.

4. Калинина И.С. О некоторых свойствах оператора FE-замыкания в счетнозначной логике // Известия высших учебных заведений. Поволжский регион. Физико-матем. науки. 2014. № 4. С. 37-46.

5. Калинина И. С. Проблема выполнимости для систем функциональных уравнений счетнозначной логики // Тезисы докладов научной конференции «Тихоновские чтения». М: МАКС ПРЕСС, 2014, С. 45-46.

Напечатано о готового оригинал-макета

Подписано в печать 02.07.2015 г. Формат 60x90 1/16. Усд.псчл. 1,0. Тираж 100 экз. Заказ 148.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.