Аннотация:В книге исследуются функциональные уравнения для классов булевых функций, функций многозначной логики, функций счётнозначной логики и функций автоматного типа. Основная решаемая проблема - определимость множеств функций системами функциональных уравнений над произвольными множествами функций. В главах 1 и 2 эта проблема полностью решена для булевых функций и функций многозначной логики. В главе 3 для функций счётнозначной логики в терминах аналитической иерархии Клини охарактеризован класс всех отношений (на декартовых произведениях множеств функций), которые определимы системами функциональных уравнений с функциональными константами 0 и x+1. Установлено, что выразительные возможности данного языка функциональных уравнений близки к выразительным возможностям языка функциональных уравнений, содержащего нетривиальные однородные функции. В главе 4 для функциональных уравнений автоматного типа получена нижняя оценка решения проблемы выполнимости для уравнений, содержащих простейшие функции 1 и t+1. Показано, что в более сложном случае с линейными функциями 2t,3t,5t данная проблема алгоритмически неразрешима.
Для научных сотрудников, аспирантов и преподавателей высшей школы, специализирующихся в области дискретной математики.