Documentation

Std.Sat.AIG.Basic

This module contains the basic definitions for an AIG (And Inverter Graph) in the style of AIGNET, as described in https://arxiv.org/pdf/1304.7861.pdf section 3. It consists of an AIG definition, a description of its semantics and basic operations to construct nodes in the AIG.

inductive Std.Sat.AIG.Decl (α : Type) :

A circuit node. These are not recursive but instead contain indices into an AIG, with inputs indexed by α.

  • const: {α : Type} → BoolStd.Sat.AIG.Decl α

    A node with a constant output value.

  • atom: {α : Type} → αStd.Sat.AIG.Decl α

    An input node to the circuit.

  • gate: {α : Type} → NatNatBoolBoolStd.Sat.AIG.Decl α

    An AIG gate with configurable input nodes and polarity. l and r are the input node indices while linv and rinv say whether there is an inverter on the left and right inputs, respectively.

Instances For
instance Std.Sat.AIG.instHashableDecl :
{α : Type} → [inst : Hashable α] → Hashable (Std.Sat.AIG.Decl α)
Equations
  • Std.Sat.AIG.instHashableDecl = { hash := Std.Sat.AIG.hashDecl✝ }
instance Std.Sat.AIG.instReprDecl :
{α : Type} → [inst : Repr α] → Repr (Std.Sat.AIG.Decl α)
Equations
  • Std.Sat.AIG.instReprDecl = { reprPrec := Std.Sat.AIG.reprDecl✝ }
Equations
  • Std.Sat.AIG.instDecidableEqDecl = Std.Sat.AIG.decEqDecl✝
Equations

Cache.WF xs is a predicate asserting that a cache : HashMap (Decl α) Nat is a valid lookup cache for xs : Array (Decl α), that is, whenever cache.find? decl returns an index into xs : Array Decl, xs[index] = decl. Note that this predicate does not force the cache to be complete, if there is no entry in the cache for some node, it can still exist in the AIG.

A cache for reusing elements from decls if they are available.

Equations
@[irreducible]

Create an empty Cache, valid with respect to any Array Decl.

Equations
@[irreducible]
def Std.Sat.AIG.Cache.noUpdate {α : Type} [Hashable α] [DecidableEq α] {decls : Array (Std.Sat.AIG.Decl α)} {decl : Std.Sat.AIG.Decl α} (cache : Std.Sat.AIG.Cache α decls) :
Std.Sat.AIG.Cache α (decls.push decl)

Given a cache, valid with respect to some decls, we can extend the decls without extending the cache and remain valid.

Equations
  • cache.noUpdate = cache.val,
@[irreducible]
def Std.Sat.AIG.Cache.insert {α : Type} [Hashable α] [DecidableEq α] (decls : Array (Std.Sat.AIG.Decl α)) (cache : Std.Sat.AIG.Cache α decls) (decl : Std.Sat.AIG.Decl α) :
Std.Sat.AIG.Cache α (decls.push decl)

Given a cache, valid with respect to some decls, we can extend the decls and the cache at the same time with the same values and remain valid.

Equations
structure Std.Sat.AIG.CacheHit {α : Type} (decls : Array (Std.Sat.AIG.Decl α)) (decl : Std.Sat.AIG.Decl α) :

Contains the index of decl in decls along with a proof that the index is indeed correct.

  • idx : Nat
  • hbound : self.idx < decls.size
  • hvalid : decls[self.idx] = decl
theorem Std.Sat.AIG.CacheHit.hbound {α : Type} {decls : Array (Std.Sat.AIG.Decl α)} {decl : Std.Sat.AIG.Decl α} (self : Std.Sat.AIG.CacheHit decls decl) :
self.idx < decls.size
theorem Std.Sat.AIG.CacheHit.hvalid {α : Type} {decls : Array (Std.Sat.AIG.Decl α)} {decl : Std.Sat.AIG.Decl α} (self : Std.Sat.AIG.CacheHit decls decl) :
decls[self.idx] = decl
theorem Std.Sat.AIG.Cache.get?_bounds {α : Type} [Hashable α] [DecidableEq α] {decls : Array (Std.Sat.AIG.Decl α)} {idx : Nat} (c : Std.Sat.AIG.Cache α decls) (decl : Std.Sat.AIG.Decl α) (hfound : c.val[decl]? = some idx) :
idx < decls.size

For a c : Cache α decls, any index idx that is a cache hit for some decl is within bounds of decls (i.e. idx < decls.size).

theorem Std.Sat.AIG.Cache.get?_property {α : Type} [Hashable α] [DecidableEq α] {decls : Array (Std.Sat.AIG.Decl α)} {idx : Nat} (c : Std.Sat.AIG.Cache α decls) (decl : Std.Sat.AIG.Decl α) (hfound : c.val[decl]? = some idx) :
decls[idx] = decl

If Cache.get? decl returns some i then decls[i] = decl holds.

