The formula ∀x ∃y ∀z ∃w R(x,y,z,w) is Skolemized. Which result is correct?
A∀x ∀z R(x, f(x,z), z, g(x,z)) — both Skolem functions depend on all universal variables
B∀x ∀z R(x, f(x), z, g(x,z)) — f depends only on x; g depends on both x and z
C∀x ∀z R(x, f, z, g) — both existentials become constants since they follow universals
D∀x ∀z R(x, f(x), z, g(z)) — g depends only on z since z is introduced last
When we Skolemize y, the universally quantified variables in scope are just x, so y becomes f(x). When we Skolemize w, the universally quantified variables in scope are x and z, so w becomes g(x,z). The Skolem function for each existential must encode exactly the universal variables in scope at that point — this dependency captures the fact that the witness for y may differ for each x, and the witness for w may differ for each combination of x and z.
Question 2 Multiple Choice
A student claims: 'Skolemization preserves logical equivalence — any model of φ is also a model of Sk(φ), and vice versa.' What is wrong with this claim?
ANothing — Skolemization does preserve logical equivalence in all cases
BSk(φ) may be strictly stronger: some models satisfy φ but not Sk(φ), even though satisfiability is preserved
CSk(φ) may be strictly weaker: models can satisfy Sk(φ) without satisfying φ
DThe claim is wrong because Skolemization only applies to prenex normal form formulas with alternating quantifiers
Skolemization preserves satisfiability — φ is satisfiable iff Sk(φ) is satisfiable — but not logical equivalence. Consider ∃x P(x): it is satisfiable in any model with at least one element satisfying P. Its Skolemization P(c) makes a stronger claim — a specific constant c satisfies P — which fails in some models where some but not the named constant satisfies P. For automated theorem proving, satisfiability preservation is what matters: we negate the goal, Skolemize, and derive a contradiction.
Question 3 True / False
If a formula φ is satisfiable, then its Skolemization Sk(φ) is guaranteed to be satisfiable.
TTrue
FFalse
Answer: True
This is the fundamental correctness property of Skolemization. Given a model M satisfying φ, the existential witnesses required by φ can be used to define the Skolem functions (using the axiom of choice for infinite domains). The resulting expanded model satisfies Sk(φ). Conversely, any model of Sk(φ) is also a model of φ by ignoring the interpretations of Skolem functions. So satisfiability is preserved in both directions.
Question 4 True / False
When Skolemizing ∃y, the Skolem function for y takes as arguments most variables currently in scope, including other existentially quantified variables that appear before y in the prenex.
TTrue
FFalse
Answer: False
Only universally quantified variables in scope become arguments to the Skolem function — not other existential variables. Existential variables are being eliminated by Skolemization; they cannot serve as inputs to a Skolem function. The dependency structure captures: 'the witness for y may depend on which universal values were chosen,' but it cannot depend on another existential that is itself being eliminated.
Question 5 Short Answer
Why must the Skolem function for an existentially quantified variable y depend on all the universally quantified variables in scope at that point, rather than being a simple constant? What would go wrong if we always used constants?
Think about your answer, then reveal below.
Model answer: The formula ∀x ∃y P(x,y) says: for EACH x, there exists some y that works — but a different y may work for each x. If we replaced y with a constant c, we would get ∀x P(x,c), which says the single value c works for every x. This is a strictly stronger claim that may be false even when the original is true. Using a Skolem function f(x) instead says c depends on x — the witness is allowed to vary with the universal variable, matching the quantifier structure of the original formula and preserving satisfiability.