Ґратка Поста — ґратка всіх клонів на булевій множині (булева множина позначається 2={0, 1}) відсортована за включенням. Була описана Емілем Постом в 1941 році.
Використовується в математичній логіці та універсальній алгебрі.
Визначення
Булевими функціями чи логічними операціями арності n є функції f: 2n → 2.
Множина таких функцій що містить всі проєкції та замкнена відносно композиції функцій називається клоном.
Поняття клона є розширенням поняття замкнений клас функцій.
Властивості
- Перетином двох клонів є клон.
- Об'єднання двох клонів чи доповнення клона можуть не бути клоном.
Решітка
Для визначення деяких класів використовуються таблиці істинності їх функцій, зі значенням аргументів впорядкованих у лексикографічному порядку.
Критерій Поста
Важливими є передповні клони (їх всього 5, в них проста будова), при добавлянні в них хоча б однієї функції, що їм не належить, їх замикання стає функціонально повним, тобто включає всі булеві функції.
Див. також
Джерела
- E. L. Post, The two-valued iterative systems of mathematical logic, Annals of Mathematics studies, no. 5, Princeton University Press, Princeton 1941
- Универсальная алгебра. — Москва : Мир, 1968. — 351 с.(рос.)
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Gratka Posta gratka vsih kloniv na bulevij mnozhini buleva mnozhina poznachayetsya 2 0 1 vidsortovana za vklyuchennyam Bula opisana Emilem Postom v 1941 roci Diagrama Gasse gratkb Posta Vikoristovuyetsya v matematichnij logici ta universalnij algebri ViznachennyaBulevimi funkciyami chi logichnimi operaciyami arnosti n ye funkciyi f 2n 2 Mnozhina takih funkcij sho mistit vsi proyekciyi ta zamknena vidnosno kompoziciyi funkcij nazivayetsya klonom Ponyattya klona ye rozshirennyam ponyattya zamknenij klas funkcij VlastivostiPeretinom dvoh kloniv ye klon Ob yednannya dvoh kloniv chi dopovnennya klona mozhut ne buti klonom ReshitkaDlya viznachennya deyakih klasiv vikoristovuyutsya tablici istinnosti yih funkcij zi znachennyam argumentiv vporyadkovanih u leksikografichnomu poryadku Kriterij PostaDokladnishe Kriterij Posta Vazhlivimi ye peredpovni kloni yih vsogo 5 v nih prosta budova pri dobavlyanni v nih hocha b odniyeyi funkciyi sho yim ne nalezhit yih zamikannya staye funkcionalno povnim tobto vklyuchaye vsi bulevi funkciyi Div takozhZamknenij klas funkcij algebri logiki Simetrichni funkciyi algebri logiki Monotonni funkciyi algebri logiki Linijni funkciyi algebri logiki Peredpovnij klas funkcij algebri logikiDzherelaE L Post The two valued iterative systems of mathematical logic Annals of Mathematics studies no 5 Princeton University Press Princeton 1941 Universalnaya algebra Moskva Mir 1968 351 s ros Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi