A Novel Method for Compact Listing of All Particular Solutions of a System of Boolean Equations

Abstract

Any system of ‘big’ Boolean equations can be reduced to a single Boolean equation {g(Z) = 1} . We propose a novel method for producing a general parametric solution for such a Boolean equation without attempting to minimize the number of parameters used, but instead using independent parameters belonging to the two-valued Boolean algebra B2 for each asserted atom that appears in the discriminants of the functiong(Z). We sacrifice minimality of parameters and algebraic expressions for ease, compactness and efficiency in listing all particular solutions. These solutions are given by additive formulas expressing a weighted sum of the asserted atoms of g(Z), with the weight of every atom (called its contribution) having a number of alternative possible values equal to the number of appearances of the atom in the discriminants of g(Z) . This allows listing a huge number of particular solutions within a very small space and the possibility of constructing solutions of desirable features. The new method is demonstrated via three examples over the ‘big’ Boolean algebras,B4,B16, and B256, respectively. The examples demonstrate a variety of pertinent issues such as complementation, algebra collapse, incremental solution, and handling of equations separately or jointly.