Оценка количества классов $\tau$-$Inf$-эквивалентности для пороговых функций

И. В. Грибушин

Московский государственный университет имени М. В. Ломоносова

Аннотация: В работе исследуются относительные влияния переменных булевой функции. Множество булевых функций разбивается на классы $\tau$-$Inf$-эквивалентности в зависимости от максимального относительного влияния переменных. Приводятся нижняя и верхняя оценки количества классов $\tau$-$Inf$-эквивалентности для пороговых функций. Они равны $2^n/2$ и $n2^{2n}$.

Ключевые слова: пороговые функции, влияние переменных булевой функции, относительное влияние переменных булевой функции, классы $\tau$-$Inf$-эквивалентности.