AlgoVerse

Karnaugh maps, DNF and CNF

From the true rows of a truth table, build the canonical disjunctive (DNF) and conjunctive (CNF) forms, then merge neighbouring cells as on a Karnaugh map (the Quine–McCluskey method) to find a simplest sum of products.

Every Boolean function can be written down from its truth table:

Read the full explanation ↓
Input:
M 1×10 · n=4PDF export

A four-variable function with minterms 0, 1, 2, 5, 6, 7, 8, 9, 10, 14; the K-map shrinks it to a few short terms.

  1. def karnaugh(M, n):
  2. # M: the minterms (rows of the truth table where f = 1) of a function of n variables a, b, c, d.
  3. ones = sorted(set(M[0]))
  4. for m in ones:
  5. if m >= 2 ** n:
  6. return None
  7. kmap = draw(ones, n)
  8. dnf = []
  9. cnf = []
  10. for m in range(2 ** n):
  11. if m in ones:
  12. dnf.append(term([m, 0], n, "∧"))
  13. else:
  14. cnf.append(clause(m, n))
  15. dnf_text = " ∨ ".join(dnf) if dnf else "0"
  16. cnf_text = " ∧ ".join(cnf) if cnf else "1"
  17. # Quine–McCluskey. An implicant is [value, mask]: the mask bits are the variables it no longer mentions.
  18. # Two implicants merge when they have the same mask and differ in one bit, as neighbouring K-map blocks do.
  19. current = [[m, 0] for m in ones]
  20. primes = []
  21. while current:
  22. merged = []
  23. used = []
  24. for i in range(len(current)):
  25. for j in range(i + 1, len(current)):
  26. a = current[i]
  27. b = current[j]
  28. x = a[0] ^ b[0]
  29. if a[1] != b[1] or x & (x - 1) != 0:
  30. continue
  31. used.append(a)
  32. used.append(b)
  33. both = [a[0] & ~x, a[1] | x]
  34. if both not in merged:
  35. merged.append(both)
  36. shown = term(both, n, "")
  37. for t in current:
  38. if t not in used and t not in primes:
  39. primes.append(t)
  40. shown = term(t, n, "")
  41. current = merged
  42. table = [] # for the picture: each prime implicant and the minterms it covers
  43. cover = []
  44. for p in primes:
  45. cover.append([m for m in ones if m & ~p[1] == p[0]])
  46. table.append([term(p, n, ""), cover[-1]])
  47. chosen = []
  48. for m in ones:
  49. holders = [k for k in range(len(primes)) if m in cover[k]]
  50. if len(holders) == 1 and holders[0] not in chosen:
  51. chosen.append(holders[0])
  52. shown = table[holders[0]][0]
  53. left = [m for m in ones if not any(m in cover[k] for k in chosen)]
  54. while left:
  55. best = 0
  56. for k in range(len(primes)):
  57. if len(set(cover[k]) & set(left)) > len(set(cover[best]) & set(left)):
  58. best = k
  59. chosen.append(best)
  60. left = [m for m in left if m not in cover[best]]
  61. shown = table[best][0]
  62. minimal = " ∨ ".join(table[k][0] for k in chosen) if chosen else "0"
  63. return minimal
  66. def term(p, n, op):
  67. parts = []
  68. for i in range(n):
  69. bit = 1 << (n - 1 - i)
  70. if p[1] & bit:
  71. continue
  72. parts.append("abcd"[i] if p[0] & bit else "¬" + "abcd"[i])
  73. if not parts:
  74. return "1"
  75. return op.join(parts)
  78. def clause(m, n):
  79. parts = []
  80. for i in range(n):
  81. bit = 1 << (n - 1 - i)
  82. parts.append("¬" + "abcd"[i] if m & bit else "abcd"[i])
  83. return "(" + " ∨ ".join(parts) + ")"
  86. def draw(ones, n):
  87. # Rows and columns in Gray-code order, so neighbouring cells differ in one variable (and the edges wrap around).
  88. gray = {1: ["0", "1"], 2: ["00", "01", "11", "10"]}
  89. rbits = n // 2
  90. cbits = n - rbits
  91. rows = [["·"] + gray[cbits]]
  92. for r in gray[rbits]:
  93. row = [r]
  94. for c in gray[cbits]:
  95. row.append("1" if int(r + c, 2) in ones else "0")
  96. rows.append(row)
  97. return rows

Invariant: Every implicant covers only minterms of the function; merging two neighbouring implicants gives a bigger one with one variable fewer.

Start

dnf_text—
cnf_text—
minimal—

kmap

The table is still empty.

table

The table is still empty.

Local variables

n4

Orange = changed in this step

M list

[0, 1, 2, 5, 6, 7, 8, 9, 10, 14]

Call stack

  1. karnaugh()line 1
Step 1 of 2,088
Black = prime · Orange = key stepcanonical: 0/1 · merge: 0/16 · prime: 0/6 · essential: 0/2 · pick: 0/1 · minimal: 0/1
    Explanation

    Canonical forms

    Every Boolean function can be written down from its truth table:

    • Canonical DNF (a sum of minterms): for each row where the function is 1, a product of all the variables (or their negations).
    • Canonical CNF (a product of maxterms): for each row where the function is 0, an "or" clause that is false exactly in that row.

    These forms are correct but long.

    Karnaugh maps

    A Karnaugh map is the truth table with its rows and columns in Gray-code order, so neighbouring cells (even across the edges) differ in one variable. Every rectangular block of 1s whose size is a power of 2 is one term with fewer variables. The goal: the fewest and largest blocks that cover every 1.

    Quine–McCluskey

    The same thing as an algorithm: merge implicants that differ in one variable (0101 and 0111 → 01-1) until nothing merges; those that never merged are the prime implicants. Then take the essential ones and cover the rest greedily (an optimal cover is hard in general).

    The input

    M lists the rows where the function is 1 (a is the most significant bit), and n is the number of variables. The first table is the Karnaugh map (rows a or ab, columns the rest) and the second the prime implicants with the minterms they cover.