Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция ( ∧ {displaystyle land } ), дизъюнкция ( ∨ {displaystyle lor } ), отрицание ( ¬ {displaystyle eg } ), импликация ( → {displaystyle o } ) и эквиваленция ( ↔ {displaystyle leftrightarrow } ). Это множество операций является функционально полным. Но оно не является минимальной функционально полной системой, поскольку:
A → B = ¬ A ∨ B {displaystyle A o B= eg Alor B} A ↔ B = ( A → B ) ∧ ( B → A ) {displaystyle Aleftrightarrow B=(A o B)land (B o A)}Таким образом { ¬ , ∧ , ∨ } {displaystyle { eg ,land ,lor }} также является функционально полной системой. Но ∨ {displaystyle lor } также может быть выражено (в соответствии с законом де Моргана) как:
A ∨ B = ¬ ( ¬ A ∧ ¬ B ) . {displaystyle Alor B= eg ( eg Aland eg B).}∧ {displaystyle land } также может быть определена через ∨ {displaystyle lor } подобным образом.
Также ∨ {displaystyle vee } может быть выражена через → {displaystyle ightarrow } следующим образом:
A ∨ B := ( A → B ) → B . {displaystyle Avee B:=(A ightarrow B) ightarrow B.}Итак { ¬ } {displaystyle { eg }} и одна из { ∧ , ∨ , → } {displaystyle {land ,lor , ightarrow }} является минимальной функционально полной системой.
Критерий полноты
Критерий Поста описывает необходимые и достаточные условия функциональной полноты множеств булевых функций. Был сформулирован американским математиком Эмилем Постом в 1941 году.
Критерий:
Множество булевых функций является функционально полным тогда и только тогда, когда оно не содержится полностью ни в одном из предполных классов.