Класс $T_0$. Теорема о замкнутости класса $T_0$

Определение. Будем говорить, что функция $f (x_1,..., x_n)$ из $P_2$ сохраняет константу 0, если $f (0,..., 0) = 0$.

Обозначим через $T_0$ класс всех функций алгебры логики, сохраняющих константу 0.

Пример 1. Легко видеть, что

$0, x, x_1 \wedge x_2, x_1 \vee x_2, x_1 + x_2 \in T_0$,

$1, \bar { x } , x_1 \rightarrow x_2, x_1 \sim x_2, x_1 | x_2 \notin T_0$,

Упражнение 1. Докажите, что свойство функции принадлежать классу $T_0$ инвариантно относительно операций введения и удаления фиктивных переменных.

Теорема 1. Класс $T_0$ замкнут.

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

$\Phi = f (f_1,...,f_n)$

принадлежит $T_0$, если функции $f, f_1,..., f_n$ принадлежат классу $T_0$. Последнее вытекает из цепочки равенств.

$\Phi (0,..., 0) = f (f_1 (0,...,0),...,f_n(0,..., 0)) = f (0,..., 0) = 0$

Доказательство. Пусть $\ { f (x_1,..., x_n), g_1(y_ { 11 } ,...,y_ { 1m_1 } ),...,g_n(y_ { n1 } ,...,y_ { nm_n } )\ } \subseteq T_0$. Рассмотрим функцию $h(y_l,...,y_r) = f(g_1(y_ { 11 } ,...,y_ { 1m_1 } ),...,g_n(y_ { nl } ,...,y_ { nm_n } ))$. Среди переменных функций $g_i$ могут встречаться и одинаковые, поэтому в качестве переменных функции $h$ возьмём все различные из них. Тогда $h (0, ..., 0) = f(g_1 (0, ..., 0), ..., g_n (0, ..., 0)) = f(0, ..., 0) = 0$ , следовательно, функция $h$ также сохраняет ноль.

Рассмотрен только частный случай { без переменных в качестве аргументов } . Однако, поскольку тождественная функция сохраняет ноль, подстановка простых переменных эквивалентна подстановке тождественной функции, теорема доказана.