Different Expressions, the Same Truth Conditions
In Truth Tables, we evaluated formulas under every assignment to their proposition letters. The final column told us exactly when each formula was true. We now compare two such columns: can different formulas have exactly the same truth conditions?
For example, \(p\land q\) and \(q\land p\) have different written forms, but both are true exactly when \(p\) and \(q\) are both true. Reversing the order does not change the output on any assignment. Logical equivalence makes this kind of agreement precise.
We continue to use \(p,q,r\) for proposition letters and T and F for truth values. Capital letters such as \(A,B,C\) will stand for formulas, which may themselves contain several connectives.
The Definition of Logical Equivalence
The words every truth assignment are essential. Agreement on one row, or even on all but one row, does not establish logical equivalence. The formulas must be true on precisely the same rows and false on precisely the same rows.
The formulas need not contain the same letters. To compare \(p\) with \(p\land(q\lor\neg q)\), we use assignments to both \(p\) and \(q\). By the Law of Excluded Middle, \(q\lor\neg q\) is always true. Conjoining it with \(p\) therefore leaves the truth value of \(p\) unchanged. Hence
In a common table, the column for \(p\) simply repeats its value for each choice of \(q\). A letter absent from a formula has no effect on that formula's output.
Comparing Two Formulas Systematically
A letter appearing on only one side must still be included among the inputs.
For \(n\) distinct letters, include all \(2^n\) rows, as established in the previous tutorial.
Compute intermediate expressions first and keep the two final columns clearly labeled.
Complete agreement proves equivalence. Any differing row disproves it.
Worked Example: Double Negation
The Double Negation Law states that \(\neg\neg p\equiv p\). There is only one proposition letter, so two rows suffice to prove it.
| \(p\) | \(\neg p\) | \(\neg\neg p\) |
|---|---|---|
| T | F | T |
| F | T | F |
In both possible assignments, the first and last columns agree. Thus negating twice returns the original truth value. The middle column differs from \(p\) on both rows, so \(\neg p\) is not equivalent to \(p\).
To disprove equivalence, a complete table is unnecessary if we can already exhibit a differing assignment. Such an assignment is a counterexample to the proposed equivalence.
Worked Example: A Single Row Is Enough to Disprove
Are \(p\lor q\) and \(p\land q\) equivalent? Set \(p=\mathrm{T}\) and \(q=\mathrm{F}\). Then
The outputs differ, so the formulas are not logically equivalent. Their agreement when both letters are true, or when both are false, cannot repair this failure.
Even the same number of T entries is insufficient. The formulas \(p\) and \(q\), evaluated on the four assignments to \(p,q\), each have two T entries. They nevertheless differ when \(p=\mathrm{T}\), \(q=\mathrm{F}\). Equivalence concerns the location of the entries, not just their counts.
Equivalence and the Biconditional
The connective \(\leftrightarrow\), introduced in Logical Connectives, produces a formula that is true when its two inputs agree. The notation \(\equiv\) makes a claim about agreement across all assignments. These are closely related, but they serve different roles.
| Notation | What it expresses |
|---|---|
| \(A\leftrightarrow B\) | A formula whose value on a given assignment is T exactly when \(A\) and \(B\) agree on that assignment. |
| \(A\equiv B\) | The assertion that \(A\) and \(B\) agree on every assignment. |
Proof. First suppose \(A\equiv B\). On any assignment to the letters in either formula, \(A\) and \(B\) have the same truth value. By the definition of the biconditional, \(A\leftrightarrow B\) is true on that assignment. Since the assignment was arbitrary, the biconditional is a tautology.
Conversely, suppose \(A\leftrightarrow B\) is a tautology. It is then true on every assignment. The biconditional is true only when its two inputs agree, so \(A\) and \(B\) agree on every assignment. This is exactly \(A\equiv B\).
Thus \(p\leftrightarrow q\) can be true on a particular row without \(p\equiv q\). By contrast, \(p\leftrightarrow\neg\neg p\) is a tautology, because the Double Negation Law guarantees agreement on every row.
De Morgan's Laws
Negating a compound statement is a frequent source of mistakes. The negation applies to the whole statement, so we must determine exactly when that whole statement fails.
Proof by truth tables. For the first law, compute the conjunction and its negation, and compare that negation with the disjunction of the individual negations.
| \(p\) | \(q\) | \(p\land q\) | \(\neg(p\land q)\) | \(\neg p\lor\neg q\) |
|---|---|---|---|---|
| T | T | T | F | F |
| T | F | F | T | T |
| F | T | F | T | T |
| F | F | F | T | T |
For the second law, compare the negation of the disjunction with the conjunction of the negations.
| \(p\) | \(q\) | \(p\lor q\) | \(\neg(p\lor q)\) | \(\neg p\land\neg q\) |
|---|---|---|---|---|
| T | T | T | F | F |
| T | F | T | F | F |
| F | T | T | F | F |
| F | F | F | T | T |
In each table the last two columns agree on all four assignments. These exhaust the possibilities for \(p,q\), proving both equivalences.
The first law says that a conjunction fails when at least one component fails; both may fail. The second says that an inclusive disjunction fails only when both components fail.
Worked Example: Negating Two Requirements
At a specified real input \(x\), let \(p\) mean “\(x>0\)” and \(q\) mean “\(x<1\).” The statement “\(x>0\) and \(x<1\)” is \(p\land q\). Its negation is equivalent to
De Morgan's first law supplies the “or”; the usual order comparisons identify the negations of the individual inequalities. At \(x=0\), the original conjunction is false and the displayed statement is true. At \(x=1\), the same is true. At \(x=1/2\), the original conjunction is true and its negation is false.
Replacing “or” by “and” would be incorrect. For example, at \(x=2\), the original conjunction fails, but “\(x\leq0\) and \(x\geq1\)” is false. That single input exposes the error.
Using Equivalences Inside Larger Formulas
An equivalence law is not limited to single-letter inputs. For example, De Morgan's first law remains valid when \(p\) is replaced consistently by a formula \(A\) and \(q\) by a formula \(B\).
To justify this, fix any assignment to all the letters in \(A\) and \(B\). Each formula has one definite truth value, so their pair of values selects one row of the law's truth table. The two outputs agree on that row. Since this holds for every assignment, \(\neg(A\land B)\equiv\neg A\lor\neg B\). The argument does not require \(A\) and \(B\) to have different letters or independent truth values.
Proof. Fix any assignment to all letters in the original and resulting formulas. The replaced expression has the same truth value before and after replacement, because \(A\equiv B\). At the connective immediately surrounding that expression, all input values therefore remain unchanged. By the connective's truth table, its output remains unchanged.
Continue outward through the finitely many surrounding connectives. At each stage the changed expression supplies the same value, while the other inputs have not changed. The value of the whole formula is therefore unchanged. If the replaced occurrence is the entire formula, agreement follows directly from \(A\equiv B\). Thus the original and resulting formulas agree under every assignment.
We may also chain equivalences. If \(A\equiv B\) and \(B\equiv C\), then on every assignment the value of \(A\) equals that of \(B\), which equals that of \(C\). Hence \(A\equiv C\). Equivalence can be used in either direction, since agreement of truth values is symmetric.
Worked Example: A Chain of Rewrites
Simplify \(\neg(\neg p\lor\neg q)\lor p\). First apply De Morgan's second law to the left part, and then use double negation:
Both steps are valid inside the larger disjunction by replacement of equivalent formulas. The remaining formula is equivalent to \(p\), an instance of an Absorption Law. We can verify this final step directly.
If \(p\) is true, \((p\land q)\lor p\) is true because its right input is true, regardless of \(q\). If \(p\) is false, \(p\land q\) is false, and both inputs to the outer disjunction are false. The whole expression is then false. These two cases exhaust all assignments and show that
Chaining the steps gives \(\neg(\neg p\lor\neg q)\lor p\equiv p\). The original expression mentions \(q\), but its final truth value does not depend on \(q\).
Logical Equivalence and Mathematical Interpretation
Logical equivalence gives a guarantee before any particular propositions are substituted. No matter which definite propositions replace the letters, equivalent formulas have the same truth value.
Agreement arising from a particular mathematical interpretation is different. At each specified real input \(x\), let \(p\) mean “\(x>2\)” and \(q\) mean “\(x>0\).” The statements represented by \(p\land q\) and \(p\) agree for every real \(x\): when \(x>2\), both inequalities hold, and when \(x\) is not greater than \(2\), both \(p\) and the conjunction are false.
Nevertheless, the unrestricted formulas \(p\land q\) and \(p\) are not logically equivalent. The abstract assignment \(p=\mathrm{T}\), \(q=\mathrm{F}\) makes their outputs differ. No real \(x\) realizes that assignment under this interpretation, as discussed in the previous tutorial.
This distinction matters when rewriting arguments. A proved logical equivalence can be used without further assumptions about its components. A rewrite that relies on an inequality, a domain restriction, or another mathematical fact must retain that justification.
Check Your Understanding
For each claimed equivalence, justify agreement on every assignment. For each failure, give an explicit differing assignment.
- Construct a common truth table for \(p\lor q\) and \(q\lor p\). Are they logically equivalent? Is \((p\lor q)\leftrightarrow(q\lor p)\) a tautology?
- Compare \(p\lor(q\land\neg q)\) with \(p\). Which letters must a complete comparison table include? Explain why the formulas are equivalent using the contradiction established in the previous tutorial.
- A learner claims \(\neg(p\land q)\equiv\neg p\land\neg q\). Give a counterexample assignment, and state the correct equivalence.
- Simplify \(\neg(\neg p\land q)\) using De Morgan's Laws and double negation. Name the justification for each step.
- Suppose \(A\equiv B\). Explain why \(\neg(A\lor r)\equiv\neg(B\lor r)\). Does the conclusion require either \(A\) or \(B\) to be a tautology?
- At specified real inputs, let \(p\) mean “\(x>5\)” and \(q\) mean “\(x>1\).” Explain why \(p\lor q\) and \(q\) agree for every real \(x\), but are not logically equivalent as unrestricted formulas in \(p,q\).