Mathematics · Ch 1 — Mathematical Logic
Logical Equivalence
Logical Equivalence
Two statement patterns are compared not by how similar they look on paper, but by how they behave under every possible truth assignment. If the truth tables of two patterns come out identical — that is, for every single combination of truth values of their prime components both patterns produce exactly the same final truth value — the two patterns are said to be logically equivalent. When pattern is equivalent to pattern , we write .
Logical equivalence is a genuinely useful idea because it lets us freely replace one statement pattern by another differently-written pattern without altering its logical content in any way — for truth-functional purposes the two are completely interchangeable, even though one may be shorter, clearer, or more convenient to work with than the other. This is precisely the method used to establish standard logic identities (such as the different equivalent ways of writing , or later De Morgan-type laws): write out the truth tables of both sides column by column, and …
Worked out. To show that two statement patterns A and B are equivalent, both are built up column by column inside a single combined truth table — sharing intermediate columns like ~p, ~q, or p ∧ q wherever both patterns need them — and then the final column for A is compared, row by row, against the final column for B. If every one of the 2ⁿ rows shows matching truth values in both final columns, A ≡ B is proved; if even a single row disagrees, the two patterns are not equivalent. This is the single most-used technique in the wo …