Does it work directly on arbitrary English rules?

No. Rules must first be given a precise logical encoding, whose correctness is a separate responsibility.

Does eliminating variables always shrink memory use?

No. Resolvents can multiply, producing substantial intermediate growth.

Does satisfiable mean every assignment is acceptable?

No. It means at least one assignment satisfies all clauses. Finding or validating a particular assignment is a separate part of the workflow.

AI Glossary / Graphs and symbolic AI / Advanced

Davis-Putnam algorithm

Definition

The Davis - Putnam algorithm is a resolution-based procedure for deciding satisfiability of propositional formulas in conjunctive normal form. It systematically eliminates variables while preserving whether a satisfying assignment exists. It should be distinguished from the later branching-based DPLL algorithm.

What it means

A satisfiability problem asks whether truth values can be assigned so that all stated conditions hold. In conjunctive normal form, the conditions are clauses joined by AND, and each clause is a group of literals joined by OR. A literal is a variable or its negation.

The Davis - Putnam idea is to replace constraints involving one variable with consequences involving only the remaining variables. Repeating this process eventually establishes whether the original clause set can be satisfied.

The name has sometimes been used loosely for related procedures. This entry uses the variable-elimination sense associated with the original Davis - Putnam approach, rather than using it as another name for Davis - Putnam - Logemann - Loveland backtracking.

How it works

Choose a variable p. Divide clauses into those containing p, those containing ¬p, and those containing neither. Resolve each positive occurrence against each negative occurrence: from p∨A and ¬p∨B, derive A∨B, where A and B stand for the remaining literals.

Keep the clauses not involving p, add the relevant non-tautological resolvents, and remove the old clauses containing p or ¬p. This eliminates p while preserving satisfiability. The resulting formula is not generally identical to the original formula over all its variables; it expresses the constraints remaining after existentially eliminating p.

Simplifications such as unit propagation, pure-literal handling, duplicate removal and subsumption can reduce work. A unit clause forces its literal to be true. A pure variable occurs in only one polarity and can be assigned to satisfy those occurrences.

An empty clause represents a contradiction and proves unsatisfiability. An empty set of clauses represents no remaining requirements and is satisfiable. Variable ordering matters because resolving many positive clauses against many negative clauses can generate a large number of intermediate clauses.

Three practical examples

A logic tutorial uses variable elimination to show how incompatible requirements produce an explicit contradiction.
A configuration analyzer translates option rules into clauses and studies whether any permitted selection exists.
A reasoning researcher examines how clause structure and elimination order affect the size of intermediate formulas.

Think of it this way

Think of removing a negotiator from a set of agreements while retaining every compatibility requirement needed among the remaining parties. Simply deleting that person's agreements would lose restrictions; replacing them with the consequences preserves the possibility of a complete agreement.

The analogy is limited to logical compatibility. Resolution does not negotiate preferences or decide which requirement the business ought to change.

Worked example

Eliminating one variable exposes a conflict

Consider four clauses: p∨q, ¬p∨r, ¬q and ¬r. All four must hold.

Eliminate p by resolving p∨q with ¬p∨r. The resolvent is q∨r. Retain ¬q and ¬r, which did not involve p. The reduced set is therefore {q∨r, ¬q, ¬r}.

Since ¬q forces q=false, the first clause requires r=true. But ¬r requires r=false. Resolving these opposing unit requirements yields the empty clause, so no satisfying assignment exists.

A procedure using unit propagation eagerly could discover the conflict in a different order; the steps here isolate the elimination idea.

Now remove the original clause ¬r. The remaining three clauses are satisfiable: set q=false, p=true and r=true. Each original clause then evaluates to true. This second check shows why an unsatisfiability conclusion concerns the complete requirement set, not the presence of a positive and negative occurrence of p by themselves.

Illustrative case study

A fictional product-configurator team, Birch Options, models rules for optional accessories as Boolean clauses. A small test configuration turns out to be impossible, and an elimination trace helps the engineers locate the conflicting requirements.

The team initially labels its prototype “DPLL,” even though it replaces variables by pairwise resolvents rather than branching on truth assignments. It corrects the documentation so that performance comparisons describe the algorithm actually implemented.

It also retains the original business-rule identifiers alongside generated clauses. A contradiction in a transformed formula becomes useful to reviewers only when they can connect it back to the requirements they control. The example does not imply that an arbitrary contradiction trace is a smallest explanation.

Common misconceptions and mistakes

Eliminating a variable means deleting all clauses mentioning it. The necessary resolvents must replace those clauses.
The empty clause and an empty clause set mean the same thing. The first is false; the second is true under conjunction semantics.
Both p and ¬p appearing somewhere imply inconsistency. They may occur inside different satisfiable disjunctions.
Davis - Putnam and DPLL perform the same central operation. The former eliminates through resolution; the latter uses branching with simplification.

Business use

The method is foundational for understanding SAT solving and variable elimination. It can also clarify why an apparently compact set of business rules becomes expensive to reason about after transformation.

For an operational satisfiability tool, choose an implementation suited to the workload rather than relying on a historical algorithm name. Measure intermediate representation size as well as runtime. When a satisfiable result is needed as a concrete configuration, preserve enough information to reconstruct values for eliminated variables and verify the final assignment against the original requirements.

Check your understanding

From p∨q and ¬p∨r, an implementation eliminates p and keeps only q. Is that the correct resolvent?

Answer: No. The resolvent is q∨r. Dropping r imposes an unjustified stronger restriction and can change the satisfiability result when combined with other clauses.

Related terms

Learn next

Check all eight assignments of p, q and r for the four-clause example, then compare the result with the elimination trace. Repeat after removing ¬r and verify the reconstructed satisfying assignment clause by clause.

Sources

Rina Dechter and Irina Rish, Directional Resolution: The Davis–Putnam Procedure, Revisited, distinguishes elimination from backtracking and analyses ordering effects: https://ics.uci.edu/~dechter/publications/R29a.pdf

Institutional record and readable summary: https://escholarship.org/uc/item/3fv0g5hg

The clause walkthrough and Birch Options case are original examples.

Previous: Davies-Bouldin Index Next: DDPM objective