De Morgan's Laws

De Morgan's laws are two fundamental rules that relate AND, OR, and NOT operations. They are among the most important tools for simplifying Boolean expressions and converting between different gate types. The OCR H446 specification explicitly requires you to know and apply these laws.

---

The Two Laws

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)

In words:

• First law: The complement of a product (AND) is the sum (OR) of the complements.
• Second law: The complement of a sum (OR) is the product (AND) of the complements.

---

Intuitive Understanding

First Law — NOT(A AND B) = (NOT A) OR (NOT B): "It is not the case that both A and B are true" is the same as "either A is false, or B is false (or both)."

Second Law — NOT(A OR B) = (NOT A) AND (NOT B): "It is not the case that A or B is true" is the same as "A is false AND B is false."

---

Proving De Morgan's First Law with a 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 NOT(A AND B) and (NOT A) OR (NOT B) are identical: {1, 1, 1, 0}.

Therefore NOT(A AND B) = (NOT A) OR (NOT B). Proved.

---

Proving De Morgan's Second Law with a Truth Table

A	B	A OR B	NOT(A OR B)	NOT A	NOT B	(NOT A) AND (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 NOT(A OR B) and (NOT A) AND (NOT B) are identical: {1, 0, 0, 0}.

Therefore NOT(A OR B) = (NOT A) AND (NOT B). Proved.

---

How to Apply De Morgan's Laws

The process for applying De Morgan's laws to simplify an expression:

1. Identify a NOT applied to a compound expression (a NOT over an AND or OR)
2. Break the NOT inward: change AND to OR (or OR to AND)
3. Apply NOT to each individual term

Step-by-Step Pattern

Original	Step 1: Change the operator	Step 2: NOT each term	Result
NOT(A AND B)	Change AND to OR	NOT A, NOT B	(NOT A) OR (NOT B)
NOT(A OR B)	Change OR to AND	NOT A, NOT B	(NOT A) AND (NOT B)

---

De Morgan's Laws with More Than Two Variables

De Morgan's laws extend to any number of variables:

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

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

The rule is the same: negate each variable and swap AND/OR.

---