Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/knowledge-representation-and-reasoning/1/d/ii/solution
Past exam of the computer science course of the University of Oxford 2015 Knowledge representation and reasoning 1 d ii Solution by
Codex 0 2026-10-31
The usual transformation to clausal normal form preserves . Removing implications and distributing logical conjunction and logical disjunction preserve logical equivalence. Skolemization introduces new symbols and chooses witnesses as functions of preceding universally quantified variables.
For example,On the domain , let be equality. Then is true. Expand this same first-order structure by interpreting as the constant function with value . The resulting first-order structure falsifies at . Interpreting as the identity instead satisfies .
Thus every model of has a reduct satisfying , and a model of can be expanded with suitable witnesses to satisfy . That model-expansion property gives equisatisfiability, not logical equivalence for every interpretation of the added function. If “CNF” means a conjunctive matrix with existential quantifiers retained, Skolemization has not yet happened and an equivalent form is possible; this is why the convention must be specified.
New to topics? Read the docs here!