Замыканием множества М ÍР₂, обозначается [M], называется множество всех булевых функций, полученных суперпозициями из М.

Например, [{&,®,Ø}]=P₂, так как согласно доказанной ранее теореме произвольная булева функция может быть представлена булевой формулой, являющейся суперпозицией над множеством {&,®,Ø}. Замыкание одноэлементного множества {Øx} определим единственной возможной подстановкой:

Таким образом, замыкание рассматриваемого множества содержит ровно две функции: тождественную функцию х и саму функцию отрицания : .

Замыкание двухэлементного множества {0,1} не содержит никаких новых функций кроме констант 0 и 1, поскольку это нульместные функции и никакие подстановки не возможны. Поэтому [{0,1}]={0,1};

Замыкание двухэлементного множества  может быть получено подстановками:

 и .

Тогда .

Пусть М ÍР₂. Операция получения множества [M] из М называется операцией замыкания. Множество М называется функционально замкнутым классом, если [M]=M. Множество Р₂ всех булевых функций является функционально замкнутым классом или просто замкнутым классом.

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

• МÍ[M],
• M₁ÍM₂, то [M₁]Í[M₂],
• [[M]]=[M].

Пусть М – замкнутый класс в Р₂. DÌM называется функционально полной системой в М, если [D] = M.

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

Функции f₁ и f₂ называются конгруэнтными, если одна из них может быть получена из другой заменой переменных (без отождествления). Например, функции  и  - конгруэнтные, а функции x&y и  – нет.

Множество функций QÍР₂ называется предполным классом в , если [Q]ÌP₂, и .

Покажем, что предполный класс замкнут, т.е.. Доказываем от противного. Пусть  и пусть имеется функция . Тогда . Но , следовательно,  т.е. , что противоречит определению предполного класса. Следовательно, такой функции не существует, т.е. предполный класс замкнут.

В математической логике рассматривается пять предполных классов.

Класс функций, сохраняющих 0, Т₀

Определение функции, сохраняющей 0:

.

Пусть функция  сохраняет 0. Тогда на нулевом наборе значений переменных значение функции равно 0, а на всех остальных наборах значений переменных функция может принимать произвольные значения. Поскольку число строк таблицы равно 2ⁿ, то число строк, на которых функция может принимать произвольные значения равно 2ⁿ-1, число n-местных булевых функций, сохраняющих 0, равно числу слов длины 2ⁿ-1 в двоичном алфавите, те равно числу размещений с повторениями из 2 по 2ⁿ-1. Таким образом, число n-местных булевых функций, сохраняющих 0 равно половине от числа всех n-местных булевых функций. |T₀(n)|= .

Приведенное выше рассуждение, определяющее мощность класса Т₀ означает замкнутость класса. Докажем это явно. Пусть имеется множество . Покажем, что произвольная суперпозиция этих функций также будет сохранять 0. Пусть суперпозиция  получена подстановкой функций из заданного множества вместо аргументов функции F. Очевидно, что на нулевом наборе значений переменных каждая из функций суперпозиции обращается в 0. В свою очередь  Следовательно, суперпозиция функций, сохраняющих 0 также сохраняет 0. Т.е. класс функций, сохраняющих 0, замкнут и включает функции всех возможных арностей: T₀= . Способ построения таблицы всех n-местных булевых функций подтверждает, что

.

Элементарные булевы функции  сохраняют 0. Функция отрицания , импликация, эквивалентность, штрих Шеффера, стрелка Пирса нуль не сохраняют. Из существования функций, не сохраняющих 0 следует, что класс Т₀ не полон в Р₂.

Лемма о функции, не сохраняющей 0: Если fÏТ₀, то отождествлением всех ее переменных и подстановкой функций, сохраняющих 0 из нее получается константа 1 или функция отрицания Øх.

Пример. Получим константу 1 и функцию отрицания из импликации.

.

.

f(x₁,x₂,…,x_n)ÎT₀(n)Ûf(0,0,…,0)=0. T₀= . Неполнота класса Т₀ следует из существования функций, не сохраняющих 0.

Класс функций, сохраняющих 1, Т₁

f(x₁,x₂,…,x_n)ÎP₂(n) Û f(1,1,…,1)=1.

.

Доказательство замкнутости класса Т₁ аналогично доказательству замкнутости класса Т₀. Мощность класса T₁(n)=|P₂(n)|/2. Неполнота класса Т₁ следует из существования функций, не сохраняющих 1. , а .

Лемма о функции, не сохраняющей 1: Если fÏТ₁, то отождествлением всех ее переменных из нее получается константа 0 или функция отрицания Øх.

Пример. Получим константу 0 и функцию отрицания из функции Å.

.

.