On the recognition problem for algebraic threshold functions.pdf Интерес к алгебраическим булевым пороговым функциям обуславливается простотой их задания, а также тем, что класс алгебраических пороговых функций содержит как собственно пороговые (или линейные пороговые) булевы функции, так и линейные булевы функции. Впервые понятие и свойства алгебраических пороговых функций (булевых и многозначных) введено в [1]. Несмотря на то, что понятие алгебраической булевой пороговой функции близко к понятию булевой пороговой функции, проблема распознавания для алгебраических булевых пороговых функций пока не имеет таких ясных способов решения, которые известны для булевых пороговых функций [2]. В работе доказано существование переборного алгоритма путем нахождения верхних оценок абсолютных значений модуля и коэффициентов линейной формы. Будем использовать следующие обозначения: Qk = {0,1,... ,k - 1}; rm(a) -функция взятия остатка при делении целого числа a на m; Fk (n) -множество всех k-значных функций от n переменных; Tk (n) - класс всех k-значных пороговых функций от n переменных; ATk (n) - класс всех k-значных алгебраических пороговых функций от n переменных; Lk (n) -множество всех линейных функций k-значной логики от n переменных вида c0 + c1x1 + c2x2 + ... + cnxn (mod k). Определение 1. Функцию f : ^П -> П2 назовем алгебраической булевой пороговой (а.б.п.ф.), если существуют ш = (ш0,ш1,... ,шп) Е Zn+1, в Е Z, m Е N\\{1}, такие, что f (Х1, . . . ,Хп) = 0 ^ Гт(шо + Ш1Х1 + Ш2Х2 + ... + ШпХп)

Скачать электронную версию публикации