Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Type a name or a two-letter code. Use the up and down arrow keys to move through the countries, Enter to choose one and Escape to close.

GATE CS & DA Preparation Guide  Module 5 – Digital logic and computer organisation (CS sections 2-3)

Boolean minimisation: K-maps and the tabular method

Minimise Boolean functions for GATE CS with K-maps and the Quine-McCluskey tabular method: prime implicants, essential ones and don't-cares.

  • Intermediate
  • 25 minutes
  • Examples run with Python 3.14.8 and Pyodide 314.0.7
  • By MySmartCoPilot
Free core, Pro depth: 9 of 25 minutes free
Free: Five identities do all the merging · A K-map puts cells that merge side by side · Essential prime implicants come first · 2 more sections. With a pass: 3 in-depth parts and 3 interview answers, about 16 minutes.

What you will learn

  • Simplify expressions with Boolean algebra, duality and the consensus theorem
  • Find minimal sums of products with don't-cares on 3-, 4- and 5-variable K-maps
  • Run the Quine-McCluskey tabular method to find prime implicants, essential prime implicants and a minimal cover
  • Count prime implicants, essential prime implicants and literals for numerical answer questions

Before you start

What you’ll learn · Before you start

What you will learn

  • Simplify expressions with Boolean algebra, duality and the consensus theorem
  • Find minimal sums of products with don't-cares on 3-, 4- and 5-variable K-maps
  • Run the Quine-McCluskey tabular method to find prime implicants, essential prime implicants and a minimal cover
  • Count prime implicants, essential prime implicants and literals for numerical answer questions

Before you start

On this page

Written as a sum of its eight minterm: A product of all of a function's variables, each plain or complemented once, which is 1 on exactly one row of the truth table: with A, B, C and D, minterm 5 is A'BC'D., the function F = Σm(1, 2, 3, 5, 7, 8, 13, 15), with don't-care: An input whose output does not matter, because it never occurs or its output is ignored. Written X on a K-map or d(…) in a list, it may be read as 1 or 0, whichever gives the simpler circuit. at 0 and 6, takes 8 product terms and 32 literal: A variable or its complement as it appears in an expression. A'B' + BD has four literals, and counting literals is how two expressions for the same function are compared.. Minimised, it takes 3 terms and 7 literals, A’B’ + BD + B’C’D’, and its circuit shrinks with it. Every minimisation method rests on one identity, xy + xy’ = x: two terms that differ in a single variable merge into one term without it.

A Karnaugh map (K-map) applies that identity by eye: it lays out the truth table in Gray-code order, so that cells which merge sit side by side, and you circle groups of 1, 2, 4 or 8 cells. The tabular method, also called the Quine-McCluskey method, applies it by bookkeeping: it merges minterms written in binary until nothing merges, then chooses a cover from a chart. A map is quicker up to five variables; the table works for any number.

Five identities do all the merging

AB + A’C + BC + A’B’C has four terms and 9 literals, yet BC and A’B’C add nothing. Five identities find such terms:

  • Combining: xy + xy’ = x. Two terms that differ in exactly one variable merge.
  • Absorption: x + xy = x, and its dual x(x + y) = x.
  • Consensus: xy + x’z + yz = xy + x’z. The term yz is redundant, because any input that makes it 1 also makes xy or x’z equal to 1.
  • De Morgan: (x + y)’ = x’y’ and (xy)’ = x’ + y’.
  • Duality: swap AND with OR, and 0 with 1, in an identity, and the result is an identity too.

Step through the two removals:

Interactive · stage by stage Two identities shrink AB + A'C + BC + A'B'C Step through the simplification. Each step removes one term with one identity and says why nothing changes on any input.
Two identities shrink AB + A'C + BC + A'B'C, step 4 of 4. Showing AB + A'C + BC + A'B'C, AB + A'C + A'B'C, AB + A'C.AB + A'C + BC + A'B'C4 terms, 9 literalsAB + A'C + A'B'Cconsensus: BC goesAB + A'Cabsorption: A'B'C goes

The drawing shows the whole scene; its 4 steps are listed below.

Every step as text
  1. Four terms. The expression has four terms and 9 literals. Look first for two terms with one variable plain in one and complemented in the other: AB and A'C disagree on A.
  2. Consensus. Drop the variable they disagree on and multiply what is left: the consensus of AB and A'C is BC. When BC is 1, AB is 1 if A = 1 and A'C is 1 if A = 0, so BC adds nothing and goes.
  3. Absorption. A'B'C is A'C with one more literal, so wherever A'B'C is 1, A'C is 1 too. x + xy = x absorbs it.
  4. Nothing left to remove. Neither of AB and A'C contains the other, and their consensus BC has already gone, so 2 terms and 4 literals remain instead of 9. The result agrees with the start on all eight inputs.

