Класс монотонных функций и его замкнутость относительно суперпозиции

Пусть наборы a=(a1, a2,…,an) и b = (b1, b2,…,bn) — два набора длины n из 0 и 1, тогда а≤b, если поразрядно a1≤b1≤,…, ≤an≤bn.

Определение: Функция f(x1, x2,…,xn) – монотонна для всяких наборов a = (a1, a2,…,an), b = (b1, b2,…,bn) условие a ≤ b влечет f(a) ≤ f(b)

Теорема: Класс монотонных функций замкнут относительно суперпозиции.

Доказательство: пусть функции f(x1, x2,…,xm), gi(x1, x2,…,xn) i=1..m монотонные функции (от одних переменных), тогда их суперпозиция h(x1, x2,…,xn) = f(g1(x1, x2,…,xn), g2(x1, x2,…,xn),…,gm(x1, x2,…,xn)) — монотонна, Пусть наборы c = (c1, c2,…,cn), d = (d1, d2,…,dn) – произвольные наборы из 0 и 1, для которых c ≤ d .т.е. ci ≤ di для ∀i. Пусть ai = gi(c), bi = gi(d) i =1,..,m, пусть a = (a1, a2,…,am), b= (b1, b2,…,bm). т.к. функции gi – монотонны и c ≤ d то gi(c) ≤ gi(d) ⇒ ai ≤ bi i =1..m, следовательно a ≤ b, отсюда в силу монотонности функции f получаем, что f(a) ≤ f(b), тогда h(c) = f(g1(c),…,gm(c)) = f(a1, a2,…,am) ≤ f(b) = f(b1, b2,…,bm) = h(d). Итак, для любых двух наборов c,d неравенство c ≤ d влечет h(c) ≤ h(d), то есть функция h монотонна.


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru