What is the empty clause?

A clause with no literals, representing a contradiction.

Is binary resolution probabilistic?

No. Standard resolution is a deductive rule in classical logic.

Does a failed proof attempt establish that a statement is false?

No. The search may be incomplete, resource-limited or still running.

AI Glossary / Graphs and symbolic AI / Advanced

Binary resolution

Definition

Binary resolution is a logical inference rule that combines two clauses by eliminating one complementary pair of literals and retaining the remaining alternatives. In first-order logic, unification makes the selected positive and negative literals match before the rule is applied.

What it means

A literal is an atomic proposition or its negation. A clause is a disjunction of literals: it says that at least one listed alternative holds. Binary resolution uses the fact that a proposition and its negation cannot both be false.

For example, from P OR Q and NOT P OR R, infer Q OR R. If P is false, the first clause requires Q. If P is true, the second requires R. Either way, at least one of Q and R must hold.

The result is called a resolvent. It is a logical consequence of the parent clauses, not a statistical prediction or a negotiated compromise. Binary refers to combining two parent clauses and resolving a selected complementary pair; it does not mean that the original problem contains only two facts.

This rule is central to automated theorem proving. Its usefulness depends on accurate formalization, sound supporting operations and a search strategy capable of finding relevant inferences.

How it works

For propositional clauses, select P in one clause and NOT P in the other. Remove those selected occurrences and form the disjunction of what remains. Do not cancel every complementary pair simultaneously; that can produce an unjustified contradiction.

For first-order clauses, first rename variables from different clauses so their names do not accidentally impose shared bindings. Find a unifying substitution for the selected atomic expressions, then apply it consistently to the remaining literals as well as the selected pair.

To prove a query by refutation, add its negation to the premises and search for a contradiction. An empty clause represents false: there are no remaining alternatives that could satisfy it. Deriving it shows that the premises together with the negated query cannot all hold.

Binary resolution alone is not a complete first-order refutation calculus. Factoring, which merges unifiable literals within a clause under an appropriate substitution, supplies an essential additional rule. Equality also requires suitable treatment, such as equality axioms or specialized inference machinery.

Even a complete calculus does not mean every practical search terminates. First-order proof search can continue indefinitely on cases where no contradiction is derivable.

Three practical examples

A theorem prover checks whether a formally stated conclusion follows from a set of mathematical assumptions by refuting its negation.
A rule-consistency checker uses clause reasoning to expose a combination of requirements that cannot all be satisfied.
An educational logic tool displays parent clauses, selected literals and substitutions so learners can inspect each proof step.

Think of it this way

Think of two notices: either the package is at the counter or in the locker; either it is not at the counter or a collection record exists. Together they imply that it is in the locker or a collection record exists.

The analogy concerns the stated alternatives only. It does not establish that the notices are accurate, and resolution cannot compensate for an omitted possibility in the original description.

Worked example

A short first-order refutation

Use the rule Ready(x) ⇒ Checked(x). In clause form this is NOT Ready(x) OR Checked(x). Add the fact Ready(Box7). Ask whether Checked(Box7) follows.

Negate the query to obtain NOT Checked(Box7). Resolve the rule with Ready(Box7), using substitution x → Box7. The complementary Ready literals disappear, leaving Checked(Box7). Resolving that result with NOT Checked(Box7) produces the empty clause.

The contradiction depends on the negated query together with the stated premises, so the original premises entail Checked(Box7). It does not prove that Box7 was physically inspected; it proves the consequence of the formal rule and fact.

For a cancellation trap, consider P OR Q and NOT P OR NOT Q. Resolving on P yields Q OR NOT Q, a tautology. It does not yield the empty clause. Indeed, P true and Q false satisfies both parent clauses, showing why canceling both pairs at once would be unsound.

Illustrative case study

Fictional case: Larch Rules builds a checker for a packing workflow. An early prototype treats any opposing literals across two clauses as removable and reports contradictions too aggressively.

The team adds proof-step records and uses tiny truth-table cases to test each inference. The two-clause cancellation example reveals the defect. After correcting it, reviewers separately examine whether the business rules accurately describe readiness and inspection.

The lesson is that an impressive-looking proof trace needs both sound inference steps and justified premises. A formal engine can correctly expose consequences of a mistaken rule without validating the rule's real-world meaning.

Common misconceptions and mistakes

Resolution proves that the premises are true. It derives consequences under those premises.
All complementary pairs may be canceled at once. A binary resolution step selects one pair.
First-order matching affects only the removed literals. The substitution must apply throughout the resolvent.
No contradiction found before timeout means consistency. A timeout is not a completed proof of satisfiability.
Binary resolution alone handles every first-order proof obligation. Factoring and appropriate equality treatment matter.

Business use

Resolution helps explain the foundations of symbolic reasoning and proof-producing systems. For business use, the practical deliverable is often a checkable explanation of which formal requirements conflict or support a conclusion.

Keep source requirements linked to their formal clauses. Require clear distinctions among proved, disproved and unresolved results. If a system reports inconsistency, inspect the contributing premises and their translations before changing operations. Proof search performance should be evaluated alongside the ability to audit individual steps and identify assumptions.

Check your understanding

Resolving P OR Q with NOT P OR R on P produces what?

Answer: Q OR R. The rule does not separately establish Q or R, because either remaining alternative can satisfy the consequence.

Related terms

Clause
Literal
Unification
Factoring
Refutation
Conjunctive normal form
substitution
automated theorem proving

Learn next

Construct a truth table for the two parent clauses in the question and verify that their resolvent is true whenever both parents are true. Then repeat the worked first-order proof, explicitly writing the substitution beside every affected literal.

Literal

Sources

University of Miami, resolution notes covering propositional and first-order binary resolution and factoring: https://www.cs.miami.edu/home/geoff/Courses/TPTPSYS/FirstOrder/Resolution.shtml

AIMA glossary, binary resolution: https://github.com/aimacode/aima-glossary/blob/master/glossary.md?plain=1

The Box7 proof, cancellation check and fictional workflow are original examples.

Previous: Binary regression Next: Binary search