This module contains an implementation of a verified Tseitin transformation on AIGs. The key results
are the toCNF
function and the toCNF_equisat
correctness statement. The implementation is
done in the style of section 3.4 of the AIGNET paper.
Produce a Tseitin style CNF for a Decl.false
, using output
as the tree node variable.
Equations
Instances For
Produce a Tseitin style CNF for a Decl.atom
, using output
as the tree node variable.
Equations
Instances For
Produce a Tseitin style CNF for a Decl.gate
, using output
as the tree node variable.
Equations
Instances For
Given an atom assignment, produce an assignment that will always satisfy the CNF generated by our Tseitin transformation. This is done by combining the atom assignment with an assignment for the auxiliary variables, that just evaluates the AIG at the corresponding node.
Equations
Instances For
The central invariant for the Cache
.
Relate satisfiability results about our produced CNF to satisfiability results about the AIG that we are processing. The intuition for this is: if a node is marked, its CNF is already part of the current CNF. Thus the current CNF is already mirroring the semantics of the marked node. This means that if the CNF is satisfiable at some assignment, we can evaluate the marked node under the atom part of that assignment and will get the value that was assigned to the corresponding auxiliary variable as a result.
Equations
Instances For
The CNF cache. It keeps track of AIG nodes that we already turned into CNF to avoid adding the same CNF twice.
Keeps track of AIG nodes that we already turned into CNF.
There are always as many marks as AIG nodes.
Instances For
We say that a cache extends another by an index when it doesn't invalidate any entry and has an entry for that index.
- extension (idx : Nat) (hidx : idx < aig.decls.size) : cache1.marks[idx] = true → cache2.marks[idx] = true
No entry is invalidated.
The second cache is true at the new index.
Instances For
Add a Decl.gate
to a cache.
Equations
Instances For
The key invariant about the State
itself (without cache): The CNF we produce is always satisfiable
at cnfSatAssignment
.
Equations
Instances For
The state to accumulate CNF clauses as we run our Tseitin transformation on the AIG.
The CNF clauses so far.
A cache so that we don't generate CNF for an AIG node more than once.
The invariant that
cnf
has to maintain as we build it up.
Instances For
An initial state with no CNF clauses and an empty cache.
Equations
Instances For
Add the CNF for a Decl.gate
to the state.
Equations
Instances For
Convert an AIG into CNF, starting at some entry node.
Equations
Instances For
An AIG is unsat iff its CNF is unsat.