доопределить функцию так чтобы она была монотонной

Доопределить функцию так чтобы она была монотонной

Определение. Булева функция f(x₁, …, x_n) называется монотонной (принадлежит классу 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 (по Хэммингу) между наборами α=a₁… a_n и β=b₁… b_n и начнем строить цепочку наборов γ₀, …, γ_d такую, что

и любые два расположенных рядом набора γ_{i –1},γ_i (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. Сравниваем значения функции на наборах, соседних по первой переменной, то есть верхнюю половину столбца значений функции (вектор φ₁) с нижней половиной (вектор φ₁). Если условие φ₁φ₁ нарушено, то функция не монотонна, идем на конец.

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

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

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

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

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

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

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

где γ и δ – булевы векторы. Так как αβ, и булевы функции f₁(x₁, …, x_n), …, f_m(x₁, …, x_n) монотонны, то γδ. Поскольку функция f₀(y₁, …, y_m) также монотонна, то f₀(γ)≤ f₀(δ), следовательно, f(α)≤ f(β), то есть f(x₁, …, x_n) монотонна, и класс M замкнут. •

Доказательство. Рассмотрим немонотонную функцию f(x₁, …, x_n). Согласно утверждению о условии немонотонности, существует пара соседних наборов α=a₁… a_n и β=b₁… b_n таких, что αβ и f(α) > f(β), то есть

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

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

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

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

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

Источник

Подтверждение

Пример я сам придумал, поэтому здесь, да, всё очевидно.

Но вот если в нём разделить вектор значений пополам и сравнивать 1101 и 1110, то несмотря на предшествование эти наборы не сравнимы.

Но вот если в нём разделить вектор значений пополам и сравнивать 1101 и 1110, то несмотря на предшествование эти наборы не сравнимы.

Ну вот!
Если они не сравнимы, значит функция немонотонна.
Т.е. несравнимость этих половинок означает, что на некоторых наборах значений переменных условие монотонности выполняется, а на некоторых нет.
Причем наборы значений переменных здесь попарно сравнимы.

Всё таки не до конца понятно, но тем не менее, уже ближе к цели.

mad-math, ну, задайте вопросы )
Я с удовольствием отвечу.
Давайте так. Вот таблица для вашей функции.
000 1
001 1
010 0
011 1
100 1
101 1
110 1
111 0

Что мы видим?
Во-первых, мы видим, что все взятые наборы переменных сравнимы и значит сравнение значений функции на них легитимно.
Во-вторых мы видим, что если бы функция была монотонна, то две половинки вектора значений были бы сравнимы. Потому что под номерами 1), 2), 3), 4) после точки с запятой как раз выполняется поэлементное сравнение первой и второй половин вектора f.

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

Спасибо большое за желание помочь, просто мне неудобно напрягать людей.

Сейчас распишу мои размышления. Поправьте, если я где-то ошибаюсь.

Пусть есть функция `f(0001 0010)`.

Источник

Общие сведения

Функцией вида р = f(r) называется зависимость ее значения от переменной величины «r» или аргумента. Функциональные тождества бывают простыми и сложными. К первым относится класс выражений, состоящих из одной переменной простого типа. Во втором случае содержится несколько аргументов или аргумент является также функцией, т. е. подчиняется определенному закону.

Монотонной называется функция, постоянно убывающая или возрастающая на заданном промежутке. Если она постоянно убывает или возрастает, то считается строго монотонной. Пусть дана функция р = f(r). Она дифференцируема на некотором интервале (а;b), является возрастающей или убывающей, когда справедливы равенства f(r1) = f(r2) соответственно. Кроме того, нужно учитывать, что r1 =» следует заменить на строгий « »: f(r1) f(r2) соответственно. Вышеописанные понятия можно записать математическим способом, который считается более компактным:

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

Теорема о пределе

Теорема о пределе монотонной функции применяется для решения задач по высшей математике с использованием пределов. Ее формулировка следующая: если функция вида р = f(r) является дифференцируемой и монотонной на интервале (а;b), то в точке r0, принадлежащей заданному интервалу, она имеет конечные пределы с левой и правой стороны, а в точках r0 = a и r0 = b у нее существуют правосторонние и левосторонние границы.

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

Критерии возрастания и убывания

Существуют определенные признаки, по которым можно определить монотонность функции p = f(r) на некотором интервале (а;b). Для этого в математике есть еще три теоремы:

Первая теорема имеет такую формулировку: дифференцируемая функция p = f(r) на интервале (а;b) является убывающей, когда выполняется неравенство f'(r) = 0 соответственно (при r ∈ данному интервалу).

Формулировка следующего утверждения только для строго возрастающей монотонной функции. В первом случае должно выполняться не одно, а два условия: f'(r) > 0 и f'(r) тождественно не эквивалентна нулю на промежутке в любой точке, принадлежащей интервалу. Для строго убывающей условия немного отличаются от предыдущих: f'(r) 0.

Основные свойства

Для функций на интервале (а;b) существуют некоторые утверждения, позволяющие исследовать составные выражения, а также решать различные задачи. К свойствам монотонных функций относятся следующие:

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

Базовые знания

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

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

Нахождение производной

Для поиска производной необходимо выполнить такие шаги: вынести константу, упростить выражение и воспользоваться таблицей дифференциалов элементарных функций (рис. 1). Первые два элемента считаются подготовительными, поскольку позволяют оптимизировать процесс вычисления. Для упрощения следует применять формулы сокращенного умножения, свойства дробей, разложение на множители и т. д. После приведения выражения к упрощенному виду нужно воспользоваться таблицей производных элементарных функций.

Рисунок 1. Дифференциалы простых выражений.

Однако при решении задач не всегда попадаются простые выражения. Для составных существуют определенные правила:

Специалисты рекомендуют для проверки использовать программы, но это не значит, что задачи должны решаться только с помощью онлайн-сервисов и математических пакетов.

Корни уравнений и критические точки

Следующим этапом является решение равенства с неизвестным. Необходимо отметить, что уравнения делятся на следующие виды: линейные, квадратные, кубические, биквадратные, тригонометрические, логарифмические, степенные, показательные и иррациональные.

Источник

Доопределить функцию так чтобы она была монотонной

8.4.2.1. Монотонные и линейные функции

Все монотонные функции образуют класс М. Для отнесения произвольной функции из табл. 4.1 к этому классу необходимо сравнить ее значения на всех пяти парах сравнимых наборов: (0,0) ≤ (0,1), (0,0) ≤ (1,0), (0,0) ≤ (1,1), (0,1) ≤ (1,1), (1,0) ≤ (1,1). Среди функций двух переменных монотонными являются шесть функций: f₀, f₁, f₃, f₅, f₇, f₁₅.

Всякая линейная функция может быть представлена в виде линейного полинома Жегалкина:
(x₁. x_n) = a₀ ⊕ a₁x₁ ⊕. ⊕ a_ix_i ⊕. ⊕ a_nx_n, где a_i ∈ <0,1>, i = 0,1. n.

Все линейные функции образуют класс L. Для проверки произвольной функции на принадлежность классу L необходимо построить для нее полином Жегалкина.

Проверим на линейность некоторые функции из табл. 4.1. Очевидно, что в такой проверке не нуждаются функции f₀(x,y) = 0, f₃(x,y) = x, f₅(x,y) = y, f₆(x,y) = x ⊕ y, f₁₅(x,y) = 1.

Функции f₁₂(x,y) = и f₁₀(x,y) = могут быть приведены к полиномам вида f₁₂(x,y) = 1 ⊕ x и f₁₀(x,y) = 1 ⊕ y, являющимся линейными, что указывает на линейность этих функций.

Функция равнозначности f₉(x,y) = x ∼ y может быть представлена СДНФ вида xy ∨ . После замены символа дизъюнкции ∨ символом ⊕ функции mod 2, замены переменных с отрицаниями, раскрытия скобок и приведения подобных членов получим полином Жегалкина

Из линейности построенного полинома Жегалкина следует линейность функции f₉(x,y) = x ∼ y.

Для функции f₁(x,y) = xy (конъюнкция) полином Жегалкина строится тривиально: f₁(x,y) = xy = 0 ⊕ xy. Как видно, полином и соответственно функция конъюнкции нелинейны.

Нелинейность полученного полинома Жегалкина указывает на нелинейность дизъюнкции.

.

Построенный полином и, следовательно, функция Шеффера нелинейны. При построении полинома Жегалкина для функции Пирса f₈(x,y) = x ↓ y воспользуемся полиномом Жегалкина для дизъюнкции, так как из табл. 4.1 нетрудно увидеть, что функции Пирса и дизъюнкции инверсны:

.

Отсюда следует, что функция Пирса нелинейна.

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

Пред.Страница След.Страница Раздел Содержание

Источник

Доопределить функцию так чтобы она была монотонной

Пусть \(y = f\left( x \right)\) является дифференцируемой функцией на интервале \(\left( \right).\) Функция называется возрастающей (или неубывающей ) на данном интервале, если для любых точек \(, \in \left( \right),\) таких, что \( строго возрастающей на интервале \(\left( \right).\)

Аналогично определяются убывающая (или невозрастающая ) и строго убывающая функции.

Если функция \(f\left( x \right)\) дифференцируема на интервале \(\left( \right)\) и принадлежит к одному из четырех рассмотренных типов (т.е. является возрастающей, строго возрастающей, убывающей или строго убывающей), то такая функция называется монотонной на данном интервале.

Снова рассмотрим функцию \(y = f\left( x \right),\) считая ее дифференцируемой на некотором интервале \(\left( \right).\) Возрастание или убывание функции на интервале определяется по знаку первой производной функции.

Поскольку \(f’\left( c \right) \ge 0,\) то правая часть равенства неотрицательна. Следовательно, \[f\left( <> \right) \ge f\left( <> \right).\] т.е. функция \(y = f\left( x \right)\) является возрастающей на интервале \(\left( \right).\)

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

\(f’\left( x \right) \ge 0\;\forall\;x \in \left( \right);\)

Производная \(f’\left( x \right)\) тождественно не равна нулю ни в каком промежутке \(\left[ <,> \right] \in \left( \right).\)

Условие \(1\) содержится в теореме \(1\) и является признаком неубывающей функции. Дополнительное условие \(2\) требуется для того, чтобы исключить участки постоянства функции, в которых производная функции \(f\left( x \right)\) тождественно равна нулю.

На практике (при нахождении интервалов монотонности) обычно используется достаточное условие строгого возрастания или строгого убывания функции. Из теоремы \(2\) следует такая формулировка достаточного признака:

Соответственно, условие \(f’\left( x \right) строго убывающую функцию.

Число точек, в которых \(f’\left( x \right) = 0,\) является, как правило, конечным. Согласно теореме \(2\), они не могут плотно заполнять какой-либо промежуток в интервале \(\left( \right).\)

Приведем также признак строгого возрастания (убывания) функции в точке:

Если \(f’\left( <> \right) > 0\), то функция \(f\left( x \right)\) строго возрастает в точке \(\);

Если \(f’\left( <> \right) сумма функций \(f + g\) также возрастает (убывает) на этом интервале.

Если функция \(f\) возрастает (убывает) на интервале \(\left( \right),\) то противоположная функция \(-f\) убывает (возрастает) на этом интервале.

Если функция \(f\) возрастает (убывает) на интервале \(\left( \right),\) то обратная функция \(\large\frac<1>\normalsize\) убывает (возрастает) на этом интервале.

Если функции \(f\) и \(g\) возрастают (убывают) на интервале \(\left( \right)\) и, кроме того, \(f \ge 0\), \(g \ge 0\), то произведение функций \(fg\) также возрастает (убывает) на этом интервале.

Если функция \(g\) возрастает (убывает) на интервале \(\left( \right),\) а функция \(f\) возрастает (убывает) на интервале \(\left( \right),\) где \(g:\left( \right) \to \left( \right),\) то композиция функций \(f \circ g\) (т.е. сложная функция \(y = f\left( \right)\) также возрастает (убывает) на интервале \(\left( \right).\)

Данная функция является суммой функций \(\) и \(3.\)

Первую функцию \(\) можно рассматривать как произведение двух одинаковых функций \(\). Из примера \(1\) следует, что квадратичная функция \(\) строго возрастает при \(x \ge 0.\) Следовательно, функция \(\) также строго возрастает при \(x \ge 0\) на основании свойства \(4\).

Второе слагаемое \(3\) представляет собой трехкратную сумму функций \(\) и, поэтому, также является строго возрастающей (на основании свойства \(1\)).

Итак, исходная функция \(f\left( x \right) = + 3\) является суммой двух строго возрастающих функций и, следовательно, также строго возрастает при \(x \ge 0.\)

Для контроля рассмотрим также неравенство \(f’\left( x \right) Рис.5

Следовательно, на основании достаточного признака монотонности, функция строго возрастает при \(x \in \left( <\large\frac<1>\normalsize,\infty > \right)\) и строго убывает при \(x \in \left( <0, \large\frac<1>\normalsize> \right).\) Ее вид схематически приведен на рисунке \(10\).

На основании достаточного признака монотонности заключаем, что функция возрастает при \(x \in \left( <0,\large\frac<1><2>\normalsize> \right)\) и убывает при \(x \in \left( <\large\frac<1><2>\normalsize,1> \right).\) График функции представляет собой полуокружность с центром в точке \(\left( <\large\frac<1><2>\normalsize,0> \right)\) и радиусом \(<\large\frac<1><2>\normalsize>\) (рисунок \(14\)).

Источник