A machine program for theorem-proving

Inside the paper

The problem

A procedure for first-order theorem proving had been described previously, but implementing it on a computer exposed limits in memory and the growth of intermediate formulas. The authors investigate both an implementation and a change to its consistency test.

The idea

The program generates quantifier-free instances and tests them for inconsistency. Its revised processor splits on a propositional variable, avoiding the rapid clause growth that occurred with the earlier elimination rule.

How it works

• The input formula is prepared in conjunctive normal form, with existential quantifiers replaced by function symbols before encoding.
• A generator makes successive substitutions to produce quantifier-free lines, and the processor tests the accumulated clauses for consistency.
• Single-literal and pure-sign rules simplify clauses; when those rules cannot proceed, the processor splits on a chosen variable.
• One branch is saved on tape while the other is explored, and the saved branch is restored if needed to complete the consistency test.

What it showed

The program proved examples that had challenged an earlier procedure, but it could not prove the group-theory example within its available storage. The authors trace that failure to the number of instances generated and show that input ordering can substantially change the work required.

Read it for

Read the splitting rule and its motivation on page 394, then the results on page 395. The group example on pages 396–397 explains the combinatorial bottleneck; the linked-table implementation on page 395 can be skimmed at first.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.