Inference and Resolution Questions and Answers

Q: What is a definite clause?

Definite clauses correspond exactly to rules with a single conclusion, and forward and backward chaining over them are sound, complete and run in linear time. Horn clauses allow zero or one positive literal, the extra case being the goal clause. Instantiation and provability are different notions. A restriction whose members are exactly the rules people naturally write is unusually convenient, and it explains why so many practical systems are built on it.

Q: What is the complexity of forward chaining over definite clauses?

With appropriate indexing each rule fires at most once per satisfying substitution, giving a linear procedure that derives every consequence. Function symbols do make the set of derivable facts infinite, which is a genuine caveat rather than the general answer. The other figures overstate the cost. A complexity result that holds under a stated restriction, with the restriction's violation changing the answer completely, is worth stating with the condition attached.

Q: Why can forward chaining fail to terminate with function symbols?

A rule deriving a successor from every number will generate an unbounded sequence of ground terms, so saturation never completes. Datalog forbids function symbols precisely to keep the derived set finite. Cycles alone are handled by not repeating derivations, unification terminates, and indexing is an efficiency matter. Identifying the syntactic feature responsible for an unbounded computation is what allows a decidable fragment to be carved out deliberately.

Q: What is Datalog?

Forbidding function symbols keeps the set of derivable facts finite, so forward chaining terminates and the language is decidable, which makes it suitable for deductive databases. Recursion is permitted and is its main advantage over relational query languages. Schema description, negation and graph querying are different things, though modern variants add some of them. A deliberate restriction adopted to obtain decidability is the same design move that produced description logics.

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.

21.

What is a definite clause?

A.A clause with exactly one positive literal
B.A clause with no negative literals at all
C.A clause whose variables are all instantiated
D.A clause that has been definitely proved true

Answer: A

Definite clauses correspond exactly to rules with a single conclusion, and forward and backward chaining over them are sound, complete and run in linear time. Horn clauses allow zero or one positive literal, the extra case being the goal clause. Instantiation and provability are different notions. A restriction whose members are exactly the rules people naturally write is unusually convenient, and it explains why so many practical systems are built on it.

Discuss in Forum

22.

What is the complexity of forward chaining over definite clauses?

A.Undecidable when function symbols are permitted
B.Linear in the size of the knowledge base
C.Exponential in the number of rules present
D.Quadratic in the number of facts derived

Answer: B

With appropriate indexing each rule fires at most once per satisfying substitution, giving a linear procedure that derives every consequence. Function symbols do make the set of derivable facts infinite, which is a genuine caveat rather than the general answer. The other figures overstate the cost. A complexity result that holds under a stated restriction, with the restriction's violation changing the answer completely, is worth stating with the condition attached.

Discuss in Forum

23.

Why can forward chaining fail to terminate with function symbols?

A.Unification does not terminate on terms with functions
B.The knowledge base grows faster than it can be indexed
C.The set of derivable ground facts may be infinite
D.The rules may contain cycles that repeat indefinitely

Answer: C

A rule deriving a successor from every number will generate an unbounded sequence of ground terms, so saturation never completes. Datalog forbids function symbols precisely to keep the derived set finite. Cycles alone are handled by not repeating derivations, unification terminates, and indexing is an efficiency matter. Identifying the syntactic feature responsible for an unbounded computation is what allows a decidable fragment to be carved out deliberately.

Discuss in Forum

24.

What is Datalog?

A.A language for describing the structure of a database
B.A logic programming language with negation as failure
C.A query language for graphs of entities and relations
D.A definite clause language without function symbols

Answer: D

Forbidding function symbols keeps the set of derivable facts finite, so forward chaining terminates and the language is decidable, which makes it suitable for deductive databases. Recursion is permitted and is its main advantage over relational query languages. Schema description, negation and graph querying are different things, though modern variants add some of them. A deliberate restriction adopted to obtain decidability is the same design move that produced description logics.

Discuss in Forum

25.

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

26.

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

27.

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

28.

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

29.

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

30.

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

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