Consensus removed BC and absorption removed A’B’C, leaving AB + A’C: 4 literals instead of 9.

Checkpoint

Check: Merging and removing terms by algebra

  1. Question 1 of 2 What is the consensus of the terms AB' and BC'?

    Choose one answer.

    Show the answer: Question 1 of 2

    Answer: AC'

    For xy + x'z the consensus is yz. Here x is B: AB' is B'·A and BC' is B·C', so the consensus is A·C' = AC'. Any input that makes AC' equal to 1 makes AB' 1 when B = 0 and BC' 1 when B = 1.

  2. Question 2 of 2 Which identity removes A'B'C from A'C + A'B'C?

    Choose one answer.

    Show the answer: Question 2 of 2

    Answer: Absorption, x + xy = x

    With x = A'C and y = B', A'C + A'B'C is x + xy, which absorption shrinks to x = A'C. The step-through above used the same identity to remove A'B'C from AB + A'C + A'B'C.

A K-map puts cells that merge side by side

Minterms 5 and 7 of F, A’BC’D and A’BCD, differ only in C, so they merge into A’BD, and on a K-map they sit side by side. A four-variable map has 16 cells, one per minterm, with rows labelled AB and columns CD in the Gray code: An order of binary numbers in which neighbours differ in exactly one bit, such as 00, 01, 11, 10. A K-map labels its rows and columns in this order, so cells that sit side by side can merge. order 00, 01, 11, 10. Neighbouring cells differ in one variable, and so do the cells at the two ends of a row or a column, so groups may wrap round the edges. Step through one group of F as it doubles:

Interactive · step by step One cell, a pair, a square of F's map Step through the group BD of F, one doubling at a time, and watch the term lose a literal at each.
One cell, a pair, a square of F's map, step 5 of 5. Showing 5: A'BC'D, 7: A'BCD, 13: ABC'D, 15: ABCD, The group's term (BD: 2 literals). In focus: 5: A'BC'D, 15: ABCD.differ in Cdiffer in Cdiffer in A5: A'BC'Drow 01, column 017: A'BCDrow 01, column 1113: ABC'Drow 11, column 0115: ABCDrow 11, column 11The group's termBD: 2 literals

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text
  1. One cell. Cell 5 is the minterm A'BC'D. On its own it is a group of one cell, a product of all 4 literals.
  2. A pair. Cell 7, A'BCD, sits beside it in row 01: the columns 01 and 11 differ only in C. xy + xy' = x merges the two into A'BD, 3 literals.
  3. The same pair below. Cells 13 and 15, ABC'D and ABCD, are the same pair in row 11, where A = 1. Rows 01 and 11 differ only in A, so the two pairs merge as well.
  4. A square of four. The square drops A as well and leaves BD, 2 literals. A group of 2² cells on a 4-variable map is a product of 4 − 2 = 2 literals.
  5. Not a group. Cells 5 and 15 alone sit diagonally: they differ in A and in C, two variables, so no identity merges them. A group is a rectangle of 1, 2, 4 or 8 cells, never a diagonal.

A group is a rectangle of 1, 2, 4 or 8 cells, and each doubling removes one literal: in an n-variable map, a group of 2k cells is a product of n − k literals. A don’t-care (X) joins a group when it makes the group larger, and otherwise stays 0.

Checkpoint

Check: Groups on a K-map

  1. Question 1 of 2 Which two columns of a four-variable K-map, labelled CD in Gray-code order, are neighbours although they sit at opposite ends?

    Choose one answer.

    Show the answer: Question 1 of 2

    Answer: 00 and 10

    The order 00, 01, 11, 10 changes one bit at each step, and from 10 back to 00 as well. So the first and last columns are neighbours, and so are the first and last rows: that is why B'C'D' of F wraps from the top row to the bottom one.

  2. Question 2 of 2 On F's map, cells 1, 3, 5 and 7 form a group of four. Which term is it?

    Choose one answer.

    Show the answer: Question 2 of 2

    Answer: A'D

    Write the cells in binary and keep the variables that never change: 0001, 0011, 0101 and 0111 all have A = 0 and D = 1. A group of 2² cells of a 4-variable map has 4 − 2 = 2 literals: A'D.

