Функции сохраняющие ноль

Определение:

Пусть [math]\displaystyle{ f(x_1,...,x_n)\in P_2 }[/math]. [math]\displaystyle{ f }[/math] называют функцией, сохраняющей ноль, если [math]\displaystyle{ f(0,...,0) = 0 }[/math].

Множество всех функций сохраняющих 0 обозначим [math]\displaystyle{ T_0 }[/math]: [math]\displaystyle{ T_0 = \{f(x_1,...,x_n) | f\in P_2, f(0,...,0) = 0\}. }[/math]

Утверждение:

Класс функций [math]\displaystyle{ T_0 }[/math] замкнут.

Доказательство:

Рассмотрим суперпозицию ранга 1 от функций из [math]\displaystyle{ T_0 }[/math].

a) Пусть [math]\displaystyle{ f(x_1,...,x_n)\in T_0 }[/math] и [math]\displaystyle{ g(x_1,...,x_{j-1},x_{j+1},...,x_n, y) =f(x_1,...,x_{j-1},y,x_{j+1},...,x_{n}) }[/math]. Тогда [math]\displaystyle{ g(0,...,0) = f(0,...,0) = 0 }[/math]. Следовательно, [math]\displaystyle{ g(x_1,...,x_{j-1},x_{j+1},...,x_n, y)\in T_0 }[/math].

b) Пусть [math]\displaystyle{ f(x_1,...,x_n)\in T_0 }[/math] и [math]\displaystyle{ h(y_1, ..., y_m)\in T_0 }[/math] и [math]\displaystyle{ g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m) = f(x_1,...,x_{j-1},h(y_1,...,y_{m}),x_{j+1},...,x_{n}) }[/math]. Тогда [math]\displaystyle{ g(0,...,0) = f(0,...,0,h(0,...,0),0,...,0) = f(0,...,0,0,0,...,0) = 0 }[/math].

Получаем, что [math]\displaystyle{ g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m)\in T_0 }[/math].

Таким образом, [math]\displaystyle{ [T_0] = T_0 }[/math].

[math]\displaystyle{ \blacksquare }[/math]

Рис. 1. На нулевом наборе все аргументы — нули: [math]\displaystyle{ h(0,\dots,0)=0 }[/math], это значение подаётся в [math]\displaystyle{ f }[/math], остальные аргументы тоже нули, поэтому [math]\displaystyle{ g(0,\dots,0)=0 }[/math]. Проверка: константа [math]\displaystyle{ 0 }[/math] и функция [math]\displaystyle{ x }[/math] лежат в [math]\displaystyle{ T_0 }[/math], а [math]\displaystyle{ 1 }[/math] и [math]\displaystyle{ \overline x }[/math] — нет.

Тождественная функция [math]\displaystyle{ f(x)=x }[/math] лежит в классе [math]\displaystyle{ T_0 }[/math].

Функция отрицания [math]\displaystyle{ f(x) = \overline x }[/math] не лежит в [math]\displaystyle{ T_0 }[/math].

Таким образом, [math]\displaystyle{ T_0\neq \varnothing }[/math] и [math]\displaystyle{ T_0\neq P_2 }[/math].

Конспект: Дискретная математика