On the Relationship between Parsimonious Covering and Boolean Minimization

Minimization of Boolean switching functions is a basic problem in the design of logic circuits. The designer first comes up with a switching function expressed in terms of several binary input variables that satisfies the desired functionality, and then attempts to minimize the function as a sum of products or product of sums. It turns out that a sum of products form of a switching function that has no redundancy is a union of prime implicants of the function. In this paper we would like to explicate some of the relationships of the boolean minimization problem to a formalization of abductive inference called parsimonious covering. Abductive inference often occurs in diagnostic problems such as finding the causes of circuit faults [Reiter, 87] or determining the diseases causing the symptoms reported by a patient [Peng and Reggia, 90]. Parsimonious covering involves covering all observed facts by means of a parsimonious set of explanations that can account for the observations. The relationship of parsimonious covering to boolean minimization has been noted by the developers of the theory; we intend to pursue a detailed mapping here