Logical Equivalence & Laws
Two statement forms are logically equivalent (\(\equiv\)) if they have the same truth value for every combination of truth values of their variables — shown via a truth table, or by chaining the laws below. To show two forms are not equivalent (\(\not\equiv\)), exhibit one combination of truth values where they differ.
\(\equiv\) compares statements (like \(=\) compares numbers); it’s not a connective itself. The connective that combines two statements into one is the biconditional \(\leftrightarrow\) — see conditional-statements.
Tautologies and contradictions
A tautology \(\mathbf{t}\) is a statement that is always true. A contradiction \(\mathbf{c}\) is a statement that is always false.
Both are written in bold upright lower case on the formula sheet, and both appear as values inside the laws — \(p \lor \sim p \equiv \mathbf{t}\) produces one, \(p \land \mathbf{t} \equiv p\) consumes one. A chain of laws that reaches \(\mathbf{t}\) or \(\mathbf{c}\) has proved the original form is always true or always false, which is usually the point of the exercise.
Laws of logical equivalence
Provided in the exam. These laws are printed on the MATH1061/MATH7861 Examination Formula Page, so they don’t need memorising. What the exercises ask for is choosing and applying them, and naming the one used at each step. The same page also carries the valid-argument-forms and the set identities of proving-set-properties.
Given statement variables \(p, q, r\), a tautology \(\mathbf{t}\), and a contradiction \(\mathbf{c}\):
| Law | Form 1 | Form 2 |
|---|---|---|
| Commutative | \(p \land q \equiv q \land p\) | \(p \lor q \equiv q \lor p\) |
| Associative | \((p \land q) \land r \equiv p \land (q \land r)\) | \((p \lor q) \lor r \equiv p \lor (q \lor r)\) |
| Distributive | \(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)\) |
| Identity | \(p \land \mathbf{t} \equiv p\) | \(p \lor \mathbf{c} \equiv p\) |
| Negation | \(p \lor \sim p \equiv \mathbf{t}\) | \(p \land \sim p \equiv \mathbf{c}\) |
| Double negative | \(\sim(\sim p) \equiv p\) | |
| Idempotent | \(p \land p \equiv p\) | \(p \lor p \equiv p\) |
| Universal bound | \(p \lor \mathbf{t} \equiv \mathbf{t}\) | \(p \land \mathbf{c} \equiv \mathbf{c}\) |
| De Morgan’s | \(\sim(p \land q) \equiv \sim p \lor \sim q\) | \(\sim(p \lor q) \equiv \sim p \land \sim q\) |
| Absorption | \(p \lor (p \land q) \equiv p\) | \(p \land (p \lor q) \equiv p\) |
| Negations of \(\mathbf{t}\)/\(\mathbf{c}\) | \(\sim \mathbf{t} \equiv \mathbf{c}\) | \(\sim \mathbf{c} \equiv \mathbf{t}\) |
De Morgan’s Laws are especially important for negating “and”/“or” statements — e.g. the negation of “5 is divisible by 2 and 6 is divisible by 2” is “5 is not divisible by 2 or 6 is not divisible by 2”. Note what changes: the connective flips from and to or, and both halves get negated. Negating only one half, or leaving the connective alone, is the standard error.
How to write a law chain
The layout expected in your own work:
- the first line is the starting expression, on its own;
- every later line begins with \(\equiv\), vertically aligned down the page;
- the name of the law used to get there sits in its own right-hand column on that line.
Two or more laws may be cited on one line if they act on the same step (e.g. “by De Morgan’s law and the double negative law”). Name a law on every line that changes the expression. The one kind of line that goes unnamed is a pure re-labelling that asserts nothing new, like the “where \(r = (p \,\land\sim q)\)” line in the first worked example below.
Treat a compound expression as a single letter
The laws are stated for variables \(p, q, r\), but they hold with any statement form substituted in. Spotting that turns a long expression into a short one:
\[(p \,\land\sim q) \;\land\; \sim(p \,\land\sim q)\]
is \(r \,\land\sim r\) with \(r = (p \,\land\sim q)\), so the negation law applies directly and it is \(\mathbf{c}\). This is exactly the move in the first worked example below.
Worked: reaching a contradiction
Show that \((p \,\land\sim q) \land (\sim p \lor q) \equiv \mathbf{c}\).
\[ \begin{aligned} (p \,\land\sim q) \land (\sim p \lor q) &\equiv (p \,\land\sim q) \;\land\; \sim(p \,\land\sim q) && \text{by De Morgan's law and the double negative law} \\ &\equiv r \,\land\sim r \quad \text{where } r = (p \,\land\sim q) \\ &\equiv \mathbf{c} && \text{by the negation law} \end{aligned} \]
The whole proof is the first line: recognising that \(\sim p \lor q\) is \(\sim(p \,\land\sim q)\) in disguise. Read De Morgan’s backwards — \(\sim p \lor q \equiv \sim p \,\lor\sim(\sim q) \equiv \sim(p \,\land\sim q)\) — and the two conjuncts are a statement and its own negation.
Worked: absorbing a conjunction
Show that \(\sim p \lor (p \land q) \equiv \sim p \lor q\).
\[ \begin{aligned} \sim p \lor (p \land q) &\equiv (\sim p \lor p) \land (\sim p \lor q) && \text{by the distributive law} \\ &\equiv \mathbf{t} \land (\sim p \lor q) && \text{by the negation law} \\ &\equiv \sim p \lor q && \text{by the identity law} \end{aligned} \]
The pattern distribute, collapse the tautology or contradiction, drop it with the identity law is the most common three-step shape in this topic, and it recurs in both routes below.
Worked: two routes to the same answer
Show that \(\sim\big((\sim p \land q) \lor (\sim p \,\land\sim q)\big) \equiv p\).
There is no unique chain. Here are two, and both are complete proofs:
Figure 1: The same equivalence proved two ways. Starting from the same expression and ending at the same p, the left route pushes the negation inward with De Morgan’s first and takes six steps; the right route factors out the common ~p with the distributive law first and takes four. Every edge names the law that licenses it — that naming is what the chain is for.
Neither route is “the” answer, and nothing turns on finding the short one. What matters is that every line follows from the one above by a named law. The shorter route is found by looking for a common factor before doing anything else: both disjuncts inside the brackets contain \(\sim p\), so the distributive law pulls it out and the rest collapses.
The same equivalence can also be established with a truth table — see the worked table in 2026-07-30-logical-form-and-equivalence, where the column for \(\sim\big((\sim p \land q) \lor (\sim p \,\land\sim q)\big)\) comes out identical to the column for \(p\).
Showing two forms are not equivalent
To show \(\not\equiv\) you do not need a full truth table. Find one assignment of truth values on which the two forms disagree, and say what each evaluates to.
Worked. Show that \(\sim(p \lor q) \;\not\equiv\; \sim p \lor \sim q\).
Take \(p\) false and \(q\) true. Then
- LHS: \(p \lor q\) is \(\mathrm{F} \lor \mathrm{T} = \mathrm{T}\), so \(\sim(p \lor q)\) is false.
- RHS: \(\sim p \,\lor\sim q\) is \(\mathrm{T} \lor \mathrm{F} = \mathrm{T}\), so it is true.
One row on which they differ is a complete disproof, so the two forms are not logically equivalent.
The correct partner for \(\sim(p \lor q)\) is of course \(\sim p \,\land\sim q\) — this is precisely the De Morgan trap of changing the sign but not the connective.
See also
- logical-connectives
- conditional-statements
- formula-sheet — what else is provided in the exam, and what is not
- proving-set-properties — the same eleven laws as set identities, and the two set-equality proof methods built on them
- 2026-07-30-logical-form-and-equivalence — Lecture 2, where these laws were introduced and applied
- practice-problems — §2 Logical Equivalence, with full worked solutions