Образовательный блог – всё для учебы

Пусть наборы 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 монотонна.

1. Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции.
2. Класс линейных функций и его замкнутость относительно суперпозиции
3. Класс функций, сохраняющих константу
4. Лемма о немонотонной функции. Критерий монотонности по сокращенной ДНФ
5. Лемма о немонотонной функции. Критерий монотонности по сокращенной ДНФ
6. Двойственные функции. Теорема о суперпозиции двойственных функций. Принцип двойственности
7. Определение ?(?) – функций, кусочно-линейной функции
8. Суперпозиция функций. Функционально замкнутые классы
9. Раскраска графов, хроматическое число и хроматический класс
10. Функции алгебры логики
11. Описание систем с помощью передаточных функций
12. Преобразование задачи нелинейного программирования при помощи функций штрафов в последовательность задач безусловной оптимизации
13. Лемма о нелинейной функции
14. Минимизация функций без вычисления производных
15. Применений функций Net в коде Win32
16. Производящая функция для сочетаний без повторений и с повторениями с ограничением на число повторений
17. Конгруенции и фактор-алгебры, теоремы о гомоморфизме