Course contentsShow
← Computer Science
Lesson 55 of 2,8722. Discrete Mathematics for CSFree lesson

Quantifiers Over Restricted Domains

Master techniques for restricting quantifier domains using conditional and conjunctive forms.

Quantifiers Over Restricted Domains

What you'll learn: How to limit the scope of quantifiers to specific subsets of a domain using conditional and conjunctive forms.

The Core Idea

When working with quantifiers like ∀ (for all) and ∃ (there exists), we often don't want to talk about every single thing in our universe—just a specific subset. For example, instead of "all numbers," we might only care about "all even numbers" or "all students in a particular course."

There are two main patterns for restricting domains:

Universal Quantifier (∀) with Conditional Form

When saying "for all X with property P, statement Q is true," use implication:

∀x (P(x) → Q(x))

Example: "All students who study pass the exam."

  • Translation: ∀x (Student(x) ∧ Studies(x) → Passes(x))

Think of it as: "If something has property P, then Q must hold."

Existential Quantifier (∃) with Conjunctive Form

When saying "there exists some X with property P and statement Q," use conjunction:

∃x (P(x) ∧ Q(x))

Example: "There is a student who studies and passes."

  • Translation: ∃x (Student(x) ∧ Studies(x) ∧ Passes(x))

Think of it as finding something that satisfies both conditions simultaneously.

Why Different Forms?

Using → with ∀ makes vacuous truth work correctly (if no element satisfies P, the statement is trivially true). Using ∧ with ∃ ensures we're actually finding something with all desired properties.

Key Takeaway: Restrict universal quantifiers with implication (∀x (P(x) → Q(x))), and existential quantifiers with conjunction (∃x (P(x) ∧ Q(x))) to precisely specify which subset of the domain you're reasoning about.