Мысль изреченная есть ложь.
Созданное Игорем Алексеевичем Рябининым в 60–х годах ХХ века логико–вероятностное исчисление (ЛВИ) – специальный раздел дискретной математики (обычно применяемый для определения надежности технических устройств), в котором установлены четкие правила вычисления вероятности истинности любой булевой функции Y(x1,…, xi,…,xm), представленной посредством арифметических операций умножения (*),сложения (+), вычитания (-) путем замещения булевых аргументов (xi) вероятностями их истинности Р{xi=1}.
Правила ЛВИ просты.
Конъюнкция заменяется арифметическим умножением И(a,b)=a*b.
Дизъюнкция заменяется по правилу ИЛИ(a, b) = a+b-a*b
HE(a) = 1-a
Р{xi^n=1} = Р{xi=1}
Задачу SAT можно свести к представлению данной булевой формулы с помощью арифметических операций согласно правил ЛВИ.
Незаданные (неизвестные) аргументы функции Y(x1,…,xi,…,xm) могут принимать значения 0 или 1 с равной вероятностью, следовательно, вероятность истинности каждого неизвестного аргумента равна ½. Если при присвоении каждой переменной значения ½ выходное значение преобразованной формулы больше 0, то данная формула выполнима.
Сложность вычислимости зависит от существования компактных форм представления преобразованных согласно правил ЛВИ конкретных формул, вопросы получения которых относятся к области упрощения выражений. Для бесповторных компактных булевых формул (каждый аргумент встречается один раз) вопрос решен на момент созания Рябининым И.А. ЛВИ.
Правила ЛВИ просты.
Конъюнкция заменяется арифметическим умножением И(a,b)=a*b.
Дизъюнкция заменяется по правилу ИЛИ(a, b) = a+b-a*b
HE(a) = 1-a
Р{xi^n=1} = Р{xi=1}
Задачу SAT можно свести к представлению данной булевой формулы с помощью арифметических операций согласно правил ЛВИ.
Незаданные (неизвестные) аргументы функции Y(x1,…,xi,…,xm) могут принимать значения 0 или 1 с равной вероятностью, следовательно, вероятность истинности каждого неизвестного аргумента равна ½. Если при присвоении каждой переменной значения ½ выходное значение преобразованной формулы больше 0, то данная формула выполнима.
Сложность вычислимости зависит от существования компактных форм представления преобразованных согласно правил ЛВИ конкретных формул, вопросы получения которых относятся к области упрощения выражений. Для бесповторных компактных булевых формул (каждый аргумент встречается один раз) вопрос решен на момент созания Рябининым И.А. ЛВИ.
-
-
02.05.2009 в 23:21-
-
03.05.2009 в 03:31Я боюсь, что у Вас часть доказательства оказалась "съеденной"
Дело в том, что знаки > и < используются для обрамления тегов.
Поэтому иногда они себя мыслят служебными символами и стирают все, что между ними оказывается.
Поэтому когда вы их используете, то выделяйте и нажимайте кнопку Unicodе.
Это я на всякий случай Вас информирую.
Формулы можно набирать в ворде и вставлять в виде графических файлов.
-
-
03.05.2009 в 13:13Спасибо!
Сейчас готовлю второе приближение обоснования ЛВИ. Надеюсь, более удобоваримое.
-
-
03.05.2009 в 14:38Рассмотрим многочлен от n переменных Y (сумму произведений произвольных комбинаций от n переменных с весовыми коэффициентами) в каноническом виде.
Переменные могут находиться в произведениях в произвольных степенях.
Переменные принимают значения из непересекающихся множеств.
Количество принимаемых некоторой переменной значений может не совпадать с количестом значений, принимаемых другой переменной.
Многочлен приведен к виду Y1, когда все его переменные представлены в 1-й степени путем ввода новых переменных. Причем
если xk=xi^j1 xl=xi^j2, и j1не= j2, то xk не=xl;
если xk=xi1^j xl=xi2^j, то xk не=xl.
Доказательство обоснования ЛВИ для простоты понимания (мною самим
1.Среднее значение всех возможных значений многочлена Y1 - S равно значению Y1, где каждой переменной xi подставлено ее среднее значение si. (Доказательство готовлю. О нем можно составить представление по первому приближению обоснования ЛВИ.)
2. В нашем случае каждая переменная двоичная, следовательно средние значение ее совпадает с вероятностью истинности, и P(xi^p)= Р(xi). Учитывая утверждаемое в п.1 получаем обоснование ЛВИ.
-
-
03.05.2009 в 15:58У меня сейчас, к сожалению, нет времени глубоко вникать в ЛВИ, но даже если то, в чём я усомнился ранее, верно, это всё рано ничего не меняет.
Предложенный Вами метод позволяет проверить выполнимость функций, записанных только в (С)К/ДНФ, что можно сделать за полиномиальное время и не прибегая к ЛВИ.
Однако, функции, представленные в (С)К/ДНФ - далеко не все булевы функции. Разумеется, любую функцию в этой форме можно представить; только вот незадача: Это делается за O(en).
Таким образом, Ваше "решение" задачи SAT всё равно не является полиномиальным.
-
-
04.05.2009 в 14:59Представлять БФ в СДНФ/СКНФ не проще, чем комбинации перебирать.
Получить ЛВИ в канонической форме можно для любой БФ.
Сложность выполнимости зависит от существования компактных форм конкретных ЛВИ , вопросы получения которых относятся к области упрощения выражений. Для бесповторных компактных булевых формул (каждый аргумент встречается один раз) вопрос решен на момент созания Рябининым И.А. ЛВИ (там ничего упрощать не надо). Правда толку от бесповторных БФ мало.
Если существует компактная форма ФВИ для данной булевой функции, которая позволяет определять вычислимость за полиномиальное время то задача SAT решается за это время. Что давало бы эффективный способ решать булевы уравнения. Я не говорил, что сам поиск компактной формы - простая задача. Бесплатный сыр сами знаете,где. Это та задача, которой возможно, будут загружаться растущие компьютерные мощости будущего. Может быть, это альтернатива квантовому компьютеру.
Нельзя объять необъятое, однако
И заодно выпить море
А обоснование ЛВИ доделываю, это интересно!
-
-
04.05.2009 в 16:53Рассмотрим многочлен от n переменных Y (сумму произведений произвольных комбинаций от n переменных с весовыми коэффициентами) в каноническом виде.
Переменные могут находиться в произведениях в произвольных степенях.
Переменные принимают значения из непересекающихся множеств.
Количество принимаемых некоторой переменной значений может не совпадать с количеством значений, принимаемых другой переменной.
Доказательство обоснования ЛВИ разделено на 2 части.
1.Среднее значение всех возможных значений многочлена Y - S равно значению Y, где каждой переменной xi подставлено ее среднее значение si.
КВЗА- количество возможных значений аргумента
СВВЗ– сумма всех возможных значений
ПВА Y -произведение всех аргументов Y
СВВЗПВА Y – сумма всех возможных значений произведения всех аргументов Y
Очевидно, СВВЗПВА Y равна произведению СВВЗ его аргументов.
Значение каждого входящего в Y произведения Т можно получить из ПВА Y , заменив в нем единицей каждый отсутствующий в Т аргумент и добавив оставшимся аргументам степени, в которых они находятся в Т.
Следовательно, частичная СВВЗ Y для Т может быть получена из СВВЗПВА Y путем замены СВВЗ отсутствующих в Т аргументов их КВЗА, а СВВЗ аргументов, представленных в степенях – СВВЗ представленных в соответствующих степенях аргументов.
Учитывая весовые коэффициенты получим S - СВВЗ многочлена Y. Поделив S на количество возможных комбинаций аргументов Y (произведение всех КВЗА) , сократив дроби, подставив вместо каждого результата деления СВВЗ аргумента на его КВЗА соответствующее среднее , получим что
Среднее значение всех возможных значений многочлена Y - S равно значению Y, где каждой переменной xi подставлено ее среднее значение si
2. В нашем случае каждая переменная двоичная, следовательно средние значение ее совпадает с вероятностью истинности, и P(xi^p)= Р(xi).
Заданный многочлен - булева функция в арифметической форме, он принимает при бинарных аргументах бинарные значения. Следовательно среднее значение булевой функция в арифметической форме совпадает с ее вероятностью истинности. Учитывая утверждаемое в п.1, получаем обоснование ЛВИ.
-
-
04.05.2009 в 17:31[CrazyPensil]
Вам, похоже, интереснее искать ошибки, чем вникать в суть.
Представлять БФ в СДНФ/СКНФ не проще, чем комбинации перебирать.
Получить ФВИ в канонической форме можно для любой БФ.
Сложность выполнимости зависит от существования компактных форм конкретных ФВИ , вопросы получения которых относятся к области упрощения выражений. Для бесповторных компактных булевых формул (каждый аргумент встречается один раз) вопрос решен на момент созания Рябининым И.А. ЛВИ (там ничего упрощать не надо). Правда толку от бесповторных БФ мало.
Если существует компактная форма ФВИ для данной булевой функции, которая позволяет определять вычислимость за полиномиальное время то задача SAT решается за это время. Что давало бы эффективный способ решать булевы уравнения. Я не говорил, что сам поиск компактной формы - простая задача. Бесплатный сыр сами знаете, где. Это та задача, которой возможно, будут загружаться растущие компьютерные мощности будущего. Может быть, это альтернатива квантовому компьютеру.
Найден помимо полного перебора еще один общий метод решения булевых уравнений.
Не верь глазам своим 0_о!
Бди 0_0 !
-
-
04.05.2009 в 21:01Так точно. Изучить ЛВИ я всегда успею, но сейчас я весьма и весьма занят. А вот повторить и покопаться в чём-то уже известном ничто не мешает.
Лично я просто не вижу смысла в Ваших экскавациях. Поскольку для использования Вашего метода требуется БФ, представленная только через И, ИЛИ и НЕ, к его трудоёмкости нужно прибавить время, затраченное на преобразование этой БФ в требуемый вид. Что на данный момент делается только за экспоненту. Очевидно, что в дальнейшем Ваш метод более трудоёмкий, чем обычный способ проверить (С) Д/К НФ. Зачем же тогда мучаться?
-
-
04.05.2009 в 22:58Задача института Клэя.
м=100 мест в общаге, п=400 претендентов,
список из нежелательных пар ( в общем случае п*(п-1)/2=79800).
Ни одной нежелательной пары в общаге!
Задаем целевую булеву функцию.
Перебор - единственный выход.
Предлагается.
м и п посильные мозговым и вычислительным ресурсам.
Задаем целевую булеву функцию. Получаем для нее ФВИ. Находим варианты минимизованного представления ФВИ.
Обобщаем полученные результаты и оцениваем возможность масштабирования для случая м=100 , п=400.
По-моему, более перспективный вариант.
-
-
05.05.2009 в 03:21То, что вас является промежуточными шагами, по сути и имеет наибольшую трудоёмкость. В итоге к экспоненциальному времени прибавляется ещё и полином(кстати, степень может достигать очень высокой). А перебор делает это с гораздо, гораздо, гораздо меньшей константой.
-
-
05.05.2009 в 12:02Если пользоваться ФВИ, то можно пользоваться уменьшенной моделью, человеческий фактор (участие гениев, доказательство теорем) может сыграть свою роль.
-
-
05.05.2009 в 18:29-
-
19.05.2009 в 09:52К тому же, как верно заметил Trotil, если функция представлена в (К/Д)НФ, проверить её выполнимость очень просто и без всяких ЛВИ.
Если вы умеете просто проверять выполнимость КНФ, срочно сообщите в институт Клэя. Миллион долларов вас ждёт.
Однако, функции, представленные в (С)К/ДНФ - далеко не все булевы функции. Разумеется, любую функцию в этой форме можно представить; только вот незадача: Это делается за O(en).
Сокращённую КНФ или ДНФ из обычной КНФ или ДНФ можно сделать не быстрее, чем за Omega( (3^n) / n).
Trotil
А всего БФ - 16.
Булевых функций счётное число; функций, зависящих от n переменных, 2^{2^n}.
-
-
19.05.2009 в 11:02Не надо выдирать из контекста. В том абзаце шла речь о БФ от двух переменных.
-
-
19.05.2009 в 11:581) Вы привели арифм. операции для трех функций. А всего БФ - 16. Что делать, если, например, в БФ входит штрих Шеффера или стрелка Пирса?
Если считать схему данной булевой формулы графом, то, если узлом графа является БФ от 2-х переменных, отличная от И, ИЛИ она заменяется одним узлом И или ИЛИ с соответствующими инверсиями.
Например
Стрелка Пирса НЕ(ИЛИ(a,b))
Штрих Шефера НЕ(И(a,b))
Сумму по модулю 2 и ее инверсию в базис И.ИЛИ НЕ преобразовывать не надо, они и так прекрасно представляются арифметическими операциями
mod2(a,b)=a+b-2*a*b
НЕ(mod2(a,b))=1-(a+b-2*a*b)
2) Если я приведу класс БФ (небесповторных для них все очевидно, там просто заменяете в графе формулы булевы узлы арифметическими), для которого существуют простые формулы и полиномиальной сложности формулы проверки выполнимости, Вам это будет интересно?
Рад, что Вас все еще интересует эта тема.