Activity 2.1.1 — Truth Tables & Logic Expressions

---

Learning Objectives

By the end of this lesson, students will be able to:

1. Construct truth tables for any number of inputs following the standard binary counting order
2. Calculate the number of rows in a truth table using the formula $2^n$
3. Read a truth table and extract the Boolean expression
4. Define and identify minterms from truth table rows
5. Write Sum of Products (SOP) expressions from truth tables
6. Distinguish between SOP and POS forms

---

Vocabulary

Vocabulary (click to expand)

Term	Definition
Truth Table	A systematic listing showing all possible combinations of input values and their corresponding output values
Minterm	An AND term containing every input variable exactly once, either in complemented (0) or uncomplemented (1) form
Sum of Products (SOP)	A Boolean expression form where product (AND) terms are summed (ORed) together; derived from truth table rows where output = 1
Product of Sums (POS)	A Boolean expression form where sum (OR) terms are multiplied (ANDed) together; derived from truth table rows where output = 0
Canonical Form	The standard or complete form of a Boolean expression where each term includes all variables
Binary Counting Order	Listing inputs in ascending binary sequence (00, 01, 10, 11 for 2 variables) when constructing truth tables

---

Part 1: Understanding Truth Table Structure

A truth table is a complete description of how a logic circuit behaves. It shows exactly what the output will be for every possible combination of inputs.

The Golden Rule: 2^n Rows

For a circuit with $n$ inputs, the truth table must have exactly $2^n$ rows to cover all possible input combinations.

flowchart LR
    n1["1 input"] --> r1["2 rows"]
    n2["2 inputs"] --> r2["4 rows"]
    n3["3 inputs"] --> r3["8 rows"]
    n4["4 inputs"] --> r4["16 rows"]
    n5["5 inputs"] --> r5["32 rows"]

Number of Inputs (n)	Number of Rows ($2^n$)
1	2
2	4
3	8
4	16
5	32

This makes sense because each input has 2 possibilities (0 or 1), and the combinations multiply: 2 × 2 × 2 × … (n times) = $2^n$.

Standard Binary Counting Order

When constructing truth tables, we use a specific ordering for the inputs: ascending binary order. Think of it as counting in binary from 0 to the maximum value.

For 2 inputs (A, B) — 4 rows:

Decimal	Binary	A	B
0	00	0	0
1	01	0	1
2	10	1	0
3	11	1	1

For 3 inputs (A, B, C) — 8 rows:

Decimal	Binary	A	B	C
0	000	0	0	0
1	001	0	0	1
2	010	0	1	0
3	011	0	1	1
4	100	1	0	0
5	101	1	0	1
6	110	1	1	0
7	111	1	1	1

Key insight: The rightmost column (C in the example above) cycles fastest (0,1,0,1,0,1,0,1), the next column (B) changes every 2 rows, and the leftmost (A) changes every 4 rows. This is exactly like counting in binary!

---

Part 2: Reading Truth Tables to Create Expressions

Now we learn the reverse process: given a truth table, derive the Boolean expression. This is how engineers translate real-world requirements into mathematical form.

The Sum of Products (SOP) Method

The SOP method follows a simple principle:

“For every row where the output is 1, write down what inputs would make that happen, then OR all those terms together.”

Understanding Minterms

A minterm is a product (AND) term that is TRUE (equals 1) for exactly one row of the truth table. Each minterm:

• Contains ALL input variables
• Uses uncomplemented form if the input is 1 in that row
• Uses complemented form if the input is 0 in that row

Example — Identifying Minterms:

Given this truth table:

A	B	Z
0	0	1
0	1	0
1	0	1
1	1	0

• Row 0: A=0, B=0, Z=1 → Minterm is $\overline{A}\overline{B}$
• Row 2: A=1, B=0, Z=1 → Minterm is $A\overline{B}$

The SOP expression is: $Z = \overline{A}\overline{B} + A\overline{B}$

Let me verify this works for each row:

