Skip to content
Digital Electronic Systems

Boolean algebra, canonical forms and Karnaugh maps

Operations and theorems of Boolean algebra, De Morgan with proof, sums of products and products of sums, Karnaugh maps with a complete example, don't-care conditions.

3 min read 0 comments

Digital circuits work with only two values, 0 and 1, and their behaviour is described by Boolean algebra. Designing a logic network means writing the function it must compute and simplifying it, because a shorter expression needs fewer gates, less area, less power and less delay. In this lesson we cover the axioms and theorems of Boolean algebra, canonical forms and the Karnaugh map method.

Operations and theorems

The basic operations are the logical product (AND, A\cdot B or AB), the logical sum (OR, A + B) and negation (NOT, \overline{A}). The commutative, associative and distributive properties hold, with one surprise: in Boolean algebra both operations distribute, including A + BC = (A + B)(A + C). Other useful identities:

NameOR formAND form
identityA + 0 = AA\cdot 1 = A
null elementA + 1 = 1A\cdot 0 = 0
idempotenceA + A = AA\cdot A = A
complementA + \overline{A} = 1A\cdot\overline{A} = 0
absorptionA + AB = AA(A + B) = A
De Morgan\overline{A + B} = \overline{A}\,\overline{B}\overline{AB} = \overline{A} + \overline{B}

Every identity has a dual, obtained by swapping AND with OR and 0 with 1.

Theorem (De Morgan). \overline{A + B} = \overline{A}\cdot\overline{B}.

Proof. With two variables there are only four cases, and it is enough to check them all (proof by exhaustion, always possible in an algebra with finitely many values): for A = B = 0 both sides equal 1; in the other three cases at least one variable is 1, so A + B = 1 and the left side is 0, and so is the right side, because at least one of the two negated factors is 0. ∎

De Morgan has a fundamental practical consequence: with NAND gates alone (or NOR gates alone) any function can be built, and that is exactly how CMOS gates are made (Electronic Devices lesson on CMOS logic).

Canonical forms

Any function can be written starting from its truth table.

  • Sum of products (SOP): for each row where the function is 1, write the product of the variables, negated where they are 0 (a minterm), and add them all. It is abbreviated with the list of row numbers: f = \sum m(\dots).
  • Product of sums (POS): the dual, starting from the rows where the function is 0.

The canonical form is correct but long: a 4-variable function with 8 minterms needs 8 four-input AND gates and one eight-input OR.

Karnaugh maps

The simplification idea is the theorem AB + A\overline{B} = A: two minterms differing in only one variable merge, and that variable disappears. The Karnaugh map lays out the truth table on a grid where adjacent cells differ in only one variable: rows and columns follow the Gray code (00, 01, 11, 10), and opposite edges are adjacent too, as if the map were wrapped on a torus.

Four-variable Karnaugh map with two groupings
Rows correspond to AB and columns to CD, both in Gray code. The 1s in the four corners form a single group, because opposite edges are adjacent, and give the term B-bar times D-bar; the central block of four 1s gives the term BD. The simplified function is the sum of the two terms.

The procedure.

  1. Enter the function’s 1s in the cells.
  2. Group the 1s into rectangles of 1, 2, 4, 8… adjacent cells, as large as possible; a 1 can belong to several groups.
  3. Each group of 2^k cells eliminates k variables: those that do not change within the group remain.
  4. The function is the sum of the group terms, chosen in minimum number to cover all the 1s.

Example. f(A, B, C, D) = \sum m(0, 2, 5, 7, 8, 10, 13, 15). Minterms 5, 7, 13, 15 form a square in the middle of the map: in all of them B = 1 and D = 1, while A and C change, so the group is BD. Minterms 0, 2, 8, 10 are in the four corners, which are adjacent to each other: they have B = 0 and D = 0, and give \overline{B}\,\overline{D}. So

    \[ f = \overline{B}\,\overline{D} + BD \]

that is the function is 1 when B and D are equal: it is the complement of an XOR, \overline{B \oplus D}. Eight four-variable minterms reduce to a single XNOR gate.

Don’t-care conditions. Often some input combinations cannot occur (for example codes 10 to 15 in a circuit receiving BCD decimal digits). They are marked with an X on the map and can be treated as 1 or 0, whichever helps form larger groups.

Beyond maps

Maps work well up to 4 to 5 variables. For larger functions algorithms are used (Quine-McCluskey, Espresso), which today live inside logic synthesis tools: the designer describes the function in a language such as VHDL or Verilog (lesson on FPGAs) and the program finds the gate network, optimising area, delay and power.

Related articles

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x