Activity 2.1.1 — Truth Tables & Logic Expressions¶
Learning Objectives¶
By the end of this lesson, students will be able to:
- Construct truth tables for any number of inputs following the standard binary counting order
- Calculate the number of rows in a truth table using the formula $2^n$
- Read a truth table and extract the Boolean expression
- Define and identify minterms from truth table rows
- Write Sum of Products (SOP) expressions from truth tables
- 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.
| 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 $A'B'$
- Row 2: A=1, B=0, Z=1 → Minterm is $AB'$
The SOP expression is: $Z = A'B' + AB'$
Let me verify this works for each row:
| A | B | $A'B'$ | $AB'$ | $Z = A'B' + AB'$ |
|---|---|---|---|---|
| 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 → $A'B'C$ - Row 3: A=0, B=1, C=1 → $A'BC$ - Row 6: A=1, B=1, C=0 → $ABC'$ - Row 7: A=1, B=1, C=1 → $ABC$
Step 2: Write SOP expression $$Z = A'B'C + A'BC + ABC' + 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.
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 + B')$
- Row 3: A=1, B=1, Z=0 → Sum term is $(A' + B')$
The POS expression is: $$Z = (A + B')(A' + 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 → $A'B'C'$ - Row 2: A=0, B=1, C=0 → $A'BC'$ - Row 4: A=1, B=0, C=0 → $AB'C'$ - Row 5: A=1, B=0, C=1 → $AB'C$ - Row 7: A=1, B=1, C=1 → $ABC$
Step 2: Write the SOP expression: $$Z = A'B'C' + A'BC' + AB'C' + AB'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 = A'BC + AB'C + ABC' + 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 = A'BC' + AB'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:
- $A'BC'$: Row where A=0, B=1, C=0 (binary 010 = decimal 2)
- $AB'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 ← $A'BC'$ |
| 3 | 0 | 1 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 1 ← $AB'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¶
- Find all rows where output Z = 1
- For each row, write a product term:
- Include each input variable exactly once
- Use $A$ if input = 1, use $A'$ if input = 0
- 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 (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