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

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

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

Отже також є функціонально повною системою. Але також може бути виражене (за законом де Моргана) як:

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

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

Отже та одна з є мінімальною функціонально повною системою.

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

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

Докладніше: Критерій Поста

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

Критерій:

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

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

множини з одного елемента
штрих Шефера (або {NAND}[1]), стрілка Пірса (або {NOR}[2]).
множини двох елементів
множини трьох елементів
{, , }, {, , }, {, , }, {, , }, {, , }, {, , }.

Посилання

Джерела

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

Дивись також