Simplifying Boolean Expressions (De Morgan's Laws)

Boolean expressions can often be simplified to use fewer gates, which makes circuits cheaper, faster, and more energy-efficient. OCR J277 Section 2.5 expects you to be able to simplify simple Boolean expressions and understand De Morgan's Laws.

---

Why Simplify?

Unsimplified	Simplified	Benefit
More gates needed	Fewer gates needed	Lower cost
More connections	Fewer connections	Less power consumption
Longer signal paths	Shorter signal paths	Faster processing
More potential faults	Fewer potential faults	Higher reliability

Simplification does not change what the circuit does — it produces an equivalent expression that gives the same output for every possible input combination.

---

Basic Boolean Algebra Laws

Before tackling De Morgan's Laws, you should know these fundamental identities:

Identity Laws

• A AND 1 = A (ANDing with 1 has no effect)
• A OR 0 = A (ORing with 0 has no effect)

Null Laws

• A AND 0 = 0 (ANDing with 0 always gives 0)
• A OR 1 = 1 (ORing with 1 always gives 1)

Complement Laws

• A AND (NOT A) = 0 (a value ANDed with its inverse is always 0)
• A OR (NOT A) = 1 (a value ORed with its inverse is always 1)

Idempotent Laws

• A AND A = A
• A OR A = A

Double Negation

• NOT (NOT A) = A (inverting twice returns to the original)

---

Simplification Examples

Example 1: A AND (A OR B)

Using the absorption law: A AND (A OR B) = A

Proof by truth table:

A	B	A OR B	A AND (A OR B)	A
0	0	0	0	0
0	1	1	0	0
1	0	1	1	1
1	1	1	1	1

The last two columns are identical, confirming A AND (A OR B) = A.

Example 2: (A AND B) OR (A AND (NOT B))

Factor out A: A AND (B OR (NOT B)) = A AND 1 = A

This uses the complement law: B OR (NOT B) = 1, and the identity law: A AND 1 = A.

OCR Exam Tip: When simplifying, look for variables that appear both as themselves and as their NOT form — you can often use the complement law to simplify them to 1 or 0.

---

De Morgan's Laws

Augustus De Morgan (1806-1871) discovered two laws that show how to convert between AND and OR operations when combined with NOT:

First Law

NOT (A AND B) = (NOT A) OR (NOT B)

In algebraic notation: (A . B)̄ = Ā + B̄

This means: "NOT of (A AND B)" is the same as "(NOT A) OR (NOT B)"

Proof by truth table:

A	B	A AND B	NOT(A AND B)	NOT A	NOT B	(NOT A) OR (NOT B)
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Columns 4 and 7 are identical, confirming the law.

Second Law

NOT (A OR B) = (NOT A) AND (NOT B)

In algebraic notation: (A + B)̄ = Ā . B̄

This means: "NOT of (A OR B)" is the same as "(NOT A) AND (NOT B)"

---

Applying De Morgan's Laws

De Morgan's Laws are useful for:

1. Converting NAND to OR with NOTs: NAND(A, B) = (NOT A) OR (NOT B)
2. Converting NOR to AND with NOTs: NOR(A, B) = (NOT A) AND (NOT B)
3. Simplifying complex expressions by changing the type of gate used

Example

Simplify: NOT((NOT A) AND B)

Using De Morgan's first law: NOT((NOT A) AND B) = (NOT(NOT A)) OR (NOT B) = A OR (NOT B)

---

Memory Aid for De Morgan's Laws

Think of it as "break the bar, change the sign":

• When you move NOT across a bracket, AND becomes OR (and vice versa)
• Each variable inside the bracket gets its own NOT

NOT (A AND B) = (NOT A) OR  (NOT B)    // AND became OR
NOT (A OR  B) = (NOT A) AND (NOT B)    // OR became AND

OCR Exam Tip: To remember De Morgan's Laws, use the phrase "break the bar, change the sign." When the NOT bar is "broken" apart to cover individual terms, the AND symbol changes to OR (and vice versa).

---

Practice Problems

1. Simplify: (A OR A) AND B Answer: A AND B (using idempotent law: A OR A = A)

2. Simplify: NOT(NOT(A AND B)) Answer: A AND B (using double negation)

3. Apply De Morgan's Law: NOT(A OR B) Answer: (NOT A) AND (NOT B)

4. Simplify: (A AND B) OR (A AND B) Answer: A AND B (using idempotent law)

---

Summary

• Simplifying Boolean expressions reduces the number of gates needed
• Key laws: identity, null, complement, idempotent, double negation, absorption
• De Morgan's First Law: NOT(A AND B) = (NOT A) OR (NOT B)
• De Morgan's Second Law: NOT(A OR B) = (NOT A) AND (NOT B)
• "Break the bar, change the sign" is a useful memory aid
• You can verify any simplification using a truth table

---

Extended Worked Example: Full De Morgan Proof

Show that NOT (A OR B) = (NOT A) AND (NOT B) using a complete truth table.

A	B	A + B	NOT (A + B)	NOT A	NOT B	(NOT A) . (NOT B)
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

Columns 4 and 7 match in every row, proving De Morgan's second law.

---

Extended Worked Example: Simplifying a Sum of Products

Simplify: Q = (A . (NOT B)) + (A . B) + ((NOT A) . B).

Step 1: Group the first two terms (both contain A):

Q = A . ((NOT B) + B) + ((NOT A) . B)

Step 2: Apply the complement law (NOT B) + B = 1:

Q = A . 1 + ((NOT A) . B)

Step 3: Apply the identity law A . 1 = A:

Q = A + ((NOT A) . B)

Step 4: This can be further simplified using the absorption-like identity X + ((NOT X) . Y) = X + Y:

Q = A + B

Verification:

A	B	Original	A + B
0	0	(0 . 1) + (0 . 0) + (1 . 0) = 0	0
0	1	(0 . 0) + (0 . 1) + (1 . 1) = 1	1
1	0	(1 . 1) + (1 . 0) + (0 . 0) = 1	1
1	1	(1 . 0) + (1 . 1) + (0 . 1) = 1	1

Both columns match — the simplification is correct. A 3-term SOP expression has been reduced to a single OR.

---