ToySolver.Arith.Cooper.FOL

Documentation

eliminateQuantifiers :: Formula (Atom Rational) -> Maybe QFFormula

Eliminate quantifiers and returns equivalent quantifier-free formula.

eliminateQuantifiers φ returns (ψ, lift) such that:

• ψ is a quantifier-free formula and LIA ⊢ ∀y1, …, yn. φ ↔ ψ where {y1, …, yn} = FV(φ) ⊇ FV(ψ), and
• if M ⊧_LIA ψ then lift M ⊧_LIA φ.

φ may or may not be a closed formula.

solveFormula :: VarSet -> Formula (Atom Rational) -> SatResult Integer

solveFormula {x1,…,xm} φ

• returns Sat M such that M ⊧_LIA φ when such M exists,
• returns Unsat when such M does not exists, and
• returns Unknown when φ is beyond LIA.