Inference and Resolution Questions and Answers

Answer: A

A clause is a disjunction, so it is satisfied if any of its literals is true, and a formula in conjunctive normal form is a set of clauses all of which must hold. Conjunctions of literals are terms in the dual form, and rules are one reading of a particular kind of clause. Precise vocabulary for each level of structure is what allows an algorithm to be described without ambiguity.

Answer: B

Since a clause is a disjunction, one true literal suffices and the clause may then be ignored for the remainder of the search. Requiring all of them would be a conjunction. Unassigned literals leave the clause undetermined, and removal is a consequence rather than the definition. Knowing the condition under which part of a problem may be set aside is what allows a search to shrink as it proceeds.

Answer: C

A clause is falsified only when every literal has been assigned false, at which point the current assignment cannot be extended to a solution and the solver must backtrack. A single false literal merely shortens it. The other conditions are not meaningful. Recognising exactly when a partial assignment is proved hopeless, rather than merely looking unpromising, is what makes the pruning sound.

Answer: D

With every other literal false, the remaining one must be true if the clause is to be satisfied, so the assignment is forced rather than chosen. Cascading such forced assignments is unit propagation, which dominates the run time of a modern solver. The other descriptions apply to different clause states. Distinguishing the four states a clause may be in is the whole of the bookkeeping a satisfiability solver performs.

Answer: A

Tracking whether a clause is already true, already false, forcing a single assignment or still open is exactly what the solver's data structures maintain, and doing so efficiently with watched literals is a large part of a modern implementation's speed. The other lists describe clause origins, resolution operations and literal polarities. Reducing a data structure's job to four states, and then implementing the transitions efficiently, is how a conceptually simple algorithm becomes a fast one.

Answer: B

Watching two unassigned literals per clause means a clause need only be inspected when one of its watches is falsified, which avoids visiting every clause on every assignment. It is the single most important implementation trick in a modern solver. Frequency, conflict statistics and assignment stacks are different mechanisms. An implementation technique that changes the constant factor by an order of magnitude deserves to be named alongside the algorithmic ideas.

Answer: C

So long as two literals remain unassigned the clause is neither unit nor conflicting, so it need not be examined, and only when a watch is falsified must a replacement be sought. Determining truth requires all the literals, clause lengths vary widely, and the watches move during the search. An invariant that guarantees a data structure need not be consulted is exactly what makes lazy updating correct as well as fast.

Answer: D

Each chosen assignment opens a new level, and everything propagated from it belongs to that level, so backjumping means returning to a specified earlier level. Conflict analysis computes which level to return to. Unsatisfied counts, priorities and watches are different quantities. Organising the assignment trail by decision level is what makes non-chronological backtracking expressible at all.

Answer: A

Conflict analysis identifies the earliest level at which the learned clause becomes unit, and the solver jumps directly there, skipping levels that had nothing to do with the conflict. Chronological backtracking would undo one decision at a time. Clause age, reverse order and restarting are different mechanisms. Returning to the decision actually responsible, rather than the most recent one, is the same idea as conflict directed backjumping in constraint solving.

Answer: B

The proof lets a small independent checker confirm that the clause set really is unsatisfiable, which is essential when the result underwrites a safety argument. It slows the solver and consumes memory rather than saving it, and the proofs are far too large for a human to read. Producing checkable evidence for a claim, so that the producing tool need not be trusted, is the assurance argument in its most concrete form.