О связи функциональных систем полиномов и арифметических полиномов, представляющих системы булевых функций

Аннотация

Одной из основных областей математической кибернетики является теория функциональных систем. Функциональная система представляет собой пару (P, O), в которой P — носитель системы, а O — совокупность операций, заданных на P, т. е. функциональная система — это алгебра, элементами которой являются функции, а операции в этой алгебре соответствуют правилам построения функций друг из друга. Традиционными модельными объектами теории считаются функциональные системы с операцией суперпозиции (переименование и отождествление переменных, подстановка функций на места переменных другой функции). Исследована функциональная система полиномов с целыми коэффициентами. Рассмотрена связь функциональной системы полиномов с целыми коэффициентами с введенными В.Д. Малюгиным для выполнения параллельных логических вычислений арифметическими полиномами. Проанализированы линейные полиномы с целыми коэффициентами. Множество всех таких функций обозначено L(Z) и рассмотрено как подмножество в более обширном множестве P(Z) функций, представленных полиномами произвольной степени с целыми коэффициентами. На L(Z) и P(Z) заданы операции суперпозиции. Приведены арифметические полиномы, представляющие некоторые системы булевых функций. Установлено, что множество арифметических полиномов, представляющих некоторые системы булевых функций, не совпадают с P(Z), однако замыкание относительно операции суперпозиции множества арифметических полиномов, представляющих некоторые системы булевых функций, с P(Z) совпадает. Показано, что множество линейных арифметических полиномов, представляющих некоторые системы булевых функций, не совпадают с L(Z), однако замыкание относительно операции суперпозиции множества линейных арифметических полиномов, представляющих некоторые системы булевых функций, совпадает с L(Z).