Классы функций, сохраняющих константы

Булева функция сохраняет константу 0,если на нулевом наборе значений переменных принимает значение 0, сохраняет константу 1, если на единичном наборе значений переменных принимает значение 1. Классы функций, сохраняющих константы, обозначаются соответственно Т ₀ и Т ₁. Функции тождественная, конъюнкция и дизъюнкция сохраняют обе константы; отрицание не сохраняет их; сумма по модулю 2 сохраняет 0, но не сохраняет 1; импликация сохраняет 1, но не сохраняет 0.

ТЕОРЕМА. Число всех различных n- местных булевых функций, сохраняющих константу 0, равно .

Доказательство. Разобьем множество всех булевых функций на пары “функция и ее отрицание”. В паре одна и только одна функция сохраняет константу ноль. Следовательно, число всех различных n- местных булевых функций, сохраняющих константу 0, равно половине общего числа всех n- местных булевых функций. Такое же утверждение верно и для функций, сохраняющих константу 1.

ТЕОРЕМА. Классы функций, сохраняющих константы 0 и 1, замкнуты.

Доказательство. Пусть f ₁(0,…,0) = 0, f ₂(0,…,0) = 0,

f = f ₁(x ₁,…, x_{n –1}, f ₂(y ₁,…, y _m)).

f (0,…,0)) = f ₁(0,…,0, f ₂(0,…,0)) = f ₁(0,…,0) = 0 Þ f Î T ₀.

Многократным повторением этого рассуждения можно доказать, что любая суперпозиция функций класса Т ₀ вновь функция класса T _0.

Точно также доказывается замкнутость класса T ₁.