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