A	B	$\overline{A}\overline{B}$	$A\overline{B}$	$Z = \overline{A}\overline{B} + A\overline{B}$
0	0	1·1 = 1	0·1 = 0	1 + 0 = 1 ✓
0	1	1·0 = 0	0·0 = 0	0 + 0 = 0 ✓
1	0	0·1 = 0	1·1 = 1	0 + 1 = 1 ✓
1	1	0·0 = 0	1·0 = 0	0 + 0 = 0 ✓

Worked Example — 3-Variable Truth Table

Given truth table:

A	B	C	Z
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Step 1: Identify rows where Z = 1

• Row 1: A=0, B=0, C=1 → $\overline{A}\overline{B}C$
• Row 3: A=0, B=1, C=1 → $\overline{A}BC$
• Row 6: A=1, B=1, C=0 → $AB\overline{C}$
• Row 7: A=1, B=1, C=1 → $ABC$

Step 2: Write SOP expression $$Z = \overline{A}\overline{B}C + \overline{A}BC + AB\overline{C} + ABC$$

Step 3: Verify (choose row 3: A=0, B=1, C=1) $$Z = (1)(1)(1) + (1)(1)(1) + (0)(1)(0) + (0)(1)(1)$$ $$Z = 1 + 1 + 0 + 0 = 1 \checkmark$$

Key insight: Each minterm is true (equals 1) for only ONE specific row. That’s why ORing them together gives us exactly the rows where Z should be 1.

Minterms and K-maps (Preview)

Each minterm from the truth table maps to exactly one cell in a Karnaugh map. This visual shows how the 8 truth table rows for a 3-variable function correspond to K-map cells — a technique we will use in Lesson 2.2.1 to simplify expressions graphically.

flowchart LR
    subgraph Truth Table
        direction TB
        R0["Row 0: 000 → m0"]
        R1["Row 1: 001 → m1"]
        R2["Row 2: 010 → m2"]
        R3["Row 3: 011 → m3"]
        R4["Row 4: 100 → m4"]
        R5["Row 5: 101 → m5"]
        R6["Row 6: 110 → m6"]
        R7["Row 7: 111 → m7"]
    end
    subgraph K-map
        direction TB
        K["Each minterm maps to one K-map cell.\nAdjacent cells differ by one variable.\nGroups of 1s simplify the expression."]
    end
    Truth Table --> K-map

---

Part 3: Product of Sums (POS) — A Brief Introduction

While SOP is the most common form, you should also know about POS. POS is the opposite approach:

“For every row where the output is 0, write down what inputs would make that row false, then AND all those terms together.”

POS Minterm (Maxterm) Formation

In POS, we write sum (OR) terms for rows where output is 0:

• If input is 1 in that row → use complemented form
• If input is 0 in that row → use uncomplemented form

Same truth table example:

A	B	Z
0	0	1
0	1	0
1	0	1
1	1	0

• Row 1: A=0, B=1, Z=0 → Sum term is $(A + \overline{B})$
• Row 3: A=1, B=1, Z=0 → Sum term is $(\overline{A} + \overline{B})$

The POS expression is: $$Z = (A + \overline{B})(\overline{A} + \overline{B})$$

Both SOP and POS are mathematically equivalent — they describe the same truth table. We primarily use SOP in this course because it maps directly to AND-OR (AOI) logic.

---

Practice Problem — Creating SOP Expressions

Problem 1: Given the truth table below, write the SOP expression.

A	B	C	Z
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

Show Solution

Step 1: Identify all rows where Z = 1:

• Row 0: A=0, B=0, C=0 → $\overline{A}\overline{B}\overline{C}$
• Row 2: A=0, B=1, C=0 → $\overline{A}B\overline{C}$
• Row 4: A=1, B=0, C=0 → $A\overline{B}\overline{C}$
• Row 5: A=1, B=0, C=1 → $A\overline{B}C$
• Row 7: A=1, B=1, C=1 → $ABC$

Step 2: Write the SOP expression: $$Z = \overline{A}\overline{B}\overline{C} + \overline{A}B\overline{C} + A\overline{B}\overline{C} + A\overline{B}C + ABC$$

