RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 1997 Volume 241, Pages 72–96 (Mi znsl482)

This article is cited in 3 papers

Number representations of satisfiability

G. V. Davydova, I. M. Davydovab

a Institute of Transport Problems, Russian Academy of Sciences
b Saint-Petersburg State University

Abstract: Propositional formulas are represented by real-valued matrices in such way that unsatisfiability is proved to be equivalent to stable non-negative solvability of linear algebraic systems. Complete calculus for the generation of all non-negatively solvable linear homogeneous systems is presented as consequence.
Solvability of systems of linear inequalities with real coefficients and Boolean variables is reduced to satisfiability of some formula. Alternative's theorem is proved for solvability of such systems. The technique of implicit enumeration for the search of solutions both in considering systems and in a wide range of discrete optimization problems is described.

UDC: 510.64

Received: 19.02.1996


 English version:
Journal of Mathematical Sciences (New York), 2000, 98:4, 464–478

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024