Том 22, номер 2, 2015 г., Стр. 49−62

УДК 519.716
С. С. Марченков
О сложности решения систем функциональных  уравнений счётнозначной логики

Аннотация:
Предложена процедура построения всех решений произвольной системы функциональных уравнений счётнозначной логики. На основе этой процедуры для систем уравнений, содержащих только тернарный дискриминатор p, указаны решения, принадлежащие классу $\Sigma_2$ арифметической иерархии Клини − Мостовского. Доказано, что для данных систем уравнений компоненты решения могут быть произвольными функциями из класса $\Sigma^1_1$−аналитической иерархии Клини.

Ключевые слова: система функциональных уравнений, функция счётнозначной логики.

DOI: 10.17377/daio.2015.22.460

Марченков Сергей Серафимович ¹
1. Московский гос. университет
Ленинские горы, 1, 119991 Москва, Россия
e-mail: ssmarchen@yandex.ru

Статья поступила 2 сентября 2014 г.
Исправленный вариант — 25 января 2015 г.

Литература

[1] Марченков С. С. Однородные алгебры // Пробл. кибернетики. 1982. Вып. 39. С. 85–106.

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

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

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

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

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

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

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

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

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