Lesson · Logic and Proof · Propositional logic

Logical Equivalence

Two formulas are equivalent when no assignment separates them. Prove it with a table or with a chain of named laws — De Morgan, distribution, absorption — and refute it with a single row.

Open the interactive lesson Practice

p ≡ q means p ↔ q is a tautology ¬(p ∧ q) ≡ ¬p ∨ ¬q De Morgan ¬(p ∨ q) ≡ ¬p ∧ ¬q De Morgan p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) distribution

Equivalence and three laws

Core ideas

What this lesson establishes

Equivalence is the relation that lets a complicated formula be replaced by a simple one without changing what it claims.

Equivalence means agreement in every row

Not similar structure, not the same variables — the same truth value under every assignment. p → q and ¬p ∨ q look nothing alike and are equivalent.

One row refutes it

To disprove an equivalence you exhibit one assignment where the two differ. That is a complete disproof and needs no further argument.

The laws are shortcuts, not new facts

Every law in this lesson could be verified by a truth table. Their value is that they let you transform a 32-row formula without writing 32 rows.

The material

Equivalence and the laws

The definition first, then the toolkit that follows from it.

Definition · Logical equivalence

Formulas A and B are logically equivalent, written A ≡ B, when they have the same truth value under every assignment — equivalently, when A ↔ B is a tautology.

Note that ≡ is not a connective. A ≡ B is a statement about two formulas, made in ordinary mathematical language; A ↔ B is itself a formula. The two are related exactly as stated in the definition.

The laws worth knowing by name

identity p ∧ T ≡ p p ∨ F ≡ p domination p ∨ T ≡ T p ∧ F ≡ F idempotent p ∧ p ≡ p p ∨ p ≡ p double negation ¬¬p ≡ p commutative p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p associative (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) distributive p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) De Morgan ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q absorption p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p negation p ∨ ¬p ≡ T p ∧ ¬p ≡ F conditional p → q ≡ ¬p ∨ q ¬(p → q) ≡ p ∧ ¬q biconditional p ↔ q ≡ (p → q) ∧ (q → p)

Two of these repay extra attention. De Morgan is how a negation is pushed inward past a connective, and the connective flips as it passes: ∧ becomes ∨ and back. Distribution works in both directions here, unlike in arithmetic where a + (b × c) is not (a + b) × (a + c).

The second distributive law is the one people doubt. Check it: at p = T both sides are T; at p = F the left is q ∧ r and the right is q ∧ r. It holds.

Theorem · Substitution

If A ≡ B, then replacing an occurrence of A inside a larger formula by B produces an equivalent formula. This is what makes chains of rewriting valid.

Example · Simplifying by chain

¬(p → q) ≡ ¬(¬p ∨ q) ≡ ¬¬p ∧ ¬q ≡ p ∧ ¬q. Three steps: conditional law, De Morgan, double negation. The result says what it should — a conditional fails exactly when the hypothesis holds and the conclusion does not.

Interactive

Truth table

Every assignment, evaluated

Prove or refute an equivalence

In compare mode the lab highlights any row that separates the two formulas. No highlighted row means equivalent; one is a complete disproof. Then set A to ~(p & q) and B to ~p & ~q — the error “Logical Connectives” warned about — and read the two rows that separate them.

What to do

Formula A

Or type your own (variables p q r s; either notation)

¬ or ~ not
∧ or & and
∨ or | or
⊕ or ^ xor (exactly one)
→ or -> implies
↔ or <-> iff

Careful: ^ is xor here, not ∧. Type & for and.

Rows—

True in—

Verdict—

Method

Proving an equivalence

Two routes. Choose by the number of variables.

Few variables? Build the table

Up to three variables a table is eight rows and takes a minute. It cannot be wrong and needs no cleverness.

Many variables? Chain the laws

Start from the more complicated side and rewrite toward the simpler one, naming the law used at each step.

Eliminate conditionals first

Rewrite every → as ¬p ∨ q and every ↔ as a conjunction of two conditionals. The remaining laws all speak ∧, ∨, ¬.

To refute, hunt for one row

Try to make one side true and the other false. Setting a variable to make the two sides disagree is usually easier than checking all rows.

Equivalences

Score 0 / 0

Choose the answer you can justify.

Show (p → q) ∧ (p → r) ≡ p → (q ∧ r)

Three variables, so a table would be eight rows. The chain is shorter.

(p → q) ∧ (p → r) ≡ (¬p ∨ q) ∧ (¬p ∨ r) conditional law, twice ≡ ¬p ∨ (q ∧ r) distribution (backwards) ≡ p → (q ∧ r) conditional law

Read the result back into English: promising q and promising r, both on the same condition, is promising q ∧ r on that condition. The chain proves it; the sentence is why it should have been expected.

Common mistakes

Negating both sides of a connective without flipping it¬(p ∧ q) is not ¬p ∧ ¬q. The two differ in two of four rows, and De Morgan exists precisely to record the flip.

Treating ≡ as a connective inside a formulap ≡ q is a claim about two formulas; p ↔ q is a formula. Writing (p ≡ q) ∧ r is a category error.

Checking a few rows and concluding equivalenceAgreement on the rows you looked at is not agreement on all of them. This is the same gap Induction and Recursion spends a whole course closing.

Check your understanding

✓

Finish when you can simplify a four-connective formula by named laws and justify each step.

Take ¬(p ∨ (¬p ∧ q)) and reduce it to ¬p ∧ ¬q, naming De Morgan, distribution and negation as you use them. A step you cannot name is a step you have guessed.

Note: Every law above has a dual, obtained by swapping ∧ with ∨ and T with F. That symmetry is not a coincidence; “Normal Forms and Boolean Algebra” makes it a structural fact about Boolean algebra.