WikiSort.ru - Не сортированное

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 21 января 2015 года.

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

См. также

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