— Ch. 1 · Historical Origins And Evolution —
Resolution (logic).
~4 min read · Ch. 1 of 6
In 1960, Martin Davis and George Putnam published an algorithm that attempted to solve logical problems by trying every possible ground instance of a given formula. This approach created a massive source of combinatorial explosion that made the method impractical for complex tasks. The breakthrough arrived in 1965 when John Alan Robinson introduced a syntactical unification algorithm. Robinson's innovation allowed mathematicians to instantiate formulas on demand during the proof process rather than beforehand. This change preserved refutation completeness while eliminating the need to generate all instances at once. The resolution rule itself traces back to their earlier work but gained its modern power through this specific unification step.
Propositional Logic Mechanics
The resolution rule operates as a single valid inference rule within propositional logic systems. It produces a new clause implied by two clauses containing complementary literals. A literal represents either a propositional variable or the negation of one. Two literals are complements if one is the direct negation of the other. The resulting clause contains all literals from the input pairs that do not have complements. When coupled with a complete search algorithm, this technique yields a sound and complete decision procedure for formula satisfiability. Any sentence in propositional logic can be transformed into conjunctive normal form before applying the inference method. The steps involve connecting sentences in the knowledge base with the negation of the conjecture to be proved. The resulting sentence transforms into a set of clauses viewed as elements in S. Applying the rule to all possible pairs generates resolvents that simplify repeated literals. If an empty clause derives, the original formula proves unsatisfiable. Tree representations show how the binary nature of the rule relates to cut-rules in sequent notation.First-Order Generalization Techniques
John Alan Robinson generalized the resolution rule to first-order logic using most general unifiers. This extension allows variables like X to unify with constants such as b during proof construction. Consider the syllogism where all Greeks are Europeans and Homer is a Greek. The conclusion states Homer is a European. To recast this reasoning, clauses convert to conjunctive normal form where universal quantifiers become implicit. Existentially-quantified variables replace Skolem functions in the transformation process. The rule finds two clauses containing the same predicate in negated and non-negated forms. Performing unification on these predicates binds variables to specific terms. Unbound variables bound in unified predicates get replaced by their values elsewhere in the clauses. Discarding unified predicates combines remaining ones into a new clause joined by disjunction operators. Factoring unifies two literals within the same clause before or during application. This enhancement makes the inference rule refutation-complete for sets of clauses. Without factoring, some unsatisfiable clause sets cannot derive the empty clause even if they contain only two literals per clause.