Journal of Computer Science

The Inverse Problem for Boolean Equations

Ali Muhammad Ali Rushdi and Hussain Mobarak Albarakati

DOI : 10.3844/jcssp.2012.2098.2105

Journal of Computer Science

Volume 8, Issue 12

Pages 2098-2105


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): Bn → 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.


© 2012 Ali Muhammad Ali Rushdi and Hussain Mobarak Albarakati. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.