Теоретическая часть. Функция , полином Жегалкина которой имеет вид , принадлежит классу линейных функций L

Функция , полином Жегалкина которой имеет вид , принадлежит классу линейных функций L: . Если для двух кортежей длины n из нулей и единиц и выполнены условия , …, , то говорят, что . При невыполнении этих условий кортежи и несравнимы. Кортежи разной длины не сравнивают.

Функция называется монотонной, если для всех корежей и из условия следует, что , монотонная функция принадлежит классу монотонных функций M: .

Функция принадлежит классу функций, сохраняющих константу 0, если : .

Функция принадлежит классу функций, сохраняющих константу 1 если : .

Функция принадлежит классу самодвойственных функций, еслидля всех кортежей выполняется условие : .

Система булевых функций называется полной, если любая булева функция является суперпозицией ((композицией) функций этой системы. Теорема Поста: система булевых функций является полной, если она целиком не принадлежит ни одному классу , , , , .