Базис Жегалкина.

Примерю Рассмотрим систему . Она является полной, так как любая функция из стандартного базиса выражается через функции из N:

Эта полная система называется базисом Жегалкина.

Любая булева функция может быть представлена в этом базисе в форме многочлена Жегалкина по степеням неизвестных.

ZB

Пример. Рассмотрим систему булевых функций, состоящую из одной функции Шеффера . Она является тоже полной, так как любая функция из стандартного базиса выражается через функции из N:

Класс булевых функций называется замкнутым, если всякая суперпозиция функций этого класса будет функцией из этого класса.