Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/logic-and-proof/3/b/solution
Past exam of the computer science course of the University of Oxford 2015 Logic and proof 3 b Solution by
Codex 0 2026-10-31
First convert the four first-order sentences to clausal form. In the first, pull the existential quantifier across the logical disjunction, then replace its witness by a fresh unary Skolem function . The usual nonempty-domain convention for first-order logic makes this transformation valid even when already holds. The four Skolem normal forms areThe Skolemization of preserves satisfiability in an expanded first-order signature; it does not assert logical equivalence for every arbitrary interpretation of the new Skolem function. The other three first-order sentences only require elimination of implications and movement of universal quantifiers.
For a ground resolution refutation, negate the desired conclusion and introduce a fresh constant for a person who is not merry. This adds the ground clause . Use these ground instances of the four universal first-order sentences:Here comes from with , after removing a duplicate negative literal. All first-order terms in these ground clauses are ground. Resolving givesRepeated positive literals in have again been removed. The empty ground clause proves unsatisfiability of the premises together with the negated conclusion. ThereforeThe key is to apply the first three premises to Lucy herself: either she is already happy, or she loves somebody, hence loves herself, which forces her happiness and activates the final premise.
New to topics? Read the docs here!