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

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

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

Дивись також

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