1. Home
2. Academy
3. Digital Logic from Zero
4. Volume 03

3.1 The rules of Boolean algebra

Boolean algebra is ordinary algebra with only two numbers, 0 and 1. A handful of rules let you rewrite a circuit's formula as a simpler one that does exactly the same job - and a simpler formula means fewer gates.

A formula such as A·B + C is called a Boolean expression. It describes a circuit exactly: every letter is an input, every · is an AND gate, every + is an OR gate and every ' is a NOT gate. Change the formula without changing its truth table, and you have a different circuit that does the same job.

The rules

Each rule below comes in two forms, one for AND and one for OR. Every one of them was checked on every row of its truth table by the simulator behind this page.

Most of these match ordinary algebra, with 0 and 1 behaving as you would expect. A few do not. In ordinary algebra A + A is 2A, but in logic A OR A is just A. And A + 1 is always 1: if one input of an OR gate is 1, the output is 1 whatever the other input does.

Proving a rule with a truth table

Any rule can be proved by checking every row, because there are only so many rows. Here is the second distributive rule, which has no match in ordinary algebra:

The A + B·C column and the (A + B)·(A + C) column match on all eight rows, so the two sides are equal. This way of proving a rule is called perfect induction: you check every case there is.

Duality

Look along any row of the rules table. The OR form is the AND form with every · swapped for +, every + for ·, every 0 for 1 and every 1 for 0. This is the duality principle: swap them all in any true rule, and you get another true rule. So you only ever need to remember half of the table.

Y = A + B·C
  = (A + B)·C     wrong: this is not the distributive rule

first row where they differ: A=1 B=0 C=0

3.2 De Morgan's theorems

De Morgan's theorems say how to invert an AND or an OR. To invert an AND, invert each input and change the AND to OR. To invert an OR, invert each input and change the OR to AND. "Break the bar, change the sign."

In formulas, the two theorems are:

Y = (A·B)'
  = A' + B'

Y = (A + B)'
  = A'·B'

Both are in the rules table of the last sub-module, and both can be proved by perfect induction:

The (A·B)' column matches the A' + B' column on every row. In words: "not both" means the same as "at least one is not".

What it means for gates

De Morgan says a NAND gate is the same as an OR gate with inverted inputs. Figure 3.1 draws both. You met the second circuit in Volume 02, where three NANDs made an OR - this is why that worked.

More than two inputs

The theorems stretch to any number of inputs:

(A·B·C)' = A' + B' + C' on every row: True
(A + B + C)' = A'·B'·C' on every row: True

Using De Morgan on a bigger formula

Work from the outside in. Break the outermost bar first, then keep going until every bar sits on a single letter:

Y = (A·B + C)'
  = (A·B)'·C'      De Morgan on the OR
  = (A' + B')·C'   De Morgan on the AND

Y = (A + B)'
  = A' + B'     wrong: the + must become ·

3.3 Sum of products and product of sums

Any truth table can be written in two standard shapes. A sum of products ORs together one AND term for each row that gives 1. A product of sums ANDs together one OR term for each row that gives 0.

An example: the majority function

A majority circuit has three inputs and gives 1 when at least two of them are 1. Three judges vote, and the majority wins:

Sum of products: one term for each 1

Take each row where Y is 1. Write an AND term that is 1 on that row and nowhere else: use the plain letter where the input is 1, and the inverted letter where it is 0.

row 011: A'·B·C = 1
row 101: A·B'·C = 1
row 110: A·B·C' = 1
row 111: A·B·C = 1

Then OR them together. Y is 1 exactly when one of those rows is happening:

from the 1s: Y = A'·B·C + A·B'·C + A·B·C' + A·B·C

A sum of products becomes two layers of gates: a row of AND gates, all feeding one OR gate.

Product of sums: one term for each 0

Now take each row where Y is 0, and write an OR term that is 0 on that row only. This time use the plain letter where the input is 0, and the inverted letter where it is 1:

