Полнота множества функций. Теорема Поста

Функциональная полнота — множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Логика обычно использует такой набор операций: конъюнкция (), дизъюнкция (), отрицание (), импликация () и эквиваленция (). Это множество операций является функционально полным.

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

Все остальные логические функции можно составить из набора логических функций, среди которых есть:

• хотя бы одна не линейная;
• хотя бы одна не монотонная;
• хотя бы одна не самодвойственная;
• хотя бы одна не сохраняющая 0;
• хотя бы одна не сохраняющая 1.