A Functional Approach to the Theory of Prime Implicants


Frank_Markham Brown, Sergiu Rudeanu


The theory of prime implicants has been developed independently to simplify truth-functions (Quine, 1952) and to solve inferential problems in propositional logic (Blake, 1937). The object of this paper is to generalize Blake's approach, which unlike Quine's is little known, in the setting of function theory. We begin by developing an axiomatic theory of prime implicants within the general framework of finite join semilattices; Blake's concepts of syllogistic representation and canonical form are defined naturally within this framework. We next specialize this axiomatic theory to simple Boolean functions (equivalently, propositional functions) to obtain the classical theory of prime implicants. Finally, we derive the theory of prime implicants for general Boolean functions, together with a few results specific to such functions.