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

Copyright(c) Masahiro Sakai 2015
LicenseBSD-style
Maintainermasahiro.sakai@gmail.com
Stabilityprovisional
Portabilityportable
Safe HaskellSafe-Inferred
LanguageHaskell2010

ToySolver.Combinatorial.HittingSet.GurvichKhachiyan1999

Description

References:

Synopsis

Documentation

findPrimeImplicateOrPrimeImplicant Source

Arguments

:: IntSet

Set of variables V

-> (IntSet -> Bool)

A monotone boolean function f from {0,1}^|V| ≅ P(V) to Bool

-> Set IntSet

Subset C' of prime implicates C of f

-> Set IntSet

Subset D' of prime implicants D of f

-> Maybe (Either IntSet IntSet) 

Find a new prime implicant or implicate.

Let f be a monotone boolean function over set of variables S. Let ∧_{I∈C} ∨_{i∈I} x_i and ∨_{I∈D} ∧_{i∈I} x_i be the irredundant CNF representation f and DNF representation of f respectively.

Given a subset C' ⊆ C and D' ⊆ D, findPrimeImplicateOrPrimeImplicant S f C' D' returns

  • Just (Left I) where I ∈ C \ C',
  • Just (Right I) where J ∈ D \ D', or
  • Nothing if C'=C and D'=D.

generateCNFAndDNF Source

Arguments

:: IntSet

Set of variables V

-> (IntSet -> Bool)

A monotone boolean function f from {0,1}^|V| ≅ P(V) to Bool

-> Set IntSet

Subset C' of prime implicates C of f

-> Set IntSet

Subset D' of prime implicants D of f

-> (Set IntSet, Set IntSet) 

Compute the irredundant CNF representation and DNF representation.

Let f be a monotone boolean function over set of variables S. This function returns C and D where ∧_{I∈C} ∨_{i∈I} x_i and ∨_{I∈D} ∧_{i∈I} x_i are the irredundant CNF representation f and DNF representation of f respectively.