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

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

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