Inference and Resolution Questions and Answers

Answer: A

Each parent contributes nothing beyond the complementary pair, so the resolvent is empty and the refutation is complete. That is the final step of every resolution proof. The other options misdescribe the result. Recognising the terminal case of a rule, and what it signifies, is what allows a procedure to know when it has succeeded.

Answer: B

Resolution operates on clauses, so every connective must first be rewritten and the quantifiers removed by skolemisation and implicit universal quantification. Conversion may increase size, models are defined for every formula, and quantifiers are handled rather than ignored. Reducing a rich syntax to a single uniform shape, so that one rule suffices, is the standard preparation for any mechanical procedure.

Answer: C

The standard sequence eliminates the defined connectives, drives negations inward, standardises variables apart, skolemises the existentials, drops the universals and distributes disjunction over conjunction. Each step preserves satisfiability, though skolemisation does not preserve equivalence. The other sequences mix in steps from unrelated procedures. A fixed recipe whose every step is justified separately is what makes the conversion mechanical rather than an exercise in ingenuity.

Answer: D

Since the negation of a universal is an existential, and the reverse, a negation left outside a quantifier would cause the wrong quantifiers to be skolemised. Driving negations to the atoms settles which quantifiers are existential before skolemisation is applied. Negations on literals are fine, function counts follow from the formula, and the size issue arises at the distribution step. An ordering constraint between steps of a procedure, arising from an interaction between them, must be respected or the result is silently wrong.

Answer: A

Backward chaining takes the goal, finds rules whose conclusion matches it and makes their conditions into new subgoals, recursing until facts are reached. Prolog works this way. Forward chaining is the data driven direction, and the other options describe unrelated operations. Choosing the direction of inference according to whether goals or data are the scarce resource is a decision that changes the work done by orders of magnitude.

Answer: B

Backward chaining replaces a goal by the conditions of a rule concluding it, and those conditions become subgoals to be proved in turn. The recursion terminates at facts or fails. Importance, prior proof and randomness are different notions. Decomposing a problem into the conditions that would settle it is the same reduction that appears in planning and in problem solving generally.

Answer: C

A rule stating that ancestor of follows from ancestor of will regenerate the same goal indefinitely unless loop detection or a tabling mechanism is present. Prolog programmers learn to order clauses to avoid it. Rule order is fixed, unbounded derivation is a forward chaining hazard, and proof length is secondary. A failure mode arising from the interaction of a search strategy with a natural way of writing rules is one that a language's users must be taught rather than protected from.

Answer: D

Memoising subgoals and their answers both prevents infinite loops on left recursive rules and avoids repeating work, which makes a whole class of natural programs terminate. It is the logic programming analogue of dynamic programming. Storage layout, indexing and presentation are different matters. Adding memoisation to a search that repeats subproblems is a general remedy and it applies here with unusual force.

Answer: A

Each rule matching a goal gives a branch, and the conditions give the successors, so proving a goal is a search whose nodes are subgoal sets. Prolog searches it depth first. Direct computation and independence are false. Recognising a familiar activity as an instance of search brings the whole vocabulary of completeness, ordering and pruning to bear on it, which is more useful than treating it as a separate topic.

Answer: B

Working backwards from a negated goal, resolving against definite clauses, is exactly what backward chaining does, which is why Prolog is described as a resolution based language. The restriction to definite clauses is what makes the search linear rather than exploding. The other options misstate the relationship. Seeing two apparently different procedures as one restricted to a fragment is what allows results about the general case to be applied to the special one.