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

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

$A\to B=\neg A\lor B$

$A\leftrightarrow B=(A\to B)\land (B\to A)$

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

$A\lor B=\neg (\neg A\land \neg B)$

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

$A\land B=\neg (\neg A\lor \neg B)$

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

$\ A\vee B=(A\rightarrow B)\rightarrow B$

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

Критерий полноты

Основная статья: Критерий Поста

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

Критерий:

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

Минимальные множества бинарных операций

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

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

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

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

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

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

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

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

См. также

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