Verification for Row 5 (A=1, B=0, C=1, Z=1): $$Z = (0)(0)(0) + (0)(1)(0) + (1)(1)(1) + (1)(1)(1) + (1)(1)(1)$$ $$Z = 0 + 0 + 1 + 1 + 1 = 1 \checkmark$$

---

Practice Problem — Truth Table Construction

Problem 2: Create a truth table for a majority voting circuit with 3 inputs (A, B, C). The output Z is 1 when at least 2 of the 3 inputs are 1 (majority wins).

Show Solution

Truth Table (8 rows for 3 inputs):

A	B	C	Z	Reason
0	0	0	0	No inputs = no majority
0	0	1	0	Only 1 input = no majority
0	1	0	0	Only 1 input = no majority
0	1	1	1	2 inputs = majority
1	0	0	0	Only 1 input = no majority
1	0	1	1	2 inputs = majority
1	1	0	1	2 inputs = majority
1	1	1	1	3 inputs = majority

SOP Expression from rows where Z = 1: $$Z = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC$$

This can be simplified later using Boolean algebra (covered in Lesson 2.1.4).

---

Practice Problem — Counting Rows

Problem 3: How many rows would each truth table have?

a) 4-input circuit b) 5-input circuit c) A circuit with 10 inputs

Show Solution

Using the formula: Number of rows = $2^n$

a) 4 inputs: $2^4 = \mathbf{16}$ rows b) 5 inputs: $2^5 = \mathbf{32}$ rows c) 10 inputs: $2^{10} = \mathbf{1,024}$ rows

Practical note: Notice how quickly truth tables grow! This is why we use Boolean algebra and Karnaugh maps to simplify circuits rather than trying to work with massive truth tables.

---

Practice Problem — Identifying Minterms

Problem 4: For the expression $Z = \overline{A}B\overline{C} + A\overline{B}C + ABC$, identify: a) Which rows of a truth table would have Z = 1? b) How many total rows does this truth table have?

Show Solution

a) Rows where Z = 1:

• $\overline{A}B\overline{C}$: Row where A=0, B=1, C=0 (binary 010 = decimal 2)
• $A\overline{B}C$: Row where A=1, B=0, C=1 (binary 101 = decimal 5)
• $ABC$: Row where A=1, B=1, C=1 (binary 111 = decimal 7)

b) Total rows: Since there are 3 inputs (A, B, C), the truth table has $2^3 = \mathbf{8}$ rows.

Complete truth table for verification:

Decimal	A	B	C	Z
0	0	0	0	0
1	0	0	1	0
2	0	1	0	1 ← $\overline{A}B\overline{C}$
3	0	1	1	0
4	1	0	0	0
5	1	0	1	1 ← $A\overline{B}C$
6	1	1	0	0
7	1	1	1	1 ← $ABC$

---

Summary

Truth Table Construction Rules

Rule	Description
Row count	$2^n$ rows for n inputs
Input order	Binary counting order (00, 01, 10, 11…)
Rightmost column	Changes every row
Leftmost column	Changes every $2^{n-1}$ rows

SOP Conversion Process

1. Find all rows where output Z = 1
2. For each row, write a product term:
   • Include each input variable exactly once
   • Use $A$ if input = 1, use $\overline{A}$ if input = 0
3. OR (sum) all the product terms together

Minterm Quick Reference

Input Value	In Minterm Term
Input = 1	Use uncomplemented form (A)
Input = 0	Use complemented form (\overline{A})

---

Key Reminders

• Always use binary counting order when constructing truth tables
• $2^n$ rows: memorize this formula — it comes up constantly
• SOP expression = OR of minterms from rows where Z = 1
• Each minterm contains ALL input variables exactly once
• Complement (’) the variable if the input is 0; don’t complement if input is 1
• You can verify your SOP expression by substituting values from the truth table
• SOP is the foundation for AOI implementation — every SOP maps directly to an AND-OR circuit

---

Custom activity — adapted from PLTW Digital Electronics