Research Article Open Access

The Inverse Problem for Boolean Equations

Ali Muhammad Ali Rushdi1 and Hussain Mobarak Albarakati1
  • 1 King Abdulaziz University, Saudi Arabia
Journal of Computer Science
Volume 8 No. 12, 2012, 2098-2105

DOI: https://doi.org/10.3844/jcssp.2012.2098.2105

Submitted On: 15 October 2012 Published On: 3 January 2013

How to Cite: Rushdi, A. M. A. & Albarakati, H. M. (2012). The Inverse Problem for Boolean Equations. Journal of Computer Science, 8(12), 2098-2105. https://doi.org/10.3844/jcssp.2012.2098.2105

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

  • 1,270 Views
  • 1,674 Downloads
  • 3 Citations

Download

Keywords

  • Inverse Problem
  • Boolean Equations
  • Subsumptive General Solutions
  • Parametric General Solutions
  • Particular Solutions