Мысль изреченная есть ложь.
Созданное Игорем Алексеевичем Рябининым в 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, то данная формула выполнима.
Сложность вычислимости зависит от существования компактных форм представления преобразованных согласно правил ЛВИ конкретных формул, вопросы получения которых относятся к области упрощения выражений. Для бесповторных компактных булевых формул (каждый аргумент встречается один раз) вопрос решен на момент созания Рябининым И.А. ЛВИ.
-
-
01.05.2009 в 11:49"Суть метода" примерно ясна. Но вот без деталей всё равно трудно понять, как же оно так получается.
И еще: под "разрешимостью" вы понимаете "выполнимость" или как в классическом определении — существование алгоритма проверки выполнимости?
-
-
01.05.2009 в 13:10Мило. А теперь докажите.
-
-
01.05.2009 в 13:40Выполнимость. Я посчитал эти слова синонимами.
Еще увидел неточность свою - вероятность истинности каждого незначимого аргумента равна ½ - это вероятность истинности каждого неизвестного аргумента равна ½.
Предложенный способ позволяет за один шаг определять выполнимость, а не за 2^n. Также выделяется класс булевых функций, у которых проверка проста. Насколько мне известно, проверка любой булевой функции на выпронимость считается NP -полной.
Закон сохранения не исчезает - сложность переходит в область поисков компактной формы "функции вероятности истинности", ЛВИ - аппарат обоснованный и за почти сорок лет не опровергнутый. Какие детали нужны? Проверка на примерах?
-
-
01.05.2009 в 13:49Попытайтель опровегнуть упомянутое Вами утверждение. В зависимости от ваших доводов выберу вариант доказательства.
-
-
01.05.2009 в 13:51Я пока не привожу никаких аргументов. Я вижу недоказанное утверждение, которое кажется весьма и весьма сомнительным.
-
-
01.05.2009 в 14:02Я, с вашего позволения, исправила в записи.
-
-
01.05.2009 в 14:07Предложенный способ позволяет за один шаг определять выполнимость, а не за 2^n.
Вот это понятно.
Способ позволяет.
Но нужно доказательство легитимности применения такого способа к произвольной булевой формуле.
Поэтому без подробного изложения тут не обойтись.
Кроме того, у меня сразу дилетантский вопрос.
Выходное значение формулы у вас изменяется от 0 до 1. Так? Если оно не равно нулю, то формула выполнима.
Вроде бы на пальцах достаточно понятно. Но ведь если мы получили какое-то конкретное значение, оно должно нести в себе еще какую-то дополнительную информацию?
Чем, к примеру, 1/2 отличается от 3/4? (Я имею в виду, что мы можем сказать об отличии двух формул с такими значениями?)
-
-
01.05.2009 в 14:07Разобьем Ваш вопрос на части.
Незаданные (неизвестные) аргументы функции Y(x1,…,xi,…,xm) могут принимать значения 0 или 1 с равной вероятностью, следовательно, вероятность истинности каждого незначимого аргумента равна ½.-это кажется Вам сомнительным?
-
-
01.05.2009 в 14:10Благодарю!
-
-
01.05.2009 в 14:34Чем, к примеру, 1/2 отличается от 3/4? (Я имею в виду, что мы можем сказать об отличии двух формул с такими значениями?)
В случае 1/2 - половину всех возможных значений булевой функции имеет составляют единичные, в случае 3/4 - 3/4 всех возможных значений булевой функции имеет составляют единичные.
Но нужно доказательство легитимности применения такого способа к произвольной булевой формуле.
Для любой булевой формулы можно найти соответствующую ей булеву функцию, которую можно представить в канонической форме и с помощью алгераических операций. Если пользоваться канонической формой представления, то на один шаг потратим время, аналогичное перебору возможных комбинаций переменных для заданной формулы. Если найдем компактную форму ( поиск может быть сложнее перебора комбинаций переменных )- получим уменьшение затрат.
-
-
01.05.2009 в 15:28В случае 1/2 - половину всех возможных значений булевой функции имеет составляют единичные, в случае 3/4 - 3/4 всех возможных значений булевой функции имеет составляют единичные.
Неужто всё так просто?
А как же сложение-умножение-сложность формулы? Это совсем не важно?
А насчет второго: тут всё-таки требуется четкое математическое доказательство.
Формулировка теоремы у вас есть. Теперь нужно доказать, что она всегда выполняется.
Конъюнкция заменяется арифметическим умножением И(a,b)=a*b.
Дизъюнкция заменяется по правилу ИЛИ(a, b) = a+b-a*b
HE(a) = a-1
Поправьте меня, если я понимаю всё не так:
Вот например, возьмем заведомо невыполнимую формулу: А ∧ не-А
А=1/2
не-А=-1/2
(1/2)(-1/2)=-1/4 не равно 0...
-
-
01.05.2009 в 16:21Спасибо за интерес !
Р{xi^n=1}
^n= Р{xi=1}Простите за опечатки, пожалуйста....Поправьте меня, если я понимаю всё не так:
Вот например, возьмем заведомо невыполнимую формулу: А ∧ не-А
А=1/2
не-А=-1/2
(1/2)(-1/2)=-1/4 не равно 0...
Все эти манипуляции с булевыми функциями - давняя рутина лабораторок по определению надежности неких устройств, схемы кототорых представлены булевыми формулами (функциями). Это не я придумал
А ∧ не(А ) = A*не(А ) = A*(1-A) = А - А^2
Р{xi^n=1}= Р{xi=1} следовательно А - А^2 = А - А
-
-
01.05.2009 в 16:33Все эти манипуляции с булевыми функциями - давняя рутина лабораторок по определению надежности неких устройств, схемы кототорых представлены булевыми формулами (функциями). Это не я придумал
я же не собираюсь уличать вас в несоответствиях.
Просто сталкиваюсь с этим впервые))
Р{xi^n=1}= Р{xi=1}
Гм... А это логично? Если это схема устройства, то степень — это последовательное соединение. Вероятность того, что оно всё вместе равно 1 — отнюдь не 1/2.
Хотя для формулы в принципе у меня возражений нет...
Разве что странновато всё это.
HE(a) = a-1
Это правильно?
Или всё-таки там 1-a должно быть?
-
-
01.05.2009 в 16:53В случае 1/2 - половину всех возможных значений булевой функции имеет составляют единичные, в случае 3/4 - 3/4 всех возможных значений булевой функции имеет составляют единичные.
Неужто всё так просто?
А как же сложение-умножение-сложность формулы? Это совсем не важно?
А насчет второго: тут всё-таки требуется четкое математическое доказательство.
Формулировка теоремы у вас есть. Теперь нужно доказать, что она всегда выполняется.
В таком случае стоит вопрос обоснованности ЛВИ. Я очень хотел бы найти четкие математическое доказательства прославленного участника Парада Победы, адмирала и академика, гордость СССР и России Игоря Алексеевича Рябинина. Я нашел только его книгу 1971 года, но там он сосредоточился на прикладном применении, математических доказательств там нет. Есть у него недавние издания в России, может там они есть? Не знаю, к кому обратиться за помощью в этом вопросе.
Я могу, конечно предоставить свое доказательство, но авторитет Рябинина кажется мне более веским.
Для любой булевой формулы можно найти соответствующую ей булеву функцию, которую можно представить в канонической форме и с помощью алгераических операций.
Вы предлагаете эту фразу в качестве формулировки теоремы?
-
-
01.05.2009 в 17:25Для любой булевой формулы можно найти соответствующую ей булеву функцию, которую можно представить в канонической форме и с помощью алгераических операций. Вы предлагаете эту фразу в качестве формулировки теоремы?
Нет, что вы!
Я о том же приблизительно, о чем [CrazyPensil]. Вот об этом:
Незаданные (неизвестные) аргументы функции Y(x1,…,xi,…,xm) могут принимать значения 0 или 1 с равной вероятностью, следовательно, вероятность истинности каждого неизвестного аргумента равна ½. Если при присвоении каждой переменной значения ½ выходное значение преобразованной формулы больше 0, то данная формула выполнима.
Это настоящая теорема.
И что бы вы ни говорили, такое утверждение я не могу принять на веру.
Может быть — совсем не исключено — от недостаточного понимания сути ЛВИ.
Но однако, если доказательство и очевидно, — его тем не менее всегда можно формализовать. Так, чтобы было "ёжику понятно".
Ну а вообще еще раз говорю: я не эксперт совсем.
Просто вполне возможно, что вы тут просто нечто революционное выложили. Ведь если всё так, что это должно быть научной сенсацией по крайней мере.
-
-
01.05.2009 в 17:32я же не собираюсь уличать вас в несоответствиях.
Просто сталкиваюсь с этим впервые))
Не обижайтесь. Это я подкреплял свою скромную фигуру могучими авторитетами
Р{xi^n=1}= Р{xi=1}
Гм... А это логично? Если это схема устройства, то степень — это последовательное соединение. Вероятность того, что оно всё вместе равно 1 — отнюдь не 1/2.
Хотя для формулы в принципе у меня возражений нет...
Разве что странновато всё это.
Непривычное всеми с трудом воспринимается. Подсознание тяжело включается. Но многие смело игнорируют непривычное, а Вы пытаетесь понять, это замечательно!
Процесс получения "функции вероятности истинности" идет в два этапа.
1. Выражаем булеву формулу с помощью арифметических операций. В случае бесповторных булевых функций на этом все и заканчивается, потому что при раскрытии скобок все переменные окажутся в первой степени.
2. Преобразуем полученную формулу так, чтобы при раскрытии скобок все переменные оказались в первой степени. Один из способов - раскрываем скобки и приравниваем все показатели степеней единице.(Вот что означает Р{xi^n=1}= Р{xi=1} ).
В противном случае значение получим не абсурдное, но ложное значение вероятности истинности, что самое неприятное, можно получить ненулевое значение при нулевой вероятности.
HE(a) = a-1
Это правильно?
Или всё-таки там 1-a должно быть?
Если не(а)=1-а
а=1 не(а)=0 1-1=0
а=0 не(а)=1 1-0=1
Если не(а)=а-1
а=1 не(а)=0 1-1=0
а=0 не(а)=1 0-1=-1 Не получится
-
-
01.05.2009 в 17:57> вероятности истинности любой булевой функции
что такое вероятность истинности булевой функции?
-
-
01.05.2009 в 18:31Если не(а)=а-1
а=1 не(а)=0 1-1=0
а=0 не(а)=1 0-1=-1 Не получится
Я поэтому и спросила.
Тогда у вас в записи неверная формула. Исправьте, пожалуйста.
Trotil
ты тоже с таким не сталкивался?
-
-
01.05.2009 в 19:24Нет.
Но я так понял, что это (число единиц)/2^n
Так или нет?
В связи с этим еще вопросы:
1) Вы привели арифм. операции для трех функций. А всего БФ - 16. Что делать, если, например, в БФ входит штрих Шеффера или стрелка Пирса?
-
-
01.05.2009 в 23:08Поправьте меня, но но ваши преобразования очень похожи на алгоритм получения из БФ полинома Жегалкина. Сложность вроде одинакова. И по полиному Жегалкина моментально можно установить, выполнима ли функция или нет.
-
-
02.05.2009 в 00:14Тогда у вас в записи неверная формула. Исправьте, пожалуйста.
Исправил.
Это настоящая теорема.
И что бы вы ни говорили, такое утверждение я не могу принять на веру.
Может быть — совсем не исключено — от недостаточного понимания сути ЛВИ.
Но однако, если доказательство и очевидно, — его тем не менее всегда можно формализовать. Так, чтобы было "ёжику понятно".
Ну а вообще еще раз говорю: я не эксперт совсем.
Просто вполне возможно, что вы тут просто нечто революционное выложили. Ведь если всё так, что это должно быть научной сенсацией по крайней мере.
Если доказательство будет предоставлено, это сделает ясным Ваше понимание предложенной мной идеи?
Можете найти книги Рябинина?
Рябинин И.А., Черкесов Г.Н. Логико-вероятностные методы исследования надёжности структурно сложных систем. - М.: Радио и связь, 1981. - 264 с.
Рябинин И. А. Надежность и безопасность структурно–сложных систем. – СПб.: Изд–во С.–Петерб. ун–та, 2007.
Если в этих книгах нет математического обоснования с доказательствами, то он ограничился интуитивными соображениями. В технике это часто работает. В статье ФЕНОМЕН ЛОГИКО-ВЕРОЯТНОСТНОГО ИСЧИСЛЕНИЯ Рябинин жаловался, что математики не придали значения ЛВИ. Но в технике идею пробил.
Что касается экспертов, мне важно, чтобы у Вас был интерес к теме и математическое высшее( даже неполное) образование. Я не вышел за рамки элементарных основ булевой алгебры и теории вероятности. И кто может стать экспертом? Сфера пограничная. Я обращался к спецам по дискретной математике, но никого, кроме его темы, ничего не интересует, вне зависимости от оригинальности. Можно причесать все это чудо, перевести на английский и послать в авторитетные западные журналы. Сам я это сделать не могу, я не математик, математическим красноречием не обладаю, английский знаю плохо и не могу с ними полноценно общаться.
Булева функция, представленная в арифметическом виде, обретает интересные свойства.
Рябинин применил то, до чего я дошел сам. Доказательство у меня есть. В том числе мат. основы ЛВИ. Мое личное. Пусть изложение стилистически не очень гладкое, но есть. Если оно покажется Вам убедительным, готовы ли Вы составить компанию в продвижении идеи в авторитетные математические западные журналы? Могу взять в соавторы.
Интересно, поддержал бы Камиль Жордан живого Галуа с его мерзким характером?
Trotil
что такое вероятность истинности булевой функции?
Но я так понял, что это (число единиц)/2^n
Так или нет?
В данном случае правильно
А всего БФ - 16. Что делать, если, например, в БФ входит штрих Шеффера или стрелка Пирса?
Основные пары операций И-НЕ, ИЛИ-НЕ. Остальные - в том числе Шеффера или стрелка Пирса - выражаются с помощью основных. Пишете для них таблицу истинности и выражаете в СКНФ или СДНФ.
-
-
02.05.2009 в 00:17Ну дык если записать в СКНФ или в СДНФ - сразу будет видна выполнимость. А записать через преобразования в виде полинома Жегалкина еще проще.
-
-
02.05.2009 в 00:29И по полиному Жегалкина моментально можно установить, выполнима ли функция или нет.
Как?
-
-
02.05.2009 в 00:34Aegypius Monachus
Разумеется, не эту часть. Если при присвоении каждой переменной значения ½ выходное значение преобразованной формулы больше 0, то данная формула разрешима - вот что вызывает недоумение. Звучит очень серьёзно и сомнительно, а доказательства нет.
К тому же, как верно заметил Trotil, если функция представлена в (К/Д)НФ, проверить её выполнимость очень просто и без всяких ЛВИ.
-
-
02.05.2009 в 00:49Вы сделали моим мозгам больно
Смысл изложенного в самом верху. Кратко.
Есть булева формула. Ее выполнимость можно проверить полным перебором аргументов. На данный момент.
Предлагается способ получения функции, подстановка в компактную форму (наверное, очень сложно получаемую для большиства булевых функций) которой, если она есть, некоторых чисел дает возможность гораздо более простого по сравнению с перебором аргументов определения выполнимости заданной булевой функции.
-
-
02.05.2009 в 00:50наверное, очень сложно получаемую для большиства булевых функций
Не наверное, а точно.
Не очень сложно, а экспоненциально.
-
-
02.05.2009 в 00:57Отлично. Доказательство в следующей серии.
Доброй ночи!
-
-
02.05.2009 в 00:58И вам тоже
-
-
02.05.2009 в 22:37Смысл изложенного в самом верху.
Есть булева формула. Ее выполнимость можно проверить полным перебором аргументов. На данный момент.
Предлагается способ получения арифметической функции, подстановка в компактную форму (наверное, очень сложно получаемую для большиства
булевыхфункций) которой, если она есть, некоторых чисел дает возможность гораздо более простого по сравнению с перебором аргументов определения выполнимости заданной булевой функции.Устал. Ошибся.
-
-
02.05.2009 в 22:39Удалено по просьбе автора.
А.Р.