On ‘Big’ Boolean-Equation Solving and Its Utility in Combinatorial Digital Design

This chapter considers the problem of solving a system of Boolean equations over a finite (atomic)
Boolean algebra other than the two-valued one. A prominent “misnomer” in mathematical and
engineering circles is the term ‘Boolean algebra’. This term is widely used to refer to switching
algebra, which is just one particular case of a ‘Boolean algebra’ that has 0 generators, 1 atom and two
elements belonging to B2 = {0, 1}. The chapter 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 chapter 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