ToySolver.Arith.FourierMotzkin.FOL

Documentation

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

• solveFormula {x1,…,xm} φ returns Sat M such that M ⊧_LRA φ when such M exists,
• returns Unsat when such M does not exists, and
• returns Unknown when φ is beyond LRA.

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

Eliminate quantifiers and returns equivalent quantifier-free formula.

eliminateQuantifiers φ returns (ψ, lift) such that:

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

φ may or may not be a closed formula.

eliminateQuantifiers' :: Formula (Atom Rational) -> Maybe (DNF Constr)