IEEE Transactions on Computers · 1975 · 18 citations · 8 references
ComputingComputer ScienceMathematicsAlgorithmsLogicNumber TheoryBoolean AlgebraBoolean OperationsComputational ComplexityDigital Logic DesignNumber-theoretic AlgorithmsBoolean Function ComplexityBoolean Function MinimizationBoolean Function RepresentationExpression SimplificationLogic Factorization
An algorithm for finding the prime implicants of a Boolean function is given. The algorithm is similar to Nelson's algorithm since both involve the operations of complementing, expanding, and simplifying, but the new algorithm includes the additional operation of factoring. The algorithm with factoring is proved, and it is shown that factoring accounts for a dramatic increase in efficiency over Nelson's algorithm. The increased efficiency is illustrated with timing results obtained from several examples that were implemented for both algorithms using the symbolic manipulation systems SETS.
8
The Problem of Simplifying Truth Functions
W. V. Quine · American Mathematical Monthly · 1952 · 801 citations
A Way to Simplify Truth Functions
W. V. Quine · American Mathematical Monthly · 1955 · 572 citations
Humanities, Mathematics, Logic +6
Simplest normal truth functions
Raymond J. Nelson · Journal of Symbolic Logic · 1955 · 101 citations