Does deriving the empty clause prove the rules are inconsistent?

Yes, if the starting clauses and every inference step are valid within the chosen logic.

Does failing to find it immediately prove consistency?

No. A partial search may simply not have found the refutation yet.

Why is the theorem called ground?

It concerns clauses without variables, which can be handled propositionally; first-order completeness needs additional reasoning about instances and lifting.

AI Glossary / Mathematics and optimization / Advanced

Ground resolution theorem

Definition

The ground resolution theorem states that an unsatisfiable set of ground clauses has a resolution derivation of the empty clause. Ground clauses contain no variables, so their atoms can be treated propositionally for this purpose. The theorem establishes completeness for detecting contradiction by resolution at the ground level. Together with the soundness of resolution, it means that deriving the empty clause is exactly the relevant contradiction test when the required search is carried out completely.

What it means

A clause is a disjunction of literals, and a literal is an atom or its negation. A set of clauses requires all its clauses to hold simultaneously. Unsatisfiable means that no truth assignment can make them all true. Resolution combines clauses containing complementary literals to infer another clause. The empty clause contains no alternatives that could be true, so it represents falsehood. The theorem explains why resolution is not merely a useful trick: a contradiction in a ground clause set cannot remain hidden from its full resolution closure.

How it works

From clauses A ∨ P and B ∨ ¬P, resolution derives A ∨ B, where A and B stand for the remaining literals. This step is sound because any assignment satisfying both premises must satisfy the resolvent. The resolution closure contains the starting clauses and every clause obtainable through repeated valid resolution. The theorem says that unsatisfiability forces the empty clause into that closure. For a finite propositional input, exhaustive generation of distinct relevant clauses can terminate, although it may be expensive. A restricted or interrupted search is not the same as computing the full closure.

Three practical examples

A rule-consistency checker can use ground clauses to expose a contradiction in a finite configuration specification.
A theorem-proving lesson can demonstrate entailment by adding the negation of a proposed conclusion and deriving the empty clause.
A proof checker can inspect each resolution step in a generated refutation, separating proof verification from the potentially difficult search that discovered it.

Think of it this way

Think of a set of requirements that eventually leaves no permitted alternative. Resolution removes one opposed pair of alternatives at a time while preserving what must still hold. The analogy has limits: ordinary arguments can involve ambiguity or uncertain facts, while the theorem concerns precisely encoded clauses and classical truth conditions. It does not certify that the original requirements accurately describe the world.

Worked example

Let P mean that a component is enabled, Q that a backup is enabled and R that a service runs. Consider four clauses: C1 = P ∨ Q; C2 = ¬P ∨ R; C3 = ¬Q ∨ R; and C4 = ¬R. Resolve C2 with C4 on R to obtain C5 = ¬P. Resolve C3 with C4 on R to obtain C6 = ¬Q. Resolve C1 with C5 on P to obtain C7 = Q. Finally, resolve C7 with C6 to obtain the empty clause. No assignment can satisfy all four original clauses: C4 forces R false, which forces P and Q false through C2 and C3, contradicting C1. For an entailment interpretation, take only C1 - C3 as the knowledge base and ask whether R follows. Adding ¬R gives the same refutation, establishing that the knowledge base entails R. If C4 is removed and no query negation is added, P true, Q false and R true is a satisfying assignment. The example also distinguishes an empty clause, which is false, from an empty set of clauses, which places no requirements and is satisfiable.

Illustrative case study

In a fictional configuration review, Alder Systems translates a small set of service dependencies into clauses. A checker returns a resolution refutation, and engineers trace each derived clause to the original requirements. They discover that one requirement forbids a service that another combination necessarily enables. The proof identifies inconsistency in the encoding; the team still determines whether the intended requirement or its translation should change. The case does not claim that a theorem prover can resolve an ambiguous policy automatically.

Common misconceptions and mistakes

Refutation completeness does not mean every possible search strategy quickly finds a contradiction. A strategy can repeatedly explore unhelpful inferences or stop too early. The empty clause must not be confused with no clauses. Removing more than one complementary pair indiscriminately can produce an invalid inference. Ground atoms such as P(a) are treated as propositional units here; variables and unification belong to the first-order extension. Equality with its intended semantics needs suitable treatment rather than being assumed to follow from ordinary propositional resolution alone. The theorem also does not assert polynomial-time proof search.

Business use

For a finite rule application, preserve the translation from requirements to clauses and keep a checkable proof trace. Distinguish a proved contradiction, a satisfying assignment and a search that ended without a conclusion. Use the appropriate logic for the modeled relationships and do not silently interpret missing facts as false unless that is part of the specification. Technical teams should separate confidence in the inference rules from confidence in the input facts. A correct refutation can expose a modeling mistake just as readily as a genuine conflict in requirements.

Check your understanding

In the worked example, what does adding ¬R and deriving the empty clause establish about C1 - C3?

Answer: It establishes that every assignment satisfying C1 - C3 makes R true, so those clauses entail R.

Related terms

Resolution
Clause
Satisfiability
Herbrand's theorem
empty clause
refutation completeness

Learn next

check each resolvent in the example by identifying the single complementary pair used. Construct a truth table for the original three-clause knowledge base and confirm that R is true in every satisfying row. Then explain why a timeout is different from a completed satisfiability result.

Sources

Sources: Temple University, CIS587 Logic Part 2, resolution and ground resolution theorem, https://cis.temple.edu/~ingargio/cis587/readings/logic2.html ; Russell and Norvig, AIMA propositional-logic chapter, https://aima.cs.berkeley.edu/newchap07.pdf . Temple's lecture and AIMA's ground resolution, finite closure and empty-clause passages were reviewed directly; an earlier AIMA PDF fetch had failed. The service clauses and refutation are original.

Previous: Grossberg network Next: Ground term