Алгоритм деления пополам для произвольной булевой функции

[involume]

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

[nikvic]

Что это за зверь - алгоритм деления пополам - применительно к булевой функции? Что за результат должен получиться?

[involume]

Результатом должно быть монотонна ли функция или нет.

[involume]

В общем может это сейчас будет странная формулировка, что надо вообще сделать. Есть алгоритм деления пополам. Вот пример

Цитата:

По вектору значений $f= 10011111$ выяснить, является ли функция f
монотонной.

Решение. Поделим вектор пополам, тогда $1001=<1111$ . На следующем
шаге отношение предшествования нарушается для пары $10=<01$, а
$11=<11$ . Таким образом, заданная функция не является монотонной.

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

[nikvic]

Теперь задача понятна: по записи булевой функции установить её монотонность/немонотонность.
Алгоритма пока нет, т.к. отсутствует какой-либо "принцип" перехода от отрезка к левой/правой его половине в случае неопределённости. Стандартные метОды - просмотр графа (у нас - дерева) в глубину либо в ширину.

[Sender]

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

[Joker_vD]

Хм, интересный алгоритм, но на практике слабо применимый... потому что на практике вы будете вектор значений булевой функции представлять как массив байтов, в каждом из которых упаковано восемь значений (т.е. эдакое big-endian число). А это значит, что эффективный алгоритм следующий:

bool checkMonotonicity(byte* arr, size_t len) {
  for (int i = 0; i < len - 1; i++) {
    if ((!isMonotonicThreeArgBoolFunction(arr[i]) || (arr[i] > arr[i+1])) return false;
  }
  return isMonotonicThreeArgBoolFunction(arr[len - 1]);
}

где isMonotonicThreeArgBoolFunction имеет прототип bool isMonotonicThreeArgBoolFunction(byte); и проверяет, является ли заданная байтом (восемью битами) булевая функция монотонной. Я бы ее сделал lookup-таблицей, или даже свитчем: не так уж и много монотонных булевых функций от трех переменных.

[involume]

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

[nikvic]

involume в сообщении #669380 писал(а):

Теперь вопрос, как это доказать математически, что это можно сделать?

Что именно? Сформулируйте себе точный вопрос - получите 90% ответа

[involume]

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

[nikvic]

Я уже заметил, что алгоритма-то у Вас пока нет. Есть что-то вроде "исчисления", когда из данной "позиции" разрешается несколько ходов. Алгоритм появится после уточнения правила выбора конкретного хода.
Попробуйте самостоятельно уточнить, 1/ что у Вас является позицией и 2/ почему разрешённые ходы продвигают к ответу.

[involume]

Собственно сегодня ещё уточнил. Есть алгоритм проверки на монотонность функции, причём абсолютно произвольной, с помощью машины Тьюринга. Сам алгоритм:
1. Сравниваем соседние биты пары, затираем пару. Формируем справа
строки из первых $Q_1$ и вторых $Q_2$ эл-в пар ($Q_1 , Q_2$ соответственно).
Повторяем до тех пор пока не сотрем исходную строку значений с ленты или пока не встретится пара с отношением $Q_1>Q_2$, во втором случае функция не монотонна.
2. Склеиваем получившиеся строки $Q_1 и Q_2$. Переходим к 1 шагу
алгоритма. Цикл повторяется $N$ раз, где $N$ число аргументов функции.
3. Если цикл выполняется $N$ раз ф-ция монотонна.

Теперь это надо как-то в виде состояний записать вида $q a \to q b D$

[nikvic]

involume в сообщении #669773 писал(а):

Есть алгоритм проверки на монотонность функции, причём абсолютно произвольной, с помощью машины Тьюринга.

Лучше на менее "примитивном" уровне. По факту Вы будете иметь дело со списками значений функции на гранях двоичного куба: фиксируется начальный кусок аргументов, ему сопоставляется грань в виде фрагмента исходной записи. Далее нужно определить, какую грань будем "резать".
Например, сам список организовать как стек или очередь - получатся известные приёмы просмотра дерева вглубь либо в ширину.

[involume]

А если без всякого булева куба, например взять 10101111 и попробовать этот алгоритм записать в виде состояний машины Тьюринга. Просто судя по алгоритму у нас будет 4 состояния и каждый раз они будут повторяться, так как цикл повторяется N раз. Сам алфавит это собственно строка значений булевой функции. Или я что-то не так пишу?

[nikvic]

involume в сообщении #669807 писал(а):

попробовать этот алгоритм записать в виде состояний машины Тьюринга

Это зависит от цели. Можно и ПК под Тьюринга перекрасить