toysolver-0.2.0: Assorted decision procedures for SAT, Max-SAT, PB, MIP, etc

Copyright(c) Masahiro Sakai 2011-2013
LicenseBSD-style
Maintainermasahiro.sakai@gmail.com
Stabilityprovisional
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

ToySolver.Arith.Cooper.FOL

Description

 

Synopsis

Documentation

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

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 Source

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.