CONSTRUCTION OF GENERAL SUBSUMPTIVE SOLUTIONS OF BOOLEAN EQUATIONS VIA COMPLETE-SUM DERIVATION

Abstract

Boolean-equation solving permeates many diverse areas of modern science. To solve a system of Boolean equations, one usually combines them into an equivalent single Boolean equation {f(X) = 0} whose set of solutions is exactly the same as that of the original system of equations. One of the general classes of solutions for Boolean equations is the subsumptive general solution, in which each variable is expressed as an interval decided by a double inequality in terms of the succeeding variables. The solution validity depends on the satisfaction of a required consistency condition. In this study, we introduce a novel method (henceforth called the CS method) for producing subsumptive Boolean-equation solutions based on deriving the complete sum (CS(f(X)) of the pertinent Boolean function f(X). The complete sum CS(f(X)) is a disjunction of all prime implicants of f(X) and nothing else. It explicitly shows all information about f(X) in the most compact form. We demonstrate the proposed CS solutions in terms of four examples, covering Boolean algebras of different sizes and using two prominent methods for deriving CS(f(X)). Occasionally, the consistency condition results in a collapse of the underlying Boolean algebra into a smaller subalgebra. We also illustrate how an expansion tree (typically reduced to an acyclic graph) can be used to deduce a complete list of all particular solutions from the subsumptive solution. The present CS method yields correct solutions, since it fits into the frame of the most general subsumptive solution. Among competing subsumptive methods, the CS method strikes a reasonable tradeoff between the conflicting requirements of less computational cost and more compact form for the solution obtained. In fact, it is the second best known method from both criteria of efficiency and compactness of solution.