Теорема 1 о функциональной полноте

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

Лемма 3.

Если функция – несамодвойственна, то подстановкой отрицания из нее можно получить константы 0 и 1.

Теорема 2 о функциональной полноте (теорема Поста).

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

хотя бы одну немонотонную,

хотя бы одну нелинейную,

хотя бы одну несамодвойственную,

хотя бы одну не сохраняющую 0,

хотя бы одну не сохраняющую 1 функцию.