Здравствуйте! У меня очередной дурацкий вопрос. Я не до конца понимаю, что такое монотонность. Вот есть функция $%0011001100110011$%. Утверждается, что она монотонна. Я вот чего не понимаю - как она может быть монотонной, если наборы из $%0$% и $%1$% для аргументов идут по возрастанию, а у нас на наборе, к примеру 4-ом идёт $%1$%, а затем на наборе 5-ом (который по идее больше) идёт $%0$%?

И еще можно простые примеры монотонных функций? Если я правильно понимаю, конъюнкция и дизъюнкция - монотонны.

И ещё вопрос - как проще всего определить, что функция монотонна или нет, если:

  1. задана формулой
  2. если задана последовательностью $%0$% и $%1$%.

задан 11 Окт '15 22:59

изменен 14 Окт '15 22:16

10|600 символов нужно символов осталось
3

Здесь рассматривается функция от 4-х переменных. На 4-м наборе она равна $%f(0,0,1,1)=1$%, а на 5-м наборе будет $%f(0,1,0,0)=0$%. Никакого противоречия тут нет, ибо наборы не сравнимы. Надо иметь в виду, что $%k$%-й набор связан с двоичной записью числа $%k-1$%. В этом смысле, первый по счёту набор удобнее было бы называть нулевым.

Функция, заданная строкой 0011, повторённой 4 раза, есть не что иное как $%f(x_1,x_2,x_3,x_4)=x_3$%. Это тождественная функция; она монотонна.

Все монотонные функции (не считая констант) представляются в виде конъюнкции дизъюнкций, а также в виде дизъюнкции конъюнкций. Скажем, $%x_1x_3\lor x_1x_4x_5\lor x_2x_4$% или $%(x_2\lor x_5)(x_1\lor x_3)x_4$%.

Если функция задана формулой общего вида, то без упрощений непонятно даже то, является ли она тождественно нулевой. Если переменных много, то для выяснения этого требуется порядка $%2^n$% операций (таблица истинности), а можно ли это сделать принципиально быстрее -- знаменитая открытая проблема.

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

Надо иметь в виду, что для всех остальных классов есть более удобные критерии, позволяющие осуществить подсчёт количества функций от $%n$% переменных из этого класса. Для монотонных функций такой подсчёт проведён только для сравнительно небольших $%n$%. Общей точной формулы для всех $%n$% не известно -- это проблема Дедекинда. Известны лишь асимптотические формулы. Если бы был простой и удобный критерий помимо перебора, то и подсчёт был бы на этой основе возможен.

P.S. Для строк небольшой длины можно сравнительно быстро проверить функцию на монотонность. Скажем, пусть строка имеет вид 0101011101110111. Напишем её "половинки" друг над другом. Легко видеть, что вторая половинка будет больше (не меньше) первой. То же самое свойство должно быть верно для половинок половинок (0101 < 0111), для половинок половинок половинок (01 < 11) и так далее. Тогда функция монотонна.

То, что я написал в примере, есть $%x_1x_3\lor x_2x_3\lor x_4$%.

ссылка

отвечен 11 Окт '15 23:36

изменен 11 Окт '15 23:45

@falcao: У меня всё же вопрос насчет метода определения монотонности функции. Вот возьмем мою: 0011001100110011. Берем половинки:

00110011

00110011

Все нормально, идём дальше. Напишем половинки половинок:

0011

0011

0011

0011

Все тоже хорошо, идем дальше. Берем половинки половинок половинок:

00

11

Они одинаковые, все писать не буду, все тоже хорошо. Дальше мы делим до 1 цифры, то есть:

0

0

1

1

Тут все нормально. И на этом останавливаемся? Так?

(12 Окт '15 20:50) Math_2012

@Math_2012: всё так, но только здесь не надо одинаковые вещи повторять. Первый тест прошёл, половинки одинаковы. Далее анализируем их (один раз!). Новый тест даёт одинаковые 0011. Далее 00 <= 11 поразрядно. На 00 и 11 можно остановиться.

(12 Окт '15 21:36) falcao

@falcao: Ну, да, можно не повторять, это я механически...

(12 Окт '15 21:45) Math_2012
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,333
×150
×16

задан
11 Окт '15 22:59

показан
8735 раз

обновлен
14 Окт '15 22:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru