Созданное Игорем Алексеевичем Рябининым в 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, то данная формула выполнима.
Сложность вычислимости зависит от существования компактных форм представления преобразованных согласно правил ЛВИ конкретных формул, вопросы получения которых относятся к области упрощения выражений. Для бесповторных компактных булевых формул (каждый аргумент встречается один раз) вопрос решен на момент созания Рябининым И.А. ЛВИ.