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

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

У логіці зазвичай застосовують такий набір операцій: кон'юнкція ($\wedge$), диз'юнкція ($\vee$), заперечення ($\mathrm{\neg }$), імплікація ($\to$) та еквівалентність ($\leftrightarrow$). Ця множина операцій є функціонально повною. Але вона не є мінімальною функціонально повною системою, оскільки:

$A\to B=\mathrm{\neg }A\vee B$

$A\leftrightarrow B=(A\to B)\wedge (B\to A)$

Отже $\{\mathrm{\neg },\wedge ,\vee \}$ також є функціонально повною системою. Але $\vee$ також може бути виражене (за законом де Моргана) як:

$A\vee B=\mathrm{\neg }(\mathrm{\neg }A\wedge \mathrm{\neg }B).$

$\wedge$ також може бути визначено через $\vee$ подібним чином.

Також $\vee$ може бути виражена через $\to$ таким чином:

$A\vee B:=(A\to B)\to B.$

Отже $\{\mathrm{\neg }\}$ та одна з $\{\wedge ,\vee ,\to \}$ є мінімальною функціонально повною системою.

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

Критерій повноти

Шаблон:Main Критерій Поста сформульовано американським математиком Емілем Постом 1941 року. Він описує необхідні та достатні умови функціональної повноти для множини булевих функцій.

Критерій:

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

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

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

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

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

$\{\vee ,\mathrm{\neg }\},\{\wedge ,\mathrm{\neg }\},\{\to ,\mathrm{\neg }\},\{\to ,\mathrm{\perp }\},\{\to ̸,\mathrm{\top }\},\{\to ,\to ̸\},\{\to ,\leftrightarrow ̸\},\{\to ̸,\leftrightarrow \}$

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

{$\vee$, $\leftrightarrow$, $\mathrm{\perp }$}, {$\vee$, $\leftrightarrow$, $\leftrightarrow ̸$}, {$\vee$, $\leftrightarrow ̸$, $\mathrm{\top }$}, {$\wedge$, $\leftrightarrow$, $\mathrm{\perp }$}, {$\wedge$, $\leftrightarrow$, $\leftrightarrow ̸$}, {$\wedge$, $\leftrightarrow ̸$, $\mathrm{\top }$}.

Джерела

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

Дивись також

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