Пусть множество булевых функций от n переменных.
Замыканием F () называется множество всех булевых функций, реализуемых формулами над F.
Множество функций (класс) называется замкнутым, если =F.
Рассмотрим следующие классы функций.
1. Класс функций, сохраняющих 0:
.
2. Класс функций, сохраняющих 1:
3. Класс самодвойственных функций:
, где .
4. Класс монотонных функций
где .
5. Класс линейных функций
, где + — означает сложение по модулю 2, а знак конъюнкции опущен.
Теорема. Классы Т0, Т1, Т*, ТМ, TL – замкнуты.
Доказательство. Чтобы доказать, что некоторый класс F замкнут достаточно показать, что, если формула реализована в виде формулы над F, то она принадлежит F.
Рассмотрим доказательство для одного класса функций Т0.
Пусть и . Тогда .
Аналогичные доказательства можно привести для остальных классов.