Prime implicants, essentials and the cover chart

Three words

• An implicant of F is a product term that is 1 only where F is 1 (or don’t-care). On a K-map: any legal group.
• A prime implicant is an implicant that cannot be made larger — removing any literal would make it cover a 0. On a K-map: a group that cannot grow.
• An essential prime implicant is a prime implicant that covers some minterm which no other prime implicant covers. It must be in every minimal solution.

A minimal SOP can always be built from prime implicants alone: if a solution used a smaller group, you could swap in the prime implicant that contains it, cover at least as much, and use fewer literals. So the question is never “which terms?” but only “which prime implicants?”

The chart

From lesson 5, the function F = Σm(0, 2, 3, 5, 7, 8, 10, 13) has five prime implicants. Draw a table with one row per prime implicant and one column per minterm, and put an × where the row covers the column.

The goal: pick the fewest rows so that every column has at least one × in a picked row.

Step 1 — columns with a single × give the essentials

Column 0 has only one ×, in row BD. Nothing else can cover minterm 0, so that row is essential. The same is true of columns 8 and 10. Column 13 has a single × too, in row BCD. Circle those marks and select both rows.

The essential rows cover 0, 2, 8, 10 and 5, 13. Cross out those columns (shaded above). Minterms 3 and 7 are still uncovered.

Step 2 — reduce what is left

Look only at columns 3 and 7:

Row ACD covers everything that ABC still covers, and more, at the same cost. We say ACD dominates it; a dominated row can be deleted. The same goes for ABD. One row is left, and it finishes the job.

F = BD + BCD + ACD

Three terms, eight literals. ABC and ABD are perfectly good prime implicants that are simply not needed — the consensus idea from lesson 3, seen in a table.

When nothing is essential: cyclic charts

Some functions have no essential prime implicant at all. The classic small case is F(A, B, C) = Σm(0, 1, 2, 5, 6, 7):

Every column has exactly two × marks, and no row dominates another. This is a cyclic chart. You have to make a choice and see where it leads. Pick P₁: columns 0 and 1 are done; now P₂ and P₃ each cover just one remaining column and are dominated by P₄ and P₅, which become essential and finish the cover:

F = AB + BC + AC

Starting with P₂ instead leads to F = AC + BC + AB. Both have three terms and six literals. Both are minimal. The K-map above shows the first one.

Petrick’s method: every solution, by algebra

Trying choices by hand does not scale, and it does not prove you found the best. Petrick’s method does. Let P_i mean “row i is selected”. For each column, write the OR of the rows that cover it, and AND the columns together — every column must be covered:

(P₁ + P₂)(P₁ + P₃)(P₂ + P₄)(P₃ + P₅)(P₄ + P₆)(P₅ + P₆) = 1

Multiply out, simplifying with X + XY = X and (X + Y)(X + Z) = X + YZ as you go:

(P₁ + P₂P₃)(P₄ + P₂P₆)(P₅ + P₃P₆)

Expanding gives eight products. Each product is a valid cover; the ones with the fewest rows are the minimal covers:

P₁P₄P₅ + P₂P₃P₆ + (six products with four rows each)

Exactly the two solutions found above — and now you know there is no third.

The whole procedure

1. Find all prime implicants (K-map, Q-M, or the Scheinman tree).
2. Build the chart. Columns are the minterms only — not the don’t-cares.
3. Select the essential rows; cross out their columns.
4. Delete dominated rows. This may create new single-× columns; go back to step 3.
5. If a cyclic chart remains, use Petrick’s method (or branch on a choice and compare).

The Scheinman tool draws this chart for any function you enter, with essential rows marked E and selected rows marked S.

Check yourself

1. F(A, B, C) = Σm(0, 1, 5, 7) has prime implicants AB (0, 1), BC (1, 5) and AC (5, 7). Which are essential, and what is the minimal SOP?
   Show answer

   Column 0 is covered only by AB and column 7 only by AC, so both are essential. Together they cover 0, 1, 5, 7 — everything. F = AB + AC. BC is a prime implicant but not needed.
2. F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15) has prime implicants BD (1, 3, 9, 11), BC (2, 3, 10, 11), CD (3, 7, 11, 15) and AD (9, 11, 13, 15). Find the minimal SOP.
   Show answer

   The chart has columns 2, 3, 7, 9, 11, 13 only — not the don’t-cares 1, 10, 15. Column 2 has a single × (BC), column 7 a single × (CD), column 13 a single × (AD). Those three essentials cover 2, 3, 7, 9, 11 and 13, so F = BC + CD + AD and BD is not needed.
3. True or false: the largest prime implicant is always part of the minimal solution.
   Show answer

   False. Size does not make a prime implicant essential; covering a minterm that nothing else covers does. A large prime implicant can be left out when smaller essential ones already cover all of its minterms.
4. In the cyclic example, suppose you must use AB (P₆) for some outside reason. Which minimal solution is still available?
   Show answer

   P₂P₃P₆: F = AC + BC + AB. With P₆ chosen, columns 6 and 7 are done; P₄ and P₅ are then dominated by P₂ and P₃, which cover the rest.