# Philosophy 2340 Symbolic Logic

## Barwise and Etchemendy, Language, Proof, and Logic Notes on Chapter 4 (Fun with Truth Tables)

• 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 2n rows. For CS types, this means that the complexity of the truth-table algorithm is O(2n), 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 P1, P2, . . . Pn iff it is impossible for P1, P2, . . . Pn to all be true and C to be false tautological consequence C is a tautological consequence of P1, P2, . . . Pn iff there is no row of their joint truth table in which P1, P2, . . . Pn 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).

• Note: in the above definitions, to say that a sentence P is "true in" a row of its truth table is to say that the column under its major operator has a "T" in that row.
• using Boole to construct truth tables and to test for the ideas above
• relation between logical necessity, tautology, and Tarski's World necessity (homework exercise 4.8 concerns this)
• .
• Logical equivalences: DeMorgan's, Double Negation, associativity, commutativity, idempotence, distribution. Here is a chart detailing these equivalences:

 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

• tautological consequence (Taut Con) in Fitch

Last update: September 13, 2013.
Curtis BrownSymbolic LogicPhilosophy Department | Trinity University
cbrown@trinity.edu