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

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

${\displaystyle A\to B=\neg A\lor B}$

${\displaystyle A\leftrightarrow B=(A\to B)\land (B\to A)}$

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

${\displaystyle A\lor B=\neg (\neg A\land \neg B)}$

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

${\displaystyle A\land B=\neg (\neg A\lor \neg B)}$

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

${\displaystyle \ A\vee B=(A\rightarrow B)\rightarrow B}$

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

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

Критерий:

Множество булевых функций является функционально полным тогда и только тогда, когда оно не содержится полностью ни в одном из предполных классов.

Множества из одного элемента

${\displaystyle \{|\}}$ (штрих Шеффера), ${\displaystyle \{\downarrow \}}$ (стрелка Пирса)

Множества двух элементов

${\displaystyle \{\lor ,\lnot \},\{\land ,\lnot \},\{\to ,\lnot \},\{\to ,\bot \},\{\not \to ,\top \},\{\to ,\not \to \},\{\to ,\not \leftrightarrow \},\{\not \to ,\leftrightarrow \}}$

Множества трёх элементов

${\displaystyle \{\lor ,\leftrightarrow ,\not \leftrightarrow \},\{\lor ,\not \leftrightarrow ,\top \},\{\land ,\leftrightarrow ,\bot \},\{\land ,\leftrightarrow ,\not \leftrightarrow \},\{\land ,\not \leftrightarrow ,\top \},\{\lor ,\leftrightarrow ,\bot \}}$.

То же в другой нотации:

${\displaystyle {\bigl \langle }\lor ,\odot ,\oplus {\bigr \rangle }}$, ${\displaystyle {\bigl \langle }\lor ,\oplus ,1{\bigr \rangle }}$, ${\displaystyle {\bigl \langle }\wedge ,\odot ,0{\bigr \rangle }}$, ${\displaystyle {\bigl \langle }\wedge ,\odot ,\oplus {\bigr \rangle }}$, ${\displaystyle {\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }}$ (см. алгебра Жегалкина), ${\displaystyle {\bigl \langle }\lor ,\odot ,0{\bigr \rangle }}$ (инверсный к предыдущему).

• Замкнутые классы булевых функций