Пусть наборы a=(a₁, a₂,…,a_n) и b = (b₁, b₂,…,b_n) — два набора длины n из 0 и 1, тогда а≤b, если поразрядно a₁≤b₁≤,…, ≤a_n≤b_n.

Определение: Функция f(x₁, x₂,…,x_n) – монотонна для всяких наборов a = (a₁, a₂,…,a_n), b = (b₁, b₂,…,b_n) условие a ≤ b влечет f(a) ≤ f(b)

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

Доказательство: пусть функции f(x₁, x₂,…,x_m), g_i(x₁, x₂,…,x_n) i=1..m монотонные функции (от одних переменных), тогда их суперпозиция h(x₁, x₂,…,x_n) = f(g₁(x₁, x₂,…,x_n), g₂(x₁, x₂,…,x_n),…,g_m(x₁, x₂,…,x_n)) — монотонна, Пусть наборы c = (c₁, c₂,…,c_n), d = (d₁, d₂,…,d_n) – произвольные наборы из 0 и 1, для которых c ≤ d .т.е. c_i ≤ d_i для ∀i. Пусть a_i = g_i(c), b_i = g_i(d) i =1,..,m, пусть a = (a₁, a₂,…,a_m), b= (b₁, b₂,…,b_m). т.к. функции g_i – монотонны и c ≤ d то g_i(c) ≤ g_i(d) ⇒ a_i ≤ b_i i =1..m, следовательно a ≤ b, отсюда в силу монотонности функции f получаем, что f(a) ≤ f(b), тогда h(c) = f(g₁(c),…,g_m(c)) = f(a₁, a₂,…,a_m) ≤ f(b) = f(b₁, b₂,…,b_m) = h(d). Итак, для любых двух наборов c,d неравенство c ≤ d влечет h(c) ≤ h(d), то есть функция h монотонна.

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