Essential prime implicants come first

A group that cannot grow any larger is a prime implicant. A prime implicant that is the only group covering some 1 is essential, and every minimal answer contains it. So take the essential prime implicants first, then cover the remaining 1s with as few groups as possible, each as large as possible. The map shows F’s cover:

A four-variable K-map of F with three groups circled: the top row A'B', the centre square BD and the wrapped pair B'C'D'.F = Σm(1, 2, 3, 5, 7, 8, 13, 15)with don't-cares d(0, 6), marked XRows AB, columns CD, in Gray-code order0001111000011110X0111312041517X60121131150141809011010A'B'top row, uses the X at 0BDcentre square, essentialB'C'D'0 and 8, wraps, essentialF = A'B' + BD + B'C'D'3 terms, 7 literals; the X at 6 stays 0

The minimal cover of F on its K-map: two essential groups and one more

Text description of the diagram

A Karnaugh map with rows labelled by AB and columns by CD, both in the Gray-code order 00, 01, 11, 10, so that any two neighbouring rows or columns differ in one bit. Each cell shows the value of F and, in small print in its top-left corner, its minterm number. A legend under the map names each group by its line style.

  • Row AB = 00 holds minterms 0, 1, 3 and 2: a don't-care (X) at 0 and 1s at 1, 3 and 2.
  • Row AB = 01 holds 4, 5, 7 and 6: 0, 1, 1 and a don't-care at 6.
  • Row AB = 11 holds 12, 13, 15 and 14: 0, 1, 1 and 0.
  • Row AB = 10 holds 8, 9, 11 and 10: 1, 0, 0 and 0.

Three groups are drawn, each with its own line style:

  • A solid outline around the whole top row: the group A'B', four cells, which uses the don't-care at 0 as a 1.
  • A dashed outline around the square of minterms 5, 7, 13 and 15: the group BD, essential because it is the only group that covers 13 and 15.
  • A dotted outline that leaves the top edge above cell 0 and comes back in from the bottom edge below cell 8: the pair B'C'D', which wraps round the map and is essential because it is the only group that covers 8.

Together they give F = A'B' + BD + B'C'D', three terms and seven literals. The don't-care at 6 is not used, so the circuit makes F(6) = 0.

The program below tries all 81 possible groups of F and keeps the prime ones. Change ONES or DONT_CARES to run it on a function of your own:

Every prime implicant of F, from all 81 possible groups Python · kmap_primes.py
"""Every prime implicant of F(A,B,C,D) = Σm(1,2,3,5,7,8,13,15) + d(0,6), found by trying every K-map group.

A group is written as a cube: one character per variable, A first, with '-' where the group spans both values.
"""
from itertools import combinations, product

NAMES = "ABCD"
ONES = {1, 2, 3, 5, 7, 8, 13, 15}
DONT_CARES = {0, 6}
ALLOWED = ONES | DONT_CARES


def cells(cube):
    """The minterms a cube covers."""
    return {m for m in range(16) if all(c in "-" + b for c, b in zip(cube, format(m, "04b")))}


def term(cube):
    """A cube as a product of literals: '0-1-' -> A'C."""
    return "".join(n + ("'" if c == "0" else "") for n, c in zip(NAMES, cube) if c != "-") or "1"


def literals(cube):
    return sum(c != "-" for c in cube)


# A group is allowed when every cell in it is a 1 or a don't-care; it is prime when no larger allowed group
# contains it, and it is only useful when it covers at least one 1.
groups = ["".join(t) for t in product("01-", repeat=4) if cells("".join(t)) <= ALLOWED]
primes = [g for g in groups if cells(g) & ONES and not any(cells(g) < cells(h) for h in groups)]
primes.sort(key=lambda g: (-len(cells(g)), g))

print("F(A,B,C,D) = Σm(1, 2, 3, 5, 7, 8, 13, 15) + d(0, 6)")
header = "cells (d = don't-care)"
print(f"{'cube':<6}{'term':<9}{header:<25}essential for")
essential = []
for p in primes:
    shown = " ".join(("d" if m in DONT_CARES else "") + str(m) for m in sorted(cells(p)))
    only = [m for m in sorted(cells(p) & ONES) if [q for q in primes if m in cells(q)] == [p]]
    if only:
        essential.append(p)
    print(f"{p:<6}{term(p):<9}{shown:<25}{', '.join('m' + str(m) for m in only) or '-'}")

