Передповний клас функцій алгебри логіки (клас Поста) — замкнений клас функцій алгебри логіки, замикання об'єднання цього класу з довільною функцією алгебри логіки (яка йому не належить) утворює повний клас функцій алгебри логіки — .
Всього є 5 класів: клас функцій, що зберігають константу 0:. клас функцій, що зберігають константу 1:. клас самодвоїстих функцій:. клас монотоних функцій:. клас лінійних функцій:.
Довільний замкнутий клас, відмінний від , повністю міститься хоча б в одному передповному класі.
Приклади Приклади належності булевих функцій до класів. Хиба Істина Заперечення, NOT Кон'юнкція, AND Диз'юнкція, OR Виключна диз'юнкція, XOR Еквівалентність, XNOR Імплікація Неімплікація Штрих Шефера, NAND Стрілка Пірса, NOR • • • • • • • • • • • • • • • • • • • • Щоб вибрати функціонально повну систему функцій потрібно, щоб таблиця з їхніх стовпців в кожному рядку містила хоча б одну порожню клітинку.
Щоб вибрати базис для класу потрібно, щоб таблиця з їхніх стовпців в кожному рядку (крім рядка цього класу) містила хоча б одну порожню клітинку.
...
В багатозначній логіці ще немає повного опису передповних класів.
Дивись також Ґратка Поста
Література