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

• Федорова, Валентина Сергеевна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Федорова, Валентина Сергеевна

Введение

Глава 1. Решения систем функциональных уравнений многозначной логики

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

1.2 Общие свойства решений систем функциональных уравнений

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

Глава 2. Оператор SFE-замыкания

2.1 Некоторые свойства SFE-замыкания.

2.2 SFE-замкнутые классы трехзначной логики.

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

3.1 Верхняя оценка сложности проблемы выполнимости.

3.2 Нижняя оценка сложности проблемы выполнимости.

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

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

Одно из простейших функциональных уравнений — это уравнение Коши 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) =<p{xi V уи . ,хп V уп),

Ряд результатов о функциональных уравнениях был получен зарубежными учеными за последнее десятилетие. О. 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) верхняя и нижняя оценки сложности проблемы выполнимости системы функциональных булевых уравнений, невозможность ее решения методом, который существенно проще непосредственного перебора.

Список литературы диссертационного исследования кандидат физико-математических наук Федорова, Валентина Сергеевна, 2010 год

1. Ахо А. В., Сети Р., Ульман Д. Д. Компиляторы: принципы, технологии и инструменты. М.: Вильяме, 2003.

2. Балюк А. С., Винокуров С. Ф., Гайдуков А. И., Зубков О. В., Кириченко К. Д., Пантелеев В. И., Перязев Н. А., Перязева Ю. Н. Избранные вопросы теории булевых функций. М.: Физматлит, 2001.

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

4. Боднарчук В. Г., Калужнин JI. А., Котов В. Н., Ромов Б. А. Теория Галуа для алгебр Поста // Кибернетика. 1969. № 3, с. 1-10. № 5, с. 1-9.

5. Гаврилов Г. П. Индуктивные представления булевых функций и конечная порождаемостъ классов Поста j j Алгебра и логика. 1984. Т. 23, вып. 1. С. 88-99.

6. Голунков Ю. В. Полнота систем функций в операторных алгоритмах, реализующих функции k-значной логики // Вероятностные методы и кибернетика. 1980. К9- 17. С. 23-34.

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

8. Катериночкина Н. Н. Об эквивалентности некоторых вычислительных устройств // Кибернетика. 1970. № 5. С. 27-31.

9. Клини С. К. Введение в метаматематику. М.: ИЛ, 1957.

10. Кобринский Н. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. М.: Физматгиз, 1962.

11. Кон П. Универсальная алгебра. М.: Мир, 1968.

12. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1986.

13. Кудрявцев В. Б., Подколзин А. С., Болотов А. А. Основы теории однородных структур. М.: Наука, 1990.

14. Кузнецов А. В. О средствах для обнаружения невыводимости и невыразимости. В книге „Логический вывод". М.: Наука, 1979. С. 5-33.

15. Курода С. И. Классы языков и линейно ограниченные автоматы // Кибернетический сборник, вып. 9. М.: Мир, 1972. С. 36-51.

16. Ложкин С. А. Лекции по основам кибернетики. М.: Изд-во факультета Вычислительной математики и кибернетики МГУ, 2004.

17. Марченков С. С. S-классификация функций многозначной логики j j Дискретная математика. 1997. Т. 9, № 3. С. 125-152.

18. Марченков С. С. S-классификация функций трехзначной логики. М.: Физматлит, 2001.

19. Марченков С. С. Дискриминаторные классы трехзначной логики j j Математические вопросы кибернетики. Вып. 12. 2003. С. 15-26.

20. Марченков С. С. Замкнутые классы булевых функций. М.: Физматлит, 2000.

21. Марченков С. С. Итерация булевых (п, п)—операторов // Вестник МГУ. Серия 15. Вычислительная математика и кибернетика. 2006. № 4. С. 3641.

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

23. Марченков С. С. Конечная порождаемость замкнутых классов булевых функций // Дискретный анализ и исследование операций. Серия 1. 2005. Т. 12, № 1. С. 101-118.

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

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

