Tautologies and Logical Equivalence

Some propositions are true no matter what values their variables take. Recognising these, and recognising when two different-looking expressions always have the same value, is how we simplify logic in proofs, code and circuits.

Three kinds of compound propositions

TautologyAll Te.g. p ∨ ¬p

ContradictionAll Fe.g. p ∧ ¬p

ContingencyA mix of T and Fe.g. p → q

Classifying a proposition by its final truth-table column

Logical equivalence

Two propositions $A$ and $B$ are logically equivalent, written $A \equiv B$, if they have the same truth value in every row. Equivalently, $A \leftrightarrow B$ is a tautology.

Worked example: $p \to q \equiv \lnot p \lor q$

$p$	$q$	$p \to q$	$\lnot p$	$\lnot p \lor q$
T	T	T	F	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

The columns for $p \to q$ and $\lnot p \lor q$ match in every row, so they are equivalent.

De Morgan’s laws

$$\lnot(p \land q) \equiv \lnot p \lor \lnot q \qquad \lnot(p \lor q) \equiv \lnot p \land \lnot q$$

In words: to negate an “and”, negate each part and switch to “or” (and vice versa). You use this every time you simplify a condition like !(a && b) in code.

Common mistakes

• Negating each part but forgetting to switch $\land$ and $\lor$.
• Checking only some rows. Equivalence needs every row to match.

Key takeaways

• Tautology: always true. Contradiction: always false. Contingency: neither.
• $A \equiv B$ means identical truth-table columns, i.e. $A \leftrightarrow B$ is a tautology.
• $p \to q \equiv \lnot p \lor q$.
• De Morgan: $\lnot(p \land q) \equiv \lnot p \lor \lnot q$ and $\lnot(p \lor q) \equiv \lnot p \land \lnot q$.

Test yourself

4 questions. Pick an answer to check it, or open "Show answer".

1. Which of the following is a tautology?

   • A$p \land \lnot p$
   • B$p \lor \lnot p$
   • C$p \to q$
   • D$p \land q$
   Show answer

   Answer: B. $p \lor \lnot p$

   Explanation: Either $p$ or $\lnot p$ is always true, so their disjunction is true in every row. $p \land \lnot p$ is the opposite: a contradiction.

2. By De Morgan’s law, $\lnot(p \lor q)$ is equivalent to:

   • A$\lnot p \lor \lnot q$
   • B$p \land q$
   • C$\lnot p \land \lnot q$
   • D$\lnot p \lor q$
   Show answer

   Answer: C. $\lnot p \land \lnot q$

   Explanation: Negate each part and switch “or” to “and”. The tempting $\lnot p \lor \lnot q$ forgets to switch the connective; it is the negation of $p \land q$ instead.

3. Which expression is logically equivalent to $p \to q$?

   • A$q \to p$
   • B$\lnot p \lor q$
   • C$p \lor \lnot q$
   • D$\lnot p \to \lnot q$
   Show answer

   Answer: B. $\lnot p \lor q$

   Explanation: The truth tables match in every row. $q \to p$ (the converse) and $\lnot p \to \lnot q$ (the inverse) are common traps; neither is equivalent to the original.

4. A compound proposition is true in some rows and false in others. It is called a:

   • ATautology
   • BContradiction
   • CContingency
   • DEquivalence
   Show answer

   Answer: C. Contingency

   Explanation: A contingency is neither always true nor always false. Most everyday propositions, like $p \to q$, are contingencies.