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:

for every valuation $v$.

In this case we write:

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:

and:

are logically equivalent.

Their truth table is:

The last two columns agree in every row, and therefore:

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:

is valid.

Proof

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

By the truth rule for the biconditional:

if and only if:

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:

Idempotence:

Commutativity:

Associativity:

Distributivity:

De Morgan laws:

Absorption:

Implication:

Biconditional:

Another useful form of the biconditional is:

Truth Constants

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

We write:

for a formula that is always true, and:

for a formula that is always false.

These constants satisfy the following laws:

Negation exchanges truth and falsehood:

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

and:

Example 1.20 (Rewriting a Formula)

Consider the formula:

Using the implication law:

we obtain:

Using De Morgan law:

Using double negation:

Therefore:

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:

for every valuation $v$.

A formula $A$ is a contradiction if:

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:

is a tautology, because every valuation makes either $p$ true or $¬p$ true.

The formula:

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

The formula:

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:

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:

and:

so by transitivity of equality:

for every valuation $v$, and therefore $A \equiv C$.

Lemma 1.24 (Substitution of Equivalents)

Suppose that:

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

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:

and:

so the result follows from the assumption $A \equiv B$.

If the context has the form:

then by the induction hypothesis:

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:

If the context has the form:

then by the induction hypothesis:

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:

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:

Using De Morgan law:

Using associativity and commutativity:

Since:

we get:

Finally:

Therefore: