Front-end algorithm for solving the SAT problem
Автор: Smetanin Yurii Mikhailovich
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Математические основы программирования
Статья в выпуске: 4 (55) т.13, 2022 года.
Бесплатный доступ
The algorithm for calculating the semantic value of conjunctive formulas of the form $U = F(X_1, X_2,..., X_n)$ in non-classical propositional logic $L_{S_{2}}$ also calculates the set of all solutions of the logical equation $F({x_1}, {x_2},..., {x_n})= 1.$ Where $F(X_1, X_2,..., X_n)$ - a formula of Boolean algebra of the sets making a discrete Venn diagram. The elements of these sets are non-negative integers. Based on this algorithm, a new algorithm is built to solve the $ SAT $ problem. A significant difference between it and a family of algorithms based on $ DPLL $ and $ CDCL $ is the replacement of Boolean variables with sets. This allows you to effectively check the feasibility of not one, but many sets of values of the logical variables ${x_1}, {x_2},..., {x_n}$.
Задача sat
Короткий адрес: https://sciup.org/143179245
IDR: 143179245 | DOI: 10.25209/2079-3316-2022-13-4-163-179