Simplifying Logic Expressions with Boolean Algebra

Welcome to the second module of our course. In the previous module, we focused on how digital systems represent information, culminating in our look at Hamming codes for ensuring data integrity. Now, we shift our focus to how we manipulate that information. This module is dedicated to Boolean algebra, the fundamental mathematics that underpins all digital logic.

In this first lesson, we will explore the core tools for transforming and simplifying logic expressions. Your goal is to learn how to apply key Boolean theorems—specifically DeMorgan's, absorption, and consensus theorems—to reduce complex expressions into simpler, more efficient forms. Mastering this skill is crucial because a simpler expression directly translates to a simpler, faster, and more cost-effective digital circuit.

Reviewing the Foundations of Boolean Algebra

You've mentioned you're already familiar with basic Boolean algebra. To ensure we have a solid shared foundation, let's quickly formalize some of the fundamental laws. These are the algebraic axioms from which we derive more powerful theorems.

BOOLEAN ALGEBRA

This document provides a concise summary of the basic laws of Boolean algebra.

Please review the section titled "3.2 Basic Laws". Focus on the following tables and definitions: Read through laws (1) to (7), which include these key laws. You'll notice many of these, like the Commutative, Associative, and first Distributive law, A(B+C) = AB + AC, behave just like in ordinary algebra. Pay special attention to the second Distributive law (7b): A + BC = (A + B)(A + C). This one is unique to Boolean algebra and is extremely useful.

These basic laws are our building blocks. Now, let's move on to the more powerful theorems that allow for significant simplification.

DeMorgan's Theorem: Inverting Expressions

DeMorgan's theorem is one of the most powerful tools in digital logic. It provides a straightforward method for simplifying expressions that involve inverting (or complementing) groups of variables. This is especially important when designing circuits with NAND and NOR gates, which we'll see are "universal" gates.

The theorem has two forms:

The complement of a sum is the product of the complements: $(A + B)^{'} = A^{'} \cdot B^{'}$
The complement of a product is the sum of the complements: $(A \cdot B)^{'} = A^{'} + B^{'}$

While you can always refer to these formulas, there's a more intuitive and practical way to apply the theorem, which the following video explains beautifully.

EEVacademy | Digital Design Series Part 2 - Digital Logic Boolean & Demorgan's Theorems

This EEVacademy video offers a memorable rule for applying DeMorgan's theorem.

First, watch the introduction to the two laws of DeMorgan's theorem. Then, watch the next segment that demonstrates the practical application rule: "drop the bar, change the sign". Notice how this simplifies handling complex nested expressions and how double inversions (A'') cancel out.

The key takeaway is the process: "Break the bar, and change the operator." When you break a long bar over an expression, the operator underneath (AND or OR) flips, and the bar is distributed over each term.

Let's work through an example: Simplify $F = [(A^{'} + B) \cdot C]^{'}$ .

The outermost bar covers an AND operation between (A' + B) and C. Break the bar and change the AND to an OR: $F = (A^{'} + B)^{'} + C^{'}$
Now we have a smaller bar over (A' + B). Let's apply the rule again. Break this bar and change the OR to an AND: $F = (A^{''}) \cdot (B^{'}) + C^{'}$
Finally, we know from the involution law that a double inversion cancels out ( $A^{''} = A$ ). $F = A \cdot B^{'} + C^{'}$

This simplified expression is much easier to implement as a circuit.

Absorption and Elimination Theorems

Next are a set of theorems excellent for removing redundant terms from an expression.

BOOLEAN ALGEBRA

This section of the previous PDF covers several key simplification theorems.

In the section "3.4 Theorems," please read about the following: The Absorption theorem: This theorem shows how a larger term can be "absorbed" by a smaller, more general term. The two forms are: A + AB = A A(A+B) = A The intuition is that if A is true, the A+AB expression is already true, making the AB part redundant. The Elimination theorem: This theorem is also very useful. The two forms are: A + A'B = A + B A(A'+B) = AB The intuition for the first form is: if A is true, the expression is true. If A is false, the expression becomes 0 + 1*B, which is just B. So the expression is equivalent to A+B.

These theorems are your first line of attack for quick simplifications by spotting common patterns.

The Consensus Theorem: Finding Hidden Redundancy

The Consensus Theorem is a powerful but sometimes tricky-to-spot tool for simplification. It allows you to remove a term that is redundant because its logic is already covered by two other terms.

The Consensus Theorem states that in expressions of the form AB + A'C + BC, the term BC is redundant and can be removed. The same logic applies to the Product-of-Sums form.

The theorem has two forms, just like the others:

Sum-of-Products (SOP) form: $X Y + X^{'} Z + Y Z = X Y + X^{'} Z$
Product-of-Sums (POS) form: $(X + Y) (X^{'} + Z) (Y + Z) = (X + Y) (X^{'} + Z)$

In the SOP form, the term YZ is called the consensus term of XY and X'Z. It is formed by the variables left over after removing the variable that appears in both its true (X) and complemented (X') form. This consensus term is redundant and can be eliminated.

The following video presents this theorem as a "trick" with a clear set of conditions, making it easy to apply.

Redundancy Theorem (Boolean Algebra Trick)

This video from Neso Academy explains the Consensus Theorem (which it calls the Redundancy Theorem) and gives you a simple checklist for using it.

Please watch the video from the beginning to the end. Pay close attention to: The three conditions required to apply the theorem (three variables, each repeated twice, one variable complemented). The algebraic proof showing why the term is redundant (proof section). The examples for both SOP (example 1) and POS (example 2) forms.

Let's Practice

Theory is best understood through practice. As you requested, let's work through some problems that require you to combine these theorems.

Problem 1: Simplify $F = A B C + A B C + A B C + A B C$

Let's solve this one together.

We can look for common terms to factor out.
- Group the first two terms: $A B C + A B C = A B (C + C)$
- Group the last two terms: $A B C + A B C = A B (C + C)$
Apply the complementary law ( $X + X = 1$ ).
- $A B (C + C) = A B (1) = A B$
- $A B (C + C) = A B (1) = A B$
The expression is now simplified to:
$F = A B + A B$
This is the definition of the XOR function, $A \oplus B$ . We have reduced a complex 4-term expression to a single, well-known 2-input gate. This problem is similar to "Exercise 12" in the advanced exercises webpage, but that one has more terms.

Problem 2: Simplify $F = A B^{'} + A^{'} B^{'} D^{'} + B C^{'} D^{'} + A B C D^{'}$

Try this one yourself. Use the theorems we've discussed. You might need to apply the Consensus theorem.

Solution

Let's analyze the expression: $F = A B^{'} + A^{'} B^{'} D^{'} + B C^{'} D^{'} + A B C D^{'}$

