Logical equivalence

Logical equivalence is about when two logical statements always have the same truth value, no matter what truth values their parts take.

In this chapter we will:

• Define what it means for statements to be logically equivalent.
• Show how to test logical equivalence using truth tables.
• Introduce common logical equivalences (sometimes called laws or identities).
• Practice rewriting statements using logical equivalence.

You should already be familiar with basic logical operators and truth tables from earlier chapters on logic; here we use them rather than reintroduce them.

What logical equivalence means

Suppose $P$ and $Q$ are two statements built from simpler statements using logical operators (such as $\lnot$, $\land$, $\lor$, $\Rightarrow$, $\Leftrightarrow$).

We say $P$ and $Q$ are logically equivalent if, for every possible assignment of truth values to their basic parts, $P$ and $Q$ have the same truth value (both true or both false).

We write this as:
$$
P \equiv Q
$$
or sometimes
$$
P \Leftrightarrow Q \text{ is a tautology.}
$$

Here, $P \Leftrightarrow Q$ is itself a compound statement. Saying it is a tautology means it is always true, for all possible truth values of the basic statements inside $P$ and $Q$.

Logical equivalence is about form, not about the specific meaning of the words. It tells us that two different-looking formulas behave the same way in all logical situations.

Using truth tables to test logical equivalence

One way to decide whether $P$ and $Q$ are logically equivalent is to build a truth table that:

1. Lists all possible combinations of truth values of the basic statements (such as $p$, $q$, $r$, …).
2. Computes the truth value of $P$ for each combination.
3. Computes the truth value of $Q$ for each combination.
4. Compares the resulting columns for $P$ and $Q$.

If the columns are identical (T and F in exactly the same rows), then
$$
P \equiv Q.
$$

Example: Show that $\lnot(p \land q)$ is logically equivalent to $\lnot p \lor \lnot q$.

We build the table:

• Basic statements: $p$, $q$.
• All combinations: TT, TF, FT, FF.

Now compute each compound expression.

$$
\begin{array}{c|c||c|c|c}
p & q & p \land q & \lnot(p \land q) & \lnot p \lor \lnot q \\
\hline
T & T & T & F & F \\
T & F & F & T & T \\
F & T & F & T & T \\
F & F & F & T & T \\
\end{array}
$$

The last two columns, for $\lnot(p \land q)$ and $\lnot p \lor \lnot q$, are identical:

• Both are false only when $p$ and $q$ are both true.
• Both are true in all other cases.

Therefore:
$$
\lnot(p \land q) \equiv \lnot p \lor \lnot q.
$$

This method is systematic and always works for a small number of variables, but the table gets very large as you add more variables (there are $2^n$ rows for $n$ variables).

Logical equivalences as rewrite rules

Logical equivalence allows us to rewrite statements without changing their truth behavior. If
$$
P \equiv Q,
$$
then in any argument or expression, you can replace $P$ by $Q$ or $Q$ by $P$ without changing whether the whole thing is true.

This idea is used:

• In simplifying logical expressions.
• In transforming statements into standard forms.
• In mathematical proofs, to move from a complicated statement to an equivalent but simpler one.
• In computer science, to optimize logical conditions in code or circuits.

You can think of logical equivalences like algebraic identities, such as $a(b + c) = ab + ac$; they let you transform one expression into another that is “the same” in behavior.

Common logical equivalences

Here are some of the most frequently used equivalences. You should not try to memorize all of them at once, but get familiar with the patterns and use them when rewriting statements.

Throughout, $p$, $q$, and $r$ are arbitrary statements.

Identity laws

These express how $\land$ and $\lor$ interact with the constants “true” and “false” (denoted by $T$ and $F$):

• $p \land T \equiv p$
• $p \lor F \equiv p$

Intuitively:

• “$p$ and true” behaves just like $p$.
• “$p$ or false” behaves just like $p$.

Domination laws

These say that certain constants dominate the expression:

• $p \land F \equiv F$
• $p \lor T \equiv T$

For example, “$p$ and false” is always false; “$p$ or true” is always true.

Idempotent laws

Repeating the same statement with $\land$ or $\lor$ does not change it:

• $p \land p \equiv p$
• $p \lor p \equiv p$

For instance, “$p$ and $p$” is no stronger than just “$p$”.

Double negation

Negating twice returns you to where you started:

• $\lnot(\lnot p) \equiv p$

Commutative laws

The order of $p$ and $q$ does not matter for $\land$ and $\lor$:

• $p \land q \equiv q \land p$
• $p \lor q \equiv q \lor p$

Associative laws

Grouping (parentheses) does not matter for repeating the same operator:

• $(p \land q) \land r \equiv p \land (q \land r)$
• $(p \lor q) \lor r \equiv p \lor (q \lor r)$

So we can write $p \land q \land r$ or $p \lor q \lor r$ without worrying about how they are grouped.

Distributive laws

These show how $\land$ and $\lor$ distribute over each other:

• $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
• $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

These are directly analogous to algebraic distribution, but with logical operators.

De Morgan’s laws

These relate negation to $\land$ and $\lor$:

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

You can remember them as:

• Negation of “and” becomes “or” of negations.
• Negation of “or” becomes “and” of negations.

Absorption laws

These show that some parts of an expression “absorb” others:

• $p \land (p \lor q) \equiv p$
• $p \lor (p \land q) \equiv p$

For example, the statement “$p$ and ($p$ or $q$)” is no stronger than just “$p$”.

Negation laws

These are simples relationships with $T$ and $F$:

• $p \lor \lnot p \equiv T$ (law of excluded middle)
• $p \land \lnot p \equiv F$ (contradiction)

These say that “$p$ or not $p$” is always true, while “$p$ and not $p$” is always false.

Equivalences involving implication

Logical implication ($\Rightarrow$) is especially important in proofs. It can be rewritten using the basic operators $\lnot$, $\land$, and $\lor$.

Implication as “or”

The key equivalence is:
$$
p \Rightarrow q \equiv \lnot p \lor q.
$$

This tells us that:

• “If $p$, then $q$” behaves like “either not $p$, or $q$”.

This is not about informal everyday language, but about the precise logical behavior of the formal operator $\Rightarrow$.

This equivalence is used to:

• Eliminate $\Rightarrow$ from logical expressions.
• Show that some apparently different statements are actually the same in logical form.

Contrapositive

The contrapositive of $p \Rightarrow q$ is $\lnot q \Rightarrow \lnot p$.

We have the equivalence:
$$
p \Rightarrow q \equiv \lnot q \Rightarrow \lnot p.
$$

That is, “if $p$ then $q$” is logically equivalent to “if not $q$ then not $p$”.

This is important in proofs: proving the contrapositive of an implication is just as good as proving the original implication, because they are logically equivalent.

Converse and inverse (not equivalences in general)

For comparison:

• The converse of $p \Rightarrow q$ is $q \Rightarrow p$.
• The inverse of $p \Rightarrow q$ is $\lnot p \Rightarrow \lnot q$.

In general, these are not logically equivalent to $p \Rightarrow q$:

• $p \Rightarrow q \not\equiv q \Rightarrow p$ (not equivalent)
• $p \Rightarrow q \not\equiv \lnot p \Rightarrow \lnot q$ (not equivalent)

So only the contrapositive is guaranteed to be equivalent.

Biconditional

The biconditional $p \Leftrightarrow q$ can be rewritten in two useful ways:

• As a conjunction of implications:
  $$
  p \Leftrightarrow q \equiv (p \Rightarrow q) \land (q \Rightarrow p).
  $$
• Using $\land$, $\lor$, and $\lnot$ only:
  $$
  p \Leftrightarrow q \equiv (p \land q) \lor (\lnot p \land \lnot q).
  $$

