Course contentsShow
← Mathematics
Lesson 2476 of 3,12150. Discrete Math — Logic and ProofFree lesson

De Morgan's Laws

State and prove De Morgan's laws for negating conjunctions and disjunctions, and apply them to simplify expressions.

De Morgan's Laws

You'll learn how to correctly negate compound logical statements using De Morgan's Laws.

What Are De Morgan's Laws?

De Morgan's Laws are two fundamental rules that tell us how to negate compound propositions involving AND (conjunction) and OR (disjunction). They reveal a beautiful symmetry: negating flips both the connective and each component.

The two laws state:

  1. ¬(P ∧ Q) ≡ ¬P ∨ ¬Q — "Not (P and Q)" is equivalent to "(Not P) or (Not Q)"
  2. ¬(P ∨ Q) ≡ ¬P ∧ ¬Q — "Not (P or Q)" is equivalent to "(Not P) and (Not Q)"

Understanding Through an Example

Consider the statement: "It is raining AND it is cold."

The negation isn't "It is not raining AND it is not cold." That's too restrictive! The original statement is false if either condition fails.

The correct negation is: "It is NOT raining OR it is NOT cold." If at least one condition fails, the original AND statement is false.

Proving De Morgan's Laws

We can verify these using truth tables:

PQP ∧ Q¬(P ∧ Q)¬P¬Q¬P ∨ ¬Q
TTTFFFF
TFFTFTT
FTFTTFT
FFFTTTT

The columns for ¬(P ∧ Q) and ¬P ∨ ¬Q match perfectly, proving logical equivalence.

Applying De Morgan's Laws

Simplify: ¬((x > 5) ∨ (y < 3))

Using De Morgan's second law: ¬(x > 5) ∧ ¬(y < 3) ≡ (x ≤ 5) ∧ (y ≥ 3)

Key Takeaway: De Morgan's Laws let you push negation inside parentheses by flipping AND↔OR and negating each component—essential for simplifying logical expressions and writing correct negations.