Predicate Logic, a Sketch

Contents
Predicate Logic
  • Deductive Logic is the formal theory of deductive reasoning.
  • Developed in 1879 by Gotlob Frege, the founder of modern formal logic, Predicate Logic is the foundation of Deductive Logic.
  • Predicate Logic consists of:
    • a symbolic language
    • rules of inference
    • a semantics.
How it Works
  • To determine whether the following argument-form is valid:
    • All F’s are H’s.
    • All G’s are non-H’s.
    • Therefore, nothing is both an F and a G.
  • First, translate the argument-form into the language of Predicate Logic
    • (x)(Fx Hx)
      • Every F is and H
    • (x)(Gx ~Hx)
      • Every G is a non-H
    • Therefore, ~(Ex)(Fx & Gx)
      • Nothing is both an F and a G
  • Then, either
    • prove the translated argument-form valid by deriving the conclusion from the premises using the rules of inference of Predicate Logic
      • or
    • show the argument-form invalid by putting forth a counterexample.
Translations into Predicate Logic
  • Black swans exist. (B: x is black, S: x is a swan)
    • (Ex)(Bx & Sx)
      • There exists an x such that x is B and x is S
  • An oral contract isn’t worth the paper it is written on. (C: x is a contract, O: x is oral, W: x is worth the paper it is written on)
    • (x)( (Ox & Cx)   ~Wx)
      • For any x, if x is O and x is C then x isn’t W
  • Nothing easy is worthwhile. (E: x is easy, W: x is worthwhile)
    • ~(Ex)(Ex & Wx)
      • It’s not the case that there exists an x such that x is E and x is W
  • Opposites attract. (O: x and y are opposites, A: x and y attract)
    • (x)(y)(Oxy Axy)
      • For any x and y if x and y are opposites then x and y attract.
  • There is a guard on duty at all times (though not necessarily the same guard). (G: x is a guard, T: x is a time, D: x is on duty at y)
    • (x)(Tx (Ey)(Gy & Dyx))
      • For any x, if x is a time then there’s a y such that y is a guard and y is on duty at x.
  • The same guard is on duty at all times (poor guy) (G: x is a guard, T: x is a time, D: x is on duty at y)
    • (Ey) (Gy & (x)(Tx Dyx))
      • There exists a y such that y is a guard and for any x if x is a time then y is on duty at x)
  • No two people have the same fingerprints. (Domain: people, F: x has the same fingerprints as y, S: x is the same person as y))
    • ~(Ex)(Ey)(Fxy & ~Sxy)
      • There’s no x and y such that x and y have the same fingerprints and x is not the same person as y
