The Inverse Problem for Boolean Equations

Abstract

The Forward Problem (FB) of Boolean equations consists of finding solutions of a system of Boolean equations, or equivalently, a single Boolean equation of the form f(X) = 0 where f(X): Bⁿ → B and B is an arbitrary Boolean algebra. By contrast, the Inverse Problem (IB) of Boolean equations aims to reconstruct the equation f (X) = 0 given the set of solutions and hence to verify the correctness of this set. This study derives methods that handle this inverse problem for the main types of solutions of Boolean equations. These include: (a) Subsumptive general solutions, in which each of the variables is expressed as an interval by deriving successive conjunctive or disjunctive eliminants of the original function, (b) Parametric general solutions, in which each of the variables is expressed via arbitrary parameters which are freely chosen elements of the underlying Boolean algebra and (c) Particular solutions, each of which is an assignment from the underlying Boolean algebra to every pertinent variable that makes the Boolean equation an identity. The reconstructed function f(X) in every case is set in a canonical form, such as the complete-sum form, to facilitate proving its equivalence to the original function. The methods presented herein are demonstrated with carefully-chosen illustrative examples over big Boolean algebras of various sizes. Among the methods utilized in handling the inverse problem for Boolean equations, the ones utilizing the variable-entered Karnaugh map offered pictorial insight and exhibited an efficient divide-and-conquer strategy.