Both expressions say that $p$ and $q$ have the same truth value: both true or both false.

Using logical equivalence to simplify expressions

Logical equivalence lets us simplify a complex logical expression step by step, using the equivalence laws as rewrite rules.

Example: Simplify $p \land (q \lor (p \land \lnot q))$.

We want an equivalent expression in a simpler form.

Step 1: Use distributive law on $q \lor (p \land \lnot q)$:
$$
q \lor (p \land \lnot q) \equiv (q \lor p) \land (q \lor \lnot q).
$$

Step 2: Use excluded middle on $(q \lor \lnot q)$:
$$
q \lor \lnot q \equiv T.
$$

So:
$$
(q \lor p) \land (q \lor \lnot q) \equiv (q \lor p) \land T.
$$

Step 3: Use identity law:
$$
(q \lor p) \land T \equiv q \lor p.
$$

Thus:
$$
q \lor (p \land \lnot q) \equiv q \lor p.
$$

Step 4: Go back to the whole expression:
$$
p \land (q \lor (p \land \lnot q)) \equiv p \land (q \lor p).
$$

Step 5: Use commutative law ($q \lor p \equiv p \lor q$) if desired:
$$
p \land (p \lor q).
$$

Step 6: Use absorption:
$$
p \land (p \lor q) \equiv p.
$$

So we have shown:
$$
p \land (q \lor (p \land \lnot q)) \equiv p.
$$

This kind of step-by-step rewriting is a common way to show equivalence without building a full truth table.

Showing equivalence: truth tables vs. algebraic laws

There are two main techniques to show that two statements $P$ and $Q$ are logically equivalent:

1. By truth tables
• Build the full truth table for $P$ and $Q$.
• If the final columns are identical, then $P \equiv Q$.

This is direct and mechanical, especially for a small number of variables.

2. By a chain of equivalences
• Start with $P$.
• Apply known equivalence laws to rewrite step by step.
• End with $Q$.

Each step must use a valid equivalence in both directions.
You then write a sequence such as:
$$
P \equiv E_1 \equiv E_2 \equiv \dots \equiv Q.
$$

Since each step preserves equivalence, $P \equiv Q$.

In more advanced contexts, the second method is preferred, because it scales better and gives insight into structure, but truth tables remain a reliable basic tool.

Logical equivalence and proof strategy

Logical equivalence is widely used in proofs and reasoning. A few common uses:

• Rewriting conditions

If you want to prove a statement of the form $p \Rightarrow q$, you can rewrite the condition $p$ or the conclusion $q$ into equivalent but more convenient forms. For example, using the equivalence
$$
p \Rightarrow q \equiv \lnot p \lor q,
$$
or using De Morgan’s laws to rewrite negations of conjunctions or disjunctions.

• Proving equivalences

To prove a statement of the form “$P$ is equivalent to $Q$”, you can either:

• Prove $P \Rightarrow Q$ and $Q \Rightarrow P$ separately, or
• Transform $P$ into $Q$ step by step using equivalence laws.

• Standard forms

Many areas of discrete mathematics and computer science use special standard forms such as:

• Conjunctive normal form (CNF): a conjunction of disjunctions.
• Disjunctive normal form (DNF): a disjunction of conjunctions.

Transforming a formula into such a form uses logical equivalences systematically.

You do not need all these applications now, but it is helpful to see that logical equivalence is a central tool for manipulating and understanding logical statements.

Practice ideas

To become comfortable with logical equivalence, you can practice:

• Using truth tables to check whether two formulas are equivalent.
• Proving common equivalences (such as De Morgan’s laws) by constructing their truth tables.
• Simplifying given logical expressions using the laws listed above.
• Rewriting implications and biconditionals using $\lnot$, $\land$, and $\lor$ only.
• Showing that a given expression is a tautology by simplifying it to $T$ using equivalences.

Through repeated use, the main equivalences will become familiar, and you will be able to recognize when two different-looking logical expressions actually say the same thing.