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

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

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

Джерела

• Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32.

Дивись також

• Ґратка Поста