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

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

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

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

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

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

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

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

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

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

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

Критерій:

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

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

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

Посилання ред.

Джерела ред.

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

Дивись також ред.