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