In the formula ∀x (P(x) → Q(x, y)), which variables are free?
Ax only
By only
Cboth x and y
Dneither — both are bound
The quantifier ∀x binds every occurrence of x within its scope (the entire subformula P(x) → Q(x, y)). The variable y appears inside that scope but is not bound by any quantifier, so y is free. A variable is bound if and only if it falls within the scope of a quantifier that names it.
Question 2 True / False
In the formula ∃x P(x) ∧ Q(x), nearly every occurrence of x is bound by the existential quantifier.
TTrue
FFalse
Answer: False
The scope of ∃x is only the immediately following formula P(x), not the entire conjunction. The x in Q(x) is outside that scope and is therefore free. If you wanted to bind both occurrences, you would write ∃x (P(x) ∧ Q(x)) with explicit parentheses to extend the scope.
Question 3 Short Answer
What distinguishes a sentence from an open formula in first-order logic?
Think about your answer, then reveal below.
Model answer: A sentence has no free variables — every variable is bound by a quantifier. An open formula has at least one free variable.
Sentences have definite truth values relative to a model because they make no unresolved reference to external variable assignments. Open formulas like P(x) can only be evaluated once x is assigned a value from the domain. This distinction is crucial: logical consequence and validity are defined for sentences.