Класс функций, сохраняющих ноль. Функция f (x1,,xn) называется сохраняющей ноль, если она на наборе из нулей принимает значение 0

Функция f (x₁,...,x_n) называется сохраняющей ноль, если она на наборе из нулей принимает значение 0, т.е. f (0,...,0) = 0.

Так, функции x₁x₂, x₁ ٧ x₂, х, 0 – сохраняют ноль, функции x₁ ® х₂,`х, 1 – не сохраняют.

Лемма 1. Из функций, сохраняющих ноль, суперпозицией можно получить только функции, сохраняющие ноль.

Доказательство. Поскольку функции, равные переменным, сохраняют ноль, достаточно показать, что функция

Φ (х₁,...,х_n) = f (f₁ (x₁,...,x_n),..., f_m (x₁,...,x_n))

сохраняет ноль, если функции f, f₁,...,f_m сохраняют ноль. Последнее следует из

f (f₁ (0,...,0),... f_m (0,...,0)) = f (0,...,0) = 0.

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