Аннотация:
Рассматриваются классы булевых функций от $n$ переменных, имеющих короткое (по сравнению с $2^n$)
представление. Подсчитаны мощности этих классов, приведены тесты на принадлежность функции классам и алгоритм доопределения частично заданной булевой функции до функции ограниченной степени.
Ключевые слова:существенная зависимость функции от переменной, степень булевой функции, алгебраическая нормальная форма.
Полный текст:
PDF файл (700 kB)