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

• Калинина, Инна Сергеевна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Калинина, Инна Сергеевна

Оглавление

Введение

Общая характеристика исследования

Краткая история развития поставленной задачи

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

Глава 1. Оператор ЕЕ-замыкания в счетнозначной логике

1.1 Основные понятия и терминология

1.2 Операторы РЕ-замыкания и Нв-замыкания

1.3 Принцип сопряженности для оператора

РЕ-замыкания

1.4 РЕ-замыкание множеств типа {0,^ + 1}

1.5 РЕ-замыкание множеств, содержащих

характеристические функции

1.6 Язык РЕ-замыкания с логическими связками

Глава 2. Оценки числа ЕЕ-замкнутых

и ГЕ-предполных классов

2.1 РЕ-замкнутые классы

2.2 РЕ-предполные классы

Глава 3. Сложность проблемы выполнимости систем функциональных уравнений

3.1 Неразрешимость проблемы выполнимости

3.2 Проблема выполнимости и класс ГЦ

3.3 Все решения системы функциональных уравнений

Заключение

Список литературы

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

Введение

Общая характеристика исследования

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

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

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

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

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

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

Одними из простейших функциональных уравнений являются функциональные уравнения Коши: /(х+у) = /(гтс)+/(у) (этому уравнению удовлетворяют все линейные однородные функции /(х) = С • х) и ¡{х + у) — 1(х)/{у) (этому уравнению удовлетворяют все показательные функции }'(х) — Сх), где С — произвольная константа.

В качестве примера системы функциональных уравнений можно привести одну из постановок задачи Коши из теории дифференциальных уравнений:

