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

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

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

Классу $T_1$ принадлежат функции $1, x, x_1 \wedge x_2, x_1 \vee x_2, x_1 \rightarrow x_2, x1 \sim x2$;

Классу $T_1$ не принадлежат функции $0, \bar { x } , x_1 \oplus x_2, x_1 | x_2, x_1 \downarrow x_2$;

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

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

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

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

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

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

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