Inference and Resolution Questions and Answers

Answer: C

Requiring that every step touch the negated goal or something derived from it prevents the prover from deriving irrelevant consequences of the premises, and it preserves completeness provided the premises alone are satisfiable. It is the most important of the classical strategies. The other options describe unrelated notions. A restriction that is both a large saving and provably harmless is worth adopting universally, which is what happened. Most errors here come from carrying a result across from a neighbouring case where it does not hold.

Answer: D

If the premises are consistent, any contradiction must involve the negated goal, so resolutions among the premises alone can be skipped without losing the proof. That condition must actually hold, and it usually does. Order restriction and universal harmlessness are false. A restriction justified by an argument about where a contradiction must lie is far stronger than one adopted heuristically, and it is worth checking that the argument's premise holds. Most errors here come from carrying a result across from a neighbouring case where it does not hold.

Answer: A

If one clause is an instance of another, or contains all its literals, it adds nothing and may be deleted, which keeps the clause set from growing uncontrollably. Forward and backward subsumption check new clauses against old and old against new respectively. The other options describe different operations. Deleting redundant information aggressively is what keeps a saturating procedure from drowning in its own output.

Answer: B

Restricting one parent of every resolution to be an original clause keeps the search linear in shape, and it is complete for Horn clauses though not in general. That partial completeness is exactly why logic programming, which is Horn, can use such a restricted strategy. The other options misread the restriction. A strategy complete for a fragment and incomplete generally is usable precisely where that fragment applies, which must be checked rather than assumed.

Answer: C

A refutation from Horn clauses can always be arranged so that each step uses an original clause, which is not true when clauses have several positive literals. That structural fact is what logic programming rests on. Horn clauses do contain negative literals, conversion is not the issue, and a Horn set may certainly be unsatisfiable. A completeness result that depends on the shape of the available proofs, rather than on the rule, is worth understanding as such.

Answer: D

Lifting the rule to first order logic requires the antecedent of the implication and the known fact to be unified rather than being identical, which is what forward and backward chaining over definite clauses use. It is sound and complete for definite clauses. The other options describe different extensions. Adding unification to a propositional rule, so that it applies to variables, is the same lifting that produces first order resolution. Framing the question as which quantity the change acts upon makes the answer follow without calculation.

Answer: A

Definite clauses correspond exactly to rules with a single conclusion, and forward and backward chaining over them are sound, complete and run in linear time. Horn clauses allow zero or one positive literal, the extra case being the goal clause. Instantiation and provability are different notions. A restriction whose members are exactly the rules people naturally write is unusually convenient, and it explains why so many practical systems are built on it.

Answer: B

With appropriate indexing each rule fires at most once per satisfying substitution, giving a linear procedure that derives every consequence. Function symbols do make the set of derivable facts infinite, which is a genuine caveat rather than the general answer. The other figures overstate the cost. A complexity result that holds under a stated restriction, with the restriction's violation changing the answer completely, is worth stating with the condition attached.

Answer: C

A rule deriving a successor from every number will generate an unbounded sequence of ground terms, so saturation never completes. Datalog forbids function symbols precisely to keep the derived set finite. Cycles alone are handled by not repeating derivations, unification terminates, and indexing is an efficiency matter. Identifying the syntactic feature responsible for an unbounded computation is what allows a decidable fragment to be carved out deliberately.

Answer: D

Forbidding function symbols keeps the set of derivable facts finite, so forward chaining terminates and the language is decidable, which makes it suitable for deductive databases. Recursion is permitted and is its main advantage over relational query languages. Schema description, negation and graph querying are different things, though modern variants add some of them. A deliberate restriction adopted to obtain decidability is the same design move that produced description logics.