Функціональна повнота

Функціональна повнота множини логічних операцій чи булевих функцій — це можливість подати всі можливі значення таблиць істинності за допомогою формул із елементів цієї множини.

У логіці зазвичай застосовують такий набір операцій: кон'юнкція (${\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 року. Він описує необхідні та достатні умови функціональної повноти для множини булевих функцій.

Критерій:

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

Мінімальні множини бінарних операцій

множини з одного елемента

штрих Шефера (або {NAND}^[1]), стрілка Пірса (або {NOR}^[2]).

множини двох елементів

${\displaystyle \{\lor ,\lnot \},\{\land ,\lnot \},\{\to ,\lnot \},\{\to ,\bot \},\{\not \to ,\top \},\{\to ,\not \to \},\{\to ,\not \leftrightarrow \},\{\not \to ,\leftrightarrow \}}$

множини трьох елементів

{${\displaystyle \lor }$, ${\displaystyle \leftrightarrow }$, ${\displaystyle \bot }$}, {${\displaystyle \lor }$, ${\displaystyle \leftrightarrow }$, ${\displaystyle \not \leftrightarrow }$}, {${\displaystyle \lor }$, ${\displaystyle \not \leftrightarrow }$, ${\displaystyle \top }$}, {${\displaystyle \land }$, ${\displaystyle \leftrightarrow }$, ${\displaystyle \bot }$}, {${\displaystyle \land }$, ${\displaystyle \leftrightarrow }$, ${\displaystyle \not \leftrightarrow }$}, {${\displaystyle \land }$, ${\displaystyle \not \leftrightarrow }$, ${\displaystyle \top }$}.