Inference and Resolution Questions and Answers

Answer: A

Model checking answers an entailment question by examining the models directly, which is correct and exponential in the number of symbols. Theorem proving instead manipulates sentences syntactically and can be far more efficient. Data fitting, proof verification and syntax checking are different activities. Having two quite different routes to the same answer, one semantic and one syntactic, is what makes soundness and completeness meaningful statements rather than definitions.

Answer: B

A conclusion following from three of a thousand premises can be proved in three steps while enumeration would examine two to the thousand models. The proof ignores everything irrelevant. Termination guarantees run the other way, negation is handled by both, and symbol counts are fixed by the problem. That the length of a proof bears no relation to the size of the model space is what makes syntactic methods worth developing at all.

Answer: C

Resolution takes two clauses, one containing a literal and the other its negation, and produces the clause containing everything else from both. That single rule is complete for refutation, which is its remarkable property. Ambiguity, normalisation and conclusion selection are different notions. A single rule sufficing for a whole logic, in place of a dozen natural deduction rules, is what makes mechanical proof search feasible.

Answer: D

Resolution cannot derive every consequence directly, but if a clause set is unsatisfiable it will eventually produce the empty clause, and that suffices because entailment is converted into unsatisfiability by negating the goal. Direct completeness, termination and model construction are different properties. A weaker completeness that is enough for the question actually being asked is a common and useful pattern in proof theory.

Answer: A

Since premises entail a conclusion exactly when the premises together with the negated conclusion are unsatisfiable, and resolution is refutation complete, the proof proceeds by deriving a contradiction. Clausal conversion and clause counts are unaffected. Converting a question the available machinery cannot answer into one it can is a move that recurs throughout automated reasoning, and here it is what makes the whole approach work. A limit that survives making every external component ideal is an intrinsic one, and worth knowing for that reason.

Answer: B

The empty clause asserts a disjunction of nothing, which is false in every model, so deriving it proves the clause set contradictory. It is the goal of every resolution refutation. Positive clauses, subsumed clauses and ground clauses are different notions. That the target of a proof is a syntactic object with no content, rather than a statement of the conclusion, is initially disconcerting and follows directly from the refutation strategy. Checking the units of each quantity catches a wrong formula before the arithmetic begins.

Answer: C

Resolution requires complementary literals, and in first order logic they may match only after variables are instantiated, which unification computes. Without it a prover would have to enumerate ground instances, which is what the Herbrand approach does far less efficiently. Clause merging is resolution itself, and duplicate removal is factoring. Operating on variables directly, rather than on their instances, is what lifts a propositional method to the first order case.

Answer: D

If two literals within one clause can be made identical, the clause may be replaced by its factor, and without this step resolution is not complete. It is easily overlooked because it never arises in the propositional case. Splitting, common factors and subsumption are different operations. A step required only in the lifted version of a rule, and invisible in the propositional one, is exactly the kind of detail that makes a first implementation subtly incomplete.

Answer: A

The set of clauses grows as resolvents are added, and each new clause may resolve with every existing one, so unrestricted search explodes immediately. That is why strategies restricting which pairs may resolve are essential rather than optional. No new predicates appear, the most general unifier is unique, and conversion happens once. A rule that is complete and unusable without restriction is the normal starting point for practical proof search. A single measurement chosen to respond to the one asymmetry beats several that respond to shared behaviour.

Answer: B

Resolving with a unit clause always shortens the other clause, so the search moves towards the empty clause rather than away from it. It is a heuristic rather than a restriction and does not affect completeness. Premise preference is input resolution, and the other options describe different rules. Preferring steps that make measurable progress towards the goal is the same principle that orders any search, applied here to clause length. A single measurement chosen to respond to the one asymmetry beats several that respond to shared behaviour.