De Morgan's Laws

De Morgan's Laws

De Morgan's Laws describe how negation distributes over AND and OR:

1. $\neg$(P $\land$ Q) $\equiv$ $\neg$P $\lor$ $\neg$Q — "not both" equals "at least one is not"
2. $\neg$(P $\lor$ Q) $\equiv$ $\neg$P $\land$ $\neg$Q — "not either" equals "both are not"

The pattern: when you push negation inside parentheses, the operator flips (AND $\leftrightarrow$ OR) and each operand gets negated.

Named after Augustus De Morgan (1806-1871), these laws are essential for simplifying and transforming logical expressions.

First Law - Negating AND

De Morgan's first law: $\neg$(P $\land$ Q) $\equiv$ $\neg$P $\lor$ $\neg$Q

In words: "not (P and Q)" means "not P, or not Q" (or both).

Why does this work? P $\land$ Q is false when at least one of P or Q is false. That's exactly when $\neg$P $\lor$ $\neg$Q is true!

Second Law - Negating OR

De Morgan's second law: $\neg$(P $\lor$ Q) $\equiv$ $\neg$P $\land$ $\neg$Q

In words: "not (P or Q)" means "not P, and not Q".

Why does this work? P $\lor$ Q is false only when both P and Q are false. That's exactly when $\neg$P $\land$ $\neg$Q is true!

Applying De Morgan (Forward)

To apply De Morgan's Laws, push the negation inside the parentheses:

1. Negate each operand
2. Flip the operator (AND $\leftrightarrow$ OR)

Examples:

• $\neg$(P $\land$ Q) $\to$ $\neg$P $\lor$ $\neg$Q
• $\neg$(X $\lor$ Y) $\to$ $\neg$X $\land$ $\neg$Y
• $\neg$($\neg$A $\land$ B) $\to$ $\neg$$\neg$A $\lor$ $\neg$B $\to$ A $\lor$ $\neg$B

Applying De Morgan (Reverse)

De Morgan's Laws also work in reverse — you can factor out negations:

• $\neg$P $\lor$ $\neg$Q $\to$ $\neg$(P $\land$ Q)
• $\neg$P $\land$ $\neg$Q $\to$ $\neg$(P $\lor$ Q)

This is useful for simplifying expressions or recognizing patterns.

The rule: if both operands are negated, you can factor the negation out and flip the operator.

De Morgan in English

De Morgan's Laws have intuitive English interpretations:

First Law ($\neg$(P $\land$ Q) $\equiv$ $\neg$P $\lor$ $\neg$Q):

• "Not both P and Q" = "Not P, or not Q"
• "It's not the case that both are true" = "At least one is false"

Second Law ($\neg$(P $\lor$ Q) $\equiv$ $\neg$P $\land$ $\neg$Q):

• "Neither P nor Q" = "Not P, and not Q"
• "It's not the case that either is true" = "Both are false"

Verifying De Morgan

We can verify De Morgan's Laws by checking that both sides give the same result for any values of P and Q.

For example, with P = T and Q = F:

• $\neg$(P $\land$ Q) = $\neg$(T $\land$ F) = $\neg$F = T
• $\neg$P $\lor$ $\neg$Q = $\neg$T $\lor$ $\neg$F = F $\lor$ T = T ✓

Choosing Which De Morgan Law

The two De Morgan laws handle different situations:

• First law: $\neg$(A $\land$ B) = $\neg$A $\lor$ $\neg$B (negation of AND becomes OR)
• Second law: $\neg$(A $\lor$ B) = $\neg$A $\land$ $\neg$B (negation of OR becomes AND)

The key is to identify what operation is inside the negation.

Nested De Morgan Applications

Sometimes we need to apply De Morgan's laws multiple times, or combine them with double negation:

