RO  EN
IMI/Publicaţii/CSJM/Ediţii/CSJM v.8, n.1 (22), 2000/

Reduction algorithms for solving large systems of logical equations

Authors: A.Zakrevskij

Abstract

Large systems of logical equations are considered in this paper, each depending on a restricted number of variables. A method of reduction is suggested that reduces the number of roots in separate equations, which in its turn saves time spent for finding roots of the whole system. Three mechanisms of reduction are proposed, each looking for some prohibited combinations of variables in separate equations (combinations that do not satisfy the equations). The first procedure looks for constants (prohibited values of some variables, or 1-bans). The second one looks in a similar way for prohibited combinations of values on pairs of variables (2-bans) and finds all their logical consequences closing the set of discovered 2-bans. The third analyses the equations by pairs, finds r common variables for them, and checks one by one all different combinations of their values looking for prohibited ones (r-bans). The found bans are used for deleting some roots in other equations. After this new bans could be found, so the procedure of reduction has the chain nature. It greatly facilitates solving large systems of logical equations. Sometimes it is enough to find the only root of a system or prove its inconsistency.

A.D.Zakrevskij
Institute of Engineering Cybernetics,
National Academy of Sciences, Belarus,
Surganov str. 6, Minsk, 220012,
Phone: 172-842182
e-mail:



Fulltext

Adobe PDF document – 0.14 Mb