Фронтальный алгоритм решения SAT задачи
Автор: Сметанин Юрий Михайлович
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Математические основы программирования
Статья в выпуске: 4 (55) т.13, 2022 года.
Бесплатный доступ
Алгоритм вычисления семантического значения конъюнктивных формул вида $U = F(X_1, X_2,..., X_n)$ в неклассической пропозициональной логике $L_{S_{2}}$ также вычисляет множество всех решений логического уравнения $F({x_1}, {x_2},..., {x_n})= 1,$ где $F(X_1, X_2,..., X_n)$ - формула булевой алгебры множеств, составляющих дискретную диаграмму Венна. Элементы этих множеств являются неотрицательными целыми числами. На основе этого алгоритма строится новый алгоритм для решения задачи $ SAT$. Существенная разница между ним и семейством алгоритмов, основанных на $ DPLL $, и $ CDCL $, - замена булевых переменных множествами. Это позволяет эффективно проверить выполнимость не одного, а многих наборов значений логических переменных ${x_1}, {x_2},..., {x_n}$.
Неклассическая пропозициональная логика, основанная на модели с невырожденной булевой алгеброй, исчисление дискретных диаграмм венна, задача sat
Короткий адрес: https://sciup.org/143179245
IDR: 143179245 | DOI: 10.25209/2079-3316-2022-13-4-163-179
Список литературы Фронтальный алгоритм решения SAT задачи
- Ю. М. Сметанин. «Непарадоксальное логическое следование и проблема решения МЛ-уравнений», Программные системы: теория и приложения, 7:1(28) (2016), с. 99-115.
- Ю. М. Сметанин. «Верификация логического следования с использованием исчисления конституентных множеств и соответствий Галуа», Программные системы: теория и приложения, 8:2(33) (2017), с. 69-93.
- Ю. М. Сметанин. «Верификация логического следования в неклассической многозначной логике», Изв. ИМИ УдГУ, 50 (2017), с. 62-82.
- В. К. Финн. «О неаристотелевском строении понятий», Логические исследования, 2015, №21(1), с. 9-48.
- Б. А. Кулик, А. А. Зуенко, А. Я. Фридман. Алгебраический подход к интеллектуальной обработке данных и знаний, Изд-во Политехн. ун-та, СПб., 2010, , 235 с.
- ISBN: 978-5-7422-2836-3
