Передповний клас функцій алгебри логіки

Передповний клас функцій алгебри логіки (клас Поста) — замкнений клас функцій алгебри логіки, замикання об'єднання цього класу з довільною функцією алгебри логіки (яка йому не належить) утворює повний клас функцій алгебри логіки — ${\displaystyle P_{2}}$.

Всього є 5 класів:

• клас функцій, що зберігають константу 0:
  ${\displaystyle T_{0}=\left\{f(x_{1},\dots ,x_{n}):\ f(0,\dots ,0)=0\right\}}$.
• клас функцій, що зберігають константу 1:
  ${\displaystyle T_{1}=\left\{f(x_{1},\dots ,x_{n}):\ f(1,\dots ,1)=1\right\}}$.
• клас самодвоїстих функцій:
  ${\displaystyle S=\left\{f(x_{1},\dots ,x_{n}):\ f({\overline {x_{1}}},\dots ,{\overline {x_{n}}})={\overline {f(x_{1},\dots ,x_{n})}}\right\}}$.
• клас монотоних функцій:
  ${\displaystyle M=\left\{f(x_{1},\dots ,x_{n}):\ \forall i(a_{i}\leq b_{i})\Rightarrow f(a_{1},\dots ,a_{n})\leq f(b_{1},\dots ,b_{n})\right\}}$.
• клас лінійних функцій:
  ${\displaystyle L=\left\{f(x_{1},\dots ,x_{n}):\ f(x_{1},\dots ,x_{n})=a_{0}\oplus a_{1}x_{1}\oplus \dots \oplus a_{n}x_{n},\;a_{i}\in \{0,1\}\right\}}$.

Довільний замкнутий клас, відмінний від ${\displaystyle P_{2}}$, повністю міститься хоча б в одному передповному класі.