Функціональна повнота множини логічних операцій чи булевих функцій — це можливість подати всі можливі значення таблиць істинності за допомогою формул із елементів цієї множини.
У логіці зазвичай застосовують такий набір операцій: кон'юнкція (), диз'юнкція (), заперечення (), імплікація () та еквівалентність (). Ця множина операцій є функціонально повною. Але вона не є мінімальною функціонально повною системою, оскільки:
Отже також є функціонально повною системою. Але також може бути виражене (за (законом де Моргана)) як:
також може бути визначено через подібним чином.
Також може бути виражена через таким чином:
Отже та одна з є мінімальною функціонально повною системою.
У контексті логіки висловлювань, функціонально повний набір зв'язків також називається (неформально) адекватним[].
Критерій повноти
Критерій Поста сформульовано американським математиком Емілем Постом 1941 року. Він описує необхідні та достатні умови функціональної повноти для множини булевих функцій.
Критерій:
- Множина булевих функцій є функціонально повною тоді і тільки тоді, коли вона не міститься повністю ні в одному з (передповних класів).
Мінімальні множини бінарних операцій
- множини з одного елемента
- штрих Шефера (або {NAND}), стрілка Пірса (або {NOR}).
- множини двох елементів
- множини трьох елементів
- {
,
,
}, {
,
,
}, {
,
,
}, {
,
,
}, {
,
,
}, {
,
,
}.
Посилання
- "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.
Дивись також
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет