Введение
Порядок-сохраняющая математическая функция
В математике монотонная функция (или монотонная функция) — это функция между упорядоченными множествами, которая сохраняет или меняет на противоположный заданный порядок. Эта концепция впервые возникла в математическом анализе и позднее была обобщена в более абстрактном контексте теории порядка.
В исчислении и анализе
В математическом анализе функция, определенная на подмножестве действительных чисел со значениями в действительных числах, называется монотонной, если и только если она либо всюду невозрастающая, либо всюду не убывающая. Аналогично, меняя знак неравенства, можно определить понятие строго убывающей (также убывающей) функции. В этом контексте термин "монотонное преобразование" относится к положительному монотонному преобразованию и используется для его отличия от "отрицательного монотонного преобразования", которое меняет порядок чисел на обратный.
В контексте алгоритмов поиска
В контексте алгоритмов поиска монотонность (также называемая согласованностью) является условием, применяемым к эвристическим функциям. Эвристика является монотонной, если для каждого узла n и каждого его преемника n', полученного в результате любого действия a, оценочная стоимость достижения цели из n не превышает стоимость перехода к n' плюс оценочная стоимость достижения цели из n'.
Это форма неравенства треугольника, где n, n' и целевой узел Gn расположены таким образом, что Gn наиболее близок к n. Поскольку любая монотонная эвристика также является допустимой, монотонность является более строгим требованием, чем допустимость. Некоторые эвристические алгоритмы, такие как A*, могут быть доказаны оптимальными при условии, что используемая ими эвристика монотонна.
В булевых функциях
В булевой алгебре монотонная функция – это функция, для которой для всех ai и bi в {0,1}, если a1 ≤ b1, a2 ≤ b2, ..., an ≤ bn (т.е. декартово произведение {0, 1}^n упорядочено по координатам), то f(a1, ..., an) ≤ f(b1, ..., bn). Иными словами, булева функция монотонна, если для каждой комбинации входов переключение одного из входов с ложного на истинное может привести только к переключению выхода с ложного на истинное, но не с истинного на ложное. Графически это означает, что n-арная булева функция монотонна, когда её представление в виде n-мерного куба, помеченного значениями истинности, не имеет ребра, идущего сверху вниз (от истинного к ложному). (Эта помеченная диаграмма Хассе является двойственной к помеченной диаграмме Венна, которая является более распространенным представлением для n ≤ 3). Монотонные булевы функции – это именно те, которые могут быть определены выражением, комбинирующим входные данные (которые могут встречаться более одного раза) с использованием только операторов И и ИЛИ (в частности, оператор НЕ запрещен). Например, "по крайней мере два из a, b, c истинны" – это монотонная функция от a, b, c, поскольку её можно записать, например, как ((a И b) ИЛИ (a И c) ИЛИ (b И c)). Количество таких функций на n переменных известно как число Дедекинда для n.
Решение задачи SAT, как правило, NP-трудная задача, может быть выполнено эффективно, когда все задействованные функции и предикаты являются монотонными и булевыми.