Predicate Logic, a Sketch

Table of 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 ~(x)(y)((Axy → Pxy) on line13 from
- (x)(y)((Bxy & Hxy) → Axy) on line 1
- (Ex)(Ey)(Bxy & Hxy & ~Pxy) one line 2

{1} (x)(y)((Bxy & Hxy) → Axy)
- Premise
{2} (Ex)(Ey)(Bxy & Hxy & ~Pxy)
- Premise
{3} (Ey)(Bay & Hay & ~Pay)
- Premise
{4} Bab & Hab & ~Pab
- Premise
{1} (y)((Bay & Hay) → Aay)
- Universal Specification on #1
{1} (Bab & Hab) → Aab
- Universal Specification on #6
{1,4} ~(Aab → Pab)
- Tautological Inference on #4 and #6
{1,4} (Ey)~(y)(Aay → Pay)
- Existential Generalization on #7
{1,4} ~(y)((Aay → Pay)
- Quantifier Exchange on #8
{1,4} (Ex)~(y)((Axy → Pxy)
- Existential Generalization on #9
{1,4} ~(x)(y)((Axy → Pxy)
- Quantifier Exchange on #10
{1,3} ~(x)(y)((Axy → Pxy)
- Existential Specification on #3, #4, #11
{1,2} ~(x)(y)((Axy → Pxy)
- Existential Specification on #2, #3, #12

Rules of Inference for Predicate Logic L′

From 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.

Counterexample 1

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

Counterexample 2

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