Функціональна повнота множини логічних операцій чи булевих функцій — це можливість подати всі можливі значення таблиць істинності за допомогою формул із елементів цієї множини.
У логіці зазвичай застосовують такий набір операцій: кон'юнкція (), диз'юнкція (), заперечення (), імплікація () та еквівалентність (). Ця множина операцій є функціонально повною. Але вона не є мінімальною функціонально повною системою, оскільки:
Отже також є функціонально повною системою. Але також може бути виражене (за законом де Моргана) як:
також може бути визначено через подібним чином.
Також може бути виражена через таким чином:
Отже та одна з є мінімальною функціонально повною системою.
У контексті логіки висловлювань, функціонально повний набір зв'язків також називається (неформально) адекватним.
Критерій повноти
Критерій Поста сформульовано американським математиком Емілем Постом 1941 року. Він описує необхідні та достатні умови функціональної повноти для множини булевих функцій.
Критерій: Множина булевих функцій є функціонально повною тоді і тільки тоді, коли вона не міститься повністю ні в одному з передповних класів.
Мінімальні множини бінарних операцій множини з одного елемента штрих Шефера (або {NAND}"NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html), стрілка Пірса (або {NOR}"NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html).
множини двох елементів
множини трьох елементів {, , }, {, , }, {, , }, {, , }, {, , }, {, , }.
Див. також Ґратка Поста
Посилання
Джерела
Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32.