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

Вводится понятие характеристического полинома булевой функции, имеющего заданную поляризацию переменных, и рассматривается метод представления булевой функции полиномом Рида–Маллера (каноническим поляризованным полиномом) с помощью характеристического полинома этой функции.
Доказывается, что значения характеристического полинома совпадают с соответствующими коэффициентами полинома Рида–Маллера, приводится линейный алгоритм нахождения коэффициентов полинома Рида–Маллера.
Отдельно рассматриваются положительно поляризованные характеристические полиномы и задачи, связанные с ними, включая проверку принадлежности булевой функции классу линейных функций.
Приведены примеры применения характеристических полиномов к нахождению полиномов Рида–Маллера, доопределению частичной булевой функции до линейной и проверке булевой функции на линейность.