Inference and Resolution Questions and Answers

Q: What is the matching problem in a rule based system?

With thousands of rules and facts, testing every rule against every combination of facts after each change is prohibitive, and matching dominates the run time of such systems. Conflict resolution, which chooses among eligible rules, is the separate next step. Resolution pairing and unification are different operations. A step that appears to be bookkeeping and turns out to dominate the cost is worth identifying early, since optimising it is where the effort belongs.

Q: How does a discrimination network reduce matching cost?

A network such as Rete keeps the partial matches computed so far and updates them incrementally as facts are added or removed, so the work is proportional to the change rather than to the size of the base. The price is considerable memory. Rule ordering, compression and decision trees are different techniques. Trading memory for incremental rather than complete recomputation is a pattern that recurs wherever a system responds to a stream of small changes.

Q: What is the Davis Putnam procedure?

The procedure assigns a variable, propagates the consequences, and backtracks when a clause becomes empty, which is the basis of every modern satisfiability solver. Its two key inferences are unit propagation and the pure symbol rule. Conversion, resolution restriction and model enumeration are different activities. A sixty year old algorithm still at the heart of state of the art tools, after decades of refinement, is unusual and worth noticing. Reading the definition literally, rather than recalling a formula, is the reliable route through questions of this shape.

Q: What is unit propagation?

A clause reduced to a single unassigned literal forces that literal true, and doing so may reduce further clauses to units, cascading through the formula. It is by far the most important inference in a satisfiability solver and consumes most of its run time. Variable selection and clause deletion are different steps. An inference that is forced rather than chosen, and that cascades, is exactly what should be performed exhaustively before any search decision is made.

Q: What is the pure symbol rule?

If a variable never appears negated, setting it true satisfies every clause containing it and can never hurt, so the assignment is safe without any search. It is a cheap inference that becomes rarer as the formula is reduced. The other options describe unrelated rules. An inference that is safe rather than merely plausible, and therefore requires no backtracking point, is worth applying whenever it is available.

Q: What is conflict driven clause learning?

When a conflict occurs, analysing the implication graph yields a clause capturing the cause, which is added permanently and prevents the same combination from being explored again. With restarts it transformed satisfiability solving from thousands to millions of variables. Variable ordering, exhaustive recording and preprocessing are different techniques. Converting a failure into a permanent constraint is the same idea as no-good learning in constraint solving, arrived at independently.

Q: Why is a learned clause more useful than simply backtracking?

The learned clause records why the conflict occurred, so any future path recreating that cause, in any order, is cut immediately, whereas chronological backtracking would rediscover it repeatedly. Variable counts rise as clauses are added, the exclusion is far broader than one assignment, and no guarantee follows. Generalising from a specific failure to the condition responsible is what makes the learning worth its memory.

Q: What is the role of restarts in a satisfiability solver?

An unlucky early decision can trap the search for a very long time, and restarting with different heuristics while retaining the learned clauses escapes without losing progress. Clause deletion policies manage memory separately. Combined with learning, restarts turn a heavy tailed runtime into a manageable one. Two mechanisms that are modest alone and transformative together are worth remembering as a pair, since neither explains the improvement by itself.

Q: What is a local search approach to satisfiability?

Algorithms such as WalkSAT start from a random complete assignment and repeatedly flip a variable from an unsatisfied clause, mixing greedy and random choices. They solve very large satisfiable instances quickly and can never prove unsatisfiability. The other options describe unrelated procedures. The same division between complete systematic methods and incomplete local ones, with the same asymmetry about proving absence, appears here as in every other search setting.

Q: Why can a local search satisfiability solver not prove unsatisfiability?

Failing to find a satisfying assignment establishes only that none was found, since the method samples rather than enumerates. Systematic solvers with learning can exhaust the space and produce a refutation proof. Clause evaluation and initialisation are unaffected. Knowing what may be concluded from a negative result decides which family a task requiring a proof must use, and it is the same consideration that arises in constraint satisfaction. Working one numerical case through both cases side by side fixes the distinction better than any rule of thumb.

21.

What is the matching problem in a rule based system?

A.Finding which rules have all their conditions satisfied
B.Determining which of two clauses may be resolved
C.Deciding whether any two terms can be unified successfully
D.Choosing which rule to fire when several are eligible

Answer: A

With thousands of rules and facts, testing every rule against every combination of facts after each change is prohibitive, and matching dominates the run time of such systems. Conflict resolution, which chooses among eligible rules, is the separate next step. Resolution pairing and unification are different operations. A step that appears to be bookkeeping and turns out to dominate the cost is worth identifying early, since optimising it is where the effort belongs.

Discuss in Forum

22.

How does a discrimination network reduce matching cost?

A.It converts the rules into an equivalent decision tree
B.It stores partial matches so only changes are reprocessed
C.It orders the rules so the most likely are tried first
D.It compresses the whole rule base into fewer equivalent rules

Answer: B

A network such as Rete keeps the partial matches computed so far and updates them incrementally as facts are added or removed, so the work is proportional to the change rather than to the size of the base. The price is considerable memory. Rule ordering, compression and decision trees are different techniques. Trading memory for incremental rather than complete recomputation is a pattern that recurs wherever a system responds to a stream of small changes.

Discuss in Forum

23.

What is the Davis Putnam procedure?

