Lesson 15 – Boolean Algebra for Digital Logic Analysis#
Learning Outcomes#
Express logic gates as Boolean equations.
Construct truth tables from Boolean equations and logic diagrams.
Develop Boolean equations from truth tables.
Simplify Boolean equations using Boolean algebra identities.
Apply Boolean algebra to design and analyze logic circuits.
Introduction#
In Lesson 14, you built logic gates from transistor switches and analyzed their behavior using truth tables. That approach works — but it doesn’t scale. Tracing a circuit with 10 gates row-by-row is tedious. Tracing one with 100 gates is impractical. And designing a new circuit from scratch by trial and error is guesswork.
Boolean algebra solves all three problems. It gives us a compact mathematical language for describing logic circuits, a set of algebraic rules for simplifying them, and a systematic procedure for designing new ones from a specification. Instead of drawing and tracing circuits, we write and manipulate equations — and the math tells us when a circuit can be replaced by something simpler.
The payoff is real: a Boolean simplification that eliminates two gates saves transistors, reduces power consumption, and decreases propagation delay in every copy of that circuit ever manufactured.
Logic Gates as Boolean Equations#
Every logic gate has a corresponding Boolean operator. Once you know the three basic ones, you can write an equation for any combination of gates just by reading the diagram left to right.
Fig. 1. Standard gate symbols and their corresponding Boolean equations: AND (\(A \cdot B\)), OR (\(A + B\)), and NOT (\(A'\)).
AND Gate#
The AND gate outputs 1 only when both inputs are 1. In Boolean notation, AND is written as multiplication:
The dot is often omitted in compact notation, so you’ll frequently see this written as:
This mirrors ordinary multiplication: \(1 \cdot 1 = 1\), and anything multiplied by 0 is 0 — which is exactly the AND truth table.
OR Gate#
The OR gate outputs 1 when at least one input is 1. OR is written as addition:
The addition symbol reflects the parallel conduction path from Lesson 14: only one switch needs to be closed for the output to be high.
NOT Gate#
The NOT gate inverts its single input. The complement is written with a prime:
The NOT operation is deceptively important. On its own it just flips a signal, but combined with AND and OR it enables every other logical function — including the simplification identities you’ll use throughout this lesson.
Boolean Arithmetic#
Boolean algebra uses the same AND, OR, and NOT operators, but the arithmetic rules are different from base-10. There are only two values — 0 and 1 — and the rules reflect that.
AND (Multiplication)#
This behaves exactly like regular multiplication: a zero anywhere in a product makes the whole thing zero.
OR (Addition)#
The last rule is the one that catches students off guard. In Boolean algebra, \(1 + 1 = 1\) — not 2. The reason is simple: the output of a logic gate can only be 0 or 1. “True OR True” is still just “True.” There is no state between 1 and 2. Keep this in mind whenever you evaluate OR expressions.
NOT (Complement)#
The NOT simply flips the value. There’s no ambiguity here — it’s always the opposite.
From Logic Diagram to Boolean Equation#
Writing a Boolean equation from a logic diagram is a mechanical process: label the output of each gate with its expression, working from inputs toward the output. By the time you reach the final gate, you have the complete equation.
Write the Boolean equation for the logic diagram shown below.
Fig. 2. Logic diagram for Example Problem 1: OR and NOT gate outputs feed into a final AND gate.
Understand: Work from inputs to output, one gate at a time. Label each gate’s output before moving to the next stage.
Identify Key Information:
Two inputs: \(A\) and \(B\)
Three gates: OR, NOT, AND (left to right)
Plan: Label the OR output, label the NOT output, then combine at the AND gate.
Solve:
The OR gate receives \(A\) and \(B\) → output is \((A + B)\)
The NOT gate receives \(B\) → output is \(B'\)
The AND gate combines both intermediate signals → \(\text{Out} = (A + B) \cdot B'\)
Fig. 3. Example Problem 1 logic diagram with intermediate signals labeled: \((A+B)\) at the OR output and \(B'\) at the NOT output.
Answer: \(\text{Out} = (A + B)B'\)
Note how the parentheses are essential — they preserve the order of operations. The OR happens first, then the result is ANDed with \(B'\).
From Boolean Equation to Truth Table#
Once you have a Boolean equation, building the truth table is straightforward: evaluate the equation for every possible input combination. For complicated expressions, add columns for intermediate sub-expressions so you’re never computing too many things at once.
Build the complete truth table for the Boolean equation:
Understand: Two inputs means \(2^2 = 4\) rows. The expression has two sub-expressions multiplied together — add a column for each to keep the evaluation clean.
Identify Key Information:
Sub-expression 1: \((A + B)\)
Sub-expression 2: \((A + B')\)
Final output: product of both
Plan: Evaluate \((A+B)\) and \((A+B')\) for each row, then AND the results.
Solve:
\(A\) |
\(B\) |
\((A+B)\) |
\((A+B')\) |
\(\text{Out} = (A+B)(A+B')\) |
|---|---|---|---|---|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Answer: The output is 1 whenever \(A = 1\), and 0 whenever \(A = 0\).
Notice the row where \(A = 1\), \(B = 1\): \((A + B') = (1 + 0) = 1\). And remember: \(1 + 1 = 1\) in Boolean algebra — the output is still just 1, not 2. This is exactly the rule from the arithmetic section above.
From Truth Table to Boolean Equation — Sum of Products#
Going the other direction — from a truth table to an equation — requires a systematic procedure. The standard method is called Sum of Products (SOP). It always produces a correct equation, and it gives you a starting point for simplification.
The SOP Procedure#
Identify every row where the output equals 1.
For each such row, write one product term (an AND of all input variables):
If a variable is 0 in that row, use its complement (e.g., \(A'\))
If a variable is 1 in that row, use it directly (e.g., \(A\))
OR all product terms together — that’s your SOP equation.
The logic behind this: each product term is designed to be 1 only for that specific row. ORing them together means the output is 1 for any row that should produce a 1, and 0 everywhere else.
Write the SOP Boolean equation for the following truth table.
\(A\) |
\(B\) |
\(F\) |
|---|---|---|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
Understand: Find every row where \(F = 1\), write a product term for each, and OR them together.
Identify Key Information:
\(F = 1\) in rows 1 and 3
Two inputs → each product term uses both \(A\) and \(B\) (or their complements)
Plan: Apply the SOP procedure to each row where \(F = 1\).
Solve:
Row 1: \(A = 0\), \(B = 0\) → both are 0, so both get complemented → \(A'B'\)
Row 3: \(A = 1\), \(B = 0\) → \(A\) is 1 (use as-is), \(B\) is 0 (complement) → \(AB'\)
OR the terms together:
Answer: \(F = A'B' + AB'\)
This expression can be simplified further — you’ll do that in a later example. For now, verify it works: plug in \((0,0)\) and you get \(1 \cdot 1 + 0 \cdot 1 = 1\) ✓. Plug in \((1,0)\) and you get \(0 \cdot 1 + 1 \cdot 1 = 1\) ✓.
Write the SOP Boolean equation for the following truth table.
\(A\) |
\(B\) |
\(F\) |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Understand: Three rows have \(F = 1\), so the raw SOP will have three product terms. This is correct — it just means simplification will be worthwhile afterward.
Identify Key Information:
\(F = 1\) in rows 2, 3, and 4
Plan: Write a product term for each row where \(F = 1\), then OR them.
Solve:
Row 2: \(A = 0\), \(B = 1\) → \(A'B\)
Row 3: \(A = 1\), \(B = 0\) → \(AB'\)
Row 4: \(A = 1\), \(B = 1\) → \(AB\)
Answer: \(F = A'B + AB' + AB\)
Three terms, three gates — but this can be simplified considerably. See Example Problem 5.
Boolean Identities#
Boolean identities are the algebraic rules that let you simplify expressions. They are always true, regardless of what values \(A\), \(B\), or \(C\) take. Knowing when to apply them is the core skill of Boolean simplification.
# |
Identity |
Plain-English Meaning |
|---|---|---|
1 |
\(A + 0 = A\) |
ORing with 0 does nothing |
2 |
\(A + 1 = 1\) |
ORing with 1 always gives 1 |
3 |
\(A + A = A\) |
ORing a variable with itself changes nothing |
4 |
\(A + A' = 1\) |
A variable OR its complement is always 1 |
5 |
\(A \cdot 0 = 0\) |
ANDing with 0 always gives 0 |
6 |
\(A \cdot 1 = A\) |
ANDing with 1 does nothing |
7 |
\(A \cdot A = A\) |
ANDing a variable with itself changes nothing |
8 |
\(A \cdot A' = 0\) |
A variable AND its complement is always 0 |
9a |
\(A(B + C) = AB + AC\) |
Distributive law (AND over OR) |
9b |
\(A + BC = (A+B)(A+C)\) |
Distributive law (OR over AND) |
10a |
\((A + B)' = A'B'\) |
DeMorgan’s Law — NOR equals AND of complements |
10b |
\((AB)' = A' + B'\) |
DeMorgan’s Law — NAND equals OR of complements |
11a |
\(A + AB = A\) |
Absorption |
11b |
\(AB + AB' = A\) |
Factoring complements |
The identities you’ll use most often are:
Identity 4 (\(A + A' = 1\)) and Identity 8 (\(A \cdot A' = 0\)) — whenever you see a variable and its complement together, they collapse immediately to 1 or 0.
Identity 9a (distributive) — lets you factor out common terms, which is usually the first step when simplifying a multi-term SOP.
Identities 10a/10b (DeMorgan’s Laws) — let you convert between AND-of-complements and NOR, or between OR-of-complements and NAND. This is particularly useful for hardware optimization because it can reduce gate count.
Simplifying Boolean Equations#
The goal of simplification is to find an equivalent expression with fewer terms or fewer literals — which translates directly to fewer gates and fewer transistors. The process is not always unique; there may be multiple valid simplified forms.
Simplify the following Boolean expression:
Understand: This came from a truth table with three output-1 rows. Three product terms is more complex than necessary — we should be able to reduce it. Look for a variable and its complement appearing together, which is always a signal to factor.
Identify Key Information:
The last two terms both start with \(A\)
\(B'\) and \(B\) are complements — Identity 4 applies after factoring
Plan: Factor \(A\) out of the last two terms, apply Identity 4, then simplify the remainder.
Solve:
Group the last two terms and factor out \(A\):
Apply Identity 4 — \(B' + B = 1\):
Apply Identity 6 — \(A \cdot 1 = A\):
Now apply Identity 9b (distributive law for OR over AND) to factor further:
Apply Identity 4 — \(A + A' = 1\):
Apply Identity 6:
Answer: \(F = A + B\)
The original three-term expression implements nothing more than a single OR gate. What looked like three AND gates feeding into an OR gate reduces to one gate — a 6-transistor circuit collapses to 2 transistors.
Starting from the logic diagram in Example Problem 1, simplify the Boolean equation and verify with a truth table.
Understand: We already derived \(F = (A + B)B'\) in Example Problem 1. Now simplify it algebraically, then verify by building a truth table.
Identify Key Information:
\(F = (A + B)B'\)
Identity 9a lets us distribute the AND across the OR
Identity 8 should eliminate a term once we distribute
Plan: Distribute using Identity 9a, then look for a complement pair.
Solve:
Distribute (Identity 9a):
Apply Identity 8 — \(BB' = 0\):
Apply Identity 1 — \(AB' + 0 = AB'\):
Verify with a truth table:
\(A\) |
\(B\) |
\(F = AB'\) |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
Answer: \(F = AB'\) — the circuit outputs 1 only when \(A = 1\) and \(B = 0\).
The simplification eliminated the OR gate entirely. What was an OR–NOT–AND circuit (3 gates, 4 transistors) is equivalent to a single AND gate with \(B\) inverted (1 AND + 1 NOT = 3 transistors). This is the kind of savings Boolean algebra is designed to find.
Three-Input Design#
When the number of inputs grows, the SOP procedure scales with it — more rows, larger product terms, but the same systematic approach. The simplification step becomes even more valuable because the raw SOP expression grows quickly.
Design a logic circuit for the following truth table, and minimize the result.
\(A\) |
\(B\) |
\(C\) |
Out |
|---|---|---|---|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
Understand: Three inputs, eight rows, three rows where Out = 1. Build the SOP, then simplify.
Identify Key Information:
Out = 1 at rows \((0,0,0)\), \((1,0,0)\), and \((1,1,1)\)
The first two rows differ only in \(A\) — a strong signal that \(A\) can be factored out
Plan: Write the SOP, factor the first two terms, apply Identity 4, then look for further simplification.
Solve:
SOP construction:
\((0,0,0)\) → \(A'B'C'\)
\((1,0,0)\) → \(AB'C'\)
\((1,1,1)\) → \(ABC\)
Factor \(B'C'\) from the first two terms:
Apply Identity 4 — \(A' + A = 1\):
This is the simplified expression. It can also be written using DeMorgan’s Law (Identity 10a):
So an equivalent form is:
Answer: \(\text{Out} = B'C' + ABC\)
Hardware note: These two forms are algebraically identical but implement differently. \(B'C'\) requires two NOT gates and one AND gate (4 transistors). \((B+C)'\) requires one OR gate and one NOT gate (3 transistors). Applying DeMorgan’s Law here saves one transistor — a small gain in isolation, but multiplied across millions of copies on a chip it becomes significant.
Fig. 4. Logic diagram implementing \(\text{Out} = B'C' + ABC\) from Example Problem 7.
Standard Workflow#
Two directions you’ll travel in this course, and a summary of the steps for each:
Given a Logic Diagram#
Write the Boolean expression gate-by-gate, labeling intermediate nodes.
Simplify with Boolean identities — look for complement pairs first.
Build the truth table from the simplified equation to verify.
Given a Truth Table#
Construct the SOP expression from every row where output = 1.
Simplify using Boolean identities — factor common terms, apply Identity 4 or 8 wherever possible.
Draw the minimized logic diagram.
Why Simplification Matters#
Every gate you eliminate saves transistors. Every transistor saved reduces power consumption, heat generation, layout area, and manufacturing cost. In a chip with billions of gates, a simplification that shaves even one transistor per gate is a meaningful engineering achievement.
Boolean algebra is not an abstract mathematical exercise — it is the primary design optimization tool for digital hardware. The same logical function can always be implemented in multiple ways; the algebraic one is usually the cheapest.
Key Takeaways#
Boolean operators. AND is written as multiplication (\(A \cdot B\)), OR as addition (\(A + B\)), and NOT as a prime (\(A'\)); these three operators are sufficient to describe any logic function.
Boolean arithmetic rule. In Boolean algebra, \(1 + 1 = 1\) (not 2), because the output of a logic gate can only be 0 or 1; this is the most common arithmetic rule that catches students off guard.
Sum of Products (SOP). A systematic procedure to derive a Boolean equation from a truth table by writing one AND product term for each row where the output is 1, then ORing all terms together.
Boolean identities. Algebraic rules such as \(A + A' = 1\), \(A \cdot A' = 0\), and the distributive law let you simplify Boolean expressions to equivalent forms with fewer terms and fewer gates.
DeMorgan’s Laws. \((A + B)' = A'B'\) and \((AB)' = A' + B'\) allow conversion between NOR/NAND forms and AND/OR-of-complements forms, enabling hardware optimization by reducing gate count.
Simplification reduces cost. Every gate eliminated by algebraic simplification saves transistors, reduces power consumption, and lowers manufacturing cost across every copy of the circuit produced.
Standard workflow. Given a diagram, write the Boolean equation gate-by-gate and simplify; given a truth table, construct the SOP expression and then minimize it before drawing the circuit.