Теорема Поста

Существует метод проверки полноты системы, называемый теоремой Поста. Она основывается на выделении пяти классов Поста булевых функций:

Класс функций сохраняющих 0

,

Класс функций сохраняющих 1

,

Класс самодвойственных функций

,

Класс монотонных функций

, где подразумевается стандартный порядок булевой алгебры (при котором существуют и несравнимые элементы!),