Теорема о предполных классах

Определение: Замкнутый класс функций $K$ из $P\_2$ предполон, если класс $K$ не является полным, но для любой функции $f$ не из $K$ система $k\vee \ { f\ }$ полна.

Теорема: Следующие замкнутые классы функций предполны:

1. Класс $T\_0$, не сохраняющий константу $0$.

2. Класс $T\_1$, не сохраняющий константу $1$.

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

4. Класс $L$ линейных функций.

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

Теорема{ перефразировка теоремы Поста в терминах предполных классов } : Система функций $F$ полна $\Longleftrightarrow$ когда $F$ не содержится целиком ни в одном из пяти предполных классов $T\_0, T\_1, M, L, S$.

**Замечание:**Пост описал все замкнутые классы алгебры логики и все их базисы, которые оказались конечными. Число замкнутых классов счетно и множество замкнутых классов образует решетку относительно включения множеств. Эта решетка имеет наибольший класс $P\_2$ { он же максимум } и три минимальных элемента $0\_1 = [ { x } ], 0\_2 = [ { 1 } ], 0\_3 = [ { 1 } ]$. Наименьшего элемента решетка не имеет.