О критерии полноты системы функций

Пусть задана система функций , как определить её полноту или не полноту. Конечно, можно построить генератор всех возможных подстановок и определять, таблица какой функции реализована. Когда подстановки (различные формулы) будут повторяться, можно проверить на полноту список порождённых таблиц.

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

В 1942 г. Пост выделил 5 классов функций принадлежность (или не принадлежность) к ним всех определяла полноту набора функций F. Каждый класс Поста был замкнутым относительно операции подстановки, т.е. система функций, обладающая свойством класса, при помощи подстановок порождала функции, имеющие это свойство, и только их. Таким образом класс являлся «ловушкой» для функций, обладающих характерным свойством. Например, если полная системасостоит из единственной функции, то она должна не принадлежать (не иметь свойств) ни к одному из классов Поста. Иначе операция подстановки не могла бы породить все функций. Порождённые функции остались бы в «ловушке» и не «выскочили» бы за пределы множества функций, обладающих уникальным свойством. Таким образом, чтобы набор был полным, в нём должны быть функции, не принадлежащие к классам Поста.