RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2024, том 36, выпуск 3, страницы 80–91 (Mi dm1828)

Об алгебраических и комбинаторных свойствах параметров критерия распространения для булевых функций

Г. А. Исаев

Новосибирский государственный технический университет

Аннотация: В работе исследуются алгебраические и комбинаторные свойства критерия распространения для булевых функций. Доказаны необходимые и достаточные условия для мощности множества векторов, удовлетворяющих критерию распространения для булевых функций, в терминах числа нулей матрицы специального вида, ассоциированной с этой функцией. Изучен критерий распространения для булевых функций, носитель которых представляет собой подпространство пространства $V_n$ размерности $n-2$. Найдены точные соотношения для мощности множества векторов, удовлетворяющих критерию распространения для функции, равной XOR двух булевых функций от не пересекающихся наборов переменных, а также для булевых функций с нетривиальным пространством линейных структур (трансляторов).

Ключевые слова: булева функция, критерий распространения, спектр Уолша, автокорреляционная функция, матрица Адамара, граф Кэли, матрица смежности, линейная структура, бент-функция.

УДК: 519.716.322+519.719.2

Статья поступила: 05.05.2024

DOI: 10.4213/dm1828



© МИАН, 2025