Inference and Resolution Questions and Answers

Answer: C

Because the checker is small it can itself be scrutinised, so trust in a large prover reduces to trust in a few hundred lines. That arrangement is called the de Bruijn criterion. Searching, translating and rule selection belong to the prover rather than the checker. Concentrating the trust in the smallest possible component is a security and assurance principle that applies well beyond theorem proving.

Answer: D

In an interactive system the human supplies the structure and the difficult steps while the machine handles the routine ones and guarantees correctness. Large mathematical results and operating system kernels have been verified this way. Progress reporting, interruption and question asking are interface features. Dividing labour between a human's judgement and a machine's rigour, rather than seeking full automation, is what made large verifications achievable.

Answer: A

Tactics let a user apply a whole family of routine steps with one command, and tactics may be composed into larger ones, which is what makes large proofs manageable. The user builds a vocabulary suited to the domain being formalised. Conjecture selection, search heuristics and history are different notions. Providing a language in which the user can extend the tool's repertoire is what allows a general system to become specialised without being rewritten.

Answer: B

The two answer different questions, though refutation connects them, since proving a theorem amounts to showing a formula unsatisfiable. Both exist for both logics, both may be automatic, and satisfiability solvers are complete. Recognising that two tools answer questions that a single identity converts into one another is what allows a problem to be handed to whichever has the better implementation.

Answer: C

Decades of engineering have made satisfiability solvers extraordinarily fast, so bounding a problem and encoding it propositionally often beats reasoning in the natural formalism. The cost is the loss of generality that bounding entails. Sound procedures exist for richer logics, constraints must still be encoded, and expressiveness runs the other way. Choosing the formalism with the best tools, rather than the most natural one, is a pragmatic move worth considering explicitly.

Answer: D

Unrolling a system's transitions to a fixed depth and asking a satisfiability solver whether a violation occurs within them finds shallow bugs very effectively. Absence of a counterexample within the bound proves nothing beyond it unless a completeness threshold is established. Model size, memory and single steps are different restrictions. A method that finds errors reliably without proving their absence is valuable precisely because errors are what most projects have.

Answer: A

Experience shows that the great majority of design errors manifest within a handful of transitions, so a bounded search finds them at a fraction of the cost of a full proof. Raising the bound indefinitely is not generally feasible, absence within a bound proves nothing beyond it, and a specification is still required. A technique that addresses the common case cheaply, while leaving the rare case to a more expensive method, is a sound division of effort. Working one numerical case through both cases side by side fixes the distinction better than any rule of thumb.

Answer: B

A rule is a syntactic pattern: given premises of this shape, this conclusion may be written. Soundness means every such conclusion is entailed. Guidelines, constraints and decision procedures are different notions. That a rule is purely a matter of form, checkable without any understanding of what the sentences mean, is exactly what makes mechanical proof possible.

Answer: C

Soundness is a semantic property established by an argument about models, even though the rule itself is purely syntactic. Efficiency, convention and length are unrelated. The bridge between a syntactic rule and a semantic guarantee is what a soundness proof supplies, and it is the reason a mechanically applied pattern can be trusted to preserve truth.

Answer: D

Resolving on a complementary pair removes both and unions the remainder, so the resolvent is entailed by the two parents. In the first order case a unifying substitution is applied first. Discarding, plain union and simplification describe different operations. Knowing exactly what a rule produces, rather than roughly what it does, is what allows an implementation to be written correctly at the first attempt.