A.A resolution strategy restricted to unit clauses only
B.A technique for enumerating all models of a formula
C.A backtracking search for a satisfying assignment with propagation
D.A method for converting formulas to conjunctive normal form

Answer: C

The procedure assigns a variable, propagates the consequences, and backtracks when a clause becomes empty, which is the basis of every modern satisfiability solver. Its two key inferences are unit propagation and the pure symbol rule. Conversion, resolution restriction and model enumeration are different activities. A sixty year old algorithm still at the heart of state of the art tools, after decades of refinement, is unusual and worth noticing. Reading the definition literally, rather than recalling a formula, is the reliable route through questions of this shape.

Discuss in Forum

24.

What is unit propagation?

A.Propagating an assignment through the whole clause set at once
B.Choosing the variable appearing in the most unit clauses
C.Removing every clause containing exactly one literal
D.Assigning the only remaining literal of a unit clause

Answer: D

A clause reduced to a single unassigned literal forces that literal true, and doing so may reduce further clauses to units, cascading through the formula. It is by far the most important inference in a satisfiability solver and consumes most of its run time. Variable selection and clause deletion are different steps. An inference that is forced rather than chosen, and that cascades, is exactly what should be performed exhaustively before any search decision is made.

Discuss in Forum

25.

What is the pure symbol rule?

A.A symbol appearing with only one polarity may be assigned that way
B.A symbol appearing in only one clause may be ignored entirely
C.A symbol appearing in every clause must be assigned first
D.A symbol with no assignment is treated as false by default

Answer: A

If a variable never appears negated, setting it true satisfies every clause containing it and can never hurt, so the assignment is safe without any search. It is a cheap inference that becomes rarer as the formula is reduced. The other options describe unrelated rules. An inference that is safe rather than merely plausible, and therefore requires no backtracking point, is worth applying whenever it is available.

Discuss in Forum

26.

What is conflict driven clause learning?

A.Deriving all consequences of the clauses before searching
B.Deriving a new clause from each conflict to prevent its recurrence
C.Learning which variables to assign first from experience
D.Recording every assignment that has been tried and failed

Answer: B

When a conflict occurs, analysing the implication graph yields a clause capturing the cause, which is added permanently and prevents the same combination from being explored again. With restarts it transformed satisfiability solving from thousands to millions of variables. Variable ordering, exhaustive recording and preprocessing are different techniques. Converting a failure into a permanent constraint is the same idea as no-good learning in constraint solving, arrived at independently.

Discuss in Forum

27.

Why is a learned clause more useful than simply backtracking?

A.It allows the solver to skip the conflicting assignment only
B.It guarantees that the next branch will succeed
C.It rules out every future assignment sharing the same cause
D.It reduces the number of variables in the formula

Answer: C

The learned clause records why the conflict occurred, so any future path recreating that cause, in any order, is cut immediately, whereas chronological backtracking would rediscover it repeatedly. Variable counts rise as clauses are added, the exclusion is far broader than one assignment, and no guarantee follows. Generalising from a specific failure to the condition responsible is what makes the learning worth its memory.

Discuss in Forum

28.

What is the role of restarts in a satisfiability solver?

A.Restarting the solver when it runs out of memory
B.Beginning again with a different clause ordering each time
C.Resetting all the learned clauses to avoid excessive memory use
D.Abandoning a bad search path while keeping the learned clauses

Answer: D

An unlucky early decision can trap the search for a very long time, and restarting with different heuristics while retaining the learned clauses escapes without losing progress. Clause deletion policies manage memory separately. Combined with learning, restarts turn a heavy tailed runtime into a manageable one. Two mechanisms that are modest alone and transformative together are worth remembering as a pair, since neither explains the improvement by itself.

Discuss in Forum

29.

What is a local search approach to satisfiability?

A.Flipping variables in a complete assignment to reduce violations
B.Searching only a local region of the clause set at a time
C.Assigning variables in the order they appear in the formula
D.Solving each of the clauses independently before combining the results

Answer: A

Algorithms such as WalkSAT start from a random complete assignment and repeatedly flip a variable from an unsatisfied clause, mixing greedy and random choices. They solve very large satisfiable instances quickly and can never prove unsatisfiability. The other options describe unrelated procedures. The same division between complete systematic methods and incomplete local ones, with the same asymmetry about proving absence, appears here as in every other search setting.

Discuss in Forum

30.

Why can a local search satisfiability solver not prove unsatisfiability?

A.It requires a satisfying assignment to exist before starting
B.It never exhausts the space of assignments
C.It cannot evaluate whether a clause is satisfied
D.It always terminates before the search is complete

Answer: B

Failing to find a satisfying assignment establishes only that none was found, since the method samples rather than enumerates. Systematic solvers with learning can exhaust the space and produce a refutation proof. Clause evaluation and initialisation are unaffected. Knowing what may be concluded from a negative result decides which family a task requiring a proof must use, and it is the same consideration that arises in constraint satisfaction. Working one numerical case through both cases side by side fixes the distinction better than any rule of thumb.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Inference and Resolution Questions and Answers || Inference and Resolution MCQ Questions and Answers || Inference and Resolution GK Questions and Answers || Inference and Resolution GK MCQ Questions || Inference and Resolution Multiple Choice Questions and Answers || Inference and Resolution GK || GK on Inference and Resolution || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Inference and Resolution Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications