|
Вестник Московского университета. Серия 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.
Поступила в редакцию: 05.04.1996
Образец цитирования:
Ю. В. Таранников, “О классе булевых функций, равномерно распределенных по шарам со степенью $1$”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 1997, № 5, 17–21
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm1921 https://www.mathnet.ru/rus/vmumm/y1997/i5/p17
|
Статистика просмотров: |
Страница аннотации: | 71 | PDF полного текста: | 26 |
|