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

В математике функциональным уравнением называется уравнение, выражающее связь между значением функции в одной точке с ее значениями в других точках. Это весьма общий класс уравнений, в которых искомой является некоторая функция, а не переменная. Функциональными уравнениями, по существу, являются дифференциальные уравнения, интегральные уравнения, уравнения в конечных разностях, однако само название &bdquo-функциональные уравнения" обычно не относят к уравнениям этих типов. Под функциональными уравнениями в узком смысле слова понимают уравнения, в которых искомые функции связаны с известными функциями одного или нескольких переменных при помощи операции образования сложной функции. Решения •функционального уравнения могут быть как конкретными функциями, так и классами функций, зависящими от произвольных параметров или произвольных функций.

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

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

Даже свойства коммутативности и ассоциативности суть не что иное как функциональные уравнения. В привычной всем записи эти законы выглядят следующим образом: а о b —boa, (а о Ь) о с = а о (Ь о с), где о — символ некоторой бинарной операции. Но если представить эту операцию в эквивалентном виде, а о b — /(а, 6), то получится как раз то, что обычно называют функциональным уравнением: а, 6) — /(6, а), /(/(а, 6), с) = /(а,/(Ь, с)).

Этот пример показывает, что функциональные уравнения можно также рассматривать как выражение некоторого свойства, характеризующего то или иное множество функций. Так, для периодических с периодом тг функций — это /(ж + 7г) = /(ж), а для четных функций — /(ж) = /(—ж).

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

Если функция известна в некоторой области, то знание для нее функционального уравнения позволяет расширить область определения этой функции. Этот прием часто применяют для аналитического продолжения функций комплексного переменного. Например, используя функциональное уравнение T (z -± 1) = zT{z) и имея значения Гамма-функции Г (^) в полосе О < Re z < 1, можно продолжить ее на всю плоскость z.

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

Также подобные примеры можно найти в различных работах, касающихся, в частности, замкнутых классов булевых функций (см., например, [2, 5, 20, 23, 41, 46, 53]).

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

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

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

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

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

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

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

Если же обратиться к дискретной математике, то можно увидеть, что целые теории строятся и развиваются на базе? подходящих языков функциональных уравнений: Так, одним из первых определенийрекурсивных функций/ в теории алгоритмов стало эрбран-геделевское определение, основанное на решениях систем функциональных уравнений специального? вида [9]. Системы канонических уравнений в теории автоматов представляют собой основной инструмент как для задания и изучения: собственно конечно-автоматных функций, так и для исследования разнообразных их обобщений [3, 10, 12].

В теории булевых функций и теории, функций многозначной, логики функциональные. уравнения представленытакже достаточношироко. Укажем" лишь три хрестоматийных" примера. Все линейные булевы функциизависящие от п переменных, могут быть определены как решения функционального уравнения. фЫ е ух,., хп ® уп) е v?(o,., о) ¦-= ., хп) ф <�р (уъ. •, уп) у где О и ® суть г заданные функциональные константы ноль и сложение по модулю дваВсе монотонные булевы функции от n переменных определяются функциональным уравнением cp (xi,., хп) V (р (х 1 V 2/1,., хп V yn) =.

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

S. Foldes в [50] усилил этот критерий, убрав предварительное условие замкнутости’класса относительно операции добавления или изъятия несущественных переменных, и* доказал его, используя методы общей алгебры, а N. Pippenger в [54]' расширил область его применения до классов функций вида /: {0,., к — 1}п —> {0,., I — 1}, к, I ^ 2, частным случаем которых являются функции многозначной логики.

L. Hellerstein в статье [52] доказала существование классов, определяемых системой с бесконечным числом функциональных уравнений (например, таков класс линейных пороговых функций).

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

В теории функций многозначной логики одними из важнейших являются вопросы классификационного характера. Чаще всего классификации строятся на основе каких-либо операторов замыкания. Самая известная классификация этого типа — это классификация на основе операции суперпозиции. Для булевых функций она приводит к счетной решетке замкнутых классов [55, 56, 46, 20], но уже для функций трехзначной логики подобная классификация оказывается континуальной [47]. Естественным образом возникает вопрос о построении конечной (или хотя бы счетной) классификации для функций многозначной логики на основе более сильного, чем оператор суперпозиции, оператора замыкания. Например, в работах [17, 18, 35−37] изучается операция 5-замыкания, в работах [7, 14, 48] — операция параметрического замыкания, в работах [6, 26, 38, 39] — операции замыкания программного типа.

Идея операции й'-замыкания, где наряду с операцией суперпозиции разрешается применять операцию перехода к двойственным функциям относительно фиксированной группы подстановок, высказывалась несколькими авторами. В настоящее время существуют две версии построения 5-классификации множества функций &—значной логики при к ^ 3, представленные в работах С. С. Марченкова [17, 18] и Нгуена Ван Хоа [35−37], где, в частности, установлено, что множество классов в данной классификации конечно, хотя и зависит от к сверхэкспоненциальным образом.

Понятия параметрической выразимости и параметрического замыкания введены А. В. Кузнецовым в работе [14]. В этой же работе получены критерий параметрической выразимости в к-значной логике для всех к ^ 2 и конечное описание параметрически замкнутых классов булевых функций. Конечность множества параметрически замкнутых классов при к = 3 показана в работе А. Ф. Данильченко [7], а при к > 3 — в работе S. Burris, R. Willard [48]. Кроме того, в [7] построены все предполные классы в Р3.

В работах Ю. В. Голункова [6] и С. С. Марченкова [26] изучаются вопросы полноты функционально-предикатных систем с операциями замыкания программного типа. В работах В. А. Тайманова [39], и В:. Д. Соловьева-[38] исследуется семейство функциональных систем многозначной логики с операциями программного типа, каждая из которых определяется своим множеством предикатов. В работе [39] показано, что в зависимости от свойств указанных множеств предикатов мощность множества замкнутых классов может быть конечной, счетной или континуальной. В [38] рассматриваются примеры конечных описаний множества замкнутых классов для некоторых операций программного типа.

С. С. Марченков в работе [28] вводит в рассмотрение на основе идеи исчисления равенств операцию эквационального замыкания, порождающую конечную классификацию классов функциймногозначной логики, а в работе [24], новые операторы замыкания, определяются* на основе логико-функциональных языков различных типов.

О. С. Тарасова в работе [40] расширяет операцию суперпозиции добавлением к ней операции перестановки в нескольких модификациях, что позволяет получить, конечную, счетную и континуальную классификации множеств функций, многозначной логики. При этом автор стремится не сколько сжать решетку замкнутых классов, сколько облегчить нахождение результата применения этой операции к функциям.

В диссертации вводится новый оператор замыкания, основывающийся, на системах функциональных уравнений, — оператор SFE-замыкания (system of functional equations), который существенно отличается от известных сильных операторов замыкания как по способу задания, так и по порождаемым классификациям функций многозначных логик. По-видимому, оператор SFE-замыкания является наиболее сильным из известных операторов замыкания. В частности, в классе Р2 булевых функций образуется лишь два SFE-замкнутых класса: сам класс и класс S самодвойственных функций. л.

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

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

Заключение

.

На защиту выносятся следующие результаты:

1) построение системы функциональных уравнений с заранее заданным единственным решением из некоторого класса функций многозначной логики, в котором множество используемых функциональных констант зависит от этого класса функций;

2) построение системы функциональных уравнений с заранее заданным множеством решений, в котором набор используемых функциональных констант зависит от свойств этого множества функций;

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

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