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.

This paper gives an algorithm for efficiently ordering the terms and factors of a set (or Boolean) expression so that the work required for the symbolic expansion of the expression according to the distributive law is minimized. Formulas are given for computing the measure of work associated with any ordering of an expression. It is shown from these formulas that reordering the factors of the intersections can possibly reduce the cost of expansion, but this cost is invariant with respect to the ordering of the terms of the unions. A simple ordering algorithm is given for quickly determining an optimal (not necessarily unique) ordering of an intersection and a union. When this algorithm is applied to all intersections and unions in an expression, the resulting order is shown to minimize the total work over all possible orderings. Thus it is easy to establish an optimal ordering for an expression and estimate the machine time for its symbolic expansion before doing the expansion.