Меню Главная Случайная статья Настройки Функциональная полнота Материал из https://ru.wikipedia.org Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция (${\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 A\land B=\neg (\neg A\lor \neg B)}$ Также ${\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 ,\not \leftrightarrow \},\{\lor ,\not \leftrightarrow ,\top \},\{\land ,\leftrightarrow ,\bot \},\{\land ,\leftrightarrow ,\not \leftrightarrow \},\{\land ,\not \leftrightarrow ,\top \},\{\lor ,\leftrightarrow ,\bot \}}$. То же в другой нотации: ${\displaystyle {\bigl \langle }\lor ,\odot ,\oplus {\bigr \rangle }}$, ${\displaystyle {\bigl \langle }\lor ,\oplus ,1{\bigr \rangle }}$, ${\displaystyle {\bigl \langle }\wedge ,\odot ,0{\bigr \rangle }}$, ${\displaystyle {\bigl \langle }\wedge ,\odot ,\oplus {\bigr \rangle }}$, ${\displaystyle {\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }}$ (см. алгебра Жегалкина), ${\displaystyle {\bigl \langle }\lor ,\odot ,0{\bigr \rangle }}$ (инверсный к предыдущему). См. также Замкнутые классы булевых функций