RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 1997, номер 5, страницы 17–21 (Mi vmumm1921)

Математика

О классе булевых функций, равномерно распределенных по шарам со степенью $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



Реферативные базы данных:


© МИАН, 2024