Prime Implicant Chart

After the Quine-McCluskey algorithm extracts all prime implicants, the prime implicant chart decides which ones actually appear in the final minimised expression. This chart is the decision engine that separates essential coverage from redundant terms.

Core Concept

A prime implicant chart is a two-dimensional table where rows represent prime implicants and columns represent the minterms of the function. An X is placed at row i, column j when prime implicant i covers minterm j. The chart makes the covering problem visible.

Any column that contains exactly one X points to an essential prime implicant (EPI). That PI must appear in every minimum cover because it is the only one that covers a particular minterm. EPIs are always selected first and their covered minterms are removed from the chart.

After EPI selection, if uncovered minterms remain, a secondary selection process chooses additional PIs with minimum overlap. This is an instance of the set cover problem, which is NP-hard in general, but the chart makes small examples tractable by inspection. The Petrick method provides an algebraic procedure for the secondary selection step.

Boolean Expression

The minimised SOP is f = EPI1 + EPI2 + ... + selected non-essential PIs. Each row in the final selected set contributes one product term. The goal is to cover all minterms with the fewest product terms and fewest literals. When two covers have equal term count, the one with fewer total literals is preferred.

Given:
  f = Σm(0,1,2,4,5)  with PIs found by Q-M:
  PI1: 0-0-  (covers m0,m1,m4,m5)  → A'C'
  PI2: 00-0  (covers m0,m2)        → A'B'D'
  PI3: 010-  (covers m4,m5)        → A'BC'

Formula / Rule:
  Build chart. Mark X at each (PI, minterm) it covers.
  A column with one X → essential PI.

Step by step:
       m0  m1  m2  m4  m5
  PI1:  X   X       X   X
  PI2:  X       X
  PI3:              X   X

  m1 has one X → PI1 is ESSENTIAL  (select PI1)
  m2 has one X → PI2 is ESSENTIAL  (select PI2)

  Remove minterms covered by PI1: m0,m1,m4,m5 gone.
  Remove minterms covered by PI2: m0,m2 gone.
  All minterms covered.
  PI3 is not needed.

Final Answer:
  Minimum SOP = A'C' + A'B'D'
  (2 terms, 4 literals total)

Exam Tip: Students often confuse prime implicants with essential prime implicants. Every essential PI is a prime implicant, but not every prime implicant is essential. GATE questions frequently ask: 'How many prime implicants are essential?' Scan every minterm column — if only one PI covers it, that PI is essential. Count carefully; a function can have zero essential PIs if every minterm is shared among two or more PIs.

Key Properties

• A prime implicant is a maximal implicant — it cannot be combined with any other implicant to form a larger one.
• An essential PI covers at least one minterm that no other PI covers; it appears in every minimal SOP.
• The number of prime implicants can grow exponentially; a 6-variable function can have up to 64 PIs.
• Petrick's method solves secondary PI selection algebraically by forming a product-of-sums expression and expanding it.
• Don't-care minterms are included during the Q-M merging phase but are not listed as columns in the PI chart.
• The final cover is not unique when secondary selection is required; multiple minimum solutions may exist.
• This is a pure algorithmic/paper method; no IC number applies.

Quick Revision

• Rows = prime implicants; columns = minterms; X = coverage.
• Column with one X → that row is an essential prime implicant.
• Always select all EPIs first.
• Remove all minterms covered by EPIs from the chart.
• Use Petrick's method or inspection for remaining uncovered minterms.
• Minimum cover = fewest terms; among ties, fewest literals wins.
• Don't-cares help form PIs but are not column entries.
• Exam trap: selecting a PI just because it covers many minterms without checking if those minterms are already covered by essential PIs — this adds redundant terms.