Вестник Московского университета. Серия 1: Математика. Механика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Вестн. Моск. ун-та. Сер. 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.
Поступила в редакцию: 05.04.1996
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.722
Образец цитирования: Ю. В. Таранников, “О классе булевых функций, равномерно распределенных по шарам со степенью $1$”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 1997, № 5, 17–21
Цитирование в формате AMSBIB
\RBibitem{Tar97}
\by Ю.~В.~Таранников
\paper О классе булевых функций, равномерно распределенных по шарам со степенью $1$
\jour Вестн. Моск. ун-та. Сер.~1. Матем., мех.
\yr 1997
\issue 5
\pages 17--21
\mathnet{http://mi.mathnet.ru/vmumm1921}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1483287}
\zmath{https://zbmath.org/?q=an:0909.06010}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/vmumm1921
  • https://www.mathnet.ru/rus/vmumm/y1997/i5/p17
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Статистика просмотров:
    Страница аннотации:71
    PDF полного текста:26
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024