Some equivalences (Logical Equivalence) come up so often that they have names. The most useful pair is De Morgan's laws, which tell you how to move a negation inside parentheses.
Key idea
Why it works
Worked examples
Worked example: Move the negation in
- Negate each part: $\neg r$, $\neg s$.
- Switch $\land$ to $\lor$.
Answer: $\neg r \lor \neg s$
Worked example: Parts that are already negated
- Negate each part: $\neg \neg p$ and $\neg q$.
- Switch $\lor$ to $\land$.
- A double negation may be dropped: $\neg \neg p$ is equivalent to $p$.
Answer: $p \land \neg q$
Worked example: Pull it out
- Read De Morgan right to left.
- Take the negations off, switch $\lor$ to $\land$, and negate the whole.
Answer: $\neg (p \land q)$
Both laws come from one idea. A conjunction claims every part; to deny it you only need one part to fail, so the denial is a disjunction of failures. A disjunction claims at least one part; to deny it every part must fail, so the denial is a conjunction of failures. Once you see that, you will not need to memorize which way the connective switches.
Worked example: In English
- In symbols: $\neg (g \land d)$.
- De Morgan gives $\neg g \lor \neg d$.
Answer: "Either the gate is not open or the dog is not outside."
Common mistake
- Negation over $\land$: negate each part, switch to $\lor$.
- Negation over $\lor$: negate each part, switch to $\land$.
- Cancel any double negation $\neg \neg p$ to $p$ if you like; they are equivalent.
- Check one row with the truth table if you are unsure.
The same laws work with larger parts: $\neg ((p \to q) \lor r)$ becomes $\neg (p \to q) \land \neg r$. And they apply in English: "it is not the case that either the bus is late or the train is late" says the bus is not late and the train is not late.