Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 57 · Boolean Algebra

Boolean Algebra Laws

Learn the laws of Boolean algebra: identity, null, complement, distributive, absorption and duality, and prove each one with a truth-table checker in Python.

A logic circuit is a picture of a Boolean expression, and the same function can be written in many ways. Some expressions need ten gates, and an equivalent one needs three. Boolean algebra is the set of rules that lets you rewrite an expression into a cheaper, faster or clearer one without changing what it computes.

The rules are few and easy to remember, and unlike ordinary algebra, every one of them can be proven by brute force: a function of n inputs has only 2n input combinations, so you can check all of them. In this lesson you will learn the laws, the principle of duality that halves the amount you must memorize, and a small Python proof engine that tests any identity you write.

Notation

Boolean variables take the values 0 and 1. The three basic operations have several notations:

Operation Written Python used here
AND a·b or ab a & b
OR a + b a | b
NOT a′ or ā N(a) (that is, 1 - a)

AND binds tighter than OR, and NOT binds tightest, so ab + c means (a AND b) OR c. In the code examples we always add explicit parentheses to avoid mistakes.

The laws

Each law below comes as a pair. The second law of a pair is the first with AND and OR swapped and 0 and 1 swapped. That pairing is the principle of duality.

Name AND form OR form
Identity a·1 = a a + 0 = a
Null (domination) a·0 = 0 a + 1 = 1
Idempotent a·a = a a + a = a
Complement a·a′ = 0 a + a′ = 1
Involution (a′)′ = a (self-dual)
Commutative ab = ba a + b = b + a
Associative (ab)c = a(bc) (a + b) + c = a + (b + c)
Distributive a(b + c) = ab + ac a + bc = (a + b)(a + c)
Absorption a(a + b) = a a + ab = a

Two of these deserve a closer look because they have no counterpart in everyday algebra:

  • Idempotent: repeating a signal changes nothing. a + a = a (not 2a), because OR only asks "is any input 1?".
  • The OR-distributive law: a + bc = (a + b)(a + c). In school algebra, addition does not distribute over multiplication, but in Boolean algebra it does. You will use it constantly when converting to product-of-sums.

Four families of laws

Constants Identity, null and complement.
Rearranging Commutative and associative.
Distributing AND over OR, and OR over AND.
Removing terms Idempotent and absorption.

Each law has a dual: swap AND with OR and 0 with 1.

1 / 2

Proving a law with a truth table

The absorption law a + ab = a says that the term ab is redundant. A truth table proves it:

a b ab a + ab
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

The last column equals a in every row, so the identity holds. This technique is called perfect induction. It needs no cleverness, and a computer does it instantly.

The program below keeps each law as a pair of text expressions. The function N is NOT. An eval call evaluates both sides for every input combination, and the checker reports PASS only if all rows agree.

Python A proof engine for Boolean laws

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All nine laws print PASS. Because the engine takes any pair of expressions, you can use it to test a rewrite you are unsure about.

Duality in code

The principle of duality says that if you swap & with | and 0 with 1 on both sides of a true identity, the new identity is true as well. That is a free second law for every law you learn.

You can verify it mechanically. The code below builds the dual of each law by swapping the symbols in the text, and checks that the dual also holds. It also tests a few popular but false statements, and prints a counterexample for each. Finding one input where two expressions disagree is the fastest way to disprove an identity.

Python Duals and counterexamples

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every dual of a true law holds. The three claims at the bottom are false, and each counterexample shows an input where the sides disagree. Notice that the second claim, N(a & b) == N(a) & N(b), is a common mistake. The correct version is one of De Morgan's theorems, the subject of the next lesson.

Simplifying with the laws

Now put the laws to work. Take f = ab + ab′ + a′b. A step-by-step reduction:

  1. ab + ab′ = a(b + b′) (distributive)
  2. a(b + b′) = a·1 (complement)
  3. a·1 = a (identity), so f = a + a′b
  4. a + a′b = (a + a′)(a + b) (OR-distributive law)
  5. (a + a′)(a + b) = 1·(a + b) = a + b (complement, identity)

The simplified function a + b needs one gate instead of five. Writing it by hand is the point, but checking each step is what keeps you honest:

Python Check every step of a simplification

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If you make a mistake in one step, the checker tells you which step broke the chain.

When simplifying by hand, look for these patterns first: a variable together with its complement (a + a′ = 1), a term contained in another (absorption), and two terms that differ in exactly one variable (xy + xy′ = x). Karnaugh maps, coming soon, make the last pattern visible at a glance.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does a + 1 equal?

    This is the null (domination) law for OR. If any input of an OR is 1, the output is 1 whatever a is.
  2. 2. Which expression is the dual of a(b + c) = ab + ac?

    Swapping AND with OR on both sides gives a + bc = (a + b)(a + c), the distributive law of OR over AND.
  3. 3. What does the absorption law a + ab = a tell you?

    When a is 1 the whole OR is 1 anyway, and when a is 0 the product ab is 0, so ab never changes the result.
  4. 4. How many rows must a truth table check to prove an identity in 4 variables?

    Four variables have 2 to the power 4 = 16 input combinations.

Summary

  • Boolean algebra lets you rewrite an expression without changing its function; fewer terms usually mean fewer gates.
  • Core laws: identity, null, idempotent, complement, involution, commutative, associative, distributive, absorption.
  • Duality: swap AND with OR and 0 with 1, and every true law yields another true law.
  • Unlike school algebra, OR distributes over AND: a + bc = (a + b)(a + c).
  • Perfect induction (a truth table over all inputs) proves any identity, and a few lines of Python automate it, including counterexample search.

Next: De Morgan's Theorems and Bubble Pushing.