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

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

См. также

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

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.