McCluskey 1956: Prime Implicants and Exact Two-Level Covering
McCluskey separates prime-implicant generation from cover selection, defines a precise lexicographic minimum-sum objective, handles don't-cares correctly, and distinguishes an approximate selection procedure from a later exact one.
Edward J. McCluskey Jr.'s 1956 paper is a 28-page primary account of tabular Boolean minimization. The scan covers printed pages 1417–1444. Every page was read through page-bounded OCR and visually inspected; equations, symbols, and every dense or rotated table were checked directly against the page images.
The two separate problems #
Sections 3–5, printed pages 1419–1427, repeatedly combine compatible bit patterns to obtain prime implicants and then place those primes in a chart. The chart is a covering problem: generating all maximal legal cubes does not itself choose an optimum subset. Sections 6–7 analyze cyclic covering structure, while Section 9, printed pages 1437–1440, develops a systematic exact product-of-factors procedure.
Don't-care combinations participate in prime generation but do not become required chart columns. McCluskey states this explicitly on printed pages 1440–1441. A modern implementation should therefore retain intermediate cubes derived only from don't-cares through all combination rounds; such a cube may still combine into a larger implicant that covers a required ON row.
What “minimum” means #
Printed page 1419 defines a minimum sum lexicographically: minimize the number of product terms first, then minimize literals among ties. The same passage warns that this need not minimize total literals or produce the most economical two-stage diode circuit. A different cell library, fan-in limit, delay objective, or multilevel factoring cost can select a different implementation.
Section 8, beginning on printed page 1432, is approximate and carries no general proof of minimum. The paper explicitly exposes that limitation before presenting the exact alternative. Summaries that turn the entire method into a greedy selection rule erase one of the paper's most important boundaries.