Prime implicants, essential prime implicants, minimal SOP and POS

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• How many literals does a group of 4 cells leave in a 4-variable map? from Lesson 4.1.1
• Maxterm M₅ of F(A, B, C)? from Lesson 3.2.1
• Consensus theorem? from Lesson 3.1.2

1 · The Hook

🎣

Students lose marks on K-maps in two ways: circling a big group that isn't needed, or missing that two different answers are both minimal. The cure is vocabulary. A prime implicant is a group you can't enlarge; an essential one is forced on you. GATE asks directly "how many prime implicants / essential prime implicants does this function have?".

2 · Predict First

🤔

In a map, the 1-cell m₉ can be covered by only one possible maximal group. Must the minimal expression include that group?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Yes. Nothing else covers m₉, so that group is essential.

🗣️

In plain words

List every group of 1s that cannot be made any bigger: these are the prime implicants (PIs). If some 1 is covered by only one PI, that PI is essential (EPI) and must be used. Take all EPIs first, then cover the remaining 1s with as few extra PIs as possible.

1. Definitions

• Implicant: any product term (group) that is 1 only where F is 1.
• Prime implicant: an implicant that is not contained in any larger implicant (a maximal group).
• Essential prime implicant: a PI that covers at least one 1 that no other PI covers.
• A minimal SOP uses only prime implicants; it uses every EPI.

2. Procedure

• Find all PIs (all maximal groups).
• Mark the EPIs: look for 1s covered by a single PI.
• Remove the 1s covered by EPIs. Cover what is left with the fewest PIs (then fewest literals).

3. Example with redundant PIs

F(A, B, C, D) = Σm(2, 3, 5, 7, 8, 9, 10, 11, 13, 15).

• PIs (5): AB' (8, 9, 10, 11), BD (5, 7, 13, 15), B'C (2, 3, 10, 11), CD (3, 7, 11, 15), AD (9, 11, 13, 15).
• EPIs (3): B'C (only it covers 2), BD (only it covers 5), AB' (only it covers 8).
• The EPIs already cover every 1, so F = AB' + BD + B'C (6 literals). CD and AD are prime but not needed.

4. The big-middle-group trap

F = Σm(1, 5, 6, 7, 11, 12, 13, 15): the centre square BD (5, 7, 13, 15) is a prime implicant, but each of its cells is also covered by one of four EPIs (A'C'D, A'BC, ACD, ABC'). The minimal SOP is those four terms; adding BD would be redundant.

5. Cyclic functions (no EPIs)

F(A, B, C) = Σm(0, 1, 2, 5, 6, 7) has 6 PIs (A'B', A'C', B'C, BC', AB, AC), each covering 2 cells, and no EPI. Two different minimal SOPs exist: A'B' + BC' + AC and A'C' + B'C + AB (3 terms, 6 literals each).

6. Minimal POS

Group the 0s instead. Each group gives an OR clause: write a variable plain if it is 0 throughout the group, primed if it is 1. AND the clauses. For the example in §3, the 0s are 0, 1, 4, 6, 12, 14:

• 0, 1 (A = 0, B = 0, C = 0) → (A + B + C).
• 4, 6, 12, 14 (B = 1, D = 0) → (B' + D).
• F = (A + B + C)(B' + D): 2 clauses, 5 literals, cheaper than the 6-literal SOP.

4 · Visual

F = Σm(2, 3, 5, 7, 8, 9, 10, 11, 13, 15) = AB' + BD + B'C. CD and AD are also prime implicants but are not needed.

The same function grouped on its 0s: F = (A + B + C)(B' + D).

5 · Worked Examples

Example 1 Easy

F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15). How many prime implicants, and how many are essential?

Solution

Only B'D' and BD: 2 PIs, both essential.

Example 2 Medium

F(A, B, C, D) = Σm(1, 5, 6, 7, 11, 12, 13, 15). How many literals does the minimal SOP have?

Solution

Four essential 3-literal terms: 12 literals (BD is not used).

Example 3 GATE

How many essential prime implicants does F(A, B, C) = Σm(0, 1, 2, 5, 6, 7) have?

Solution

0: every 1 is covered by two prime implicants.

6 · GATE Traps

⚠️

• Not every PI is essential, and not every PI appears in the minimal answer.
• A big group can be redundant (the centre-square trap).
• For POS, a variable that is 1 throughout the 0-group appears primed in the clause.
• A function can have several minimal SOPs; count literals to compare.

7 · Memory Hook

🧠

"Prime = can't grow. Essential = some 1 has no other cover. Take essentials first, then the fewest extras."

8 · Connect the Dots

Real designs often have input combinations that never happen (a BCD digit is never 1010). The next lesson lets those don't-care cells help the grouping, and extends K-maps to 5 variables.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksPrime implicants

How many prime implicants does F(A, B, C, D) = Σm(2, 3, 5, 7, 8, 9, 10, 11, 13, 15) have?

Numerical answer: ________

Q2NAT2 marksEssential PIs

How many of them are essential?

Numerical answer: ________

Q3NAT2 marksLiterals

F(A, B, C, D) = Σm(0, 1, 2, 3, 5, 7, 8, 10, 14, 15). How many literals are in its minimal SOP?

Numerical answer: ________

Q4MCQ2 marksPOS

The minimal POS of F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15) is:

• (A) (B + D')(B' + D)
• (B) (B' + D')
• (C) (B + D)(B' + D')
• (D) (A + B)(C + D)

Q5MCQ1 markDefinitions

An essential prime implicant is one that:

• (A) appears in every implicant
• (B) covers the most 1s
• (C) contains no complemented literals
• (D) covers at least one 1 that no other prime implicant covers

10 · Rule Card

• Implicant ⊂ prime implicant (maximal group) ⊂ essential PI (sole cover of some 1).
• Minimal SOP: all EPIs + fewest extra PIs for the remaining 1s; only PIs are used.
• Redundant PIs (like a centre square fully covered by EPIs) are left out. Cyclic functions have no EPIs and several minimal answers.
• POS: group 0s; clause literal plain if the variable is 0 in the group, primed if 1.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

implicantprime implicantessential prime implicantminimal coverredundant prime implicantscyclic functionsmultiple minimal solutionsminimal POS from the 0s

12 · Answer Vault