Функціональна повнота
Функціональна повнота множини логічних операцій чи булевих функцій — це можливість подати всі можливі значення таблиць істинності за допомогою формул із елементів цієї множини.
У логіці зазвичай застосовують такий набір операцій: кон'юнкція (), диз'юнкція (), заперечення (), імплікація () та еквівалентність (). Ця множина операцій є функціонально повною. Але вона не є мінімальною функціонально повною системою, оскільки:
Отже також є функціонально повною системою. Але також може бути виражене (за законом де Моргана) як:
також може бути визначено через подібним чином.
Також може бути виражена через таким чином:
Отже та одна з є мінімальною функціонально повною системою.
У контексті логіки висловлювань, функціонально повний набір зв'язків також називається (неформально) адекватним[джерело?].
Критерій повноти
Критерій Поста сформульовано американським математиком Емілем Постом 1941 року. Він описує необхідні та достатні умови функціональної повноти для множини булевих функцій.
Критерій:
- Множина булевих функцій є функціонально повною тоді і тільки тоді, коли вона не міститься повністю ні в одному з передповних класів.
Мінімальні множини бінарних операцій
- множини з одного елемента
- штрих Шефера (або {NAND}[1]), стрілка Пірса (або {NOR}[2]).
- множини двох елементів
- множини трьох елементів
- {, , }, {, , }, {, , }, {, , }, {, , }, {, , }.
Посилання
- ↑ "NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
- ↑ "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.