Introduction to Boolean Algebra
Welcome to Boolean Algebra! Have you ever wondered how computers, smartphones, and digital systems make decisions? At their absolute core, digital devices do not understand words, pictures, or complex numbers; they only understand two states: True or False, represented numerically as \(1\) or \(0\).
Boolean algebra is the branch of mathematics that formalises this two-state logic. Developed by the 19th-century mathematician George Boole, it provides the mathematical foundation for computer science, digital circuit design, and decision mathematics in your CCEA AS Further Mathematics course.
Don't worry if this seems abstract at first! Although the rules look a little different from regular algebra, you will quickly find that Boolean algebra is logical, systematic, and satisfying once you master a few fundamental laws.
1. Fundamental Concepts: Variables and Operations
In standard algebra, a variable like \(x\) can be any real number (\(2\), \(-5\), \(3.14\)). In Boolean algebra, every variable can take only one of two values:
• \(1\) (True, High voltage, Closed switch, On)
• \(0\) (False, Low voltage, Open switch, Off)
The Three Basic Operations
There are three primary operations used in Boolean algebra:
1. Conjunction (AND): Written as \(A \cdot B\), \(A \land B\), or simply \(AB\).
The output is \(1\) only if both \(A\) and \(B\) are \(1\).
Everyday analogy: To enter a secure building, you need a keycard AND a PIN code. If either is missing, you cannot enter.
• \(0 \cdot 0 = 0\)
• \(0 \cdot 1 = 0\)
• \(1 \cdot 0 = 0\)
• \(1 \cdot 1 = 1\)
2. Disjunction (OR): Written as \(A + B\) or \(A \lor B\).
The output is \(1\) if at least one of the inputs is \(1\).
Everyday analogy: You can pay for your coffee with cash OR a card. Having either (or both) lets you buy the coffee.
• \(0 + 0 = 0\)
• \(0 + 1 = 1\)
• \(1 + 0 = 1\)
• \(1 + 1 = 1\) (Remember: in Boolean algebra, \(1 + 1 = 1\), not \(2\)!)
3. Negation (NOT / Complement): Written as \(A'\), \(\overline{A}\), or \(\sim A\).
This operation simply flips the value to its opposite.
• If \(A = 0\), then \(A' = 1\)
• If \(A = 1\), then \(A' = 0\)
Key Takeaway: Boolean algebra has only two numbers: \(0\) and \(1\). The primary operations are AND (multiplication), OR (addition), and NOT (inversion).
2. Truth Tables
A truth table is a systematic diagram showing all possible input combinations for a set of Boolean variables alongside the resulting output. For \(n\) input variables, there are always \(2^n\) possible combinations.
Two-Variable Truth Table
For two variables, \(A\) and \(B\), there are \(2^2 = 4\) rows:
• Row 1: \(A = 0, B = 0 \implies A' = 1, AB = 0, A + B = 0\)
• Row 2: \(A = 0, B = 1 \implies A' = 1, AB = 0, A + B = 1\)
• Row 3: \(A = 1, B = 0 \implies A' = 0, AB = 0, A + B = 1\)
• Row 4: \(A = 1, B = 1 \implies A' = 0, AB = 1, A + B = 1\)
Three-Variable Truth Table
For three variables (\(A, B, C\)), there are \(2^3 = 8\) rows. To ensure you do not miss any combinations, write inputs in binary counting order: \(000, 001, 010, 011, 100, 101, 110, 111\).
Key Takeaway: Truth tables are foolproof tools. If you are ever stuck trying to prove that two Boolean expressions are equal, draw a truth table for each side. If the final output columns match row-for-row, the expressions are equivalent.
3. Switching Circuits
Boolean algebra directly models electrical switching circuits:
• Series Connection: Current flows through switch \(A\) AND switch \(B\). Both switches must be closed for the circuit to be complete. This represents the AND operation: \(AB\).
• Parallel Connection: Current can flow through switch \(A\) OR switch \(B\). If either switch is closed, the circuit is complete. This represents the OR operation: \(A + B\).
• Normally Closed Switch: A switch that opens when activated represents the NOT operation: \(A'\).
Did you know? Claude Shannon discovered in 1937 that electrical switches could solve Boolean algebra problems, laying the foundation for all modern digital computing hardware!
4. The Laws of Boolean Algebra
To simplify complex Boolean expressions and minimise the number of logic gates or switches needed, we apply specific mathematical laws. Many mimic standard algebra, but some are unique to Boolean logic.
1. Identity Laws
• \(A + 0 = A\) (Adding "False" does not change the state)
• \(A \cdot 1 = A\) (AND with "True" keeps the original state)
2. Null (or Dominance / Annihilation) Laws
• \(A + 1 = 1\) (OR with "True" is always True)
• \(A \cdot 0 = 0\) (AND with "False" is always False)
3. Idempotent Laws
• \(A + A = A\)
• \(A \cdot A = A\)
Explanation: Checking the same condition twice gives no new information.
4. Complement (or Inverse) Laws
• \(A + A' = 1\) (Either \(A\) is true, or \(A\) is not true — one must be true!)
• \(A \cdot A' = 0\) (Something cannot be both true and false at the same time)
5. Double Negation (Involution) Law
• \((A')' = A\) (Negating a statement twice brings you back to the start)
6. Commutative Laws
• \(A + B = B + A\)
• \(AB = BA\)
7. Associative Laws
• \(A + (B + C) = (A + B) + C\)
• \(A(BC) = (AB)C\)
8. Distributive Laws
• First Distributive Law: \(A(B + C) = AB + AC\) (Just like standard algebra)
• Second Distributive Law: \(A + BC = (A + B)(A + C)\) (Crucial Exam Rule: This does NOT work in regular algebra, but is fully valid in Boolean algebra!)
9. Absorption Laws
• \(A + AB = A\)
• \(A(A + B) = A\)
Why does this work? Look at \(A + AB\): factor out \(A\) to get \(A(1 + B)\). Since \(1 + B = 1\), this simplifies to \(A \cdot 1 = A\).
10. Redundancy (or Consensus) Variations
• \(A + A'B = A + B\)
• \(A(A' + B) = AB\)
Proof of \(A + A'B = A + B\): Using the Second Distributive Law, \(A + A'B = (A + A')(A + B) = 1 \cdot (A + B) = A + B\).
Key Takeaway: Memorise the unique Boolean laws: \(A + A = A\), \(A + 1 = 1\), \(A + A' = 1\), and \(A + BC = (A + B)(A + C)\). These are the keys to successful algebraic simplification.
5. De Morgan's Laws
Augustus De Morgan formulated two powerful laws for negating combined expressions. These are among the most frequently tested rules in CCEA examinations.
First Law: \((A + B)' = A' \cdot B'\)
"The negation of an OR is the AND of the negations."
Second Law: \((AB)' = A' + B'\)
"The negation of an AND is the OR of the negations."
Memory Trick: "Break the line, change the sign."
When you break the bar over an expression, an addition sign (\(+\)) becomes a multiplication sign (\(\cdot\)), and vice versa.
Extended Example with 3 Variables:
\((A + B + C)' = A'B'C'\)
\((ABC)' = A' + B' + C'\)
6. Step-by-Step Algebraic Simplification
Simplifying Boolean expressions requires applying the laws step-by-step. Always state the law used where possible.
Worked Example 1: Basic Simplification
Simplify the expression: \(E = AB + AB'\)
Step 1: Factor out the common term \(A\):
\(E = A(B + B')\)
Step 2: Apply the Complement Law (\(B + B' = 1\)):
\(E = A(1)\)
Step 3: Apply the Identity Law (\(A \cdot 1 = A\)):
\(E = A\)
Worked Example 2: Using De Morgan's Laws
Simplify the expression: \(E = (A + B')'(A' + B)\)
Step 1: Apply De Morgan's Law to the first bracket \((A + B')'\):
\((A + B')' = A' \cdot (B')' = A'B\)
Step 2: Substitute this back into the expression:
\(E = (A'B)(A' + B)\)
Step 3: Expand the bracket:
\(E = (A'B \cdot A') + (A'B \cdot B)\)
Step 4: Rearrange and apply the Idempotent Law (\(A'A' = A'\) and \(BB = B\)):
\(E = A'B + A'B\)
Step 5: Apply the Idempotent Law (\(X + X = X\)):
\(E = A'B\)
Worked Example 3: A More Challenging Problem
Simplify: \(E = A'BC + AB'C + ABC' + ABC\)
Helpful Strategy: You can duplicate a term using the Idempotent Law (\(ABC = ABC + ABC\)) so it can pair with multiple terms!
Step 1: Write \(ABC\) three times:
\(E = (A'BC + ABC) + (AB'C + ABC) + (ABC' + ABC)\)
Step 2: Factorise each pair:
\(E = BC(A' + A) + AC(B' + B) + AB(C' + C)\)
Step 3: Apply the Complement Law (\(A' + A = 1\), etc.):
\(E = BC(1) + AC(1) + AB(1)\)
Step 4: Final simplified expression:
\(E = BC + AC + AB\)
Key Takeaway: Always look for common terms to factorise, terms that can pair with their complements (\(X + X' = 1\)), and opportunities to apply De Morgan's laws when expressions are negated.
7. Proving Boolean Equivalences
In the exam, you may be asked to prove that two expressions are equivalent (e.g. "Show that \(A + A'B = A + B\)"). There are two standard methods:
Method A: Algebraic Proof
Start with the Left-Hand Side (LHS) and manipulate it using known laws until it matches the Right-Hand Side (RHS):
LHS \(= A + A'B\)
\(= (A + A')(A + B)\) (by the Second Distributive Law)
\(= (1)(A + B)\) (since \(A + A' = 1\))
\(= A + B = \text{RHS}\) [Q.E.D.]
Method B: Truth Table Proof
Construct a single truth table containing columns for the sub-expressions and both final sides. Show that the final columns are identical for every combination of inputs.
8. Common Pitfalls & Exam Checklist
Common Mistakes to Avoid:
• Mistake: Writing \(1 + 1 = 0\) with a carry. In Boolean algebra, \(1 + 1 = 1\) (True OR True is True).
• Mistake: Forgetting that \(A + BC = (A + B)(A + C)\). This is unique to Boolean algebra and extremely useful.
• Mistake: Incorrectly applying De Morgan's Law: \((AB)' \neq A'B'\). Remember that the operator must flip: \((AB)' = A' + B'\).
• Mistake: Losing brackets during negations. \((A + B)'\) is NOT the same as \(A' + B\).
Quick Revision Checklist:
1. Can I construct complete truth tables for up to 3 variables without missing rows?
2. Do I know all basic laws (Identity, Idempotent, Complement, Null)?
3. Can I quote and apply De Morgan's Laws correctly?
4. Can I translate between switching circuits and Boolean expressions?