Identify Potential Consensus Terms: We need to look for a variable and its complement. Let's focus on variable A. We have a term with A ( $A B^{'}$ ) and a term with A' ( $A^{'} B^{'} D^{'}$ ).
- Let $X = A$ and $Y = B^{'}$ .
- Let $X^{'} = A^{'}$ and $Z = B^{'} D^{'}$ .
- The consensus term would be $Y Z = B^{'} \cdot (B^{'} D^{'}) = B^{'} D^{'}$ .
- Wait, the term B'D' is not in the expression. Let's re-examine. The expression has A'B'D'. Maybe B'D' is not the right Z.
Let's try again. Look at the terms AB' and A'B'D'. The consensus is B' \cdot B'D' = B'D'. The term A'B'D' contains this, but isn't just this. This path isn't a direct application of XY + X'Z + YZ.
Let's rearrange and look for other patterns. Notice the term ABCD'. We can rewrite this.
- Using the idempotency law ( $X = X X$ ), AB' = AB'AB'. This isn't helpful.
- Let's try applying absorption. AB' + ABCD'. No direct absorption.
A better approach: Find the consensus term directly.
- Consider terms $A B^{'}$ and $B C^{'} D^{'}$ . Here, the variable appearing in true and complemented form is B and B'.
- Let $X = B$ and $X^{'} = B^{'}$ .
- The term with B' is $A * * B^{'} * *$ . The term with B is $(C^{'} D^{'}) * * B * *$ .
- The consensus term should be $A \cdot (C^{'} D^{'}) = A C^{'} D^{'}$ . Is AC'D' in the expression? No. So we can't eliminate it. But perhaps we can add it to help simplify. This is an advanced technique.
Let's try another pair: Look at $A^{'} B^{'} D^{'}$ and $B C^{'} D^{'}$ .
- Variable pair is B and B'.
- Term with B' is $(A^{'} D^{'}) * * B^{'} * *$ . Term with B is $(C^{'} D^{'}) * * B * *$ .
- Consensus is $(A^{'} D^{'}) \cdot (C^{'} D^{'}) = A^{'} C^{'} D^{'}$ . Is this term present? No.
There must be a simpler way. Let's go back to the original expression and simplify using basic laws first.
$F = A B^{'} + A^{'} B^{'} D^{'} + B C^{'} D^{'} + A B C D^{'}$
- Let's group by B': $F = B^{'} (A + A^{'} D^{'}) + B C^{'} D^{'} + A B C D^{'}$
- Apply the Elimination theorem ( $X + X^{'} Y = X + Y$ ) to $A + A^{'} D^{'}$ :
  $A + A^{'} D^{'} = A + D^{'}$
- So, the expression becomes: $F = B^{'} (A + D^{'}) + B C^{'} D^{'} + A B C D^{'}$
- Distribute: $F = A B^{'} + B^{'} D^{'} + B C^{'} D^{'} + A B C D^{'}$
Now let's look at this new expression: $F = A B^{'} + B^{'} D^{'} + B C^{'} D^{'} + A B C D^{'}$
- Consider the terms B'D' and BC'D'. Can we simplify this? No direct rule.
- Consider the term B'D'. The expression B'D' + BC'D' can be factored: D'(B' + BC').
- Apply Elimination again: B' + BC' = B' + C'.
- So, D'(B' + BC') = D'(B' + C') = B'D' + C'D'.
- Our expression becomes: $F = A B^{'} + B^{'} D^{'} + C^{'} D^{'} + A B C D^{'}$ . This doesn't seem simpler.

Let's restart with the expression $F = A B^{'} + B^{'} D^{'} + B C^{'} D^{'} + A B C D^{'}$ and look for consensus.

The terms are AB', B'D', BC'D', ABCD'.
Let's check the triplet AB', BC'D', and AC'D' (which is not present). The consensus of AB' and BC'D' is AC'D'.
Let's check the triplet B'D', ABCD', and some consensus. The variable is A/A'? No A'. The variable is B/B'? Let's check B'D' and ABCD'.
- Term with B' is $(_D^{'}) * * B^{'} * *$ . Term with B is $(A C D^{'}) * * B * *$ .
- Consensus is $D^{'} \cdot (A C D^{'}) = A C D^{'}$ . This term is not present.

This problem is more complex than it first appears. Let's consult the source of a similar problem, from problem 7(b) in the LINK PDF: ab’ + a’b’d’ + bc’d’ + abcd’.
The simplification shown there is usually done with Karnaugh maps, which we will learn soon. Algebraic simplification can be non-obvious.
Let's try to apply Consensus theorem on the original expression:
F = ab' + a'b'd' + bc'd' + abcd'
The consensus of a'b'd' and bc'd' is a'c'd'. Adding it does not seem to help.
The consensus of ab' and bc'd' is ac'd'.
Let's try to use the fact that X + X = X.
F = ab' + a'b'd' + bc'd' + abcd' + abcd' (add a copy)
F = ab' + a'b'd' + (bc'd' + abcd') + abcd'
F = ab' + a'b'd' + b d'(c' + ac) + abcd'
Using elimination c' + ac = c' + a.
F = ab' + a'b'd' + b d'(c' + a) + abcd'
F = ab' + a'b'd' + bc'd' + abd' + abcd'
The consensus of ab' and abd' is ad'. Does not help.

Let's try a different approach, which is often key in Boolean algebra: try to absorb terms.
F = AB' + A'B'D' + BC'D' + ABCD'
The term A'B'D' is absorbed by B'D' if B'D' is present. Is it?
The consensus of AB' and BC'D' is AC'D'.
The consensus of A'B'D' and ABCD' is B'CD'.
Let's add the consensus of AB' and A'B'D'. This is not a valid consensus pair.

Let's look at it again: F = AB' + A'B'D' + BC'D' + ABCD'.
From the term AB', we can derive AB' = AB' + AB'C + AB'D... etc.
ABCD' is absorbed by ABD' if it existed.
A'B'D' is absorbed by B'D' if it existed.

Let's try to prove that B'D' is a consensus term.
Consider (A+D') and (B+D'). These are not in the expression.

This demonstrates that algebraic simplification can be an art. Often, the easiest path is not obvious. Let's use the provided solution from a similar problem online. The simplification for ab’ + a’b’d’ + bc’d’ + abcd’ is b'(a+d') + bc'd'.
Let's verify this.
F = AB' + A'B'D' + BC'D' + ABCD'
Group terms with B':
F = B'(A + A'D') + C'D'(B + AB)... this grouping is not good.
Let's try grouping terms with D':
F = D'(A'B' + BC' + ABC) + AB'
Let's simplify the bracket: G = A'B' + BC' + ABC
G = A'B' + B(C' + AC)
G = A'B' + B(C' + A) (Elimination)
G = A'B' + BC' + AB
Now, A'B' + AB... No, A'B' + AB is not A' + B'.
G = A'B' + BC' + AB. The consensus of A'B' and AB is not defined. The consensus of BC' and AB is AC'.
Let's look at A'B' and B(C'+A). The consensus is A'(C'+A) = A'C'.
So, G = A'B' + B(C'+A) + A'C'.
This is getting complicated. The simplest path often involves Karnaugh Maps, which is a topic for our next module. For now, a valid simplification via algebra is:
F = B'(A + A'D') + BC'D' + ABCD'
F = B'(A + D') + BC'D' + ABCD' = AB' + B'D' + BC'D' + ABCD'
Now, note that B'D' + BC'D' = D'(B' + BC') = D'(B' + C') = B'D' + C'D'.
And AB' + ABCD' = AB'(1+CD') = AB'.
So, F = AB' + B'D' + BC'D'.
This is a valid simplification.
Let's check the consensus of AB' and BC'D'. It's AC'D'.
Let's check the consensus of B'D' and BC'D'. It's B'C'.

