double arrow

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


Набор a = (a1,...,an) предшествует набору b = (b1,...,bn), если ai £ bi (i=1,2,...,n). Этот факт обозначаем как a ≼ b. Наборы, которые находятся в отношении ≼, называются сравнимыми.

Функция f (x1,...,xn) называется монотонной, если для любой пары наборов a = (a1,...,an) и b = (b1,...,bn) таких, что a ≼ b, f (a) £ f(b).

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

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

Доказательство. Пусть функции f (y1,...,ym), f1 (x1,...,xn),...,fm (x1,...,xn) -монотонные. Надо показать, что

Φ(x1,...,xn) = f (f1 (x1,...,xn),...,fm (x1,...,xn)) - монотонная функция.

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

Φ(a) = f (f1 (a),...,fm (a)) £ f (f1 (b),...,fm (b)) = Φ(b).

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

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

Доказательство. Пусть дана немонотонная функция f (x1,...,xn), т.е. для неё существуют наборы a = (a1,...,an) и b = (b1,...,bn) такие, что

a ≼b, а f (a) > f (b). Рассмотрим функцию y(x), которая получается из функции f (x1,...,xn) подстановкой констант 0, 1 и функции x. Подстановку определим следующим образом: вместо xi будем подставлять ai, если ai = bi, и x, если ai bi. Рассмотрим функцию y(x).

y (0) = f (a1,...,a n) > f (b1,...,b n) = y(1).

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


Сейчас читают про: