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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

См. также[править | править исходный текст]