The key insight for this problem is often to add a redundant term that helps absorption. The consensus of A'B'D' and BC'D' is A'C'D'. If we add it, do we get anywhere? The problem is tricky for pure algebraic methods without a clear path. The simplification to AB' + B'D' + BC'D' is correct and achievable.
Final check:
Original: AB' + A'B'D' + BC'D' + ABCD'
Simplified: AB' + B'D' + BC'D'
The term ABCD' is absorbed by AB'. (AB') + (AB' * CD') = AB'. So AB' + ABCD' = AB'.
The expression becomes AB' + A'B'D' + BC'D'.
Now, the consensus of AB' and BC'D' is AC'D'.
The consensus of A'B'D' and BC'D' is A'C'D'.
The consensus of AB' and A'B'D' is not valid.
F = AB' + A'B'D' + BC'D'. This is a simplified form.
We used absorption X+XY = X where X = AB' and Y = CD' to remove ABCD'.
Then we have AB' + A'B'D' + BC'D'. This is a valid simplified SOP expression.

Conclusion

In this lesson, we moved from data representation to data manipulation by exploring the power of Boolean algebra. You learned how to use fundamental theorems to simplify logic expressions, which is a critical first step in efficient digital design.

Key Takeaways:

Boolean Algebra is the mathematical system for manipulating logic variables.
DeMorgan's Theorem is essential for handling inverted expressions and is key to working with NAND/NOR logic. Remember the rule: "break the bar, change the operator."
Absorption and Elimination Theorems (A+AB=A, A+A'B=A+B) are used to remove straightforward redundancies.
Consensus Theorem (AB + A'C + BC = AB + A'C) helps eliminate more subtle, "hidden" redundancies in logic expressions.

In our next lesson, we will build upon this by learning how to structure any Boolean function into standardized formats: the Sum-of-Products (SOP) and Product-of-Sums (POS) canonical forms. These standard forms are the starting point for many automated design and minimization tools.

Recommended resources