AFTD Auto-Formalizing Theoretical Domains

cnf_restrict

def

The restriction F|x=b of a CNF formula F: delete every clause containing the literal satisfied by x = b, and in the remaining clauses erase the falsified literal on x.

Statement

def cnf_restrict {V : Type*} [DecidableEq V] (F : Finset (Finset (CnfLit V))) (x : V) (b : Bool) : Finset (Finset (CnfLit V))
Source
step towards resolution_fpt_incidence_treewidth
Verified
23 Oct 2026
Axioms
none listed
Built on 2
  • cnf_lit_decidable_eqDecidable equality on CNF literals, derived from decidable equality on the underlying variables.
  • CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.

Lean source view module on GitHub

/-- Restriction of a CNF formula to the variable `x = b`: clauses containing the satisfied literal are deleted, and in the remaining clauses the falsified literal is erased. -/
def cnf_restrict {V : Type*} [DecidableEq V] (F : Finset (Finset (CnfLit V))) (x : V) (b : Bool) : Finset (Finset (CnfLit V)) := (F.filter (fun C => (if b then CnfLit.pos x else CnfLit.neg x) ∉ C)).image (fun C => C.erase (if b then CnfLit.neg x else CnfLit.pos x))
See it in the graphDiscuss this resultChallenge it