• $\neg$($\neg$A $\land$ $\neg$B) = $\neg$$\neg$A $\lor$ $\neg$$\neg$B = A $\lor$ B
• $\neg$($\neg$A $\lor$ $\neg$B) = $\neg$$\neg$A $\land$ $\neg$$\neg$B = A $\land$ B

The pattern: negating a De Morgan result gives back the original!

De Morgan with Three Variables

De Morgan's laws extend to more than two terms:

• $\neg$(A $\land$ B $\land$ C) = $\neg$A $\lor$ $\neg$B $\lor$ $\neg$C
• $\neg$(A $\lor$ B $\lor$ C) = $\neg$A $\land$ $\neg$B $\land$ $\neg$C

The pattern: negate each term and flip AND$\leftrightarrow$OR.

De Morgan Proof by Truth Table

We can prove De Morgan's Laws by checking all possible input combinations.

For two variables, there are 4 combinations. If both sides of the law produce the same output for all 4, they are equivalent!

This is called proof by exhaustion - we exhaustively check every case.

De Morgan in Programming

De Morgan's Laws appear constantly in programming:

Language syntax:

• NOT: ! (C, Java, JS) or not (Python)
• AND: && (C, Java, JS) or and (Python)
• OR: || (C, Java, JS) or or (Python)

The laws in code:

• !(a && b) $\equiv$ !a || !b
• !(a || b) $\equiv$ !a && !b

De Morgan with Multiple Operands

De Morgan's Laws generalize to any number of operands:

Extended De Morgan:

• $\neg$(A $\land$ B $\land$ C) = $\neg$A $\lor$ $\neg$B $\lor$ $\neg$C
• $\neg$(A $\lor$ B $\lor$ C) = $\neg$A $\land$ $\neg$B $\land$ $\neg$C

The pattern: negate each operand and flip all connectives.

Nested De Morgan Application

When expressions are nested, apply De Morgan from the outside in:

Example: $\neg$(P $\land$ (Q $\lor$ R))

1. Outer: $\neg$P $\lor$ $\neg$(Q $\lor$ R)
2. Inner: $\neg$P $\lor$ ($\neg$Q $\land$ $\neg$R)

Each negation that "enters" parentheses flips the operator inside.

De Morgan Simplification Challenge

De Morgan's Laws are a powerful simplification tool:

• Remove outer negations by pushing them inward
• Combine with other laws (double negation, identity, etc.)
• Transform to equivalent but simpler forms

The goal: fewer operations, clearer structure.

Evaluating De Morgan Expressions

De Morgan's Laws give us two equivalent ways to express the same thing:

• $\neg$(P $\land$ Q) $\equiv$ $\neg$P $\lor$ $\neg$Q (negation of AND becomes OR of negations)
• $\neg$(P $\lor$ Q) $\equiv$ $\neg$P $\land$ $\neg$Q (negation of OR becomes AND of negations)

Being able to quickly evaluate these expressions builds fluency with the laws.

Catching Contradictions

A contradiction occurs when statements cannot all be true simultaneously.

If we have P $\to$ Q (if P then Q) and we observe $\neg$Q, then by modus tollens we conclude $\neg$P.

In detective work: "If the butler did it, there would be muddy footprints. There are no muddy footprints. Therefore, the butler didn't do it."

Spotting contradictions is how alibis unravel.

When to Apply De Morgan

When De Morgan is the right move:

1. Negation outside parentheses. You have $\neg$(compound) and need to simplify or manipulate the terms inside. De Morgan pushes the $\neg$ inward.

2. Converting between AND/OR forms. Preparing for CNF or DNF often requires flipping operators. De Morgan is how you cross the AND/OR boundary under negation.

3. Simplifying nested negations. After applying De Morgan, you may find double negations that cancel, or complement pairs that resolve to constants.

4. Reverse application. Sometimes you want to pull negation outward— combining $\neg$A $\lor$ $\neg$B into $\neg$(A $\land$ B)—to group terms or prepare for further manipulation.