Аннотация:
Рассматривается определимость функций и отношений в языке FE функциональных уравнений счетнозначной логики. Доказано, что класс отношений, определимых функциональными уравнениями над множеством функций $\{0,x+1\}$, совпадает с классом $\Sigma_1^1$ аналитической иерархии Клини. Предложены два расширения языка FE, которые по выразительным возможностям эквивалентны языку FE с функциональными константами для всех однородных функций.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 13-01-00958.
Полный текст:
PDF файл (169 kB)