# 1.3 Logical Equivalence

Logical equivalence compares formulas by their truth values under all valuations, rather than by their written form, and it gives a precise way to say that two formulas express the same logical content.

### Definition 1.17 (Logical Equivalence)

Let $A$ and $B$ be formulas. We say that $A$ and $B$ are logically equivalent if:
$$
v(A)=v(B)
$$
for every valuation $v$.

In this case we write:
$$
A \equiv B
$$

This means that no valuation can distinguish $A$ from $B$, because whenever one is true the other is true, and whenever one is false the other is false.

### Example 1.18

The formulas:
$$
A \to B
$$
and:
$$
¬A \lor B
$$
are logically equivalent.

Their truth table is:

| $A$ | $B$ | $A \to B$ | $¬A \lor B$ |
|---|---|---|---|
| $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{F}$ |
| $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{T}$ |

The last two columns agree in every row, and therefore:
$$
A \to B \equiv ¬A \lor B
$$

This equivalence is one of the most useful transformations in propositional logic, because it allows implication to be eliminated in favor of negation and disjunction.

### Lemma 1.19 (Equivalence by Biconditional)

For formulas $A$ and $B$, the following are equivalent.

The formulas $A$ and $B$ are logically equivalent.

The formula:
$$
A \leftrightarrow B
$$
is valid.

Proof

By definition, $A \equiv B$ means that for every valuation $v$:
$$
v(A)=v(B)
$$

By the truth rule for the biconditional:
$$
v(A \leftrightarrow B)=\mathrm{T}
$$
if and only if:
$$
v(A)=v(B)
$$

Therefore $A$ and $B$ agree under every valuation if and only if $A \leftrightarrow B$ is true under every valuation, which is exactly to say that $A \leftrightarrow B$ is valid.

### Basic Laws

The following equivalences hold for all formulas $A$, $B$, and $C$, and they are used as algebraic rules for transforming formulas while preserving truth value.

Double negation:
$$
¬¬A \equiv A
$$

Idempotence:
$$
A \land A \equiv A
$$

$$
A \lor A \equiv A
$$

Commutativity:
$$
A \land B \equiv B \land A
$$

$$
A \lor B \equiv B \lor A
$$

Associativity:
$$
(A \land B) \land C \equiv A \land (B \land C)
$$

$$
(A \lor B) \lor C \equiv A \lor (B \lor C)
$$

Distributivity:
$$
A \land (B \lor C) \equiv (A \land B) \lor (A \land C)
$$

$$
A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)
$$

De Morgan laws:
$$
¬(A \land B) \equiv ¬A \lor ¬B
$$

$$
¬(A \lor B) \equiv ¬A \land ¬B
$$

Absorption:
$$
A \land (A \lor B) \equiv A
$$

$$
A \lor (A \land B) \equiv A
$$

Implication:
$$
A \to B \equiv ¬A \lor B
$$

Biconditional:
$$
A \leftrightarrow B \equiv (A \to B) \land (B \to A)
$$

Another useful form of the biconditional is:
$$
A \leftrightarrow B \equiv (A \land B) \lor (¬A \land ¬B)
$$

### Truth Constants

It is often convenient to use symbols for formulas that are always true or always false.

We write:
$$
\top
$$
for a formula that is always true, and:
$$
\bot
$$
for a formula that is always false.

These constants satisfy the following laws:
$$
A \land \top \equiv A
$$

$$
A \lor \bot \equiv A
$$

$$
A \land \bot \equiv \bot
$$

$$
A \lor \top \equiv \top
$$

Negation exchanges truth and falsehood:
$$
¬\top \equiv \bot
$$

$$
¬\bot \equiv \top
$$

Even if $\top$ and $\bot$ are not included as primitive symbols in the language, they may be represented using ordinary formulas, for example:
$$
\top \equiv p \lor ¬p
$$
and:
$$
\bot \equiv p \land ¬p
$$

### Example 1.20 (Rewriting a Formula)

Consider the formula:
$$
¬(A \to B)
$$

Using the implication law:
$$
A \to B \equiv ¬A \lor B
$$

we obtain:
$$
¬(A \to B) \equiv ¬(¬A \lor B)
$$

