Том 2, номер 3, 1995 г., Стр. 18-23

УДК 519.71
Н. Ю. Золотых, В. Н. Шевченко
Расшифровка пороговых функций $k$-значной логики

Аннотация:
Рассматривается класс пороговых функций $k$-значной логики от $n$ переменных. Под расшифровкой функции из этого класса понимается процедура из последовательности вопросов о значении функции в точке, после завершения которой функция восстанавливается в остальных точках. Доказано, что при любом фиксированном $n$ существует алгоритм расшифровки любой пороговой функции $k$-значной логики, который использует не более $C_n\log^n(k+1)$ вопросов о значении функции в точке, где $C_n$ – константа, зависящая только от $n$.
Библиогр. 15.

Золотых Н. Ю. ¹
Шевченко В. Н. ¹
1. Нижегородский государственный университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603600 Нижний Новгород, Россия

Статья поступила 23 ноября 1994 г.