Discrete Math · Undergraduate

Boolean Algebra and Logic Gates

Quick answer

Boolean algebra is the arithmetic of the two values 0 and 1, with AND (written AB), OR (A + B) and NOT (A′). Its laws, such as A + AB = A and De Morgan's (A + B)′ = A′B′, simplify expressions, and every expression is a circuit of logic gates. Any truth table can be written as a sum of products, one product for each row that outputs 1, and then simplified. A half adder, the circuit that adds two bits, needs only an XOR gate for the sum and an AND gate for the carry.

What you'll learn

  • Evaluate Boolean expressions with AND, OR and NOT
  • Simplify expressions with the laws of Boolean algebra
  • Write a sum-of-products formula from a truth table
  • Describe simple circuits such as a half adder

Arithmetic with 0 and 1

Propositional logic becomes algebra when true is 11 and false is 00:

AABBABAB (AND)A+BA + B (OR)A′A' (NOT)A⊕BA \oplus B (XOR)
000010
010111
100101
111100

Each operation is a logic gate in a circuit, and each expression is a wiring diagram. The laws of Boolean algebra simplify those diagrams:

LawAND formOR form
identityA⋅1=AA \cdot 1 = AA+0=AA + 0 = A
complementAA′=0AA' = 0A+A′=1A + A' = 1
idempotentAA=AAA = AA+A=AA + A = A
absorptionA(A+B)=AA(A + B) = AA+AB=AA + AB = A
distributiveA(B+C)=AB+ACA(B + C) = AB + ACA+BC=(A+B)(A+C)A + BC = (A + B)(A + C)
De Morgan(AB)′=A′+B′(AB)' = A' + B'(A+B)′=A′B′(A + B)' = A'B'

Why every truth table has a formula

Look at one row where the output is 11, say A=1A = 1, B=0B = 0, C=1C = 1. The product AB′CAB'C is 11 on that row and 00 on every other, because some factor fails elsewhere. ORing together one such product for each row that outputs 11 gives an expression that is 11 on exactly those rows: a sum of products. So any function of bits can be built from AND, OR and NOT gates. The laws then shrink the formula, saving gates.

Worked examples

Common mistakes

Practice problems

  1. Simplify (A+B)(A+B′)(A + B)(A + B').

    Answer

    AA

    Full solution

    By the distributive law, A+BB′=A+0=AA + BB' = A + 0 = A.

  2. Apply De Morgan’s law to (A+B′)′(A + B')'.

    Answer

    A′BA'B

    Full solution

    (A+B′)′=A′(B′)′=A′B(A + B')' = A'(B')' = A'B.

  3. Evaluate F=AB+C′F = AB + C' at A=1A = 1, B=0B = 0, C=0C = 0.

    Answer

    11

    Full solution

    AB=0AB = 0 and C′=1C' = 1, so F=0+1F = 0 + 1.

  4. Simplify A+AB+AB′CA + AB + AB'C.

    Answer

    AA

    Full solution

    Every term contains the factor AA, so absorption reduces the whole sum to AA.

  5. Write a sum of products for the function that is 11 exactly when A=BA = B.

    Answer

    A′B′+ABA'B' + AB

    Full solution

    The rows (0,0)(0, 0) and (1,1)(1, 1) give the products A′B′A'B' and ABAB. This is NOT of XOR.

  6. How many different Boolean functions of three variables are there?

    Answer

    256256

    Full solution

    A truth table has 23=82^3 = 8 rows, each with output 00 or 11: 282^8 tables.

  7. Show that A⊕B=(A+B)(AB)′A \oplus B = (A + B)(AB)'.

    Answer

    Both are 11 exactly when one input is 11.

    Full solution

    (A+B)(A′+B′)=AA′+AB′+A′B+BB′=AB′+A′B(A + B)(A' + B') = AA' + AB' + A'B + BB' = AB' + A'B.

  8. A student writes (AB)′=A′B′(AB)' = A'B'. Give inputs that show the error.

    Answer

    A=1A = 1, B=0B = 0

    Full solution

    (AB)′=(0)′=1(AB)' = (0)' = 1, but A′B′=0⋅1=0A'B' = 0 \cdot 1 = 0. The correct law is (AB)′=A′+B′(AB)' = A' + B'.

Frequently asked questions

What is Boolean algebra?

Algebra on the values 0 and 1 with three operations: AND (AB is 1 only if both are 1), OR (A + B is 1 if either is 1) and NOT (A′ flips the value).

How is it related to logic?

It is propositional logic with 1 for true and 0 for false: AND is ∧, OR is ∨ and NOT is ¬.

What is a sum of products?

An OR of AND terms, such as A′B + AB′. Every truth table has one: take a product for each row that outputs 1.

What are De Morgan's laws in Boolean form?

(A + B)′ = A′B′ and (AB)′ = A′ + B′. Negating flips AND and OR and negates each variable.

What does a half adder do?

It adds two bits A and B, producing a sum bit S = A ⊕ B (exclusive OR) and a carry bit C = AB.