Activity 2.1.4 — Boolean Algebra — Theorems¶
Learning Objectives¶
By the end of this lesson, students will be able to:
- State and apply the basic theorems of Boolean algebra
- Use Boolean theorems to simplify logic expressions
- Identify when to apply each theorem correctly
- Prove Boolean theorems using truth tables
- Simplify expressions to minimum cost implementations
- Distinguish between standard algebra and Boolean algebra rules
Vocabulary¶
Vocabulary (click to expand)
| Term | Definition |
|---|---|
| Boolean Algebra | The mathematical system governing operations on Boolean variables (variables with only 0 and 1 values) |
| Theorem | A proven statement that can be used to simplify Boolean expressions |
| Identity | An element that does not change the value when used in an operation (0 for OR, 1 for AND) |
| Complement | The inverse of a variable; A' is the complement of A |
| Duality | The principle that every Boolean expression remains valid when exchanging 0↔1 and AND↔OR |
| Simplification | The process of reducing a Boolean expression to an equivalent form with fewer terms or literals |
| Literal | A variable or its complement; A and A' are both literals |
Part 1: Introduction to Boolean Algebra¶
Boolean algebra is the mathematical foundation of digital logic. It was developed by George Boole in 1854, long before electronic computers existed. When engineers developed electronic logic circuits in the 1960s, Boolean algebra became the perfect tool for describing and simplifying them.
How Boolean Algebra Differs from Regular Algebra¶
| Property | Regular Algebra | Boolean Algebra |
|---|---|---|
| Variables | Any value (1, 2, 3, -5, etc.) | Only 0 or 1 |
| Operations | +, -, ×, ÷ | AND (·), OR (+), NOT (') |
| 1 + 1 | 2 | 1 (still just "true") |
| 1 × 1 | 1 | 1 |
| X × 0 | 0 | 0 |
| X + X | 2X | X (idempotent) |
The Three Basic Operations¶
- AND (Multiplication): $A \cdot B$ or $AB$ — Output is 1 only when both A AND B are 1
- OR (Addition): $A + B$ — Output is 1 when A OR B (or both) are 1
- NOT (Complement): $A'$ or $\overline{A}$ — Output is opposite of input
Key insight: In Boolean algebra, we don't subtract or divide. We only use AND, OR, and NOT. This makes it simpler than regular algebra in some ways, but the rules are different, so don't let your algebra class knowledge trick you!
Part 2: Fundamental Theorems¶
Identity and Null Theorems¶
| Theorem | Expression | Description |
|---|---|---|
| Identity 1 | $A + 0 = A$ | OR with 0 returns original value |
| Identity 2 | $A \cdot 1 = A$ | AND with 1 returns original value |
| Null 1 | $A + 1 = 1$ | OR with 1 always gives 1 |
| Null 2 | $A \cdot 0 = 0$ | AND with 0 always gives 0 |
Proof of Null 1 using truth table:
| A | A + 1 | Result |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 | 1 |
Since the result is always 1 regardless of A, $A + 1 = 1$.
Proof of Null 2: | A | A · 0 | Result | |---|---|-------| | 0 | 0 | 0 | | 1 | 0 | 0 |
Since the result is always 0, $A \cdot 0 = 0$.
Idempotent Theorems¶
| Theorem | Expression | Description |
|---|---|---|
| Idempotent 1 | $A + A = A$ | ORing a variable with itself |
| Idempotent 2 | $A \cdot A = A$ | ANDing a variable with itself |
Intuition: If A is true, "A OR A" is still true (not "twice true"). If A is false, "A OR A" is still false.
Complement Theorems¶
| Theorem | Expression | Description |
|---|---|---|
| Complement 1 | $A + A' = 1$ | A OR NOT A equals 1 (always true) |
| Complement 2 | $A \cdot A' = 0$ | A AND NOT A equals 0 (always false) |
Proof of Complement 1:
| A | A' | A + A' |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 1 |
No matter what A is, either A or A' is 1, so the OR is always 1.
Commutative Theorems¶
| Theorem | Expression | Description |
|---|---|---|
| Commutative 1 | $A + B = B + A$ | OR is commutative |
| Commutative 2 | $A \cdot B = B \cdot A$ | AND is commutative |
The order of operands doesn't matter for AND and OR.
Associative Theorems¶
| Theorem | Expression | Description |
|---|---|---|
| Associative 1 | $(A + B) + C = A + (B + C)$ | OR is associative |
| Associative 2 | $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ | AND is associative |
We can group AND or OR operations in any order.
Distributive Theorems¶
| Theorem | Expression | Description |
|---|---|---|
| Distributive 1 | $A(B + C) = AB + AC$ | AND distributes over OR |
| Distributive 2 | $A + BC = (A + B)(A + C)$ | OR distributes over AND |
Distributive 1 should look familiar from regular algebra (factorization).
Distributive 2 is unique to Boolean algebra — it has no equivalent in regular algebra!
Proof of Distributive 1:
| A | B | C | B+C | AB | AC | AB+AC | A(B+C) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Since AB+AC equals A(B+C) for all rows, the theorem is proven.
Part 3: Absorption Theorems¶
These theorems let you simplify expressions by "absorbing" terms.
Absorption 1: $A + AB = A$¶
Proof using algebra: $$A + AB = A(1 + B) \quad \text{[Factor out A]}$$ $$= A(1) \quad \text{[1 + B = 1 (Null theorem)]}$$ $$= A \quad \text{[Identity]}$$
Intuition: If A is 1, the result is 1. If A is 0, the result is 0 (because AB is also 0). Either way, the result equals A.
Truth table proof:
| A | B | AB | A + AB |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Absorption 2: $A(A + B) = A$¶
Proof: $$A(A + B) = AA + AB \quad \text{[Distributive]}$$ $$= A + AB \quad \text{[Idempotent: AA = A]}$$ $$= A(1 + B) \quad \text{[Factor]}$$ $$= A(1) \quad \text{[Null]}$$ $$= A \quad \text{[Identity]}$$
Absorption 3: $A + A'B = A + B$¶
This is more complex but very useful!
Proof: $$A + A'B = (A + A')(A + B) \quad \text{[Distributive 2]}$$ $$= 1(A + B) \quad \text{[Complement: A + A' = 1]}$$ $$= A + B \quad \text{[Identity]}$$
Key insight: Absorption theorems show that sometimes a larger-looking expression simplifies to something smaller. Always look for patterns like $A + AB$ or $A(A + B)$ that can be reduced.
Part 4: Additional Useful Theorems¶
Double Inversion: $(A')' = A$¶
Two inversions cancel each other out.
Redundancy (Consensus): $AB + A'C + BC = AB + A'C$¶
The term BC is redundant and can be eliminated!
Proof: $$AB + A'C + BC = AB + A'C + BC(A + A') \quad \text{[A + A' = 1]}$$ $$= AB + A'C + ABC + A'BC \quad \text{[Distributive]}$$ $$= AB(1 + C) + A'C(1 + B) \quad \text{[Factor]}$$ $$= AB(1) + A'C(1) \quad \text{[Null]}$$ $$= AB + A'C \quad \text{[Identity]}$$
This is called the consensus theorem because BC is the "consensus" of AB and A'C.
Part 5: Simplification Examples¶
Worked Example 1: Simplify $Z = AB + AB'$¶
$$Z = AB + AB'$$ $$= A(B + B') \quad \text{[Factor out A]}$$ $$= A(1) \quad \text{[Complement: B + B' = 1]}$$ $$= A \quad \text{[Identity]}$$
Result: $Z = A$ — This is remarkable! The output depends only on A, regardless of B.
Intuition: If A = 0, both AB and AB' are 0. If A = 1, either B or B' must be 1, so one term is 1. Either way, Z = A.
Worked Example 2: Simplify $Z = (A + B)(A + B')$¶
$$Z = (A + B)(A + B')$$ $$= A + BB' \quad \text{[Distributive 2: (A+B)(A+C) = A + BC]}$$ $$= A + 0 \quad \text{[Complement: B·B' = 0]}$$ $$= A \quad \text{[Identity]}$$
Worked Example 3: Simplify $Z = ABC + AB' + AC$¶
$$Z = ABC + AB' + AC$$ $$= AB(C + 1) + AB' + AC - AB \quad \text{[Adding and subtracting AB]}$$
Actually, let's use a cleaner approach:
$$Z = AB(C + 1) + AB' + AC$$ $$= AB + AB' + AC \quad \text{[C + 1 = 1]}$$ $$= A(B + B') + AC \quad \text{[Factor A from first two]}$$ $$= A(1) + AC \quad \text{[Complement: B + B' = 1]}$$ $$= A + AC \quad \text{[Identity]}$$ $$= A(1 + C) \quad \text{[Factor]}$$ $$= A(1) \quad \text{[Null]}$$ $$= A \quad \text{[Identity]}$$
Result: $Z = A$
Worked Example 4: Simplify $Z = (A + B)(A' + C)(B + C)$¶
Use the consensus theorem: $AB + A'C + BC = AB + A'C$
First, expand to SOP: $$Z = (A + B)(A' + C)(B + C)$$
This is getting complex. Let's use the dual approach or recognize patterns. Actually, using the consensus theorem in reverse:
The SOP form has terms: $A \cdot A'$, $A \cdot C$, $B \cdot A'$, $B \cdot C$, $A' \cdot C$, and $B \cdot C$
Some terms will simplify using complement theorems. The result often simplifies to something much smaller.
For this specific expression, using Boolean algebra identities: $$(A + B)(A' + C)(B + C) = (A + B)(A' + C)$$
This is because $(B + C)$ is absorbed by the consensus term.
Key insight: When simplifying, look for patterns: common factors, complement pairs ($A + A'$), and terms that match absorption forms.
Part 6: Duality Principle¶
Every Boolean theorem has a dual that is also true. To find the dual: - Swap 0 ↔ 1 - Swap AND ↔ OR (· ↔ +)
Examples:
| Original | Dual |
|---|---|
| $A + 0 = A$ | $A \cdot 1 = A$ |
| $A + 1 = 1$ | $A \cdot 0 = 0$ |
| $A + A' = 1$ | $A \cdot A' = 0$ |
| $A(B + C) = AB + AC$ | $A + BC = (A + B)(A + C)$ |
If an expression is true, its dual is also true!
Practice Problem — Basic Simplification¶
Problem 1: Simplify each expression using Boolean theorems.
a) $Z = X + XY$ b) $Z = A(A + B)$ c) $Z = P + P'Q$ d) $Z = MN + M'N$
Show Solution
a) $Z = X + XY$ $= X(1 + Y)$ [Factor X] $= X(1)$ [Null: 1 + Y = 1] $= X$ [Identity]
b) $Z = A(A + B)$ $= AA + AB$ [Distributive] $= A + AB$ [Idempotent: AA = A] $= A(1 + B)$ [Factor] $= A(1)$ [Null] $= A$ [Identity]
c) $Z = P + P'Q$ $= (P + P')(P + Q)$ [Distributive 2] $= 1(P + Q)$ [Complement: P + P' = 1] $= P + Q$ [Identity]
d) $Z = MN + M'N$ $= N(M + M')$ [Factor N] $= N(1)$ [Complement: M + M' = 1] $= N$ [Identity]
Practice Problem — Multi-Step Simplification¶
Problem 2: Simplify $Z = ABC + AB' + AC'$
Show Solution
$$Z = ABC + AB' + AC'$$
Step 1: Factor A from all terms $$Z = A(BC + B' + C')$$
Step 2: Apply distributive in reverse to group terms $$Z = A[(BC + B') + C']$$
Step 3: Use absorption: $BC + B' = B' + C$ (from $A + A'B = A + B$ with A = B', A' = B) Actually, let's use: $B' + BC = B' + C$ because: $B' + BC = B'(1) + BC = B'(1 + C) + BC = B' + B'C + BC = B' + C(B' + B) = B' + C$
So: $Z = A(B' + C + C')$
Step 4: Apply complement: $C + C' = 1$ $$Z = A(B' + 1)$$
Step 5: Apply null: $B' + 1 = 1$ $$Z = A(1) = A$$
Result: $Z = A$
We can verify: if A = 0, all terms are 0. If A = 1, then: - ABC = BC - AB' = B' - AC' = C' - BC + B' + C' = B' + C' + BC
If B' + C' = 0, then B = 1 and C = 1, so BC = 1. Otherwise at least one term is 1. So the expression = 1 when A = 1.
Verification: $Z = A$ ✓
Practice Problem — Using Distributive Theorem¶
Problem 3: Simplify $Z = (A + B)(A + B')$
Show Solution
$$Z = (A + B)(A + B')$$
Method 1: Multiply out $$Z = A \cdot A + A \cdot B' + B \cdot A + B \cdot B'$$ $$= A + AB' + AB + 0 \quad \text{[Idempotent, Complement]}$$ $$= A(1 + B' + B)$$ $$= A(1) = A$$
Method 2: Use distributive theorem 2 directly $$(A + B)(A + B') = A + BB' = A + 0 = A$$
Result: $Z = A$
This makes physical sense: (A OR B) AND (A OR NOT B) always equals A. If A is true, both expressions are true. If A is false, both depend on B, and they are complementary—one is true, one is false—so the AND is false.
Practice Problem — Finding Errors¶
Problem 4: A student claims that $A + B = A \cdot B$. Is this correct? Prove or disprove.
Show Solution
Claim: $A + B = A \cdot B$ (OR equals AND)
Truth table:
| A | B | A + B | A · B |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 |
Analysis: - When A=0, B=1: A+B = 1, but A·B = 0 - The values are different
Conclusion: The claim is FALSE. OR and AND are not equivalent.
Correct equivalences: - $A + B$ is only true when at least one input is true - $A \cdot B$ is only true when both inputs are true - They are complementary only in special cases (DeMorgan's theorem: $(A + B)' = A' \cdot B'$)
Practice Problem — Real Application¶
Problem 5: A traffic light system has inputs: - A = North-South sensor active - B = East-West sensor active - C = Emergency vehicle priority
The output Z = 1 (green light) when the normal condition (A AND B) is met, OR when the emergency override (C) is active. Write and simplify the expression.
Original: $Z = AB + C$
Can this be simplified?
Show Solution
Expression: $Z = AB + C$
Can we simplify? Let's check:
$$Z = AB + C$$
Is there a simplification? Not really—this is already minimal. The term C (emergency) overrides the normal AB condition.
Verification: - If C = 1 (emergency), Z = 1 regardless of A and B ✓ - If C = 0 (normal), Z = AB, meaning only green when both sensors detect traffic ✓
Different scenario: If the system was $Z = (A + B)C$: $$= AC + BC$$ This is 3 literals instead of 2 + 1, so not simpler.
Conclusion: $Z = AB + C$ is the minimal form.
Summary¶
Theorem Quick Reference¶
| Category | Theorem | Expression |
|---|---|---|
| Identity | 1 | $A + 0 = A$ |
| 2 | $A \cdot 1 = A$ | |
| Null | 1 | $A + 1 = 1$ |
| 2 | $A \cdot 0 = 0$ | |
| Idempotent | 1 | $A + A = A$ |
| 2 | $A \cdot A = A$ | |
| Complement | 1 | $A + A' = 1$ |
| 2 | $A \cdot A' = 0$ | |
| Commutative | 1 | $A + B = B + A$ |
| 2 | $A \cdot B = B \cdot A$ | |
| Associative | 1 | $(A+B)+C = A+(B+C)$ |
| 2 | $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ | |
| Distributive | 1 | $A(B+C) = AB + AC$ |
| 2 | $A + BC = (A+B)(A+C)$ | |
| Absorption | 1 | $A + AB = A$ |
| 2 | $A(A+B) = A$ | |
| 3 | $A + A'B = A + B$ | |
| Double Inversion | $(A')' = A$ | |
| Consensus | $AB + A'C + BC = AB + A'C$ |
Simplification Strategy¶
- Look for complement pairs: $A + A'$, $A \cdot A'$
- Factor common terms: $AB + AC = A(B + C)$
- Apply absorption: $A + AB = A$
- Use distributive to combine or separate as needed
- Verify by comparing truth tables of original and simplified expressions
Key Reminders¶
- Boolean algebra has only 0 and 1 — no other values
- Don't apply regular algebra rules to Boolean expressions
- Complement theorem ($A + A' = 1$) is one of the most powerful simplification tools
- Absorption theorems ($A + AB = A$) eliminate redundant terms
- Always verify simplified expressions with truth tables
- Simplification reduces cost: fewer gates, fewer inputs, lower power
- The dual of any true theorem is also true
Custom activity — adapted from PLTW Digital Electronics