Математика
О классе булевых функций, равномерно распределенных по шарам со степенью $1$
Ю. В. Таранников
Аннотация:
Весом булевой функции
$f$ назовем величину
$W_f$, равную числу наборов, на которых функция
$f$ принимает
значение
$1$ (далее такие наборы будем называть
$1$-наборами). Шаром радиуса
$r$ с центром
$\tilde\alpha$ называется множество наборов, отстоящих от
$\tilde\alpha$ на расстояние, не большее
$r$. Весом функции
$f$ на шаре (или для краткости просто весом шара) назовем число
$1$-наборов функции
$f$, принадлежащих этому шару. Пусть
$l$ – целое неотрицательное число. Булеву функцию
$f(x_1,x_2,\dots,x_n)$ будем называть равномерно распределенной по шарам со степенью
$l$ (
$l$-РРШ-функцией), если модуль разности весов любых двух шаров одинакового радиуса не превосходит
$l$. В работе полностью описан класс
$1$-РРШ-функций, определена мощность этого класса и доказано, что любую
$1$-РРШ-функцию можно реализовать схемой из функциональных элементов с линейной относительно числа переменных сложностью. Основное содержание работы составляет следующая теорема.
Теорема. Если $n$-местная булева функция $f$ с весом $W_f\le2^{n-1}$ является 1-РРШ-функцией, то имеет место один из следующих 3-х случаев: 1)
$W_f\le2$; 2)
$n\le4$; 3)
$n=6$,
$W_f=4$.
Библиогр. 3.
УДК:
519.722 Поступила в редакцию: 05.04.1996