Logical equivalences and De Morgan's laws

Two formulae are equivalent ($\equiv$) if they have the same truth table: in every row they take the same value. Equivalences allow a complicated condition to be rewritten as a simpler one, without changing its meaning.

Property — Fundamental logical equivalences

• Double negation: $\lnot(\lnot p)\equiv p$.
• De Morgan’s laws: $\lnot(p\land q)\equiv \lnot p\lor\lnot q$ and $\lnot(p\lor q)\equiv \lnot p\land\lnot q$.
• Implication as an “or”: $p\Rightarrow q\equiv \lnot p\lor q$.
• Contraposition: $p\Rightarrow q\equiv \lnot q\Rightarrow\lnot p$ (the basis of proofs by contradiction).
• Double implication: $p\Leftrightarrow q\equiv (p\Rightarrow q)\land(q\Rightarrow p)$.

De Morgan’s laws say that negating a conjunction is equivalent to taking the disjunction of the negations, and vice versa: negation “swaps” $\land$ and $\lor$. We shall meet them again, identical, as laws that swap intersection and union between sets.

Links

Topics: Set theory
Concepts: Contraposition · Logical equivalence · De Morgan’s laws
Skills: Proving
People: Augustus De Morgan