Об аналоге теоремы Слупецкого для полиномиальных функций

Аннотация

Функциональные системы являются одним из основных объектов дискретной математики и математической кибернетики. Содержательная связь функциональных систем с реальными кибернетическими моделями управляющих систем, с одной стороны, определяет серию существенных требований, которые накладываются на функциональные системы, а с другой стороны, порождает класс важных задач, имеющих как теоретическое, так и прикладное значение. Проблематика теории функциональных систем обширна. К числу основных относятся проблемы о полноте и относительной полноте, о выразимости, синтезе и анализе и другие. В настоящей статье рассмотрены функциональные системы полиномиальных функций: • с натуральными коэффициентами, где значения как аргументов, так и самих функций, принадлежат множеству натуральных чисел; • с целыми коэффициентами, где значения как аргументов, так и самих функций, принадлежат множеству целых чисел; • с рациональными коэффициентами, где значения как аргументов, так и самих функций, принадлежат множеству рациональных чисел. В качестве множества операций во всех функциональных системах взяты операции суперпозиции (перестановка переменных, переименование переменных без отождествления, отождествление переменных, введение фиктивной переменной, удаление фиктивной переменной и подстановка одной функции в другую), и для этих систем исследована проблема относительной полноты. Представлен алгоритмический подход данной проблемы (аналог теоремы Слупецкого) для указанных функциональных систем. В частности, доказано, что поставленная задача имеет положительный ответ только для функциональной системы с натуральными коэффициентами, а для двух других ответ отрицательный.