pith. machine review for the scientific record. sign in
def definition def or abbrev

CircuitWithEvalDecides

show as:
view Lean formalization →

No prose has been written for this declaration yet. The Lean source and graph data below render without it.

generate prose now

formal statement (Lean)

 120def CircuitWithEvalDecides {n : ℕ} (c : BooleanCircuitWithEval n) (f : CNFFormula n) : Prop :=

proof body

Definition body.

 121  ∀ a : Assignment n, c.eval a = (f.satisfiedBy a)
 122
 123/-- For backward compatibility: CircuitEval and CircuitDecides use an
 124    existential model — a circuit "decides" a formula if there EXISTS an
 125    evaluation function consistent with the gate structure that matches
 126    satisfiability. This is the correct abstract model: it says "the
 127    circuit's structure is rich enough to compute satisfiability." -/

depends on (15)

Lean names referenced from this declaration's body.