Теорема Поста

Теорема Поста устанавливает необходимые и достаточные условия полноты системы булевых функций.

(Post E.L. The two-valued interactive systems of mathematical logic. – Annals of Math. Studies, v. 5, Princeton Univ. Press. Princeton-London, 1941).

Требования : P₂ класс - замкнутый, то Базис - конечный.

Теорема (Пост). Каждый замкнутый класс из P₂ имеет конечный базис.

Теорема (Пост). Мощность множества замкнутых классов в P₂ - счетная.

Хотя вторая теорема следует из первой, тем не менее, в доказательстве Поста сначала устанавливается второй факт, а затем - первый.

Теорема (Пост). Система булевых функций F полна тогда и только тогда, когда она содержит

хотя бы одну функцию, не сохраняющую нуль,

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

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

хотя бы одну немонотонную функцию,

хотя бы одну нелинейную функцию: