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 2ⁿ rows. For CS types, this means that the complexity of the truth-table algorithm is O(2ⁿ), which is pretty bad!)

  The truth-table relations don't capture everything that is captured by the informal notions, so there are logical equivalences 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



• 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 9, 2011. 
Curtis Brown  |  Symbolic Logic   |  Philosophy Department  |   Trinity University
cbrown@trinity.edu