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))