RUS  ENG
Full version
JOURNALS // Program Systems: Theory and Applications // Archive

Program Systems: Theory and Applications, 2022 Volume 13, Issue 4, Pages 163–179 (Mi ps412)

This article is cited in 1 paper

Mathematical Foundations of Programming

Front-end algorithm for solving the SAT problem

Yu. M. Smetanin

Udmurt State University, Izhevsk, Russia

Abstract: 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}$.

Key words and phrases: non-classical propositional logic based on a model with non-degenerate Boolean algebra, calculus of discrete Venn diagrams, problem SAT.

UDC: 519.68:510.64
BBK: 22.12

MSC: Primary 08A70; Secondary 03G05, 93B60

Received: 14.10.2022
Accepted: 10.11.2022

DOI: 10.25209/2079-3316-2022-13-4-163-179



© Steklov Math. Inst. of RAS, 2025