Predicate Logic and Quantification
What the exam tests
Predicate logic analyzes the internal structure of propositions using predicates, individual terms, and quantifiers. The exam tests translation from English, scope and binding, quantifier negation, and the rules of inference for ∀ and ∃.
Core rules
- Universal quantifier ∀x means “for every x”; existential ∃x means “for at least one x.”
- “All A are B” becomes ∀x(Ax→Bx), not ∀x(Ax∧Bx). “Some A are B” becomes ∃x(Ax∧Bx), not ∃x(Ax→Bx).
- A variable is bound if it falls within the scope of its quantifier; otherwise it is free. A closed sentence has no free variables.
- Quantifier negation: ¬∀xPx ≡ ∃x¬Px; ¬∃xPx ≡ ∀x¬Px.
- Inference: universal instantiation (∀xPx ⊢ Pa); existential generalization (Pa ⊢ ∃xPx); existential instantiation (∃xPx ⊢ Pa, where a is a new constant); universal generalization (from a proof for an arbitrary individual).
Worked example
“All humans are mortal. Socrates is human. Therefore Socrates is mortal.” Symbolize: ∀x(Hx→Mx), Hs ⊢ Ms. From the universal premise, universal instantiation gives Hs→Ms. With Hs, modus ponens yields Ms. The argument is valid. The middle step is not a new assumption; it is licensed because the universal premise applies to every individual, including Socrates.
Traps
The most frequent translation error is using a conjunction with ∀: ∀x(Hx∧Mx) says everything is a human and mortal. Existential instantiation must introduce a fresh constant; using an existing name can produce unsound results. Do not generalize from a constant that was introduced by existential instantiation. Watch scope in sentences such as ∀x(Fx→∃yRxy).