Logical Equivalence

Two formulas can look different and still say the same thing. Truth tables (Tautologies, Contradictions and Contingent Statements) let us make that precise.

Key idea

Two formulas are logically equivalent when they have the same truth value in every row of a joint truth table. Then their biconditional is a tautology.

Why it works

A formula's meaning, as far as logic is concerned, is its column: the rows where it is true. If two formulas have identical columns, there is no situation in which one is true and the other false, so either one can stand in for the other in any argument. That is also exactly when $A \leftrightarrow B$ is true in every row, since a biconditional is true when the sides match.

Equivalent: the two main columns match in every row.

Worked examples

Worked example: Conditional and disjunction

Are $p \to q$ and $\neg p \lor q$ equivalent?

Column for $p \to q$: T, F, T, T.
Column for $\neg p \lor q$: $\neg p$ is F, F, T, T, so the disjunction is T, F, T, T.
The columns match.

Answer: Equivalent

Worked example: A look-alike that is not

Are $(p \land q) \to r$ and $(p \to q) \to r$ equivalent?

Try the row $p$ F, $q$ F, $r$ F.
$(p \land q) \to r$: F → F is T.
$(p \to q) \to r$: $p \to q$ is T, and T → F is F.

Answer: Not equivalent: they differ in that row.

Worked example: Use the biconditional

How could you test the first example with one column?

Build $(p \to q) \leftrightarrow (\neg p \lor q)$.
If it is T in every row, the two are equivalent.

Answer: It is a tautology, so they are equivalent.

Worked example: Two ways to say if and only if

Are $p \leftrightarrow q$ and $(p \land q) \lor (\neg p \land \neg q)$ equivalent?

$p \leftrightarrow q$ is T when the values match: rows TT and FF.
$(p \land q) \lor (\neg p \land \neg q)$ is T when both are T or both are F: the same two rows.
Both are F in the other two rows.

Answer: Equivalent

Notice the difference between being equivalent and merely having the same value in one row. In the row where $p$ and $q$ are both true, $p \land q$ and $p \lor q$ are both T, but they are not equivalent: in the row $p$ T, $q$ F they differ. Equivalence is a claim about every row.

Common mistake

Comparing only the rows where the formulas are true, or deciding by how alike they look. Two formulas can share every T row and still differ where one is F and the other T only if you skipped rows; check every row, T and F alike. And look-alikes are often not equivalent: $(p \land q) \to r$ and $(p \to q) \to r$ differ, as the second example shows.

Equivalences are the raw material of the rules of replacement later in the course (Rules of Replacement). Each of those rules is a pair of equivalent forms, checked once by a truth table and then used anywhere.

Logical Equivalence

Worked examples

Practice

Builds on

Leads to

Sources and further reading