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

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

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

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

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

Критерий полноты[править]

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

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

Критерий:

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

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

множества из одного элемента: {NAND}, {NOR}.

множества двух элементов: $\{ \lor, \lnot \}, \{ \land, \lnot \}, \{ \to, \lnot \}, \{ \to, \bot \}, \{ \not\to, \top \}, \{ \to, \not\to \}, \{ \to, \not\leftrightarrow \}, \{ \not\to, \leftrightarrow \}$

множества трёх элементов: { $\lor$ , $\leftrightarrow$ , $\bot$ }, { $\lor$ , $\leftrightarrow$ , $\not\leftrightarrow$ }, { $\lor$ , $\not\leftrightarrow$ , $\top$ }, { $\land$ , $\leftrightarrow$ , $\bot$ }, { $\land$ , $\leftrightarrow$ , $\not\leftrightarrow$ }, { $\land$ , $\not\leftrightarrow$ , $\top$ }.