Згадаємо, що система булевих функцій називається повною (функціонально повною), якщо будь-яка булева функція може бути записана як композиція функцій цієї системи.
Теорема (Теорема Поста про повноту). Для того, щоб система функцій =була повною, необхідно и достатньо, щоб вона не містилася цілком в жодному з класів , , , ,.
Наслідок.Будь-який замкнений клас функцій з Р2, який не збігається з Р2, міститься принаймні в одному з замкнених класів , , , ,.
Для перевірки функціональної повноти системи булевих функцій будується таблиця Поста, в якій відмічається належність функцій замкненим класам. Якщо у кожному стовпці таблиці Поста є хоча б один мінус – система повна, інакше – ні.
Приклад.Перевірити функціональну повноту системи булевихфункцій .
Розв’язання. Перевіримо належність замкненим класам функції . Побудуємо таблицю істинності даної функції: