Relations between a number of general concepts and ways to construct precise (but incomplete) analogs using truth tables. The truth-table analogs are more restrictive than their general counterparts. But they have the virtue of being precise, clearly specified, and in fact algorithmic. (On the other hand, although constructing and checking a truth table provides an algorithm for determining tautology, tautological equivalence, and tautological consequence, the algorithm is not very efficient. For n distinct atomic sentences, a truth table requires 2^{n} rows. For CS types, this means that the complexity of the truth-table algorithm is O(2^{n}), which is pretty bad!)
The truth-table relations don't capture everything that is
captured by the informal notions, so there are logical truths that are
not tautologies, logical equivalences that aren't tautological equivalences,
and logical consequences that aren't tautological consequences. However, the
truth-table concepts are nevertheless extremely helpful, because every
tautology is a logical necessity; every tautological equivalence is a
logical equivalence; and every tautological consequence is a logical
consequence. This is the sense in which the truth-table analogs give us a
very precise and clear way of capturing part of the informal concepts.
general logical concept | truth-table analog |
logical necessity
(= logical truth) P is logically necessary iff it is impossible for P to be false |
tautology P is a tautology iff it is true in every row of its truth table |
logical equivalence P and Q are logically equivalent iff it is impossible for it to be the case that one of them is true and the other false |
tautological equivalence P and Q are tautologically equivalent iff there is no row of their joint truth table in which one is true and the other false |
logical consequence C is a logical consequence of P_{1}, P_{2}, . . . P_{n} iff it is impossible for P_{1}, P_{2}, . . . P_{n} to all be true and C to be false |
tautological consequence C is a tautological consequence of P_{1}, P_{2}, . . . P_{n} iff there is no row of their joint truth table in which P_{1}, P_{2}, . . . P_{n} are all true and C is false |
We can also add two further logical concepts that apply to individual sentences. A sentence P is a logical possibility iff it is possible for P to be true. P is a tt-possibility if it is true in at least one row of its truth table. (Every logical possibility is tt-possible, but not vice versa.) And a sentence P is a logical impossibility or logical falsehood iff it is not possible for P to be true. P is a tt-impossibility iff it is false in every row of its truth table. (Every tt-impossibility is logically impossible, but not vice versa.)
In addition to logical necessities and tautologies, our book introduces the idea of a Tarski's World necessity or TW-necessity. This is a sentence which must be true in every Tarski's world. This is a broader category than logical necessity: there are sentences which are true in every Tarski's world even though they are not logically necessary. For instance, in TW every block is a cube, tetrahedron, or dodecahedron. So that is a TW-necessity, but it is not logically necessary, because there are more than three logically possible shapes (for example in the real world we could have spherical or cylindrical blocks).
Name of Equivalence | Meaning |
Associativity | (A
∧ B)
∧ C
⇔ A
∧ (B
∧ C)
⇔ A
∧ B
∧ C (A ∨ B) ∨ C ⇔ A ∨ (B ∨ C) ⇔ A ∨ B ∨ C |
Commutativity | A
∧ B
⇔
B
∧ A A ∨ B ⇔ B ∨ A |
Idempotence | A
∧ A
⇔
A A ∨ A ⇔ A A ∧ B ∧ A ⇔ A ∧ B A ∨ B ∨ A ⇔ A ∨ B |
Distributivity | A
∧ (B
∨
C)
⇔
(A
∧ B)
∨
(A
∧ C) A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C) |
DeMorgan's | ¬(A
∧ B)
⇔
¬A
∨
¬B ¬(A ∨ B) ⇔ ¬A ∧ ¬B |
Double Negation | ¬¬A ⇔ A |
Last update: September
13, 2013.
Curtis Brown | Symbolic Logic | Philosophy Department
| Trinity University
cbrown@trinity.edu