Determination of the Irredundant Normal Forms of a Truth Function by Iterated Consensus of the Prime Implicants

Abstract

This paper describes a new algebraic way of determining irredundant forms from the prime implicants. The method does not require using the developed normal form, and it makes novel application of Quine's technique of iterative consensus-taking. Thus, by applying repeatedly the rule of consensus to the prime implicants, it is possible to derive alist of implication relations that express the necessary and sufficient conditions of eliminability of the prime implicants in terms of which the irredundant normal forms can be computed. The extension of Quine's technique to this phase of simplification serves to shorten considerably the logical machinery needed for complete solution of the simplification problem. By the same token, it renders the method suitable for use with a digital computer.