Predicate Logic·Advanced·5 lessons·62 practice activities·~320 min
Predicate Logic: Quantifiers, Predicates, and Formal Structure
How internal sentence structure changes formal reasoning
What you'll learn
By the end of this unit, you can…
- Identify predicates and arity.
- Translate simple quantified claims.
- Translate multi quantifier claims.
- Construct quantifier proofs.
Lessons
Lesson sequence
- 1Open →
Why Predicate Logic Extends Propositional Logic
Motivates the move from propositional to predicate logic by showing arguments that propositional logic cannot capture and introduces the basic vocabulary of predicates, constants, and variables.
- 2Student Pro
Universal and Existential Quantifiers
Introduces the universal and existential quantifiers, teaches students to translate simple quantified English claims into first-order form, and establishes the relationship between quantifiers and the connectives that typically accompany them.
- 3Student Pro
Multiple Quantifiers and Scope
Tackles the hardest translation challenges in predicate logic: multiple quantifiers, nested scope, mixed universal and existential claims, and the subtleties of relational predicates.
- 4Student Pro
Quantifier Rules in Proof
Introduces the four quantifier inference rules (universal instantiation, existential instantiation, universal generalization, existential generalization) and explains the restrictions that each rule imposes.
- 5Student Pro
Capstone: Quantified Reasoning in Mixed Arguments
An integrative lesson that asks students to translate ordinary-language arguments involving quantifiers and predicates, construct short proofs using quantifier rules, and diagnose scope errors.
How to study
Three moves that work for this unit
Read the explanation
Each lesson opens with a guided walkthrough — read it before the activity.
Study the worked example
Look at why each step follows, not just what the answer is.
Practice with the target in mind
Know which rule applies and what would make the response weak before you start.
Reference materials
Optional context for the unit. Each lesson surfaces the concepts and rules it uses — these are here when you want the bigger picture.
Concept map (10 terms)
Predicate
An expression that attributes a property to an object or a relation among several objects; a one-place predicate applies to a single object, while a relational predicate applies to two or more.
Individual Constant
A symbol that names a specific object in the domain of discourse, typically written with lowercase letters like a, b, c.
Variable
A symbol like x, y, or z that does not name a specific individual but can range over the domain when bound by a quantifier.
Domain of Discourse
The set of objects that the variables of a predicate-logic formula are taken to range over in a given interpretation.
Quantifier
An operator that binds a variable and states how much of the domain it ranges over; the universal quantifier ∀ means 'for all,' and the existential quantifier ∃ means 'for some' or 'there exists.'
Scope and Binding
The scope of a quantifier is the portion of a formula it governs; a variable occurrence is bound if it falls within the scope of a quantifier using the same variable, and free otherwise.
Universal Quantifier
The quantifier ∀x, read 'for all x,' which claims that the formula it binds holds for every object in the domain.
Existential Quantifier
The quantifier ∃x, read 'there exists x such that,' which claims that the formula it binds holds for at least one object in the domain.
Instantiation
A proof move that goes from a quantified claim to a claim about a specific individual; universal instantiation picks any individual, while existential instantiation introduces a fresh name for a witness.
Generalization
A proof move that goes from a claim about an individual to a quantified claim; universal generalization is allowed only when the individual was arbitrary, and existential generalization is always allowed when a specific instance has been found.
Rules and standards (5)
- Universal Instantiation. From ∀x φ(x), infer φ(a) for any individual constant or previously introduced name a. Common failures: Instantiating to a name that has been reserved for existential reasoning.; Substituting the same variable for two different bound variables by accident..
- Existential Instantiation. From ∃x φ(x), infer φ(c), where c is a fresh name not appearing earlier in the proof. Common failures: Reusing an existing name for the witness, which can lead to spurious identifications.; Treating the witness name as if it had arbitrary properties beyond φ(c)..
- Universal Generalization. From φ(a), where a was introduced as an arbitrary individual, infer ∀x φ(x). Common failures: Generalizing from a name introduced by existential instantiation.; Generalizing from a name that already has specific properties from earlier premises..
- Existential Generalization. From φ(a), infer ∃x φ(x) for any individual constant a. Common failures: Generalizing to the wrong variable when φ(a) already contains that variable free.; Using existential generalization to justify a claim that the original individual was unspecified..
- Respect Scope and Binding. No variable occurrence may be treated as bound unless a quantifier with that variable actually governs it, and no free variable may be ignored in semantic evaluation. Common failures: Claiming a free variable is bound because another quantifier uses the same letter.; Misplacing a quantifier so that it binds fewer or more occurrences than intended..
Formalization patterns (2)
- Quantified Translation Schema. From natural_language_claim to first_order_formula — Identify the domain of discourse.; Identify the predicates needed and their arities (one-place, two-place, etc.).; Decide whether each part of the claim is universal, existential, or relational.; Place quantifiers in the order that the English demands.; Verify that every variable occurrence is bound and that the scope matches the English meaning..
- Predicate Proof Schema. From first_order_argument to quantifier_sensitive_derivation — Formalize premises and conclusion.; Instantiate universal premises to names that fit the goal.; When using an existential premise, introduce a fresh witness name.; Apply propositional inference rules to the instantiated formulas.; Generalize only when the name is arbitrary (for universal generalization) or when a specific witness is available (for existential generalization)..
Full mastery and assessment guidance
Mastery requirements
- Identify predicates and arity. Correct Identifications · 10_correct_identifications
- Translate simple quantified claims. Correct Translations · 10_correct_translations
- Translate multi quantifier claims. Correct Translations · 6_correct_translations
- Construct quantifier proofs. Successful Proofs · 4_successful_proofs
Assessment advice
- Have I identified the arity of every predicate?
- Have I respected argument order in relational predicates?
- Is my domain of discourse clear?
- Do not mix up predicates and their arguments; the order in Lab is not interchangeable with Lba.
- Do not move on to quantifiers before atomic syntax feels natural.
- Did I use the right pairing (conditional for universal, conjunction for existential)?
- Does the formalization say what the English says when I read it back?
- Is any negation inside or outside the quantifier where I need it to be?
- Do not pair universals with conjunctions; the resulting formula overreaches.
- Do not pair existentials with conditionals; the resulting formula is usually vacuously satisfied.
- Did I ask 'same or different' before committing to quantifier order?
- Does each quantifier's scope contain everything it should bind and nothing else?
- Does the read-back match the original English?
- Do not swap ∀...∃ with ∃...∀; the change is usually not meaning-preserving.
- Do not forget the pairing rule at inner quantifiers just because you already used it outside.
- Does every existential instantiation use a fresh name?
- Does every universal generalization use a name that was arbitrary?
- Did I instantiate before applying propositional rules?
- Do not skip the fresh-name requirement for existential instantiation; it is what keeps the proof honest.
- Do not generalize from any name whose provenance you cannot trace to arbitrary assumptions.
- Is my translation faithful to the original when I read it back in English?
- Did I check scope at every quantifier rule application?
- Did I distinguish invalidity from mere scope confusion in my diagnosis?
- Ignoring scope because the formula 'looks right'.
- Conflating 'some' with 'the' in existential translations.
Historical context (3)
- Gottlob Frege. Introduced the first formal system of quantified logic in his Begriffsschrift, making generality and existence expressible with explicit variable binding. The entire modern apparatus of universal and existential quantifiers, variable binding, and formal proof for quantified arguments descends from Frege.
- Bertrand Russell and Alfred North Whitehead. Systematized quantified logic in Principia Mathematica and used it to formalize large portions of mathematics. The notation and proof rules used in most predicate logic textbooks today are the descendants of Russell-Whitehead formalism, simplified through several decades of refinement.
- Alfred Tarski. Gave the first rigorous model-theoretic semantics for quantified logic, defining truth in a model in terms of variable assignments. Modern accounts of quantifier meaning, domain of discourse, and formal semantics follow Tarski's definitions directly.