Класс монотонных функций

Набор a = (a₁,...,a_n) предшествует набору b = (b₁,...,b_n), если a_i £ b_i (i=1,2,...,n). Этот факт обозначаем как a ≼ b. Наборы, которые находятся в отношении ≼, называются сравнимыми.

Функция f (x₁,...,x_n) называется монотонной, если для любой пары наборов a = (a₁,...,a_n) и b = (b₁,...,b_n) таких, что a ≼ b, f (a) £ f(b).

Например, функции x₁x₂, x₁ ٧ x₂, x – монотонные, а`x - немонотонная.

Лемма 5. Из монотонных функций с помощью суперпозиции можно получить только монотонные функции.

Доказательство. Пусть функции f (y₁,...,y_m), f₁ (x₁,...,x_n),...,f_m (x₁,...,x_n) -монотонные. Надо показать, что

Φ(x₁,...,x_n) = f (f₁ (x₁,...,x_n),...,f_m (x₁,...,x_n)) - монотонная функция.

Пусть a ≼ b, тогда f_i (a) £ f_i (b) (i=1,...,m). Отсюда

Φ(a) = f (f₁ (a),...,f_m (a)) £ f (f₁ (b),...,f_m (b)) = Φ(b).

Следствие.Полная система функций должна содержать хотя бы одну немонотонную функцию.

Лемма 6. Из немонотонной функции путём подстановки констант 0, 1 и функции x можно получить`x.

Доказательство. Пусть дана немонотонная функция f (x₁,...,x_n), т.е. для неё существуют наборы a = (a₁,...,a_n) и b = (b₁,...,b_n) такие, что

a ≼b, а f (a) > f (b). Рассмотрим функцию y(x), которая получается из функции f (x₁,...,x_n) подстановкой констант 0, 1 и функции x. Подстановку определим следующим образом: вместо x_i будем подставлять a_i, если a_{i =} b_i, и x, если a_i b_i. Рассмотрим функцию y(x).

y (0) = f (a₁,...,a _n) > f (b₁,...,b _n) = y(1).

Следовательно, y(x) =`x.