Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Prove an Equivalence with the Laws of Logic

Start from one side and rewrite it, one named law per line, until it becomes the other side. Every law is an equivalence, so each line has the same truth table as the one before.

Recognize the task

The question says "prove using the laws of logic", "without a truth table", or "show algebraically": (P→Q)∧(P→¬Q)≡¬P(P \to Q) \land (P \to \neg Q) \equiv \neg P, P→(Q→R)≡(P∧Q)→RP \to (Q \to R) \equiv (P \land Q) \to R. The laws are the better tool with four or more letters, where a table needs 16 rows or more. Test: one side looks more complicated than the other; start there.
The laws are collected in the propositional logic laws reference and explained on the equivalences lesson.

Ways to do it

Rewrite one side into the otherusual
A≡A1≡A2≡⋯≡BA \equiv A_1 \equiv A_2 \equiv \cdots \equiv B
Work on the more complex side only and name a law on every line.
Meet in the middleboth sides
A≡CandB≡CA \equiv C \quad \text{and} \quad B \equiv C
Rewrite both sides into the same simple form, for example by converting to CNF.
Truth tablecheck
A and B agree in all 2n rowsA \text{ and } B \text{ agree in all } 2^n \text{ rows}
Fine for up to three letters; see proving equivalence with a truth table.

Steps

StepOn (P→Q)∧(P→¬Q)≡¬P(P \to Q) \land (P \to \neg Q) \equiv \neg P
1Start from the more complex side. Copy it as the first line. The simpler side is the target.(P→Q)∧(P→¬Q)(P \to Q) \land (P \to \neg Q)
2Rewrite every arrow. Use material implication for →\to and the biconditional as two conditionals for ↔\leftrightarrow.Material implication ↗(¬P∨Q)∧(¬P∨¬Q)(\neg P \lor Q) \land (\neg P \lor \neg Q)
3Push negations onto single letters. Use De Morgan's laws for a negated bracket and the double negation law for ¬¬\neg\neg. Here every ¬\neg already sits on a letter.no change: (¬P∨Q)∧(¬P∨¬Q)(\neg P \lor Q) \land (\neg P \lor \neg Q)
4Factor or expand with a distributive law. Both brackets share ¬P∨\neg P \lor, so the distributive law of or over and, read right to left, pulls it out.Distributive laws ↗¬P∨(Q∧¬Q)\neg P \lor (Q \land \neg Q)
5Collapse complements and constants. Q∧¬Q≡⊥Q \land \neg Q \equiv \bot by the law of non-contradiction, then ¬P∨⊥≡¬P\neg P \lor \bot \equiv \neg P by the identity law. Stop when you reach the target.¬P∨⊥≡¬P\neg P \lor \bot \equiv \neg P

Worked examples

Example 1 · De Morgan then double negation

2 laws
¬(P∨¬Q)\neg(P \lor \neg Q)
start
≡¬P∧¬¬Q\equiv \neg P \land \neg\neg Q
De Morgan: ∨\lor becomes ∧\land
≡¬P∧Q\equiv \neg P \land Q
double negation

Example 2 · exportation

arrows
P→(Q→R)≡¬P∨(¬Q∨R)P \to (Q \to R) \equiv \neg P \lor (\neg Q \lor R)
material implication twice
≡(¬P∨¬Q)∨R\equiv (\neg P \lor \neg Q) \lor R
associative law
≡¬(P∧Q)∨R\equiv \neg(P \land Q) \lor R
De Morgan, read backward
≡(P∧Q)→R\equiv (P \land Q) \to R
material implication, read backward

Example 3 · a negated arrow

factor
¬(P→Q)∨(P∧Q)\neg(P \to Q) \lor (P \land Q)
start
≡(P∧¬Q)∨(P∧Q)\equiv (P \land \neg Q) \lor (P \land Q)
negation of a conditional
≡P∧(¬Q∨Q)\equiv P \land (\neg Q \lor Q)
factor out PP
≡P∧⊤≡P\equiv P \land \top \equiv P
excluded middle, then identity
Check each line against the one before in the equivalence validator.

See it happen

Each law is a pair of formulas with identical truth tables, checked once and for all. Replacing a part of a formula by an equivalent part cannot change any row of the whole table, so every line of the chain has the same table as the first. The chain proves that the two ends agree in all 2n2^n rows without writing out a single row.

Common mistakes

Keeping the connective in De Morgan's law

✗ ¬(P∧Q)≡¬P∧¬Q\neg(P \land Q) \equiv \neg P \land \neg Q
✓ ¬(P∧Q)≡¬P∨¬Q\neg(P \land Q) \equiv \neg P \lor \neg Q: the connective flips

Negating an arrow part by part

✗ ¬(P→Q)≡¬P→¬Q\neg(P \to Q) \equiv \neg P \to \neg Q
✓ ¬(P→Q)≡P∧¬Q\neg(P \to Q) \equiv P \land \neg Q

Distributing to only one part

✗ P∧(Q∨R)≡(P∧Q)∨RP \land (Q \lor R) \equiv (P \land Q) \lor R
✓ P∧(Q∨R)≡(P∧Q)∨(P∧R)P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)

Using a one-way rule as a law

✗ (P∧Q)→P(P \land Q) \to P holds, so replace P∧QP \land Q by PP
✓ only equivalences may replace a part; P∧QP \land Q and PP differ at P=TP = T, Q=FQ = F