Inference and Resolution Questions and Answers

Answer: A

Provers check that a processor design meets its specification, that a program satisfies its contract and that a formalised mathematical argument is correct, all applications where a guarantee rather than a plausible answer is required. General question answering and learning are served by other techniques, and mathematicians use provers as assistants rather than being replaced. A technology finding its niche wherever certainty is worth its cost is a fair description of the field's trajectory.

Answer: B

When a design error costs a product recall, spending days of computation to prove the absence of a fault is obviously worthwhile, and testing can only show the presence of errors. The problems are large and the formalisation effort is substantial, both being genuine costs. Simulation examines designs too. Matching a technology to the applications where its particular guarantee justifies its particular cost is what determines where it is actually used. Framing the question as which quantity the change acts upon makes the answer follow without calculation.

Answer: C

The first two are correct. Resolution cannot derive an arbitrary entailed sentence directly; it establishes entailment by refuting the negated goal, which is a weaker but sufficient property. Confusing refutation completeness with direct completeness leads to expectations the rule cannot meet, and the distinction explains why every prover begins by negating what it has been asked to prove.

Answer: D

Two of these belong to propositional satisfiability and two to first order resolution, yet all four address the same underlying problem of keeping a combinatorial search tractable. Two restrict what is explored and two remove what has been shown useless, which is a classification worth carrying to any search procedure.

Answer: A

The first three are correct. A local search samples assignments and can therefore only report success or failure to find one, never a proof that none exists. Systematic solvers with clause learning produce refutation proofs that can be checked independently. The distinction between finding and proving absence recurs in every search setting and it decides which method a verification task must use.

Answer: B

Set of support and input resolution restrict which clauses may be resolved, and unit preference orders the choice. Factoring is an additional inference rule required for completeness rather than a restriction, and omitting it makes the prover unable to find some proofs. Distinguishing rules that must be present from strategies that may be imposed is essential, since leaving out a rule and leaving out a strategy have opposite consequences. The shared properties explain why these belong to one family, and the differences explain why more than one exists.

Answer: C

Both are true and the second is the reason. Since the rule guarantees only that an unsatisfiable set will yield the empty clause, the entailment question must first be converted into an unsatisfiability question by negating what is to be proved. The refutation identity makes that conversion sound. A proof strategy dictated by the precise form of the completeness result available is a good illustration of theory determining practice.

Answer: D

Inference produces conclusions that follow from what is already believed, which is what distinguishes a knowledge base from a store of records. Syntax checking, storage and translation are supporting operations. Keeping the derivation of new content separate from the management of existing content is what allows a general reasoner to be written once and applied to any domain, which is the architectural promise of the whole approach.

Answer: A

A proof is a syntactic object whose steps can be checked mechanically, which is why a machine derived proof can be verified independently of the machine that found it. Truth in an interpretation is semantic, persuasion is informal, and the search record is usually far larger than the proof. That finding a proof is hard and checking one is easy is the asymmetry the whole enterprise rests on.

Answer: B

Verification examines each step in turn and confirms it instantiates an inference rule, which is linear in the proof's length, while finding the proof required searching an enormous space. Proof length varies, domain knowledge is not needed by either, and assuming correctness would defeat the purpose. An asymmetry between constructing and verifying is what allows a complex tool to be trusted through a simple one.