Функциональная полнота

---

Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция (${\displaystyle \land }$), дизъюнкция (${\displaystyle \lor }$), отрицание (${\displaystyle \neg }$), импликация (${\displaystyle \to }$) и эквиваленция (${\displaystyle \leftrightarrow }$). Это множество операций является функционально полным. Но оно не является минимальной функционально полной системой, поскольку:

Таким образом ${\displaystyle \{\neg ,\land ,\lor \}}$ также является функционально полной системой. Но ${\displaystyle \lor }$ также может быть выражено (в соответствии с законом де Моргана) как:

${\displaystyle \land }$ также может быть определена через ${\displaystyle \lor }$ подобным образом:

Также ${\displaystyle \vee }$ может быть выражена через ${\displaystyle \rightarrow }$ следующим образом:

Итак ${\displaystyle \{\neg \}}$ и одна из ${\displaystyle \{\land ,\lor ,\rightarrow \}}$ является минимальной функционально полной системой.

Критерий Поста описывает необходимые и достаточные условия функциональной полноты множеств булевых функций. Был сформулирован американским математиком Эмилем Постом в 1941 году.

---