Past exam of the computer science course of the University of Oxford / 2015 / Intelligent systems / 1 / d / Solution

Yes: $h_1(R)=|R|$ is an admissible heuristic. One application of the resolution inference rule removes just one current negative Boolean literal. It may add other negative Boolean literals, and some of those may already occur, but it cannot remove any other current obligation. ConsequentlyIf $\ell$ actions lead from $R$ to $\varnothing$, applying this inequality at every step gives $0\ge |R|-\ell$. ThusIt is also a consistent heuristic, since $h_1(R)\le 1+h_1(R^{\prime })$ and $h_1(\varnothing )=0$. In particular, merging duplicate obligations cannot invalidate the lower bound: removing several duplicates from the representation never counts as removing several distinct members of a set.