Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 37 · Applications in CS

Boolean Algebra and Logic Circuits

Connect logic to hardware: Boolean algebra laws, sum-of-products and product-of-sums, minimization, NAND universality and adders built from gates, with Python simulations.

Every digital computer is, underneath, a machine that computes with 0 and 1. Boolean algebra, named after George Boole, is the mathematics of those values, and it is the same algebra as propositional logic and as set operations (union, intersection, complement). In 1937 Claude Shannon showed that switching circuits obey Boole's laws, which launched digital design.

A Boolean algebra is a set with two binary operations (AND ·, OR +), a complement (NOT ¬ or an overbar) and two constants 0 and 1. The two-element algebra {0, 1} is the one used in hardware; (P(A), ∪, ∩, ᶜ, ∅, A) from the set operations lesson is another. This is the Boolean lattice structure mentioned in partial orders and lattices.

The laws

Law AND form OR form
Identity x · 1 = x x + 0 = x
Domination x · 0 = 0 x + 1 = 1
Idempotent x · x = x x + x = x
Complement x · ¬x = 0 x + ¬x = 1
Commutative, associative yes yes
Distributive x(y+z) = xy + xz x + yz = (x+y)(x+z)
Absorption x(x+y) = x x + xy = x
De Morgan ¬(xy) = ¬x + ¬y ¬(x+y) = ¬x · ¬y

Every law has a dual: swap AND with OR and 0 with 1 and you get another law. So each proof gives you two theorems. The distributive law of OR over AND has no counterpart in ordinary arithmetic and often surprises beginners.

Python Verify the laws by exhaustion

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.

Normal forms: from truth table to formula

Any Boolean function given by a truth table has a formula. The canonical sum of products (SOP, DNF) takes one minterm (an AND of all variables, each possibly negated) for every row where the output is 1, and ORs them. The product of sums (POS, CNF) takes one maxterm per 0-row. Because every function has such a form, {AND, OR, NOT} is functionally complete.

Even smaller sets work: alone is complete since ¬x = x NAND x and x AND y = ¬(x NAND y). Chip designers love this, because one gate type suffices to build everything.

Python From truth table to SOP, and NAND universality

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.

Minimization

The canonical SOP is correct but wasteful. Simplifying reduces gates and cost. Two classic methods: Karnaugh maps, a visual grouping of adjacent 1s for up to about four variables, and the Quine-McCluskey algorithm, which repeatedly merges minterms that differ in one bit into prime implicants and then selects a minimal cover. The merging step is the same as the algebraic law xy + xy' = x.

Python Quine-McCluskey merging, compared with sympy

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.

Gates and arithmetic circuits

Gates implement the operators: AND, OR, NOT, NAND, NOR and XOR. Arithmetic is built from them. A half adder adds two bits: sum = a XOR b, carry = a AND b. A full adder adds three (including a carry-in) using two half adders and an OR. Chain n full adders and you have an n-bit ripple-carry adder: the carry ripples from the lowest bit up.

flowchart LR
    A["a"] --> X1["XOR"]
    B["b"] --> X1
    A --> A1["AND"]
    B --> A1
    X1 --> S["sum"]
    A1 --> C["carry"]

A half adder: XOR gives the sum bit, AND gives the carry.

Python A ripple-carry adder built from gates

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.

The final check matters: gate-level logic gives a machine-verified match with the integer arithmetic. Hardware verification at scale does the same using the SAT solvers from the previous lesson, by asking whether any input makes two circuits disagree.

When you design a circuit, write the truth table first, derive the canonical SOP, minimize, and only then draw gates. Check the result against the table by exhaustive simulation as shown above.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which is De Morgan's law for Boolean algebra?

    The complement of an OR is the AND of the complements. The others are wrong: x + xy = x, x · ¬x = 0, x + 1 = 1.
  2. 2. Why is NAND called a universal gate?

    NOT, AND and OR can all be expressed with NAND, and those three are functionally complete.
  3. 3. A half adder computes the sum bit and carry bit with which gates?

    sum = a XOR b, carry = a AND b.
  4. 4. Which rule underlies the merging step in Quine-McCluskey?

    Two minterms that differ in one variable combine into a term without that variable.

Summary

  • Boolean algebra obeys identity, complement, distributive, absorption and De Morgan laws, and each law has a dual.
  • Every truth table has a canonical SOP and POS form; AND/OR/NOT, and even NAND alone, are functionally complete.
  • Karnaugh maps and Quine-McCluskey minimize circuits by merging terms that differ in one variable.
  • Adders are built from XOR/AND gates; exhaustive simulation or SAT checks that a circuit meets its specification.

Next: Hoare Logic and Program Verification