Using De Morgan law:
$$
¬(¬A \lor B) \equiv ¬¬A \land ¬B
$$

Using double negation:
$$
¬¬A \land ¬B \equiv A \land ¬B
$$

Therefore:
$$
¬(A \to B) \equiv A \land ¬B
$$

This equivalence says that an implication fails exactly when its antecedent is true and its consequent is false.

### Definition 1.21 (Tautology, Contradiction, Contingency)

A formula $A$ is a tautology if:
$$
v(A)=\mathrm{T}
$$
for every valuation $v$.

A formula $A$ is a contradiction if:
$$
v(A)=\mathrm{F}
$$
for every valuation $v$.

A formula $A$ is contingent if it is neither a tautology nor a contradiction, so that it is true under at least one valuation and false under at least one valuation.

### Example 1.22

The formula:
$$
p \lor ¬p
$$
is a tautology, because every valuation makes either $p$ true or $¬p$ true.

The formula:
$$
p \land ¬p
$$
is a contradiction, because no valuation can make both $p$ and $¬p$ true at the same time.

The formula:
$$
p \land q
$$
is contingent, because it is true when both $p$ and $q$ are true, but false under any valuation in which at least one of them is false.

### Lemma 1.23 (Logical Equivalence is an Equivalence Relation)

Logical equivalence is reflexive, symmetric, and transitive.

Proof

Reflexivity holds because for every formula $A$ and every valuation $v$, we have:
$$
v(A)=v(A)
$$
and therefore $A \equiv A$.

Symmetry holds because if $A \equiv B$, then $v(A)=v(B)$ for every valuation $v$, and equality of truth values is symmetric, so $v(B)=v(A)$ for every valuation $v$, which gives $B \equiv A$.

Transitivity holds because if $A \equiv B$ and $B \equiv C$, then for every valuation $v$ we have:
$$
v(A)=v(B)
$$
and:
$$
v(B)=v(C)
$$
so by transitivity of equality:
$$
v(A)=v(C)
$$
for every valuation $v$, and therefore $A \equiv C$.

### Lemma 1.24 (Substitution of Equivalents)

Suppose that:
$$
A \equiv B
$$

If $C[\ ]$ is a formula context with one distinguished placeholder, then:
$$
C[A] \equiv C[B]
$$

This means that an occurrence of a formula may be replaced by a logically equivalent formula inside any larger formula without changing the truth behavior of the larger formula.

Proof

The proof is by structural induction on the context $C[\ ]$.

If the context is only the placeholder, then:
$$
C[A]=A
$$
and:
$$
C[B]=B
$$
so the result follows from the assumption $A \equiv B$.

If the context has the form:
$$
¬D[\ ]
$$
then by the induction hypothesis:
$$
D[A] \equiv D[B]
$$

This means that $D[A]$ and $D[B]$ have the same truth value under every valuation, and therefore their negations also have the same truth value under every valuation, giving:
$$
¬D[A] \equiv ¬D[B]
$$

If the context has the form:
$$
D[\ ] \land E
$$
then by the induction hypothesis:
$$
D[A] \equiv D[B]
$$

Since conjunction depends only on the truth values of its two components, replacing $D[A]$ by $D[B]$ does not change the truth value of the whole conjunction, and hence:
$$
D[A] \land E \equiv D[B] \land E
$$

The cases for $\lor$, $\to$, and $\leftrightarrow$ are proved in the same way, using the corresponding truth rules for those connectives.

### Example 1.25 (Algebraic Simplification)

Consider:
$$
¬(p \land q) \lor p
$$

Using De Morgan law:
$$
¬(p \land q) \lor p \equiv (¬p \lor ¬q) \lor p
$$

Using associativity and commutativity:
$$
(¬p \lor ¬q) \lor p \equiv (¬p \lor p) \lor ¬q
$$

Since:
$$
¬p \lor p \equiv \top
$$

we get:
$$
(¬p \lor p) \lor ¬q \equiv \top \lor ¬q
$$

Finally:
$$
\top \lor ¬q \equiv \top
$$

Therefore:
$$
¬(p \land q) \lor p \equiv \top
$$