The first two rules of replacement are De Morgan's rule (DM) and double negation (DN). You know both equivalences already from De Morgan's Laws; now they become steps in a proof. They are the rules from Rules of Replacement you will use most.
| Rule | Form | Form |
|---|---|---|
| DM | $\neg (p \land q)$ | $\neg p \lor \neg q$ |
| DM | $\neg (p \lor q)$ | $\neg p \land \neg q$ |
| DN | $p$ | $\neg \neg p$ |
Key idea
Why it works
Worked examples
Worked example: DM on a whole line
- A negated disjunction becomes a conjunction of negations.
Answer: $\neg r \land \neg s$
Worked example: DM inside a line
- Only the antecedent changes.
Answer: $(\neg p \lor \neg q) \to r$
Worked example: DN removing negations
- Remove the two negations in front of $t$.
Answer: $t \land u$
Worked example: Both rules in a proof
- Line 3: $\neg p \land \neg q$ by DM 1.
- Line 4: $\neg p$ by Simp 3.
- Line 5: $\neg r$ by MT 2, 4.
Answer: Three lines.
Common mistake
When should you reach for DM? Whenever a negation stands in front of parentheses and the next rule needs the parts separately. A negated conjunction becomes a disjunction, which DS can use; a negated disjunction becomes a conjunction, which Simp can take apart. DN is the finishing touch whenever a rule wants $\neg \neg p$ and you have $p$, or the other way round.
Each use of a replacement rule changes one part, once. If a line needs DM in two places, use two lines, each justified "DM" with the line it came from. That keeps every step easy to check.