Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/logic-and-proof/3/c/solution
Past exam of the computer science course of the University of Oxford 2015 Logic and proof 3 c Solution by
Codex 0 2026-10-31
For a first-order signature with at least one constant symbol, its Herbrand universe is the set of all ground terms built from its constant and function symbols. If necessary add a fresh constant to make this set nonempty. A Herbrand structure has exactly this domain; each constant denotes itself and each function symbol forms the corresponding syntactic first-order term. Its remaining choices are the truth values of the ground predicate atoms. For example, with constant and unary function , the Herbrand universe is .
One useful clausal form of Herbrand's theorem is the following. For a set of universally quantified, equality-free first-order clauses,Ground instances substitute ground terms for all variables. On the right, treat the ground predicate atoms as independent Boolean variables. Equivalently, is satisfiable if and only if it has a Herbrand model. A general first-order sentence can first be put into Skolem normal form and clausal form, with the new symbols included in the Herbrand universe.
An equivalent existential version says that a valid equality-free first-order sentence with quantifier-free formula has finitely many ground tuples such that is propositionally valid, adding a constant if needed. This explains why a finite ground resolution refutation can establish a consequence involving infinitely many possible ground terms.
The equality-free qualification matters. If first-order equality is present, one must handle its axioms and use a term model modulo a suitable congruence, or use the corresponding theorem with equality. Literal syntactic term interpretation alone cannot model a consistent requirement such as for distinct constant symbols.
New to topics? Read the docs here!