Simplifying Logic with Boolean Algebra

1. Why We Need to Simplify

Before diving into the laws themselves, it's essential to understand the motivation. A single logical function can be represented by many different Boolean expressions, which in turn correspond to many different circuit implementations. Our goal is always to find the simplest one.

To see a concrete example of this, let's watch a short video that illustrates how a complex arrangement of logic gates can be drastically simplified.

2. The Fundamental Laws of Boolean Algebra

Boolean algebra is a system of logic built around three basic operations you've likely heard of: AND, OR, and NOT.

• AND is represented by a dot ($\cdot$) or no symbol (e.g., $A\cdot B$ or $AB$). The output is 1 only if all inputs are 1.
• OR is represented by a plus sign ($+$) (e.g., $A+B$). The output is 1 if any input is 1.
• NOT is represented by an overbar or a prime (e.g., $\bar{A}$ or $A^{\prime }$). It inverts the input.

Just like in regular algebra, Boolean algebra has a set of laws or identities that we can use to manipulate expressions. Let's explore them.

For your reference, here is a complete table of the fundamental Boolean identities from a university logic design course. It's a great resource to have handy.

3. A Closer Look at De Morgan's Law

Among all the laws, De Morgan's Law is especially powerful and deserves special attention. It provides a method for complementing a complex expression and is key to converting between different types of logic gates (for instance, implementing an OR function using only NAND gates).

De Morgan's two laws are:

1. $\overline{A+B}=\bar{A}\cdot \bar{B}$
2. $\overline{A\cdot B}=\bar{A}+\bar{B}$

A simple way to remember this is the phrase: "Break the bar, change the sign." You break the long overbar into smaller ones over each variable and change the operator from OR to AND, or vice-versa.

Let's see this visualized.

The following video provides a focused explanation of De Morgan's law, proving it with truth tables and showing how to apply it to more complex expressions.

4. Putting It All Together: Simplification in Action

Now, let's apply these laws to simplify a Boolean expression derived from a logic circuit.

Let's walk through the simplification shown in the image:
The initial expression derived from the circuit is $F=\bar{A}\bar{A}+AB$.

1. $F=\bar{A}+AB$

   • Idempotent Law: $\bar{A}\bar{A}=\bar{A}$.

2. $F=(\bar{A}+A)(\bar{A}+B)$

   • Distributive Law: $X+YZ=(X+Y)(X+Z)$. Here, $X=\bar{A}$, $Y=A$, and $Z=B$.

3. $F=(1)(\bar{A}+B)$

   • Inverse Law: $\bar{A}+A=1$.

4. $F=\bar{A}+B$

   • Identity Law: $1\cdot X=X$.

The final circuit, which requires only one NOT gate and one OR gate, is significantly simpler than the original, yet functionally identical.

Practice Exercise

Now it's your turn. Use the Boolean laws to simplify the following expression. List the law you use for each step.

Simplify: $F(x,y,z)=\bar{x}y+xy{z}^{\prime }+xyz$

Conclusion

In this lesson, we transitioned from representing numbers to manipulating the logic that operates on them. You've learned the fundamental rules that govern digital circuits and how to apply them to make those circuits more efficient.

Here are the key takeaways:

• Boolean algebra is the mathematics used to analyze and simplify digital logic circuits.
• Simplifying Boolean expressions is critical for creating hardware that is smaller, faster, and consumes less power.
• The basic laws (Identity, Idempotent, Distributive, etc.) are your tools for manipulation.
• De Morgan's Law is a particularly powerful tool for complementing expressions and transforming logic, remembered by the rule "break the bar, change the sign."

So far, we've taken an existing expression and simplified it. But where do these expressions come from in the first place? In our next lesson, we will learn how to derive a Boolean expression from a truth table using the sum-of-products form, allowing us to translate a desired behavior directly into the language of logic.