opaque Std.Sat.AIG.Cache.get? {α : Type} [Hashable α] [DecidableEq α] {decls : Array (Std.Sat.AIG.Decl α)} (cache : Std.Sat.AIG.Cache α decls) (decl : Std.Sat.AIG.Decl α) :

Lookup a Decl in a Cache.

def Std.Sat.AIG.IsDAG (α : Type) (decls : Array (Std.Sat.AIG.Decl α)) :

An Array Decl is a Direct Acyclic Graph (DAG) if a gate at index i only points to nodes with index lower than i.

Equations

The empty array is a DAG.

structure Std.Sat.AIG (α : Type) [DecidableEq α] [Hashable α] :

An And Inverter Graph together with a cache for subterm sharing.

Instances For
theorem Std.Sat.AIG.invariant {α : Type} [DecidableEq α] [Hashable α] (self : Std.Sat.AIG α) :
Std.Sat.AIG.IsDAG α self.decls

In order to be a valid AIG, decls must form a DAG.

An AIG with an empty AIG and cache.

Equations
def Std.Sat.AIG.Mem {α : Type} [Hashable α] [DecidableEq α] (aig : Std.Sat.AIG α) (a : α) :

The atom a occurs in aig.

Equations
Equations
  • Std.Sat.AIG.instMembership = { mem := Std.Sat.AIG.Mem }
structure Std.Sat.AIG.Ref {α : Type} [Hashable α] [DecidableEq α] (aig : Std.Sat.AIG α) :

A reference to a node within an AIG. This is the AIG analog of Bool.

  • gate : Nat
  • hgate : self.gate < aig.decls.size
Instances For
theorem Std.Sat.AIG.Ref.hgate {α : Type} [Hashable α] [DecidableEq α] {aig : Std.Sat.AIG α} (self : aig.Ref) :
self.gate < aig.decls.size
@[inline]
def Std.Sat.AIG.Ref.cast {α : Type} [Hashable α] [DecidableEq α] {aig1 : Std.Sat.AIG α} {aig2 : Std.Sat.AIG α} (ref : aig1.Ref) (h : aig1.decls.size aig2.decls.size) :
aig2.Ref

A Ref into aig1 is also valid for aig2 if aig1 is smaller than aig2.

Equations
  • ref.cast h = { gate := ref.gate, hgate := }
@[inline]
def Std.Sat.AIG.BinaryInput.cast {α : Type} [Hashable α] [DecidableEq α] {aig1 : Std.Sat.AIG α} {aig2 : Std.Sat.AIG α} (input : aig1.BinaryInput) (h : aig1.decls.size aig2.decls.size) :
aig2.BinaryInput

The Ref.cast equivalent for BinaryInput.

Equations
  • input.cast h = { lhs := input.lhs.cast h, rhs := input.rhs.cast h }
structure Std.Sat.AIG.TernaryInput {α : Type} [Hashable α] [DecidableEq α] (aig : Std.Sat.AIG α) :

A collection of 3 of Refs, useful for LawfulOperators that act on three Refs at a time, in particular multiplexer style functions.

  • discr : aig.Ref
  • lhs : aig.Ref
  • rhs : aig.Ref
Instances For
@[inline]
def Std.Sat.AIG.TernaryInput.cast {α : Type} [Hashable α] [DecidableEq α] {aig1 : Std.Sat.AIG α} {aig2 : Std.Sat.AIG α} (input : aig1.TernaryInput) (h : aig1.decls.size aig2.decls.size) :
aig2.TernaryInput

The Ref.cast equivalent for TernaryInput.

Equations
  • input.cast h = { discr := input.discr.cast h, lhs := input.lhs.cast h, rhs := input.rhs.cast h }

An entrypoint into an AIG. This can be used to evaluate a circuit, starting at a certain node, with AIG.denote or to construct bigger circuits on top of this specific node.

  • aig : Std.Sat.AIG α

    The AIG that we are in.

  • ref : self.aig.Ref

    The reference to the node in aig that this Entrypoint targets.

Transform an Entrypoint into a graphviz string. Useful for debugging purposes.

Equations
  • One or more equations did not get rendered due to their size.
@[irreducible]
def Std.Sat.AIG.toGraphviz.go {α : Type} [DecidableEq α] [ToString α] [Hashable α] (acc : String) (decls : Array (Std.Sat.AIG.Decl α)) (hinv : Std.Sat.AIG.IsDAG α decls) (idx : Nat) (hidx : idx < decls.size) :
StateM (Std.HashSet (Fin decls.size)) String
Equations
  • One or more equations did not get rendered due to their size.
Equations
def Std.Sat.AIG.toGraphviz.toGraphvizString {α : Type} [DecidableEq α] [ToString α] [Hashable α] (decls : Array (Std.Sat.AIG.Decl α)) (idx : Fin decls.size) :
Equations
  • One or more equations did not get rendered due to their size.
structure Std.Sat.AIG.RefVec {α : Type} [Hashable α] [DecidableEq α] (aig : Std.Sat.AIG α) (w : Nat) :

