Princeton University
Computer Science Department

Computer Science 598A
Automated Theorem Proving

Andrew Appel

Conjunct provers
Spring 2003

General Information | Schedule | Assignments | Announcements

Here are four different logic programs, each one designed to find proofs of formulas (A imp B), where A is a conjunction of several formulas and B is a different conjunction of (some subset) of the same formulas. These programs can be loaded using the "as5" logic.
static.elf
Quadratic-time algorithm using static clauses.
static-sem.elf
Quadratic-time algorithm using static clauses, with a semantic model that proves soundness of the clauses.
dynamic.elf
Linear-time algorithm using dynamic clauses.
dynamic-sem.elf
Linear-time algorithm using dynamic clauses, with a semantic model that proves soundness of the clauses.
Now, we generalize to a logic program that proves that (subset A B) where A is an intersection of several sets and B is a different intersection of the same sets.
subset.elf
Linear-time subset-of-intersection algorithm.
subset-sem.elf
Linear-time subset-of-intersection algorithm, with a semantic model that proves soundness of the clauses.
Another way to write provers is to instantiate the proof as one of the arguments of a logic-programming predicate:
static2.elf
Quadratic-time implication-of-conjuction prover.
dynamic2.elf
A linear-time prover is also easy to do, using dynamic clauses, but I won't show it here.