26. Марченков С. С. Операторы замыкания с разветвлением по предикату // Вестник МГУ. Серия 1. Математика. Механика. 2003. № 6. С. 37-39.

27. Марченков С. С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004.

28. Марченков С. С. Эквациональное замыкание // Дискретная математика. 2005. Т. 17, вып. 2. С. 117-126.

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

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

31. Марченков С1 С., Федорова В. С. Решения систем функциональных уравнений многозначной логики // Вестник МГУ: Серия 15. Вычислительная математика и кибернетика: 2009. № 4; С. 29^33.

32. Мучник А. А. Добавление переводчика к статьям „Об альтернировании, I- II" // Кибернетический сборник (новая серия) ■ вып. 20. М.: Мир, 1983. С. 141-158.

33. Нгуен Ван Хоа О замкнутых классах k-значной логики, самодвойственных относительно транзитивных групп // Дискретная математика. 1996. Т. 8,.№ 1. С. 129-156.

34. Нгуен Ван Хоа О семействах замкнутых классов k-значной логики, сохраняемых всеми автоморфизмами // Дискретная математика. 1993. Т. 5, № 4. С. 87-108.

35. Нгуен Ван Хоа О структуре самодвойственных замкнутых классов трехзначной логики Рз / / Дискретная математика. 1992. Т. 4, № 4. С. 8295.

36. Соловьев В. Д. Замкнутые классы в k-значной логике с операцией разветвления по предикатам // Дискретная математика. 1990. Т. 2, № 4. С. 19-25.

37. Тайманов В. А. О функциональных системах k-значной логики с операциями программного типа // Доклады АН СССР. 1983. Т. 268, № 6. С. 1307-1310.

38. Тарасова О. С. Классы k-значной логики, замкнутые относительно расширенной операции суперпозиции // Вестник МГУ. Серия 1. Математика. Механика. 2001. № 6. С. 54-57.

39. Угольников А. Б. О замкнутых классах Поста // Известия вузов. Математика. 1988. Вып. 7. С. 79-88.

40. Федорова В. С. Сложность проблемы выполнимости для одного языка с функциональными булевыми переменными J/ Материалы VI молодежной научной школы по дискретной математике и ее приложениям

41. Москва, 16-21 апреля 2007 г.), часть 3. Изд-во ИПМ РАН, Москва, 2007. С. 17-23. . • ' •, ■ ■■ ' ' ,

42. Федорова В. С. SFE-замкнутые классы трехзначной логики // Сборник статей молодых ученых факультета ВМК МГУ, 2010, вып. 7. Москва, издательский отдел факультета Вычислительной математики и кибернетики МГУ имени М. В. Ломоносова.

43. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.

44. Яблонский С. В., Гаврилов R П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.

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

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

47. Ganter В., Plonka J., Werner H. Homogeneous algebras are simple // Fundi Math. 1973. V. 79. № 3. P. 217-220.

48. Hellerstein L. Ongeneralized constraints and certificates / / Rutcor Reserch Report 26 98. Rutcor, Rutgers University, 1998.53.? Kuntzman J. Algebre de Boole. Paris: Dunod, 1965.

49. Pippenger N. Galois theory for minors of finite functions // Discrete Mathematics. 2002. V. 254. P. 405-419.

50. Post E. L. Introduction to a general theory of elementary propositions j j Amer. J. Math. 1921. V. 43. P. 163-185.

51. Post E. L. The two-valued iterative systems of mathematical logic. Princeton Univ. Press, Princeton, NJ. 1941.

52. Rosenberg I. G. U&er die funktionale Vollsf&ndigkeit in den mehrwertigen Logiken // Rozpravy Ceskoslovenske Akad. Ved. Rada Math. Prir. Ved.

53. Praha. 1970. V. 80. S. 3 93.