Is one round of resolution enough to reach closure?

Not generally. Newly derived clauses can produce further new clauses.

Can propositional resolution closure be large?

Yes. Finiteness does not guarantee a small or inexpensive calculation.

Does the absence of the empty clause prove satisfiability?

For a genuinely completed finite propositional resolution closure, yes. A partial search does not justify that conclusion.

AI Glossary / Graphs and symbolic AI / Intermediate

Resolution closure

Definition

The resolution closure of a clause set is the collection containing its starting clauses and every clause obtainable by repeatedly applying resolution to available clauses. It is closed under the rule: another permitted resolution step adds nothing new. In finite propositional logic, this concept helps explain why exhaustive resolution can determine whether a clause set is satisfiable.

What it means

A single resolution step produces one consequence. That consequence may then combine with another clause to produce something not available after the first step. Closure includes these later consequences as well as immediate ones.

The term is about exhausting a particular inference operation, not merely stopping a program or marking a proof complete. A procedure that has considered the original pairs once has not necessarily reached closure, because newly derived clauses create additional pairs. The discussion here uses propositional clauses represented as sets of literals, with duplicate literals and duplicate clauses removed.

How it works

Start with the input clause set. Resolve eligible pairs on complementary literals and add previously unseen resolvents. Continue considering combinations involving new clauses until no new clause can be obtained.

If the empty clause appears, the input is unsatisfiable. For finite propositional clauses, resolution is refutation-complete: an unsatisfiable input has a derivation of the empty clause. If genuine closure is reached without it, the input is satisfiable.

There are only finitely many distinct clauses over a fixed finite collection of propositional symbols when repetitions are removed, although the number can be very large. Practical reasoning systems use selection and simplification techniques rather than naively storing every possible consequence. First-order settings need additional qualifications and may generate indefinitely many clauses.

Three practical examples

Logic education: enumerate the closure of a tiny clause set to see how multi-step consequences arise.
Reasoner validation: check that a saturation routine revisits combinations involving newly added clauses rather than stopping after one initial pass.
Formal consistency analysis: use the refutation-completeness result to explain what an exhaustive propositional resolution result establishes about an encoded rule set.

Think of it this way

Think of a recipe collection in which every newly created ingredient can become an input to another permitted recipe. Closure is reached only when the recipes yield nothing new. The analogy explains iteration, but logical clauses are not consumed when used, and their meaning depends on truth conditions rather than physical cooking processes.

Worked example

Take the clause set S containing A, not-A or B, and not-B or C. Resolve A with not-A or B to obtain B. Resolve not-A or B with not-B or C to obtain not-A or C. Resolve B with not-B or C to obtain C. Resolving A with not-A or C also obtains C, which is already present.

The closure for this example contains six distinct clauses: A; not-A or B; not-B or C; B; not-A or C; and C. No remaining complementary-literal pairing produces a new clause. The empty clause is absent, and the assignment A = true, B = true, C = true satisfies the original set.

Now add not-C to the input. The previous derivation of C is still available, and resolving C with not-C produces the empty clause. The enlarged input is unsatisfiable.

Notice why a single pass over the original clauses is insufficient as a general stopping rule. The unit clause C emerges through a derived clause such as B. A program that never combines newly generated clauses can miss that consequence and the eventual contradiction.

The example also distinguishes closure from a catalog of every logical consequence. For the simpler input consisting only of A, B, and C as positive unit clauses, ordinary resolution has no complementary pair to use. It does not explicitly generate A or B, even though that disjunction is logically entailed.

Illustrative case study

Fictional case: Larch Proof Workshop writes a classroom saturation tool. Its first version generates all resolvents of the initial input and stops. A chain of implications passes its consistency check even after a contradictory final literal is added.

Students replace the one-pass routine with an iterative worklist. Each newly derived clause is scheduled for the necessary comparisons, and duplicate clauses are recognized so they do not keep restarting the same work. They test the corrected logic on small truth tables whose satisfiability is independently known.

The case illustrates a termination error. A classroom implementation needs further engineering before handling large clause sets.

Common misconceptions and mistakes

Closure does not mean that every sentence logically implied by the premises appears literally in the stored collection. It is closure under the specified inference rule and representation conventions.

An interrupted search is not a completed closure calculation. Reporting “no contradiction found” after a resource limit is weaker than reporting that exhaustive propositional resolution terminated without the empty clause.

Also distinguish the empty clause from an empty set of clauses. The former is false under every assignment. The latter imposes no constraints and is satisfiable. Confusing the two reverses the meaning of a crucial result.

Business use

The concept is useful when evaluating formal reasoning claims. A team can ask whether a result rests on a complete procedure, an incomplete heuristic search, or a timeout. Those distinctions matter more than an interface simply reporting that processing has finished.

For explainability, retain derivations of important clauses and links to the original requirements. Full closure can be much larger than a short contradiction proof, so storing it all is not necessarily a sensible operational objective. The business question is usually whether constraints are consistent or a claim follows, with evidence appropriate to that question.

Check your understanding

A procedure stops because its time budget expires and has not found the empty clause. Has it established resolution closure?

Answer: No. It must establish that no further new resolvents are possible under the procedure's complete rules; elapsed time does not provide that evidence.

Related terms

Resolution
Resolvent
Clause
Satisfiability
Saturation (point operation)
Fixed point
saturation
refutation completeness
proof search

Learn next

Compute the six-clause example by hand and record each parent pair. Then add not-C and trace the contradiction. Compare the result with a truth table. Finally, study how subsumption and clause selection can avoid storing unnecessary material while preserving the intended reasoning guarantees.

Clause

Sources

Russell and Norvig, Logical Agents, completeness of resolution: https://aima.cs.berkeley.edu/2nd-ed/newchap07.pdf University of Rochester, Propositional Logic and Resolution: https://www.cs.rochester.edu/users/faculty/nelson/courses/csc_173/proplogic/resolution.html Primary material was consulted. Clause sets, closure enumeration, and fictional case are original.

Previous: Resolution Next: Resolvent