CHAPTER 7: THE PREDICATE CALCULUS

7.1 Reasoning in Predicate Logic

Terms:

Predicate logic: the study of the logical concept of validity insofar as this is due to the truth-functional operators, the quantifiers, and the identity predicate

Predicate calculus: the system of inference rules designed to yield a proof of the valid argument forms of predicate logic.

7.2 Inference Rules for the Universal Quantifier

Universal Elimination (∀E universal instantiation UI)

Two forms (works with both variables and constants)

∀x(Fx)

˫ Fy

e.g., For all things, things fluctuate; therefore things fluctuate.

∀x(Fx)

˫ Fa

e.g., For all things, things fluctuate; therefore atoms fluctuate.

Example of use in a proof:

All humans are mortal; Socrates is human; therefore Socrates is mortal.

1. ∀x(Hx → Mx)

__2. Hs / ____˫ Ms__

3. Hs → Ms (1 ∀E)

4. Ms (3, 2 →E MP)

Universal Introduction (∀I universal generalization UG)

One form (works only with variables)

Fy

˫ ∀x(Fx)

e.g., things fluctuate; therefore, for all things, things fluctuate.

Not permitted with constants:

Fa

˫ ∀x(Fx)

e.g., atoms fluctuate; therefore, for all things, things fluctuate.

Example of use in a proof:

All dogs are mammals; all mammals are warm-blooded; therefore all dogs are warm-blooded.

1. ∀x(Dx → Mx)

__2. ____∀x(Mx → Wx) / ____˫ ____∀x(Dx
→ Wx)__

3. Dx → Mx (1 ∀E)

4. Mx → Wx (2 ∀E)

5. Dx → Wx (3, 4 HS)

6. ˫ ∀x(Dx → Wx) (5. ∀I)

7.3 Inference Rules for the Existential Quantifier

Existential Introduction (ƎI existential generalization EG)

Two forms (works with both variables and constants):

Fa

˫ Ǝx(Fx)

e.g., atoms fluctuate; therefore, there exists some thing that fluctuates

Fy

˫ Ǝx(Fx)

e.g., things fluctuate; therefore, there exists some thing that fluctuates

Example of use in a proof:

All frogs are green things; Alex is a frog; therefore, there is at least one green thing

1. ∀x(Fx → Gx)

__2. Fa / ____˫ Ǝx(Gx)__

3. Fa → Ga (1 ∀E)

4. Ga (3, 2 MP)

5. ˫ Ǝx(Gx) (4 ƎI)

Existential Elimination (ƎE existential instantiation EI)

One form (works only with constants)

Ǝx(Fx)

˫ Fa

e.g.: There exists some thing such that this thing is a frog; therefore Alex (which we will call him) is a frog.

Restriction: the existential name a must be a new name that has not occurred in any previous line

Not permitted with variables:

Ǝx(Fx)

˫ Fy

There exists some thing such that this thing is a frog; therefore things are frogs.

Example of use in a proof:

All guitarists are musicians; some guitarists are homeless; therefore some homeless are musicians. (Alex is a stipulated person)

1. ∀x(Gx → Mx)

__2. Ǝx(Gx & Hx)
/ ____˫ Ǝx (Hx & Mx)__

3. Ga & Ha (2 ƎE)

4. Ga → Ma (1 ∀E)

5. Ga (3 SIMP)

6. Ma (4, 5 MP)

7. Ha & Ga (3 COM)

8. Ha (7 SIMP)

9. Ha & Ma ( CONJ)

10. ˫ Ǝx (Hx & Mx) (ƎI)

7.4 Theorems and Quantifier Equivalence Rules

Quantifier Equivalence rules (Quantifier Exchange QE)

∀x(Fx) ↔ ~Ǝx~(Fx)

~∀x(Fx) ↔ Ǝx~(Fx)

∀x~(Fx) ↔ ~Ǝx(Fx)

~∀x~(Fx) ↔ Ǝx(Fx)

7.5 Inference Rules for the Identity Predicate