Course contentsShow
← Mathematics
Lesson 2487 of 3,12150. Discrete Math — Logic and ProofFree lesson

Binding Variables and Scope

Understand bound vs free variables and the scope of quantifiers in logical expressions.

Binding Variables and Scope

What You'll Learn

You'll learn how quantifiers "bind" variables in logical expressions and understand what parts of a formula each quantifier controls.

The Core Idea

When you write a quantified statement like ∀x P(x) or ∃y Q(y), the quantifier binds the variable that appears immediately after it. A bound variable is one that's controlled by a quantifier. Any variable not bound by a quantifier is called a free variable.

The scope of a quantifier is the portion of the logical expression where that quantifier has control over its variable. Think of scope like a pair of parentheses around the quantifier's "territory"—the quantifier binds its variable only within that region.

Examples of Bound and Free Variables

  • In ∀x (x > 5), the variable x is bound by ∀. The scope is the entire expression (x > 5).
  • In P(x) ∧ ∀y Q(y), the variable x is free (no quantifier controls it), while y is bound by ∀. The scope of ∀y is only Q(y), not the entire expression.
  • In ∀x (P(x) → ∃x Q(x)), we have two different scopes! The first x in P(x) is bound by the outer ∀x, but the second x in Q(x) is bound by the inner ∃x. This is like reusing variable names in nested loops—each quantifier creates its own scope.

Why It Matters

Understanding scope prevents confusion in complex statements. The formula ∀x P(x) ∧ Q(x) means "for all x, P(x) is true, AND Q(x) is true for some other x"—but the second x is free and ambiguous! Proper scope would be ∀x (P(x) ∧ Q(x)).

Key Takeaway: A quantifier binds a variable within its scope; variables outside any quantifier's scope are free and potentially ambiguous.