Ґратка Поста ґратка всіх клонів на булевій множині булева множина позначається 2 0 1 відсортована за включенням Була опи

Ґратка Поста — ґратка всіх (клонів) на булевій множині (булева множина позначається 2={0, 1}) відсортована за (включенням). Була описана Емілем Постом в 1941 році.

Використовується в математичній логіці та універсальній алгебрі.

Визначення

Булевими функціями чи логічними операціями арності n є функції f: 2ⁿ → 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 с.(рос.)

Це незавершена стаття з математики.
Ви можете проєкту, виправивши або дописавши її.