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

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

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

клас функцій, що зберігають константу 0:
$T_{0} = {f (x_{1}, \dots, x_{n}) : f (0, \dots, 0) = 0}$ .
клас функцій, що зберігають константу 1:
$T_{1} = {f (x_{1}, \dots, x_{n}) : f (1, \dots, 1) = 1}$ .
клас самодвоїстих функцій:
$S = {f (x_{1}, \dots, x_{n}) : f (\overline{x_{1}}, \dots, \overline{x_{n}}) = \overline{f (x_{1}, \dots, x_{n})}}$ .
клас монотоних функцій:
$M = {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})}$ .
клас лінійних функцій:
$L = {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}}$ .

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

Приклади

Приклади належності булевих функцій до класів.

	Хиба $⊥$	Істина $⊤$	Заперечення, NOT $\neg A$	Кон'юнкція, AND $A \land B$	Диз'юнкція, OR $A \lor B$	Виключна диз'юнкція, XOR $A \oplus B$	Еквівалентність, XNOR $A \leftrightarrow B$	Імплікація $A \to B$	Неімплікація $A \to̸ B$
$T_{0}$	•			•	•	•			•
$T_{1}$		•		•	•		•	•
$S$			•
$M$	•	•		•	•
$L$	•	•	•			•	•

Щоб вибрати функціонально повну систему функцій потрібно, щоб таблиця з їхніх стовпців в кожному рядку містила хоча б одну порожню клітинку.

Щоб вибрати базис для класу потрібно, щоб таблиця з їхніх стовпців в кожному рядку (крім рядка цього класу) містила хоча б одну порожню клітинку.

...

В багатозначній логіці ще немає повного опису передповних класів.