Show understanding of Boolean algebra

15.2 Boolean Algebra and Logic Circuits

Learning Objective

Demonstrate a clear understanding of Boolean algebra, including its laws, identities, simplification techniques and how they are applied to design and analyse logic circuits.

1. Introduction to Boolean Algebra

Boolean algebra is a mathematical system for manipulating logical expressions. It uses two binary values:

• 0 – representing FALSE (LOW)
• 1 – representing TRUE (HIGH)

Logical variables are usually denoted by letters such as \$A\$, \$B\$, \$C\$, … and the basic operations are:

• AND – \$A \cdot B\$ (or \$AB\$)
• OR – \$A + B\$ (or \$A + B\$)
• NOT – \$\overline{A}\$ (or \$\overline{A}\$)

2. Fundamental Laws of Boolean Algebra

The following laws hold for any Boolean variables \$X\$, \$Y\$, \$Z\$:

• Identity Laws: \$X + 0 = X\$, \$X \cdot 1 = X\$
• Null Laws: \$X + 1 = 1\$, \$X \cdot 0 = 0\$
• Idempotent Laws: \$X + X = X\$, \$X \cdot X = X\$
• Complement Laws: \$X + \overline{X} = 1\$, \$X \cdot \overline{X} = 0\$
• Commutative Laws: \$X + Y = Y + X\$, \$X \cdot Y = Y \cdot X\$
• Associative Laws: \$(X + Y) + Z = X + (Y + Z)\$, \$(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)\$
• Distributive Laws: \$X \cdot (Y + Z) = X\cdot Y + X\cdot Z\$, \$X + (Y \cdot Z) = (X + Y)\cdot (X + Z)\$
• De Morgan’s Theorems: \$\overline{X + Y} = \overline{X}\cdot\overline{Y}\$, \$\overline{X\cdot Y} = \overline{X} + \overline{Y}\$

3. Common Boolean Identities

These identities are frequently used for simplification:

• Absorption: \$X + X\cdot Y = X\$, \$X\cdot (X + Y) = X\$
• Consensus: \$X\cdot Y + \overline{X}\cdot Z + Y\cdot Z = X\cdot Y + \overline{X}\cdot Z\$
• Double Negation: \$\overline{\overline{X}} = X\$

4. Simplification Techniques

1. Apply the fundamental laws and identities step‑by‑step.
2. Use algebraic manipulation to factor or expand expressions.
3. Employ Karnaugh maps (K‑maps) for up to four variables to obtain minimal sum‑of‑products (SOP) or product‑of‑sums (POS) forms.

5. Karnaugh Maps

A K‑map is a visual tool that groups adjacent 1’s (for SOP) or 0’s (for POS) to minimise the expression.

6. Example: Simplifying a Boolean Expression

Given the expression:

\$F = \overline{A}B\overline{C} + \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC\$

Simplify using algebraic methods:

1. Group terms with common factors:

   • \$\overline{A}B\overline{C} + \overline{A}BC = \overline{A}B(\overline{C}+C) = \overline{A}B\$
   • \$A\overline{B}C + AB\overline{C} + ABC = AC(\overline{B}+B) + AB\overline{C} = AC + AB\overline{C}\$

2. Combine the results:

   \$F = \overline{A}B + AC + AB\overline{C}\$

3. Apply absorption on \$AB\overline{C}\$:

   \$AB\overline{C} + AC = A(C + B\overline{C}) = A(C + B)\$

   (since \$C + B\overline{C}=C + B\$ by distributive law)

4. Final simplified form:

   \$F = \overline{A}B + A(C + B)\$

7. Translating Boolean Expressions to Logic Circuits

Each basic operation corresponds to a standard gate:

• AND → \$\cdot\$ (gate symbol: ∧)
• OR → \$+\$ (gate symbol: ∨)
• NOT → \$\overline{\phantom{X}}\$ (gate symbol: inverter)

For the final expression \$F = \overline{A}B + A(C + B)\$ the circuit can be built as follows:

1. Invert \$A\$ to obtain \$\overline{A}\$.
2. AND \$\overline{A}\$ with \$B\$.
3. OR \$C\$ and \$B\$.
4. AND the result with \$A\$.
5. OR the two AND‑gate outputs to produce \$F\$.

8. Truth Table Construction

Below is the truth table for the simplified function \$F = \overline{A}B + A(C + B)\$.

9. Practice Questions

1. Use Boolean algebra to simplify the expression \$G = A\overline{B} + AB + \overline{A}\overline{B}\$.
2. Construct a Karnaugh map for the function \$H(A,B,C) = \sum m(1,2,5,6,7)\$ and write the minimal SOP expression.
3. Draw the logic‑gate diagram for the minimal expression obtained in question 2.
4. Verify the result of question 1 by completing a truth table.

10. Summary

Understanding Boolean algebra enables you to:

• Analyse and simplify logical expressions.
• Design efficient combinational circuits with the fewest possible gates.
• Apply Karnaugh maps to obtain minimal SOP or POS forms for up to four variables.
• Translate algebraic results directly into practical hardware implementations.