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

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

Пусть $f(x_1,...,x_n)\in P_2$. $f$ называют функцией, сохраняющей единицу, если $f(1,...,1) = 1$. Множество всех функций сохраняющих 1 обозначим $T_1$: $T_1 = \{f(x_1,...,x_n)

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

Класс функций $T_1$ замкнут.

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

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

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

Рис. 1. [math]\displaystyle{ T_1 }[/math] получается из [math]\displaystyle{ T_0 }[/math] заменой [math]\displaystyle{ 0 }[/math] на [math]\displaystyle{ 1 }[/math]: зелёная клетка — значение совпало с целевым. В обоих классах лежат [math]\displaystyle{ x }[/math], [math]\displaystyle{ x\vee y }[/math], [math]\displaystyle{ x\wedge y }[/math]; только в [math]\displaystyle{ T_1 }[/math] — [math]\displaystyle{ 1 }[/math], [math]\displaystyle{ x\supset y }[/math], [math]\displaystyle{ x\equiv y }[/math]; ни в одном — [math]\displaystyle{ \overline x }[/math], [math]\displaystyle{ x|y }[/math], [math]\displaystyle{ x\downarrow y }[/math].

Тождественная функция $f(x)=x$ лежит в классе $T_1$.

Функция отрицания $f(x) = \overline x$ не лежит в $T_1$.

Таким образом, $T_1\neq \varnothing$ и $T_1\neq P_2$.

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