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

• Автор: Федорова, Валентина Сергеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 83 с.

Оглавление
Введение
Глава 1. Решения систем функциональных уравнений многозначной логики
1.1 Основные понятия и терминология
1.2 Общие свойства решений систем функциональных уравнений .
1.3 Системы функциональных булевых уравнений
Глава 2. Оператор ЭГЕ-замыкания
2.1 Некоторые свойства БРЕ-замыкания
2.2 ЭРЕ-замкнутые классы трехзначной логики
Глава 3. Сложность проблемы выполнимости системы функциональных булевых уравнений
3.1 Верхняя оценка сложности проблемы выполнимости
3.2 Нижняя оценка сложности проблемы выполнимости
Заключение
Список литературы

Введение
В математике функциональным уравнением называется уравнение, выражающее связь между значением функции в одной точке с ее значениями в других точках. Это весьма общий класс уравнений, в которых искомой является некоторая функция, а не переменная. Функциональными уравнениями, по существу, являются дифференциальные уравнения, интегральные уравнения, уравнения в конечных разностях, однако само название „функциональные уравнения“ обычно не относят к уравнениям этих типов. Под функциональными уравнениями в узком смысле слова понимают уравнения, в которых искомые функции связаны с известными функциями одного или нескольких переменных при помощи операции образования сложной функции. Решения функционального уравнения могут быть как конкретными функциями, так и классами функций, зависящими от произвольных параметров или произвольных функций.
Одно из простейших функциональных уравнений — это уравнение Коши /(ж + у) = /(ж) + /(у). Его непрерывные решения имеют вид /(ж) — С • ж, где С — произвольная константа.
Также одним из видов функциональных уравнений является рекуррентное соотношение, содержащее неизвестную функцию от целочисленных переменных и оператор сдвига.
Даже свойства коммутативности и ассоциативности суть не что иное как функциональные уравнения. В привычной всем записи эти законы выглядят

следующим образом:
а о b = Ъ о а, (а о Ъ) о с — а о [Ь о с),
где о — символ некоторой бинарной операции. Но если представить эту операцию в эквивалентном виде а о Ъ = /(ы, 6), то получится как раз то, что обычно называют функциональным уравнением:
Да, Ь) = f(b,a), /(/(а, 6), с) = f(aj(b,c)).
Этот пример показывает, что функциональные уравнения можно также рассматривать как выражение некоторого свойства, характеризующего то или иное множество функций. Так, для периодических с периодом 7Г функций — это /(ж + 7г) = /(ж), а для четных функций — /(ж) — /(—ж).
В теории аналитических функций функциональные уравнения часто применяются для введения новых классов функций. Например, автоморфные функции описываются функциональными уравнениями вида f(saz) — f(z), где sa есть элемент некоторой счетной подгруппы группы дробно-линейных преобразований комплексной плоскости, двоякопериодические функции — парой функциональных уравнений f(z + а) — f(z) и j(z + Ь) = f(z).
Если функция известна в некоторой области, то знание для нее функционального уравнения позволяет расширить область определения этой функции. Этот прием часто применяют для аналитического продолжения функций комплексного переменного. Например, используя функциональное уравнение T{z + 1) = zF(z) и имея значения Гамма-функции Г (л) в полосе О < Re < 1, можно продолжить ее на всю ПЛОСКОСТЬ Z.
Постановка задач математической физики заключается в построении математических моделей, описывающих основные закономерности изучаемого класса физических явлений. Такая постановка состоит в выводе функциональных уравнений (дифференциальных, интегральных, интегро-

быть получены как единственное решение некоторой системы функциональных уравнений над <3- ЭРЕ-замыкание множества <3 обозначим через ЗРЕ[<3]. Множество <2 назовем БРЕ-замкнутым, если <3 = ЭРЕ[<3]. Понятия ЭРЕ-полпоты, ЭРЕ-предполноты и ЭРЕ-порождающей системы вводятся по аналогии с соответствующими понятиями для операции суперпозиции [45].
Из введенного определения следует, что ЭРЕ-замыкание удовлетворяет трем аксиомам замыкания [11]:
1) д с зре[<з],
2) если <3 С Д, то ЭРЕ[<3] С ЭРЕ[Д],
3) ЭРЕ [ЭРЕ [<3]] = ЗРЕ[<3],
то есть действительно является замыканием.
Для любого множества <3 (в том числе и для <3 = 0) множеству ЭРЕ[<3] принадлежат все селекторные функции, также ЭРЕ-замыкание множества <3 замкнуто относительно операции суперпозиции согласно утверждению 1. Таким образом, любое ЭРЕ-замкнутое множество является клоном.
Докажем БРЕ-полноту некоторых систем функций £-значной логики. Для большей наглядности будем опускать фигурные скобки, в которых перечислены функции, внутри квадратных скобок БРЕ-замыкания.
Пусть для г 6 Ек
II, если х — г,
Мх) = <
I 0 в остальных случаях.
Теорема 7. Справедливы следующие равенства:
1. 8РЕ[0,1,..., Л: — 1] = ^ (Л >2).
2. Для любого в Е Е% имеет место ЭРЕ[0,1,... ,5 — 1,5+1,..., £—1] — Р/с
Ок > з).