Proof that the Astral Twin Argument against Astrology is Valid
  • Astral Twin Argument against Astrology
    • People born within minutes of each other in the same hospital have the same astrological chart.  
    • But some people born within minutes of each other in the same hospital don’t have the same personality traits. 
    • Therefore, not everyone with the same astrological chart has the same personality traits.
  • Argument in Symbolic Notation
    • (x)(y)((Bxy & Hxy)  Axy)
      • For any x and y, if x and y are born minutes apart and x and y are born in the same hospital, then x and y have the same astrological chart.
    • (Ex)(Ey)(Bxy & Hxy & ~Pxy)
      • There are x and y such that x and y are born minutes apart and x and y are born in the same hospital and it’s false that x and y have the same personality traits
    • Therefore, ~(x)(y)((Axy  Pxy)
      • It’s false that, for any x and y, if x and y have the same astrological chart then x and y have the same personality traits.

Derivation of Conclusion (#13) from Premises (#1 and #2)

  1. {1} (x)(y)((Bxy & Hxy)  Axy) 
    • Premise
  2. {2} (Ex)(Ey)(Bxy & Hxy & ~Pxy)
    • Premise
  3. {3} (Ey)(Bay & Hay & ~Pay)
    • Premise
  4. {4} Bab & Hab & ~Pab
    • Premise
  5. {1} (y)((Bay & Hay)  Aay)
    • Universal Specification on #1
  6. {1}  (Bab & Hab)  Aab
    • Universal Specification on #6
  7. {1,4} ~(Aab  Pab)
    • Tautological Inference on #4 and #6
  8. {1,4} (Ey)~(y)(Aay  Pay)
    • Existential Generalization on #7
  9. {1,4} ~(y)((Aay  Pay)
    • Quantifier Exchange on #8
  10. {1,4} (Ex)~(y)((Axy  Pxy)
    • Existential Generalization on #9
  11. {1,4} ~(x)(y)((Axy  Pxy)
    • Quantifier Exchange on #10
  12. {1,3} ~(x)(y)((Axy  Pxy)
    • Existential Specification on #3, #4, #11
  13. {1,2} ~(x)(y)((Axy  Pxy)
    • Existential Specification on #2, #3, #12
Rules of Inference for Predicate Logic L′
Benson Mates’ Elementary Logic
  • Premise Introduction (P): Any sentence may be entered on any line of a derivation. 
    • As the sole premise-number of the line take the line-number.
  • Tautological Inference (T): Any sentence may be entered on a line if it is a tautological consequence of a set of sentences that appear on earlier lines.  
    • As premise-numbers of the new line take all those of the earlier lines.
  • Conditionalization (C): The sentence φ → ψ  may be entered on a line if ψ appears on an earlier line. 
    • As premise-numbers of the new line take all those of the earlier line, with the exception of any that is the line number of a line on which φ appears.
  • Universal Specification (US): The sentence φα/β may be entered on a line if (α)φ appears on an earlier line. 
    • As premise-numbers of the new line take all those of the earlier line. 
    • Note: β is any constant term.
  • Existential Generalization (EG): The sentence (∃α)φ may be entered on a line if φα/β appears on an earlier line. 
    • As premise-numbers of the new line take all those of the earlier line. 
    • Note: β is any constant term.
  • Universal Generalization (UG): The sentence (α)φ may be entered on a line if φα/β appears on an earlier line and β occurs neither in φ nor in any premise of that earlier line. 
    • As premise-numbers of the new line take all those of the earlier line. 
    • Note: β is any individual constant.
  • Existential Specification (ES): Suppose that (∃α)ψ appears on a line i of a derivation, that ψα/β appears (as a premise) on a later line j, and that φ appears on a still later line k; and suppose further that the constant β occurs neither in φ, ψ nor in any premise of line k other that Ψα/β; then φ may be entered on a new line.  
    • As premise-numbers of the new line take all those of lines i and k, except the number j. 
    • Note: β is any individual constant.
  • Quantifier Exchange (Q): The sentence -(α)-φ may be entered on a line if (∃α)φ appears on an earlier line and vice versa. Likewise for the following pairs of sentences: (α)φ and -(∃α)-φ; -(α)φ and (∃α)-φ; -(∃α)φ and (α)-φ. 
    • As premise-numbers of the new line take all those of the earlier line.
  • Identity Part A: α=α may be entered on any line of a derivation with no premise-numbers. 
    • Note: α is any constant term.
  • Identity Part B: φ may be entered on a line if α=β and ψ appear on earlier lines (where φ results from ψ by replacing one or more occurrences of α in ψ with β).  
    • As premise-numbers of the new line take all those of the earlier lines.  
    • Note: α and β are any constant terms.
Counterexamples in Predicate Logic

A counterexample to an argument-form is an interpretation of the predicate letters under which the premises are true and the conclusion false, showing the argument-form invalid.

  • Invalid Argument-form
    • ~(x)(Fx Gx)
      • It’s not the case that all F’s are G’s
    • ~(x)(Gx Hx)
      • It’s not the case that all G’s are H’s
    • Therefore, ~(x)(Fx Hx)
      • It’s not the case that all F’s are H’s
  • Counterexample
    • F: x is an integer > 10
    • G: x is an integer < 7
    • H: x is an integer > 5
  • So
    • Not every integer greater than 10 is less than 7.
      • True
    • Not every integer less than 7 is greater than 5.
      • True
    • Not every integer greater than 10 is greater than 5
      • False
  • Invalid Argument-form
    • (x)(Ey)Rxy
      • For every entity, at least one entity R’s it.
    • (x)(y)(Rxy  Ryx)
      • For any entities x and y, if x R’s y then y R’s x.
    • Therefore, (x)Rxx
      • Every entity R’s itself
  • Counterexample
    • R: x and y are integers next to each other so that either x-y=1 or y-x=1
  • So
    • For every integer, at least one integer is next to it.
      • True
    • For any integers x and y, if x and y are next to each other, then y and x are next to each other.
      • True
    • Every integer is next to itself.
      • False