A vector of references into aig. This is the AIG analog of BitVec.

  • refs : Array Nat
  • hlen : self.refs.size = w
  • hrefs : ∀ {i : Nat} (h : i < w), self.refs[i] < aig.decls.size
Instances For
theorem Std.Sat.AIG.RefVec.hlen {α : Type} [Hashable α] [DecidableEq α] {aig : Std.Sat.AIG α} {w : Nat} (self : aig.RefVec w) :
self.refs.size = w
theorem Std.Sat.AIG.RefVec.hrefs {α : Type} [Hashable α] [DecidableEq α] {aig : Std.Sat.AIG α} {w : Nat} (self : aig.RefVec w) {i : Nat} (h : i < w) :
self.refs[i] < aig.decls.size
structure Std.Sat.AIG.RefVecEntry (α : Type) [DecidableEq α] [Hashable α] [DecidableEq α] (w : Nat) :

A sequence of references bundled with their AIG.

def Std.Sat.AIG.denote {α : Type} [Hashable α] [DecidableEq α] (assign : αBool) (entry : Std.Sat.AIG.Entrypoint α) :

Evaluate an AIG.Entrypoint using some assignment for atoms.

Equations
@[irreducible]
def Std.Sat.AIG.denote.go {α : Type} (x : Nat) (decls : Array (Std.Sat.AIG.Decl α)) (assign : αBool) (h1 : x < decls.size) (h2 : Std.Sat.AIG.IsDAG α decls) :
Equations
  • One or more equations did not get rendered due to their size.

Denotation of an AIG at a specific Entrypoint.

Equations
  • One or more equations did not get rendered due to their size.

Denotation of an AIG at a specific Entrypoint with the Entrypoint being constructed on the fly.

Equations
  • One or more equations did not get rendered due to their size.
Equations
  • One or more equations did not get rendered due to their size.
def Std.Sat.AIG.UnsatAt {α : Type} [Hashable α] [DecidableEq α] (aig : Std.Sat.AIG α) (start : Nat) (h : start < aig.decls.size) :

The denotation of the sub-DAG in the aig at node start is false for all assignments.

Equations
  • aig.UnsatAt start h = ∀ (assign : αBool), assign, { aig := aig, ref := { gate := start, hgate := h } } = false

The denotation of the Entrypoint is false for all assignments.

Equations
  • entry.Unsat = entry.aig.UnsatAt entry.ref.gate
structure Std.Sat.AIG.Fanin {α : Type} [Hashable α] [DecidableEq α] (aig : Std.Sat.AIG α) :

An input to an AIG gate.

  • ref : aig.Ref

    The node we are referring to.

  • inv : Bool

    Whether the node is inverted

@[inline]
def Std.Sat.AIG.Fanin.cast {α : Type} [Hashable α] [DecidableEq α] {aig1 : Std.Sat.AIG α} {aig2 : Std.Sat.AIG α} (fanin : aig1.Fanin) (h : aig1.decls.size aig2.decls.size) :
aig2.Fanin

The Ref.cast equivalent for Fanin.

Equations
  • fanin.cast h = { ref := fanin.ref.cast h, inv := fanin.inv }
structure Std.Sat.AIG.GateInput {α : Type} [Hashable α] [DecidableEq α] (aig : Std.Sat.AIG α) :

The input type for creating AIG and gates.

  • lhs : aig.Fanin
  • rhs : aig.Fanin
Instances For
@[inline]
def Std.Sat.AIG.GateInput.cast {α : Type} [Hashable α] [DecidableEq α] {aig1 : Std.Sat.AIG α} {aig2 : Std.Sat.AIG α} (input : aig1.GateInput) (h : aig1.decls.size aig2.decls.size) :
aig2.GateInput

The Ref.cast equivalent for GateInput.

Equations
  • input.cast h = { lhs := input.lhs.cast h, rhs := input.rhs.cast h }
def Std.Sat.AIG.mkGate {α : Type} [Hashable α] [DecidableEq α] (aig : Std.Sat.AIG α) (input : aig.GateInput) :

Add a new and inverter gate to the AIG in aig. Note that this version is only meant for proving, for production purposes use AIG.mkGateCached and equality theorems to this one.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
def Std.Sat.AIG.mkAtom {α : Type} [Hashable α] [DecidableEq α] (aig : Std.Sat.AIG α) (n : α) :

Add a new input node to the AIG in aig. Note that this version is only meant for proving, for production purposes use AIG.mkAtomCached and equality theorems to this one.

Equations
  • aig.mkAtom n = { aig := { decls := aig.decls.push (Std.Sat.AIG.Decl.atom n), cache := aig.cache.noUpdate, invariant := }, ref := { gate := aig.decls.size, hgate := } }
Instances For

Add a new constant node to aig. Note that this version is only meant for proving, for production purposes use AIG.mkConstCached and equality theorems to this one.

Equations
  • aig.mkConst val = { aig := { decls := aig.decls.push (Std.Sat.AIG.Decl.const val), cache := aig.cache.noUpdate, invariant := }, ref := { gate := aig.decls.size, hgate := } }
Instances For