First-order logic introduces free and bound variables, crucial concepts for understanding formula structure. Free variables act as placeholders, while bound variables are controlled by quantifiers. This distinction impacts how formulas are interpreted and evaluated for truth.

Quantifier scope determines the range of a quantifier's influence in a formula. The arrangement of quantifiers and their scopes can dramatically alter a formula's meaning. Understanding these concepts is essential for accurately interpreting and constructing logical statements in first-order logic.

Free vs Bound Variables

Defining Free and Bound Variables

• In first-order logic, variables can be either free or bound within a formula
• Free variables are not quantified by a quantifier (∀ or ∃) and act as placeholders for arbitrary values ($x$ in $P(x)$)
• Bound variables are quantified by a quantifier, and their values are determined by the quantifier ($x$ in $∀x P(x)$)
• The interpretation and truth value of a formula depend on the values assigned to its free variables, while bound variables do not affect the truth value as they are governed by their quantifiers

Variable Status and Formula Classification

• The status of a variable as free or bound can change within a formula depending on the presence and scope of quantifiers
• A variable can be free in one part of the formula and bound in another ($x$ is free in $P(x)$ but bound in $∀x P(x)$)
• Formulas containing only free variables are called open formulas ($P(x) ∧ Q(y)$)
• Formulas with no free variables are called closed formulas or sentences ($∀x P(x) → ∃y Q(y)$)

Quantifier Scope and Meaning

Defining Quantifier Scope

• The scope of a quantifier is the part of the formula where the quantifier binds its associated variable and determines the range over which the quantifier applies
• Quantifier scope is typically denoted by parentheses or brackets immediately following the quantifier symbol ($∀x (P(x) ∧ Q(x))$)
• The scope extends from the opening parenthesis to the matching closing parenthesis

Impact of Quantifier Scope on Formula Meaning

• The relative positions of quantifiers and their scopes can significantly impact the meaning and truth conditions of a formula
• Changing the scope of quantifiers can alter the logical interpretation ($∀x ∃y P(x, y)$ vs $∃y ∀x P(x, y)$)
• Nested quantifiers create a hierarchy of variable binding, with the outermost quantifier having the widest scope and the innermost quantifier having the narrowest scope ($∀x (P(x) ∧ ∃y Q(x, y))$)

Determining Quantifier Scope

Rules for Multiple Quantifiers

• If a formula contains multiple quantifiers, the scope of each quantifier is determined by the parentheses or brackets following it
• The scope extends until the matching closing parenthesis or bracket ($∀x (P(x) ∧ ∃y (Q(y) ∨ R(x, y)))$)
• In the absence of explicit parentheses, the scope of a quantifier extends as far to the right as possible while maintaining well-formed formula structure ($∀x P(x) ∧ Q(x)$ is equivalent to $∀x (P(x) ∧ Q(x))$)

Nested Quantifiers and Scope Boundaries

• When quantifiers are nested, the innermost quantifier has the narrowest scope, and its scope is contained within the scope of the outer quantifiers ($∀x ∃y ∀z P(x, y, z)$)
• The scope of a quantifier does not extend beyond the logical connectives (∧, ∨, →, ↔) at the same level of nesting
• Connectives act as boundaries for quantifier scope ($∀x P(x) ∧ ∃y Q(y)$ is not equivalent to $∀x ∃y (P(x) ∧ Q(y))$)

Variable Binding and Interpretation

Effects of Quantifier Binding on Variables

• The binding of variables by quantifiers determines how the variables are interpreted and affects the truth conditions of the formula
• Variables bound by the universal quantifier (∀) must satisfy the formula for all possible values within the domain of discourse ($∀x P(x)$ is true if $P(x)$ is true for all $x$)
• Variables bound by the existential quantifier (∃) require at least one value within the domain of discourse to satisfy the formula for the formula to be true ($∃x P(x)$ is true if there exists at least one $x$ such that $P(x)$ is true)
• Free variables act as placeholders for arbitrary values and do not have a fixed interpretation ($P(x)$ can be true or false depending on the value assigned to $x$)

Analyzing Formulas with Quantifiers and Connectives

• The interplay between quantifiers, their scopes, and the logical connectives determines the overall meaning and truth conditions of a formula
• Analyzing the structure and variable binding is crucial for accurate interpretation
• Example: $∀x (P(x) → ∃y Q(x, y))$ means for every $x$, if $P(x)$ is true, then there exists a $y$ such that $Q(x, y)$ is true
• Example: $∃x ∀y (P(x) ∨ Q(y))$ means there exists an $x$ such that for all $y$, either $P(x)$ is true or $Q(y)$ is true