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

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

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

У контексті логіки висловлювань, функціонально повний набір зв'язків також називається (неформально) адекватним^{[джерело?]}.