Монотонные функции. Монотонная функция

Монотонная функция

Моното́нная фу́нкция — это функция, приращение которой не меняет знака, то есть либо всегда неотрицательное, либо всегда неположительное. Если в дополнение приращение не равно нулю, то функция называется стро́го моното́нной. Монотонная функция — это функция, меняющаяся в одном и том же направлении.

Функция возрастает, если большему значению аргумента соответствует большее значение функции. Функция убывает, если большему значению аргумента соответствует меньшее значение функции.

Содержание

Определения

Пусть дана функция Тогда

  • функция называется возраста́ющей на , если

y Rightarrow f(x) ge f(y)» border=»0″ />.

  • функция называется стро́го возраста́ющей на , если

y Rightarrow f(x) > f(y)» border=»0″ />.

  • функция называется убыва́ющей на , если

y Rightarrow f(x) le f(y)» border=»0″ />.

  • функция называется стро́го убыва́ющей на , если

y Rightarrow f(x) .

(Строго) возрастающая или убывающая функция называется (строго) монотонной.

Другая терминология

Иногда возрастающие функции называют неубыва́ющими, а убывающие функции невозраста́ющими. Строго возрастающие функции тогда зовут просто возрастающими, а строго убывающие просто убывающими.

Свойства монотонных функций

  • Монотонная функция, определённая на интервале, измерима относительно борелевских сигма-алгебр.
  • Монотонная функция, определённая на замкнутом интервале, ограничена. В частности, она интегрируема поЛебегу.
  • Монотонная функция может иметь разрывы только первого рода. В частности, множество точек разрыва не более чем счётно.
  • Монотонная функция дифференцируемапочти всюду относительно меры Лебега.

Условия монотонности функции

  • (Критерий монотонности функции, имеющей производную на интервале) Пусть функция непрерывна на и имеет в каждой точке производнуюТогда не убывает на тогда и только тогда, когда не возрастает на тогда и только тогда, когда
  • (Достаточное условие строгой монотонности функции, имеющей производную на интервале) Пусть функция непрерывна на и имеет в каждой точке производную Тогда если 0,» border=»0″ /> то строго возрастает на если то строго убывает на

Обратное, вообще говоря, неверно. Производная строго монотонной функции может обращаться в ноль. Однако, множество точек, где производная не равна нулю, должно быть плотно на интервале Точнее имеет место

  • (Критерий строгой монотонности функции, имеющей производную на интервале) Пусть и всюду на интервале определена производная Тогда строго возрастает на интервале тогда и только тогда, когда выполнены следующие два условия:
  1. 0.» border=»0″ />

Аналогично, строго убывает на интервале тогда и только тогда, когда выполнены следующие два условия:

Монотонные функции. Монотонная функция

Определение. Булева функция f(x1, …, xn) называется монотонной (принадлежит классу M), если для любой пары наборов α и β таких, что αβ, выполняется условие f(α)≤ f(β) (назовем его условием монотонности).

Читать еще:  Смотреть аниме про темную магию. Смотреть аниме про школу и любовь

Примеры. Исследуем мажоритарную булеву функцию.

Перебор пар начнем с наборов α=000 и β=001: для них αβ и выполнено условие монотонности f(000)=f(001). Отметим, что набор α таков, что любой другой набор β является последователем α, и, казалось бы, следует анализировать каждую из этих пар. Однако f(α)=0, поэтому условие f(α)≤ f(β) будет выполнено для любого набора β. Значит, в качестве α достаточно рассмотреть лишь те наборы, на которых функция принимает значение единица: 011, 101, 110 и 111. Кроме того, наборы в таблице истинности расположены в естественном порядке, значит, наборы –последователи лежат ниже предшественников. Набор α=011 имеет единственного последователя β=111 и f(011)=f(111), то есть условие монотонности для этой пары не нарушено. Рассмотрим остальные возможные пары наборов: α=101, β=111 и α=110, β=111 (набор α=111 последователей не имеет). Для них условие монотонности также не нарушено. Значит, мажоритарная функция монотонна.