row 000: (A + B + C) = 0
row 001: (A + B + C') = 0
row 010: (A + B' + C) = 0
row 100: (A' + B + C) = 0

AND them together, and Y is 0 exactly when one of those rows is happening:

from the 0s: Y = (A + B + C)·(A + B + C')·(A + B' + C)·(A' + B + C)

Both formulas describe the same truth table, so they are equal. The simulator checked both against it:

sum of products matches the table: True
product of sums matches the table: True

Two levels of NAND

A sum of products turns neatly into NAND gates alone. By De Morgan, an AND-then-OR circuit is the same as a NAND-then-NAND circuit:

Y = A·B + C·D
  = ((A·B)'·(C·D)')'   De Morgan, twice

That is why a sum of products is the favourite shape for real circuits: it maps straight onto the cheapest gates there are.

3.4 Minterms and maxterms

Number the rows of a truth table 0, 1, 2 and so on. A minterm is the AND term that is 1 on just one row, and a maxterm is the OR term that is 0 on just one row. Listing row numbers is the shortest way to write down a whole function.

Each row's number is its inputs read as a binary number, which is why truth tables are written in counting order. For three inputs:

Minterm number 3 is written m₃, and maxterm number 3 is M₃. Notice that each maxterm is its minterm inverted, by De Morgan.

Σ and Π notation

Instead of writing the whole sum of products, list the rows that give 1 after a Σ, which means "OR of the minterms". Instead of the whole product of sums, list the rows that give 0 after a Π, which means "AND of the maxterms". For the majority function:

majority: Y = Σm(3, 5, 6, 7) = ΠM(0, 1, 2, 4)

Every row is in exactly one of the two lists, so if you know one list you know the other. The rows missing from the Σ list are the ones where the output is 0. They also give the inverted function:

Y' = Σm(0, 1, 2, 4)

How many functions are there?

A function of n inputs has 2ⁿ rows, and each row can be 0 or 1. So there are 2 to the power 2ⁿ different functions of n inputs:

There are exactly 16 functions of two inputs. AND, OR, NAND, NOR, XOR and XNOR are six of them.

3.5 Simplifying step by step

Simplifying means finding a smaller formula with the same truth table. Each step uses one rule, and every step keeps the function the same - so the circuit you end with does exactly what the first one did, with fewer gates.

The majority function, simplified

The sum of products from sub-module 3.3 needs four 3-input AND gates and a 4-input OR gate. Watch it shrink. The trick in the second line is the idempotent rule, used backwards. Since A·B·C = A·B·C + A·B·C, a term may be copied as often as it is useful.

Y = A'·B·C + A·B'·C + A·B·C' + A·B·C
  = A'·B·C + A·B'·C + A·B·C' + A·B·C + A·B·C + A·B·C   idempotent: copy A·B·C twice
  = (A'·B·C + A·B·C) + (A·B'·C + A·B·C) + (A·B·C' + A·B·C)   regroup in pairs
  = B·C·(A' + A) + A·C·(B' + B) + A·B·(C' + C)   distributive
  = B·C·1 + A·C·1 + A·B·1   complement
  = B·C + A·C + A·B   identity

Each line of that listing was checked against the first on all eight rows. The result needs three 2-input AND gates and one 3-input OR gate:

letters: 12 before, 6 after

Three short ones

The same few moves come up again and again. Each of these was checked on every row:

Y = A·B + A·B'
  = A·(B + B')   distributive
  = A·1          complement
  = A            identity

Y = (A + B)·(A + B')
  = A + B·B'     distributive, the OR form
  = A + 0        complement
  = A            identity

Y = A·B + A'·C + B·C
  = A·B + A'·C + B·C·(A + A')   complement and identity
  = A·B + A'·C + A·B·C + A'·B·C   distributive
  = A·B + A·B·C + A'·C + A'·C·B   regroup
  = A·B + A'·C                  absorption, twice

The last one is called the consensus theorem. When one term has A and another has A', a third term made of their other letters (here B·C) adds nothing, and can go.

When are you done?

Algebra always gives a correct answer, but it never tells you whether a smaller one exists. You stop when you cannot see another step, and a better answer might still be hiding. For the majority function, a search of every possible answer confirms that three terms is the least:

the cheapest possible: A·B + A·C + B·C

Volume 04 gives you a method that finds the smallest answer every time, by drawing the truth table as a map.

What you learned

• Boolean algebra has rules that match ordinary algebra, and a few that do not: A + A = A, A + 1 = 1 and A + B·C = (A + B)·(A + C).
• Any rule can be proved by perfect induction: check it on every row of its truth table.
• Swap · with +, and 0 with 1, in a true rule and you get another true rule. This is duality.
• De Morgan: (A·B)' = A' + B' and (A + B)' = A'·B'. Break the bar, change the sign.
• A sum of products has one AND term per 1; a product of sums has one OR term per 0.
• Minterms and maxterms are numbered by row, so a function can be written Σm(...) or ΠM(...).
• Simplifying keeps the truth table and shrinks the circuit: the majority function falls from 12 letters to 6.
• Algebra cannot prove that an answer is the smallest. Volume 04's K-maps can.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• Boolean algebra
• Boolean expression
• Duality
• De Morgan's theorems
• Sum of products
• Product of sums
• Minterm
• Maxterm
• Consensus theorem

Practice

Y = A + A·B
  = A·1 + A·B    identity
  = A·(1 + B)    distributive
  = A·1          null: 1 + B = 1
  = A            identity

Y = ((A + B')·C)'
  = (A + B')' + C'   De Morgan on the AND
  = A'·B'' + C'      De Morgan on the OR
  = A'·B + C'        double inversion

Y = A ⊕ B ⊕ C = Σm(1, 2, 4, 7) = ΠM(0, 3, 5, 6)

(A + B)·(A' + C)·(B + C) = (A + B)·(A' + C) on every row: True

Interview corner

Volume 04 draws truth tables as maps, where the simplest formula can simply be read off.