# Smallest covers: fewest terms first, then fewest literals.
best = None
for k in range(1, len(primes) + 1):
    for combo in combinations(primes, k):
        if ONES <= set().union(*(cells(p) for p in combo)):
            cost = (k, sum(literals(p) for p in combo))
            if best is None or cost < best[0]:
                best = (cost, [combo])
            elif cost == best[0]:
                best[1].append(combo)
    if best:
        break

(terms, lits), covers = best
print(f"prime implicants: {len(primes)}, essential: {len(essential)}")
for combo in covers:
    print(f"minimal SOP: {' + '.join(term(p) for p in combo)} ({terms} terms, {lits} literals)")
print("minimal covers found:", len(covers))
cover = covers[0]
agrees = all((m in ONES) == any(m in cells(p) for p in cover) for m in range(16) if m not in DONT_CARES)
print("agrees with F on all", 16 - len(DONT_CARES), "specified inputs:", agrees)

Output

F(A,B,C,D) = Σm(1, 2, 3, 5, 7, 8, 13, 15) + d(0, 6)
cube  term     cells (d = don't-care)   essential for
-1-1  BD       5 7 13 15                m13, m15
0--1  A'D      1 3 5 7                  -
0-1-  A'C      2 3 d6 7                 -
00--  A'B'     d0 1 2 3                 -
-000  B'C'D'   d0 8                     m8
prime implicants: 5, essential: 2
minimal SOP: BD + A'B' + B'C'D' (3 terms, 7 literals)
minimal covers found: 1
agrees with F on all 14 specified inputs: True

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 kmap_primes.py

F has five prime implicants. Follow the choice of its cover:

Interactive · stage by stage Choosing F's cover, essential groups first Step through the choice, starting from the program's list of prime implicants. Each step names the 1s that force a group into the cover.
Choosing F's cover, essential groups first, step 5 of 5. Showing Five prime implicants, BD is essential, B'C'D' is essential, 1, 2 and 3 are left, F = A'B' + BD + B'C'D'. In focus: F = A'B' + BD + B'C'D'.Five prime implicantsBD, A'D, A'C, A'B', B'C'D'BD is essentialthe only group on 13 and 15B'C'D' is essentialthe only group on 81, 2 and 3 are leftA'B' covers all threeF = A'B' + BD + B'C'D'3 terms, 7 literals

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text
  1. The list. The program found five prime implicants: BD, A'D, A'C, A'B' and B'C'D'. Before choosing any, look for the 1s that only one of them covers.
  2. Cells 13 and 15. Cells 13 and 15 lie in BD and in no other prime implicant, so every cover must contain BD: it is essential.
  3. Cell 8. Cell 8 lies only in B'C'D', the pair that wraps from the top row to the bottom row through the don't-care 0. B'C'D' is essential too.
  4. What is left. BD covers 5, 7, 13 and 15, and B'C'D' covers 8. The 1s still uncovered are 1, 2 and 3: A'B' covers all three, where A'D and A'C cover two each.
  5. The cover. Three terms and seven literals. The don't-care 0 lies in two chosen groups, so it reads as 1; the don't-care 6 lies in none, so the circuit makes F(6) = 0.

The don’t-care 0 is used and 6 is not, so the circuit makes F(6) = 0, and A’B’ + BD + B’C’D’ is the only minimal cover.

Checkpoint

Check: Prime and essential prime implicants

  1. Question 1 of 2 How many of the five prime implicants of F are essential?

    Type a number.

    Show the answer: Question 1 of 2

    Answer: 2 essential prime implicants

    BD is the only group that covers 13 and 15, and B'C'D' the only one that covers 8. Every other 1 of F lies in at least two prime implicants, so A'B', A'C and A'D are not essential.

  2. Question 2 of 2 Suppose input 8 of F were a don't-care instead of a 1. Which group of F's cover would no longer be needed?

    Choose one answer.

    Show the answer: Question 2 of 2

    Answer: B'C'D'

    An essential prime implicant is essential because of a 1 that only it covers. B'C'D' was the only group on 8, so once 8 is a don't-care it covers only don't-cares, and the cover becomes A'B' + BD: 2 terms and 4 literals.

The tabular method does the same by bookkeeping

Follow the method on a function of three variables, f = Σm(0, 1, 3, 7):

Interactive · stage by stage The tabular method on f = Σm(0, 1, 3, 7) Step through the five steps on a function of three variables, from its minterms in binary to its cover.
The tabular method on f = Σm(0, 1, 3, 7), step 5 of 5. Showing 1. Binary, grouped by 1s, 2. Combine one bit apart, 3. Combine again, 4. A chart of the 1s, 5. Essentials, then cover. In focus: 5. Essentials, then cover.1. Binary, grouped by 1s000 · 001 · 011 · 1112. Combine one bit apart00-, 0-1, -11: all ticked3. Combine againno pair left: three primes4. A chart of the 1scolumns 0, 1, 3 and 75. Essentials, then coverf = A'B' + BC

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text
  1. Binary. Write the minterms 0, 1, 3 and 7 of A, B and C in binary and group them by their number of 1s: 000 has none, 001 one, 011 two and 111 three.
  2. Combine. Compare each term with the terms of the next group. 000 and 001 differ in the last bit and give 00-; 001 and 011 give 0-1; 011 and 111 give -11. Every term combined, so every term is ticked.
  3. Repeat. 00-, 0-1 and -11 have their dashes in different places, so no two of them combine. Nothing is ticked in this round, so all three are prime implicants: A'B', A'C and BC.
  4. The chart. Draw a row per prime implicant and a column per 1. A'B' has an X under 0 and 1, A'C under 1 and 3, and BC under 3 and 7.
  5. The cover. Column 0 has its only X in the row of A'B', and column 7 in the row of BC, so both are essential. Together they cover 0, 1, 3 and 7, so f = A'B' + BC. A'C is left out: it is the consensus of A'B' and BC.

In general, the five steps are:

  1. Write each minterm and don’t-care in binary, grouped by their number of 1s.
  2. Compare each term with every term of the next group: two terms that differ in exactly one bit combine, with a dash in that bit, and both are ticked.
  3. Repeat until nothing combines. The terms never ticked are the prime implicants.
  4. Draw the prime-implicant chart: a row per prime implicant, a column per 1 (never per don’t-care), and an X where the row covers the column.
  5. A column with a single X marks an essential prime implicant. Take those, delete the columns they cover, and cover the rest.

When no column has a single X, the chart is cyclic. Petrick’s method settles it by writing the chart as a product of sums, one sum per column, and multiplying out to list every cover. The two methods side by side:

K-map Tabular method
Variables, in practice up to 4, or 5 with two maps any number
Groups found by eye, in Gray-code order by combining terms that differ in one bit
Cover chosen by eye from the prime-implicant chart
Typical slip a missed wrap-around group a missed combination
Karnaugh Map Solver Enter Σm(1, 2, 3, 5, 7, 8, 13, 15) with d(0, 6) to see the function on its K-map with its minimal sum of products.

Checkpoint

Check: The tabular method

  1. Question 1 of 2 In the tabular method, which pair of terms combines?

    Choose one answer.

    Show the answer: Question 1 of 2

    Answer: 0-01 and 0-11, into 0--1

    Two terms combine when they have their dashes in the same places and differ in exactly one other bit, which becomes a dash: xy + xy' = x written as bit strings. 0-01 and 0-11 give 0--1, the group A'D.

  2. Question 2 of 2 A column of the prime-implicant chart has a single X. What does that tell you?

    Choose one answer.

    Show the answer: Question 2 of 2

    Answer: The row with that X is an essential prime implicant

    A column stands for one 1 of the function, and an X marks a prime implicant that covers it. A single X means only one prime implicant covers that 1, so it is essential. In the small function f, columns 0 and 7 made A'B' and BC essential.

Practise: minimise, then count

What the GATE 2027 syllabus asks

Section 2 of the CS syllabus now names “Boolean algebra and minimization – algebraic technique, Karnaugh map, tabular method”, where the 2026 syllabus said only “Minimization”. Expect minimal expressions and counts of prime implicants, essential ones or literals, often as numerical answers.

Exercise · Medium · Python

List the prime and essential prime implicants of a function

Write two functions in primes.py for a Boolean function of n variables given by its 1s and its don't-cares, both as lists of minterm numbers.

A cube describes a K-map group: one character per variable, the first variable first, 1 for the variable, 0 for its complement and - where the group spans both values. With four variables A, B, C, D, the cube 0-1- is the term A'C and covers the minterms 2, 3, 6 and 7.

  • prime_implicants(n, ones, dont_cares=()) returns every prime implicant as a sorted list of cubes. A cube is an implicant when every minterm it covers is a 1 or a don't-care, and prime when no larger implicant contains it. Leave out a prime implicant that covers don't-cares only: it is never needed.
  • essential_prime_implicants(n, ones, dont_cares=()) returns, as a sorted list, the prime implicants that are the only prime implicant covering at least one of the 1s.
prime_implicants(2, [1, 2])                  # ['01', '10']: XOR has nothing to group
prime_implicants(3, [7], [3, 5, 6])          # ['-11', '1-1', '11-']
essential_prime_implicants(3, [7], [3, 5, 6])  # []: three groups cover the one 1

Starter code · primes.py

"""Prime implicants of a Boolean function, written as cubes.

A cube has one character per variable, the first variable first: '1' for the variable, '0' for its
complement and '-' where the variable is absent. With four variables A, B, C, D, '0-1-' is A'C.
"""


def prime_implicants(n, ones, dont_cares=()):
    """Every prime implicant that covers at least one 1, as a sorted list of cubes."""
    # Replace this line with your code.
    return []


def essential_prime_implicants(n, ones, dont_cares=()):
    """The prime implicants that alone cover some 1, as a sorted list of cubes."""
    # Replace this line with your code.
    return []
The sample tests · test_primes.py
from primes import essential_prime_implicants, prime_implicants


def test_the_lesson_function():
    """F = Σm(1,2,3,5,7,8,13,15) + d(0,6) has five prime implicants, two of them essential"""
    ones, dcs = [1, 2, 3, 5, 7, 8, 13, 15], [0, 6]
    assert prime_implicants(4, ones, dcs) == ["-000", "-1-1", "0--1", "0-1-", "00--"]
    assert essential_prime_implicants(4, ones, dcs) == ["-000", "-1-1"]


def test_xor_does_not_group():
    """no two 1s of XOR are neighbours, so each 1 is its own essential prime implicant"""
    assert prime_implicants(2, [1, 2]) == ["01", "10"]
    assert essential_prime_implicants(2, [1, 2]) == ["01", "10"]


def test_constant_functions():
    """the 0 function has no implicant at all; the 1 function is one cube"""
    assert prime_implicants(3, []) == []
    assert prime_implicants(3, range(8)) == ["---"]
    assert essential_prime_implicants(3, range(8)) == ["---"]


def test_dont_cares_make_groups_but_are_not_required():
    """the three groups each cover the single 1 with a don't-care, so none is essential"""
    assert prime_implicants(3, [7], [3, 5, 6]) == ["-11", "1-1", "11-"]
    assert essential_prime_implicants(3, [7], [3, 5, 6]) == []


def test_a_cyclic_chart():
    """G = Σm(0,2,6,8,9,11,14,15): eight prime implicants, every 1 covered twice, none essential"""
    ones = [0, 2, 6, 8, 9, 11, 14, 15]
    assert len(prime_implicants(4, ones)) == 8
    assert essential_prime_implicants(4, ones) == []


def test_a_group_of_dont_cares_alone_is_left_out():
    """d(4,5,6,7) would form the group A, but it covers no 1"""
    assert prime_implicants(3, [0], [4, 5, 6, 7]) == ["-00"]
A hint

There are only 3 ** n cubes, so try them all: itertools.product("01-", repeat=n) lists them. Work out the minterms a cube covers by comparing it with format(m, f"0{n}b") for every m below 2 ** n: each character must be - or equal to the bit. Keep the cubes whose minterms are all 1s or don't-cares, then drop every cube whose minterms are a strict subset of another kept cube's.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Practice that adapts to you

Practise this lesson

15 questions about 9 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

  1. Question 1 of 15 On a four-variable K-map, how many literals does a group of four cells have?

    Type a number.

    Show the answer: Question 1 of 15

    Answer: 2 literals

    Each doubling of a group removes one literal. A single cell of a four-variable map has 4 literals, a pair 3, a group of four 2 and a group of eight 1: in an n-variable map a group of 2^k cells has n − k literals.

  2. Question 2 of 15 In which order are the columns of a K-map labelled?

    Choose one answer.

    Show the answer: Question 2 of 15

    Answer: 00, 01, 11, 10

    Gray-code order changes one bit at a time, so neighbouring columns, and the first and last columns, differ in one variable and their cells can be grouped.

  3. Question 3 of 15 When should a don't-care be included in a group?

    Choose one answer.

    Show the answer: Question 3 of 15

    Answer: When it makes the group larger

    A don't-care may be treated as 1 or 0, whichever gives the simpler circuit. Include it only when it lets a group double; an X that joins no group is simply left as 0.

  4. Question 4 of 15 What is the minimal sum of products of F(A,B,C,D) = Σm(0, 2, 8, 10)?

    Choose one answer.

    Show the answer: Question 4 of 15

    Answer: B'D'

    The four corner cells of the map are neighbours of each other, because groups wrap round both edges. Together they form one group of four in which only B = 0 and D = 0 stay fixed, so F = B'D', with 2 literals.

  5. Question 5 of 15 Which identity removes the term BC from AB + A'C + BC?

    Choose one answer.

    Show the answer: Question 5 of 15

    Answer: The consensus theorem

    BC is the consensus of AB and A'C: any input that makes BC equal to 1 makes AB or A'C equal to 1, depending on A. So AB + A'C + BC = AB + A'C.

  6. Question 6 of 15 x + x'y = x + y is an identity. Which identity is its dual?

    Choose one answer.

    Show the answer: Question 6 of 15

    Answer: x(x' + y) = xy

    The dual swaps AND with OR, and 0 with 1, and leaves every literal alone. The dual of an identity is an identity too: x(x' + y) = xx' + xy = xy.

  7. Question 7 of 15 A circuit computes AB + BC' + AC. Which term can be removed without changing the function?

    Choose one answer.

    Show the answer: Question 7 of 15

    Answer: AB

    Look for two terms that disagree on one variable: AC and BC' disagree on C, and their consensus is AB, which is also a term. So AB + BC' + AC = BC' + AC, checked on all eight inputs.

  8. Question 8 of 15 Which statements about essential prime implicants are true?

    Choose every answer that is right.

    Show the answer: Question 8 of 15

    Answer:

    • Every minimal sum of products contains every essential prime implicant
    • An essential prime implicant is the only prime implicant that covers some 1

    An essential prime implicant is the only group that covers at least one of the 1s, so no cover can leave it out. It need not be large, a single cell can be essential, and a cyclic chart has none at all.

  9. Question 9 of 15 How many prime implicants does F(A,B,C) = Σm(1, 2, 3, 4, 5, 6) have?

    Type a number.

    Show the answer: Question 9 of 15

    Answer: 6 prime implicants

    F is 1 everywhere except 000 and 111. Every 1 has two neighbouring 1s and no group of four fits, so the prime implicants are the six pairs A'C, A'B, B'C, AB', BC' and AC'.

  10. Question 10 of 15 How many of the prime implicants of F(A,B,C) = Σm(1, 2, 3, 4, 5, 6) are essential?

    Type a number.

    Show the answer: Question 10 of 15

    Answer: 0 essential prime implicants

    Each 1 is covered by exactly two of the six pairs, so no column of the chart has a single X. The chart is cyclic and a minimal cover, of three pairs, has to be chosen another way, for example with Petrick's method.

  11. Question 11 of 15 F's minimal cover A'B' + BD + B'C'D' leaves the don't-care 6 outside every group. What does the circuit output for input 6, 0110?

    Choose one answer.

    Show the answer: Question 11 of 15

    Answer: 0

    A circuit built from a cover outputs 1 exactly on the cells its groups contain. The don't-care 0 lies inside A'B' and B'C'D', so F(0) = 1; the don't-care 6 lies in none, so F(6) = 0.

  12. Question 12 of 15 In the tabular method, which entries get a column in the prime-implicant chart?

    Choose one answer.

    Show the answer: Question 12 of 15

    Answer: The 1s of the function only

    Don't-cares help terms combine, but a cover does not have to cover them, so they get no column. Giving them columns can make a prime implicant look essential when it is not.

  13. Question 13 of 15 In the tabular method, in how many bit positions must two terms differ for them to combine?

    Type a number.

    Show the answer: Question 13 of 15

    Answer: 1 bit position

    Two terms combine when they differ in exactly one bit and have their dashes in the same places; the bit where they differ becomes a dash. That is the identity xy + xy' = x.

  14. Question 14 of 15 The tabular method runs on g(A,B,C) = Σm(0, 2, 4, 6). How many prime implicants are left unticked at the end?

    Type a number.

    A hint

    Write the four minterms in binary and look at the last bit.

    Show the answer: Question 14 of 15

    Answer: 1 prime implicant

    000, 010, 100 and 110 combine into four pairs (0-0, -00, -10 and 1-0), and those combine into --0, which takes every term in. --0 is C', the only prime implicant: g = C'.

  15. Question 15 of 15 A function of 7 variables has to be minimised exactly. Which approach fits, and why?

    Choose one answer.

    Show the answer: Question 15 of 15

    Answer: The tabular method, because it works for any number of variables and suits a program

    The comparison table of the lesson sets the limit: a K-map in practice up to 4 variables, or 5 with two maps, the tabular method any number. Its steps are mechanical, which is also why programs use it.

The tabular method traced table by table, and cyclic charts solved Pro: opens with a Pro, Premium or Ultimate pass

The tabular method is mechanical, and that is its strength in an exam: every step can be checked. This part runs it on F one table at a time, proves why the cover only ever needs prime implicants, and settles a chart in which no column has a single X.

In this part:

  • Every table of the tabular method on F, worked
  • Why a minimal cover needs prime implicants only, proved
  • A cyclic chart settled with Petrick’s method

2 runnable examples (Python) · about 5 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Counting implicants, literals and functions for numerical answers Pro: opens with a Pro, Premium or Ultimate pass

Numerical answer questions have no options to eliminate, so every count must be exact. This part counts implicants two independent ways, checks the formulas for counting Boolean functions by brute force, and extends maps to five variables.

In this part:

  • Five functions counted two ways, with the numbers
  • How many functions, self-dual and neutral, with the formulas checked
  • Five-variable maps and complete gate sets, worked

3 runnable examples (Python) · about 5 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Three traps that cost marks, reproduced and corrected Pro: opens with a Pro, Premium or Ultimate pass

Most wrong answers on minimisation come from a handful of habits that work on easy maps and fail on others. This part reproduces three of them on original functions and shows the correct reasoning next to each.

In this part:

  • The biggest group is not always in the answer
  • Don’t-cares in a product of sums are decided separately
  • XOR patterns never group, and the counts questions ask for

1 runnable example (Python) · about 4 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Interview questions

  1. Fresher · Warm-up

    What is the difference between a prime implicant and an essential prime implicant?

    An implicant is a product term that is 1 only where the function is 1 (or a don't-care); on a K-map it is a group of 1, 2, 4 or 8 cells. A prime implicant is an implicant that cannot be made any larger: no bigger group containing it stays inside the 1s and don't-cares. An essential prime implicant is a prime implicant that is the only one covering at least one of the function's 1s, so every minimal sum of products must contain it. A function can have many prime implicants and no essential ones at all: in a cyclic chart every 1 is covered by two or more prime implicants. The usual procedure takes the essential prime implicants first and then chooses among the others to cover the 1s that are left.

  2. Fresher to mid

    A classmate's K-map program always circles the largest remaining group first. It passes every textbook example you try, then gives five terms where four are enough. What kind of function breaks it, and how would you change the algorithm so that it is always right?

    Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups

  3. Fresher to mid

    For a function with don't-cares, your minimal sum of products and your minimal product of sums give different outputs on one input. A friend says one of them must be wrong. Is that true? Explain, and say how you would check both answers.

    Model answer, Pro. First step and follow-ups

  4. Fresher

    A numerical answer question asks for the number of essential prime implicants of a four-variable function with two don't-cares. How do you get an exact count in about three minutes, and where do most candidates lose the mark?

    Model answer, Pro. First step and follow-ups

Key takeaways

  • Two terms that differ in one variable merge, and consensus and absorption remove terms that add nothing.
  • On a K-map, a rectangle of 2k cells in Gray-code order, wrapping round the edges, is a product of n − k literals.
  • Essential prime implicants go into every minimal cover first, and the fewest, largest groups cover the rest.
  • The tabular method merges terms one bit apart until nothing merges, then picks a cover from a chart of the 1s.

Terms in this lesson

don't-care
An input whose output does not matter, because it never occurs or its output is ignored. Written X on a K-map or d(…) in a list, it may be read as 1 or 0, whichever gives the simpler circuit.
essential prime implicant
A prime implicant that is the only one covering some 1 of the function, so every minimal sum of products contains it.
Gray code
An order of binary numbers in which neighbours differ in exactly one bit, such as 00, 01, 11, 10. A K-map labels its rows and columns in this order, so cells that sit side by side can merge.
literal
A variable or its complement as it appears in an expression. A'B' + BD has four literals, and counting literals is how two expressions for the same function are compared.
minterm
A product of all of a function's variables, each plain or complemented once, which is 1 on exactly one row of the truth table: with A, B, C and D, minterm 5 is A'BC'D.
prime implicant
A product term that is 1 only where the function is 1 or a don't-care and cannot be made larger: on a K-map, a group that no bigger rectangle of 1s and don't-cares contains.

References

Related tools

Report a problem with this lesson

Quick answers and tool search

Type to search tools or to get a quick answer, for example 18% of 2500. Use the up and down arrow keys to move through the results, Enter to choose, and Escape to close.