Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция ( ${\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 }}$ (инверсный к предыдущему).

См. также

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