§1.5. Полнота, замкнутость. Теорема Поста о полноте

Для функций и функция называется суперпозицией.

Класс булевых функций называется (функционально) полным, если любая функция из может быть представлена в виде формулы над , т.е. любая функция получается из функций класса применением конечного числа операции суперпозиций.

Замечание. Класс может быть конечным или бесконечным.

Примеры полных классов: а) ; б) (любая булева функция выражается формулой в виде конъюнкции, дизъюнкции и инверсии); в) любую булеву функцию можно представить в виде полинома Жегалкина.

Пусть некоторый класс булевых функций. Замыканием называется множество всех булевых функций, получающихся в виде формул над (обозначается ).

Свойства замыкания:

1. .

2. .

3. .

Класс называется:

– замкнутым, если ;

– полным, если (см. определение выше);

– предполным, если не полный, но для любой функции класс полный.