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

Abstract

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 B = { 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 B 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.