Prover9 Manual Version June-2006

FOF Reduction

FOF (First-Order Formula) reduction is a method of attempting to simplify a problem by reducing it to an equivalent set of independent subproblems. A trivial example is to reduce the conjecture A <-> B to the pair of problems A -> B and B -> A.

Flags for FOF Reduction

set(fof_reduction).
clear(fof_reduction).    % default clear
If this flag is set, and if the logical specification is all formulas (rather than clauses), Prover9 will attempt to transform the problem into a set of independent subproblems. The problem reduction uses a miniscope method [Champeaux-miniscope], and it can easily blow up on complex formulas. Therefore, if the reduction procedure fails to terminate within a few seconds, or if the subproblems it produces are more complex than the original problem, the reduction attempt is aborted, and Prover9 reverts to standard clausification. If the reduction succeeds, each subproblem is given to the ordinary Prover9 search procedure.
set(print_subproblems).    % default set
clear(print_subproblems).
This flag is consulted when the FOF reduction procedure is in use. If the flag is set, each subproblem is printed just before search starts on that subproblem.

An Example of FOF Reduction

This example was given by Peter Andrews as a challenge problem for resolution systems in the 1970s. Prover9's miniscope procedure reduces it to 32 trivial subproblems. (More powerful miniscope methods can solve the problem by reducing it to 0 subproblems.)
prover9 -f andrews.in > andrews.out
Here is the same problem without FOF reduction.
prover9 -f andrews2.in > andrews2.out
The preceding example is artificial and seems tailor-made for FOF reduction. Other, more realistic examples can be found in the standard set of Prover9 examples.