Philosophy 2340
Symbolic Logic

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

Curtis Brown

(Note: symbols will not display correctly unless you have the Lucida Sans Unicode font installed.)

• 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!)
   

  general logical concept	truth-table analog
  logical necessity 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 2.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