[ У'(х) = ¡(х,у{х)), [ У{хо) = З/о-

Здесь и у0 — функциональные константы (известные функции), а у(х)

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

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

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

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

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

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

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

Свойство рефлексивности для бинарного отношения R также можно переписать в виде функционального уравнения xr(x,x) — 1> гДе xr ~~ характеристическая функция отношения R.

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

— уравнению f{x) = f(—x), нечетные функции — уравнению f(x) = —f(—x).

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

автоморфные функции описываются функциональными уравнениями вида f(saz) = f(z), где sa есть элемент некоторой счетной подгруппы группы дробно-линейных преобразований комплексной плоскости.

Постановка задач математической физики заключается в построении математических моделей, описывающих основные закономерности изучаемого класса физических явлений. Такая постановка состоит в определении функциональных уравнений (дифференциальных, интегральных, интегро-дифференциальных или алгебраических), которым удовлетворяют функции, характеризующие физический процесс. Характерным примером является уравнение щ{х,Ь) = a2uxx(x,t), являющееся канонической формой уравнения теплопроводности. Если добавить к нему уравнения, определяющие начальное и граничные условия, то можно получить систему функциональных уравнений, определяющую задачу теплопроводности на отрезке, луче или прямой.

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

<p{xi © 2/i, ■ • •, хп 0 уп) 0 <р(0,... , 0) = ip(xi, ...,хп)@ (р{уъ ..., уп),

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

<p(xi, • • • ,хп) = <p{xi,.. .,хп).

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

ний с функциональными константами 0 и 1 и одной функциональной переменной — определяемой функцией /.

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

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

(р(х1, ...,Хп)= /(Л(Ж1, . . .,Хр), . . .,/т(х 1, . . .,Хр)),

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

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

1р{хъ ... ,ж„_1,0) = /1(3:1,... ,ж„_1), (р(хь ... ,хп + 1) = /2(жь .. .,хп,(р(х1,.. .,хп))

с функциональными константами 0, х + 1, /1, /2.

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

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

ют вид

/

y{t) = f(x!(t),..., sn(t), - 1), •. ■, ?r(t - 1)),

qi(t) = 9i{xi(t),... :Xri{t),qi(t - 1),.. .,qr{t - 1)), < ..............................

Qr(t) = 9r{xi{t),. . .,xn(t),q i(t - 1), •. .,qr{t - 1)),

?i(0) = ... = 9r(0) = 0,

где f,gi,---,gr~~ (булевы) функциональные константы.

Краткая история развития поставленной задачи

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

В данном направлении можно отметить несколько результатов о функциональных уравнениях, рассматриваемых на множестве булевых функций: О. Ekin, S. Foldes, P. L. Hammer, L. Iiellerstein в работе [45j вывели уравнения, задающие множества рефлексивных, полярных, супермодулярных, субмодулярных, билинейных, квадратичных и принадлежащих классам Хорна булевых функций, а также доказали критерий задания класса булевых функций функциональным уравнением: класс булевых функций, замкнутый относительно операции добавления и изъятия несущественных переменных, может быть описан функциональным уравнением тогда и только тогда, когда этот класс замкнут относительно операции отождествления переменных. В работе [46] этот критерий был усилен, а в работе [47] доказано существование классов, определяемых системой с бесконечным числом функциональных уравнений (например, как класс линейных пороговых функций).

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

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

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

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

во многих работах исследуются лишь отдельные фрагменты решетки. Чаще всего рассматриваются все замкнутые (либо прсднолныс) классы, содержащие некоторое множество функций, представляющих наибольший интерес. Например, в работе [29] описаны все классы, содержащие тернарный дискриминатор, в работе [36] — все предполные классы, содержащие класс полиномов, а в работе [59] — все минимальные классы, включающие в себя целиком множество селекторных функций.

В случае многозначной логики для создания решетки замкнутых классов простой структуры вводятся более «сильные» операторы замыкания, такие, как оператор параметрического замыкания (см., например, [8]), оператор позитивного замыкания (см., например, [27] ), оператор lL-замыкания (см., например, [24, 30]). Действие этих «сильных» операторов замыкания, как правило, начинается с исследования случая булевых функций (см. [25]). Исследования в данном направлении актуальны и в последнее время. К примеру, в работе [1] рассматривается замыкание относительно операции расширенной суперпозиции, в работе [38] исследуется замыкание относительно суперпозиции и перестановки с множеством наборов специального вида, в работе [35] рассматриваются классы функций, допускающих неявное представление над некоторой системой функций.

В данной диссертации исследуются функциональные уравнения счет-нозначной логики и оператор замыкания, основанный на системах функциональных уравнений. Сам термин «счетнозначная логика» предложен C.B. Яблонским (см. [40-41]) для обозначения функциональной системы с операцией суперпозиции, функции которой заданы на множестве натуральных чисел. Получение первых нетривиальных результатов в счетнозпачной логике потребовало привлечения теоретико-множественных конструкций большой технической сложности. В этом направлении следует выделить работы

Г.П. Гаврилова (см. [5-6]) и С.С. Марченкова (см. [17]), в которых исследуются вопросы полноты и выразимости относительно операции суперпозиции. Следует также отметить, что в настоящее время исследований по счетнознач-ной логике проводится крайне мало, что, вероятно, отчасти связано с тем, что мощность множества предполных относительно суперпозиции классов функций счетнозначной логики гиперконтинуальна (см. [17]), а, как сказано выше, даже континуальная мощность существенно ограничивает круг подобных исследований. Таким образом, в исследовании класса функций счетнозначной логики (например, посредством подходящих операторов замыкания) имеются лишь первоначальные результаты, которые связаны с операцией суперпозиции, и которые пока не получили дальнейшего развития.

Как и в случае многозначной логики, в случае счетнозначной логики вводятся другие, отличные от суперпозиции, операции. Подобные операции чаще всего используются вместе с операцией суперпозиции, причем рассматриваются замыкания лишь некоторых множеств функций. Самыми простыми примерами могут служить множество примитивно-рекурсивных функций, которое получаются в результате замыкания системы функций {О, а; + 1,/£(жь • • • с помощью операций суперпозиции и примитивной

рекурсии, и множество частично-рекурсивных функций, которое получаются также из системы {0,£ + 1, /£(£1, ■.., хп)} в результате замыкания по суперпозиции, примитивной рекурсии и минимизации (см., например, [52]). Также отметим счетное семейство классов Гжегорчика £2... (см. [7,

28]), порождаемых операциями суперпозиции и ограниченной рекурсии из множеств вида (0,.т + 1, /£(жь • • • > хп), Л}, где {Д-(х 1,^2)} — специальным образом выбранная последовательность монотонных примитивно- рекурсивных функций. Эти классы образуют возрастающую иерархию множества всех примитивно-рекурсивных функций.

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

Изучение структуры множества рекурсивных функций, не принадлежащих классу примитивно-рекурсивных, началось с примера В. Аккермана (см. [44]) функции, являющейся всюду определенной и вычислимой, но не примитивно-рекурсивной. Дальнейшее развитие это иследование получило в работе [54] Р. Петер, в которой она изучала счетную иерархию вложенных классов, определяемых рекурсиями различных ступеней.

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

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

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

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

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

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

• Что представляют собой множества решений систем функциональных уравнений? Как эти множества связаны с известными классами функций, рассматриваемыми в теории алгоритмов?

• Как зависят решения систем функциональных уравнений от функциональных констант, используемых в уравнениях?

• Что дает расширение языка функциональных уравнений с помощью дополнительных логических связок?

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

• Что можно сказать о совокупности всех решений заданной системы уравнений?

• Что дает применение функциональных уравнений в вопросах классификации функций счетнозначной логики?

• Насколько сильным является оператор РЕ-замыкания? Каковы оценки числа замкнутых и предполных классов, которые он порождает?

Цель настоящей диссертации — постараться найти ответы на сформулированные выше вопросы.

Основными результатами диссертации являются следующие положения:

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

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

аналитической иерархии Клини.

• Исследована сложность проблемы выполнимости для систем функциональных уравнений над множествами {р(х, у, г)} и {р(х, у. г), аь ..., а*;},

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

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

Диссертация состоит из введения, трех глав, заключения и списка литературы.

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

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

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

класс Е}, в следствии из этой теоремы доказывается, что замыкания систем, подобных системе {х + 1}, также дают класс Е|.

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

В шестом параграфе расширяются выразительные возможности языка РЕ-замыкания путем добавления логических связок. Доказываются равенства РЕ&у[0] = РЕ|р], РЕ&_>[0] = ¥Е\р] и РЕ&^[0] = РЕИ, где р - тернарный дискриминатор. Также доказываются утверждения о том, что классы РЕ&у[шах(ж, у)] и РЕ^[тт(а;, у)] совпадают с классом Е|. Устанавливается справедливость теоремы: РЕ-замыкание множества {р(х, у, г), ах,..., а^}, где а^ ..., а^ — константы, совпадает с классом всех функций, самосопряженных относительно любых перестановок с неподвижными точками ах, ..., ац. Выводится следствие из этой теоремы: РЕ-замыкание множества {%=} совпадает с классом всех функций, самосопряженных относительно любых перестановок с неподвижными точками 0,1.

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

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

Результаты диссертации опубликованы в рецензируемых журналах из списка ВАК (работы [9-11, 31]) и в сборниках тезисов конференций (работа [12]).

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

Глава 1

Оператор ЕЕ-замыкания в счетнозначной логике

В этой главе вводятся основные понятия и терминология, принятые при изложении результатов (параграф 1.1), проводится сравнение операторов РЕ-замыкания и НС-замыкания (параграф 1.2), доказывается принцип сопряженности для оператора РЕ-замыкания и некоторые свойства замыкания систем, содержащих однородные функции (параграф 1.3), исследуется замыкание системы {х + 1,0} и подобных ей систем (параграф 1.4), исследуется замыкание некоторых систем, содержащих характеристические функции (параграфы 1.5 и 1.6), растирается язык оператора РЕ-замыкания за счет введения новых логических связок и исследуются выразительные возможности получающихся языков (параграф 1.6).

Результаты второго и третьего параграфов опубликованы в работе [31], результаты четвертого параграфа — в работах [9, 31], результаты пятого параграфа — в работе [9], результаты шестого параграфа — в работе [11].

1.1 Основные понятия и терминология

Список литературы диссертационного исследования кандидат наук Калинина, Инна Сергеевна, 2015 год

Список литературы

[1] Акулов Я. В. О полноте систем функций для классов расшиненной суперпозиции // Вестник МГУ. Серия 1. Математика. Механика. 2011. № 1. 36-41.

[2] Барздинь Я.М., Трахтенброт Б.А. Конечные автоматы (поведение и синтез). М.: Наука, 1970. С. 13-24.

[3] Верещагин Н. К., Шснь А. Языки и исчисления М.: МЦНМО, 2012. С. 178-195.

[4] Волков С. А. Конечная порождаемость некоторых групп рекурсивных перестановок // Дискретная математика. 2008. Т. 20, вып. 4. С. 61-78.

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

[6] Гаврилов Г.П. Мощность множества классов конечной высоты в счетнозначной логике // Проблемы кибернетики. Вып. 29. М.: Наука, 1974. С. 5-26.

[7] Гжегорчик А. Некоторые классы рекурсивных функций // Проблемы математической логики. М.: Мир. 1970. С. 9-49.

[8] Данильченко А. Ф. О параметрической выразимости функций трехзначной логики // Алгебра и логика. 1977. Т. 16, № 4. С. 397-416.

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

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

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

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

[13] Клини С.К. Введение в метаматематику. М.: ИЛ, 1957. С. 195-220, 234274.

[14] Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. М.: Наука, 1986. С. 151-164, 253-264.

[15] Курош А.Г. Лекции по общей алгебре. М.: Наука, 1973. С. 28-32.

[16] Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986. 367 с.

[17] Марченков С.С. О мощности множества предполных классов в некоторых классах функций счетнозначной логики // Проблемы кибернетики. Вып. 38. М.: Наука, 1981. С. 109-116.

[18] Марченков С.С. Однородные алгебры // Проблемы кибернетики. Вып. 39. М.: Наука, 1982. С. 85-106.

|19] Марченков С.С. Оператор замыкания в многозначной логике, базирующийся на функциональных уравнениях // Дискретный анализ и исследование операций. 2010. Т. 17, № 4. С. 18-31.

[20] Марченков С.С. О классификациях функций многозначной логики с помощью групп автоморфизмов // Дискретный анализ и исследование операций. 2011. Т. 18. № 4. С. 66-76.

[21] Марченков С.С. О решениях систем функциональных уравнений автоматного типа // Дискретный анализ и исследование операций. 2012. Т. 19, № 4. С. 86- 98.

[22] Марченков С.С. Определимость в языке функциональных уравнений счетпозначной логики // Дискрет, математика. 2013. Т. 25, № 4. С. 13-23.

[23] Марченков С.С. О функциональных уравнениях для функций действительных переменных // Вестник Московского ун-та. Серия 15. Вычислит, матем. и кибернет. 2014. № 1. С. 26-32.

[24] Марченков С. С. Операторы замыкания логико-функционалыюго типа. М.: МАКС ПРЕСС. 2012. С. 66-75.

[25] Марченков С. С. Основы теории булевых функций. М.: ФИЗМАТЛИТ. 2014. С. 92-110.

[26] Марченков С. С. Клоновая классификация дуально дискриминатроных алгебр с конечным носителем // Математические заметки. 1997. Т. 61. № 3. С. 359-366.

[27] Марченков С. С. Критерий позитивной полноты в трехзначной логике // Дискретный анализ и исследование операций. Сер. 1. 2006. Т. 13, № 3. С. 27-39.

[28] Марченков С. С. Элементарные рекурсивные функции. М.: МЦНМО. 2003. С. 50-71, 78-82.

[29] Марченков С.С. РЕ-классификация функций многозначной логики // Вестник Московского ун-та. Сер. 15. Вычисл. матем. и кибери. 2011. № 2. С. 32-39.

[30] Марченков С. С. О выразимости функций многозначной логики в некоторых логико-функциональны х языках // Дискретная математика. 1999. Т. И, № 4. С. 110-126.

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

[32] Марченков С. С., Федорова В. С. О решениях систем функциональных булевых уравнений // Дискретный анализ и исследование операций. 2008. Т. 15, № 6. С. 48-57.

[33] Марченков С. С., Федорова В. С. О решениях систем функциональных уравнений многозначной логики // Доклады РАН. 2009. Т. 426, № 4. С. 448-449.

[34] Марченков С. С., Федорова В. С. Решения систем функциональных уравнений многозначной логики // Вестник. Московского ун-та. Сер. 15. Вычисл. матем. и киберн. 2009. № 4. С. 29-33.

[35] Михайлец Е. В. О ранге неявных представлений над одним классом функций трехзначной логики // Вестник МГУ. Серия 1. Математика. Механика. 2008. № 2. С. 65-70.

[36] Нечаев А. А. Критерий полноты системы функций рп-значной логики, содержащий операции сложения и умножения по модую рп // Методы

дискретного анализа в решении комбинаторных задач. 1980. Вып. 34. С. 74-89.

[37] Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972. 624 с.

[38| Тарасова О. С. Классы функций трехзначной логики, замкнутые относительно суперпозиции и перестановок // Математические вопросы кибернетики. 2004. Вып. 13. С. 59 112.

[39] Федорова B.C. О сложности проблемы выполнимости системы функциональных булевых уравнений // Дискрет, анализ и исслед. операций. 2013. Т. 20, № 3. С. 84-100.

[40] Яблонский С.В. О предельных логиках // Доклады АН СССР. 1958. Т. 118, № 4. С. 657-660.

[41] Яблонский С.В. О некоторых свойствах счетных замкнутых классов из Рх0 // Доклады АН СССР. 1958. Т. 124, № 5. С. 990-993.

[42] Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. С. 14-32.

[43] Янов Ю. И., Мучник А. А. О существовании /г-значных замкнутых классов, не имеющих конечного базиса // Докл. АН СССР. 1959. Т. 127, № 1. С. 44-46.

[44] Ackermann W. Zum Hilbertschen Aufbau der reellen Zahlen // Math. Annalen. 1928. V. 99. S. 118-133.

[45] Ekin O., Foldes S., Hammer P. L., Hellerstein L. Equational characterizations of Boolean function classes // Discrete Math. 2000. V. 211. P. 27-51.

[46] Foldes S. Equational classes of Boolean functions via the HSP Theorem // Algebra Univers. 2000. V. 44. P. 309-324.

[47] Hellerstein L. Ongeneralized constraints and certificates / / Rut cor Reserch Report 26 98. Rutcor, Rutgers University, 1999. P. 1-53.

[48] Herbrand J. Sur le problème fondamental de la logique mathématique // Compt. rend. Soc. Sei. Lettr. Vars. Classe III. 1931. V. 24. P. 12-56.

[49] Herbrand J. Sur la non-contradiction de l'arithmétique // J. reine und angew. Math. 1931. Bd. 166. P. 1-6.

[50] Gödel K. Uber formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I // Monatsh. Math, und Phys. 1931. Bd. 38. S. 173198.

[51] Kalmar L. Ein einfaches Beispiel fur unentscheibares Problem // Matematikai e s fizikai lapok. 1943. B. 50. S. 1-23.

[52] Kleene S. The theory of recursive functions, approaching its centennial // Bulletin of the American Mathematical Society. 1981. V. 5, 1. P. 43-61.

[53] Marczewski E. Homogeneous operations and homogeneous algebras // Fund. Math. 1964. V. 56, № 1. P. 81-103.

[54] Peter R. Uber die mehrfache Rekursion // Mathematische Aniialen. Vol. 113. Ger., 1937. S. 489-527.

[55] Pippenger N. Galois theory for minors of finite functions // Discrete Math. 2002. V. 254. P. 405-419.

[56] Pixley A.F. The ternary discriminator function in universal algebra // Math. Ann. 1971. Bd. 191, P. 167-180.

[57] Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. V. 43. № 3. P. 163-185.

[58] Post E. L. Two-valued iterative systems of mathematical logic // Annals of Math. Studies. Princeton-London: Princeton Univ. Press. 1941. V. 5. P. 122.

[59] Rosenberg I. G. Minimal clones I: The five types // Lectures in Universal Algebra (Proc. Conf. Szeged 1983). 1986. V. 43. P. 405-427.

[60] Skolem Th. Proof of some theorems on recursively enumerable sets // Notre Dame Journal of Formal Logic. 1962. V. 3, N 2. P. 65-74.