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

Определение. Будем говорить, что функция $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$, подстановка простых переменных эквивалентна подстановке тождественной функции, теорема доказана.