Функциональная полнота
 | В статье не хватает ссылок на источники (см. также рекомендации по поиску). |
Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция ([math]\displaystyle{ \land }[/math]), дизъюнкция ([math]\displaystyle{ \lor }[/math]), отрицание ([math]\displaystyle{ \neg }[/math]), импликация ([math]\displaystyle{ \to }[/math]) и эквиваленция ([math]\displaystyle{ \leftrightarrow }[/math]). Это множество операций является функционально полным. Но оно не является минимальной функционально полной системой, поскольку:
- [math]\displaystyle{ A \to B = \neg A \lor B }[/math]
- [math]\displaystyle{ A \leftrightarrow B = (A \to B) \land (B \to A) }[/math]
Таким образом [math]\displaystyle{ \{\neg, \land, \lor\} }[/math] также является функционально полной системой. Но [math]\displaystyle{ \lor }[/math] также может быть выражено (в соответствии с законом де Моргана) как:
- [math]\displaystyle{ A \lor B = \neg(\neg A \land \neg B). }[/math]
[math]\displaystyle{ \land }[/math] также может быть определена через [math]\displaystyle{ \lor }[/math] подобным образом.
Также [math]\displaystyle{ \vee }[/math] может быть выражена через [math]\displaystyle{ \rightarrow }[/math] следующим образом:
- [math]\displaystyle{ \ A \vee B := (A \rightarrow B) \rightarrow B. }[/math]
Итак [math]\displaystyle{ \{\neg\} }[/math] и одна из [math]\displaystyle{ \{\land, \lor, \rightarrow\} }[/math] является минимальной функционально полной системой.
Критерий полноты
Критерий Поста описывает необходимые и достаточные условия функциональной полноты множеств булевых функций. Был сформулирован американским математиком Эмилем Постом в 1941 году.
Критерий:
- Множество булевых функций является функционально полным тогда и только тогда, когда оно не содержится полностью ни в одном из предполных классов.
Минимальные множества бинарных операций
- Множества из одного элемента
- [math]\displaystyle{ \{ | \} }[/math] (штрих Шеффера), [math]\displaystyle{ \{ \darr \} }[/math] (стрелка Пирса)
- Множества двух элементов
- [math]\displaystyle{ \{ \lor, \lnot \}, \{ \land, \lnot \}, \{ \to, \lnot \}, \{ \to, \bot \}, \{ \not\to, \top \}, \{ \to, \not\to \}, \{ \to, \not\leftrightarrow \}, \{ \not\to, \leftrightarrow \} }[/math]
- Множества трёх элементов
- [math]\displaystyle{ \{ \lor, \leftrightarrow, \not\leftrightarrow \}, \{ \lor, \not\leftrightarrow, \top \}, \{ \land, \leftrightarrow, \bot \}, \{ \land, \leftrightarrow, \not\leftrightarrow \}, \{ \land, \not\leftrightarrow, \top \}, \{ \lor, \leftrightarrow, \bot \} }[/math].
То же в другой нотации:
- [math]\displaystyle{ \bigl\langle \lor, \odot, \oplus \bigr\rangle }[/math], [math]\displaystyle{ \bigl\langle \lor, \oplus, 1 \bigr\rangle }[/math], [math]\displaystyle{ \bigl\langle \wedge, \odot, 0 \bigr\rangle }[/math], [math]\displaystyle{ \bigl\langle \wedge, \odot, \oplus \bigr\rangle }[/math], [math]\displaystyle{ \bigl\langle \wedge, \oplus, 1 \bigr\rangle }[/math] (см. алгебра Жегалкина), [math]\displaystyle{ \bigl\langle \lor, \odot, 0 \bigr\rangle }[/math] (инверсный к предыдущему).