THE INVERSE PROBLEM FOR BOOLEAN EQUATIONS | Science Publications

Journal of Computer Science

Hussain Mobarak Albarakati¹  Ali Muhammad Ali Rushdi¹ 

关键词: Inverse Problem;    Boolean Equations;    Subsumptive General Solutions;    Parametric General Solutions;    Particular Solutions;   

DOI  :  10.3844/jcssp.2012.2098.2105

学科分类：计算机科学（综合）

来源: Science Publications

【 摘 要 】

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.

【 授权许可】

Unknown