Why can an earlier derived clause be reused?

Linear resolution permits ancestor clauses on the current derivation chain as side clauses.

Does linear mean the proof search is fast?

No. It describes a restriction on proof structure, not a general runtime guarantee.

What does an empty clause mean?

It represents falsehood and therefore demonstrates inconsistency of the input clauses under the logic used.

AI Glossary / Graphs and symbolic AI / Advanced

Linear resolution

Definition

Linear resolution is a strategy for organizing resolution proofs around a continuing chain of derived clauses. The current clause is resolved with an input clause or with an ancestor clause already on that proof chain. Allowing ancestor clauses makes the strategy more general than input resolution.

What it means

Resolution is a rule for combining clauses containing complementary literals, such as P and not P. A strategy determines which permitted combinations a proof search explores. Linear resolution restricts the shape of the derivation while retaining a way to reuse earlier clauses on its central chain.
The word linear describes proof structure. It does not promise linear running time, a short proof, or a single possible search path. The prover may still need to try many starting clauses and resolution choices. This is a logic term, distinct from linear resolution in some areas of algebra.

How it works

A proof begins with an input clause. Each step resolves the current central clause against an eligible side clause, producing the next central clause. An input clause is eligible; an ancestor on the same chain can also be eligible. Arbitrary unrelated derived clauses are not simply interchangeable with ancestors.
For first-order clauses, complementary literals must be unified, with variable handling and factoring treated correctly. In refutation, reaching the empty clause establishes that the input clause set is inconsistent. To prove a query, the input normally includes the negation of that query alongside the knowledge base. The method is refutation-complete under its standard calculus and adequate search conditions.

Three practical examples

An automated-reasoning lesson can compare input-only derivations with derivations that reuse a chain ancestor.
A proof-checking tool can record the two parent clauses and resolved literals for each inference.
A symbolic-rule project can use refutation to investigate whether a set of formalized requirements is inconsistent, while keeping the inference trace available for review.

Think of it this way

Think of a running calculation that can combine its latest result with an original premise or an earlier result from the same calculation. That produces a visible central thread. The analogy is limited because resolution has exact rules about complementary literals and substitutions; combining two statements intuitively is not enough.

Worked example

Consider four propositional input clauses, where OR is inclusive and NOT is negation:
C1: P OR Q.
C2: NOT P OR Q.
C3: P OR NOT Q.
C4: NOT P OR NOT Q.
Start the central chain with C1. Resolve C1 with input C2 on P and NOT P. The remaining literals are Q OR Q, which simplifies to Q because repeating a literal does not change the clause.
Next, resolve current clause Q with input C3 on Q and NOT Q. The result is P. Resolve that current P with input C4 on P and NOT P. The result is NOT Q.
Finally, resolve current NOT Q with the earlier central clause Q. These are complementary unit clauses, so the result is the empty clause. The final side clause Q is an ancestor on the chain; it is not one of the four original inputs. That step illustrates the additional permission in linear resolution.
As an independent check, there are four truth assignments for P and Q. Both false violates C1; P true and Q false violates C2; P false and Q true violates C3; both true violates C4. Thus no assignment satisfies all four clauses, agreeing with the refutation.
The example is propositional, so it avoids first-order variable complications. It shows one valid proof, not a claim that every sequence of allowable choices will immediately find the contradiction.

Illustrative case study

In a fictional rule-audit project, Cedar Logic stores proof steps but labels every reused derived clause as an input. A reviewer cannot tell which proof strategy was actually followed, even though the individual resolutions may be valid.
The team records whether each side clause is original or an ancestor, and links every derived clause to its parents. This invented case illustrates the difference between validating an inference and validating a strategy restriction. It makes no claim that a particular commercial theorem prover implements this exact strategy.

Common misconceptions and mistakes

Linear resolution is not the same as input resolution. Input resolution requires an original input clause in each inference; the ancestor option is the relevant extension. It is also not the same as unit resolution, which restricts inference by requiring a unit clause.
Completeness must not be confused with guaranteed termination on every first-order input or success under an arbitrary unfair search order. A sound refutation establishes inconsistency of the encoded premises, not accuracy of those premises about the real world. Conversely, failure to find a refutation within a time limit does not establish consistency.

Business use

For business-facing symbolic systems, the useful principle is traceable inference. Preserve the source of each formal rule, the representation used, and the proof steps that produce a conclusion. That makes a detected inconsistency easier to investigate than an unexplained error indicator.
Keep mathematical verification separate from domain review. A proof may correctly expose a contradiction introduced by mistranslating a policy into logic. If a reasoning service stops because of a resource limit, report that outcome accurately. Do not convert an unfinished proof search into a positive claim that a requirement set is safe, complete, or consistent.

Check your understanding

Which step in the worked example uses the permission that distinguishes linear resolution from input resolution?

Answer: The final step resolves NOT Q with the previously derived Q. That Q is an ancestor central clause rather than an original input clause.

Related terms

Learn next

Draw the worked proof as a central chain, attaching each side clause beside its inference. Mark original clauses differently from ancestor clauses. Then study a first-order resolution example to see how substitutions add another correctness requirement beyond the propositional trace.

Sources

Russell and Norvig, Artificial Intelligence: A Modern Approach, first-order inference chapter, resolution strategies and input resolution: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap09.pdf

Previous: Linear relationship Next: Linear search