Из элементарных булевых функций монотонными являются, например, конъюнкция и дизъюнкция. Не являются монотонными, например, штрих Шеффера и стрелка Пирса. •

В общем случае набор имеет несколько последователей, и для всех таких пар надо проверять выполнение условия монотонности. Чтобы сформулировать более простой алгоритм распознавания монотонной функции, докажем утверждение, которое к тому же будет использовано при доказательстве леммы о немонотонной функции.

Утверждение о условии немонотонности. Для любой пары наборов α и β таких, что αβ и f(α) > f(β), найдется пара соседних наборов α’, β’ с теми же свойствами: α’β’ и f(α’) > f(β’).

Доказательство. Если α и β – соседи, то утверждение верно (α’=α, β’=β). Иначе вычислим расстояние d (по Хэммингу) между наборами α=a1… an и β=b1… bn и начнем строить цепочку наборов γ, …, γd такую, что

и любые два расположенных рядом набора γi –1i (i=1, …, d) являются соседями. Очередной набор γi получим из предыдущего набора γi –1 заменой значения одной из ортогональных компонент наборов γi –1 и β (это будет замена 0 на 1, так как αβ), затем проверим условие немонотонности f(γi –1)>f(γi). Если оно выполнено, утверждение доказано (α’=γi –1, β’=γi). Иначе получим и исследуем очередной набор. В худшем случае, когда постоянно выполняется условие монотонности, имеем

но тогда f(γd –1)=1 и f(β)=0, значит, условие немонотонности выполнится для последней пары: α’=γd –1 и β’=γd=β. •

Читать еще:  Слова утешения другу. Как не надо поддерживать в трудную минуту

Пример. Пусть задана пара булевых векторов , тогда цепочка соседей может иметь следующий вид:

Если f(α)>f(β), то смена значения функции с 1 на 0 произойдет по крайней мере на одной из четырех пар соседей. •

Алгоритм распознавания монотонной булевой функции (основан на утверждении о условии немонотонности).

Начало. Задана таблица истинности булевой функции.

Шаг 1. Сравниваем значения функции на наборах, соседних по первой переменной, то есть верхнюю половину столбца значений функции (вектор φ1) с нижней половиной (вектор φ1). Если условие φ1φ1 нарушено, то функция не монотонна, идем на конец.

Шаг 2. Сравниваем значения функции на наборах, соседних по второй переменной, то есть верхние четвертины столбца значений функции (векторы φ’2, φ»2) с нижними четвертинами (векторами φ’2, φ»2) в каждой половине. Если хотя бы одно из условий φ’2φ’2 и φ»2φ»2нарушено, то функция не монотонна, идем на конец.

Шаги 3 –n. Аналогично сравниваем восьмые, шестнадцатые части, и так далее. Если ни одно из проверяемых условий не нарушено, то функция монотонна.

Примеры. Рассмотрим две булевых функции (первая – мажоритарная).

Проверим на монотонность мажоритарную функцию. Сравниваем половины столбца значений: φ1=0001 0111=φ1. Сравниваем четвертины: φ’2=00 01=φ’2, φ»2=01 11=φ»2. Сравниваем осьмушки: 0 0 , 0 1, 0 1 , 1 1 . Следовательно, мажоритарная функция монотонна.

Проверим на монотонность функцию g(x,y,z). Сравниваем половины столбца значений: φ1=0110 0111=φ1. Сравниваем четвертины: так как φ’2=01 не предшествует φ’2=10, функция g(x,y,z) не монотонна. •

Теорема о замкнутости класса M. Множество всех монотонных булевых функций является замкнутым классом.

Доказательство. Рассмотрим суперпозицию любых булевых функций из M, то есть функцию

и покажем, что она монотонна. Подставим в суперпозицию любую пару наборов α и β таких, что αβ, получим:

где γ и δ – булевы векторы. Так как αβ, и булевы функции f1(x1, …, xn), …, fm(x1, …, xn) монотонны, то γδ. Поскольку функция f(y1, …, ym) также монотонна, то f(γ)≤ f(δ), следовательно, f(α)≤ f(β), то есть f(x1, …, xn) монотонна, и класс M замкнут. •

Лемма о немонотонной булевой функции. Если булева функция немонотонна, то из нее подстановкой вместо аргументов констант 0 и 1 и переменной x можно получить инверсию переменной x .

Доказательство. Рассмотрим немонотонную функцию f(x1, …, xn). Согласно утверждению о условии немонотонности, существует пара соседних наборов α=a1… an и β=b1… bn таких, что αβ и f(α) > f(β), то есть

Пусть α и β – соседи по k –й компоненте, тогда

Читать еще:  К чему снятся семечки. К чему снится подсолнух

Подставим в функцию f(x1, …, xn) вместо каждого аргумента xi либо константу ai, если i ≠ k, либо переменную x, если i = k (подстановка константы и переменной допустима по условию теоремы). В результате получим функцию одного аргумента

Покажем, что g(x)= x :

Итак, инверсия x получена. •

Пример. Рассмотрим функцию f(y,z) = y ↓ z.

Она немонотонна, так как существует пара наборов α=00 и β=10 таких, что αβ и f(α)>f(β). Так как α и β – соседи по первой компоненте, то, согласно доказательству леммы, положим y=x и подставим вместо z константу 0, получим:

Монотонность функций

Функция f (x) называется возрастающей на промежутке D, если для любых чисел x1 и x2 из промежутка D таких, что x1 f (x2).

На показанном на рисунке графике функция y = f (x), возрастает на каждом из промежутков [a; x1) и (x2; b] и убывает на промежутке (x1; x2). Обратите внимание, что функция возрастает на каждом из промежутков [a; x1) и (x2; b], но не на объединении промежутков

Если функция возрастает или убывает на некотором промежутке, то она называется монотонной на этом промежутке.

Заметим, что если f – монотонная функция на промежутке D (f (x)), то уравнение f (x) = const не может иметь более одного корня на этом промежутке.

Перечислим свойства монотонных функций (предполагается, что все функции определены на некотором промежутке D).

  • Сумма нескольких возрастающих функций является возрастающей функцией.
  • Произведение неотрицательных возрастающих функций есть возрастающая функция.
  • Если функция f возрастает, то функции cf (c > 0) и f + c также возрастают, а функция cf (cn также возрастает.
  • Композиция g (f (x)) возрастающих функций f и g также возрастает.

Аналогичные утверждения можно сформулировать и для убывающей функции.

Точка a называется точкой максимума функции f, если существует такая ε-окрестность точки a, что для любого x из этой окрестности выполняется неравенство f (a) ≥ f (x).

Точка a называется точкой минимума функции f, если существует такая ε-окрестность точки a, что для любого x из этой окрестности выполняется неравенство f (a) ≤ f (x).

Точки, в которых достигается максимум или минимум функции, называются точками экстремума.

В точке экстремума происходит смена характера монотонности функции. Так, слева от точки экстремума функция может возрастать, а справа – убывать. Согласно определению, точка экстремума должна быть внутренней точкой области определения.

Если для любого (xa) выполняется неравенство f (x) ≤ f (a) то точка a называется точкой наибольшего значения функции на множестве D:

Если для любого (xb) выполняется неравенство f (x) > f (b) то точка b называется точкой наименьшего значения функции на множестве D.

Точка наибольшего или наименьшего значения может быть экстремумом функции, но не обязательно им является.

Точку наибольшего (наименьшего) значения непрерывной на отрезке функции следует искать среди экстремумов этой функции и ее значений на концах отрезка.

Источники:

http://biograf.academic.ru/dic.nsf/ruwiki/1583971/biograf.academic.ru/dic.nsf/ruwiki/95510

http://ido.tsu.ru/iop_res/bulevfunc/text/g15_5.html

http://studopedia.ru/7_87545_monotonnost-funktsiy.html

Ссылка на основную публикацию
Статьи на тему:

Adblock
detector