Derivation of All Particular Solutions of a ‘Big’ Boolean Equation with Applications in Digital Design

This paper considers the problem of solving a system of Boolean equations over a finite (atomic) Boolean algebra other than the two-valued one. The paper outlines classical and novel direct methods for deriving the general parametric solution of such a system and for listing all its particular solutions. A detailed example over B256 is used to illustrate these two methods as well as a third method that starts by deriving the subsumptive solution first. The example demonstrates how the consistency condition forces a collapse of the underlying Boolean algebra to a subalgebra, and also how to list a huge number of particular solutions in a very compact space. Subsequently, the paper proposes some potential applications for the techniques of Boolean-equation solving. These techniques are very promising as useful extensions of classical techniques based on two-valued Boolean algebra.