Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/knowledge-representation-and-reasoning/1/c/ii/solution
Past exam of the computer science course of the University of Oxford 2015 Knowledge representation and reasoning 1 c ii Solution by
Codex 0 2026-10-31
For ordinary function-free Datalog, has the required form. Sentence (i) is not a definite first-order Horn clause: the category choice gives two positive alternatives, and its second clause is a negative constraint. Even allowing constraints would not remove the positive choice. Semantically, the category-choice condition fails closure under intersection of interpretations with fixed domain and functions: one model can choose only the undergraduate category, another only the masters category, and their intersection chooses neither.
Sentence (ii) needs an existentially supplied supervisor. Function-free Datalog cannot demand such a witness without naming or otherwise fixing it in the rule. Its Skolemized form is a first-order Horn clause with a function, rather than a Datalog rule. Sentence (iii) also contains a nonconstant function. Being Horn is therefore insufficient for membership in Datalog.
New to topics? Read the docs here!