AFTD Auto-Formalizing Theoretical Domains

cnf_incidence_graph

def

The incidence graph G*(F) of a CNF formula F: the bipartite graph whose vertices are the variables of F and the clauses of F, a variable x adjacent to a clause C iff x occurs in C.

Statement

def cnf_incidence_graph {V : Type*} [DecidableEq V] (F : Finset (Finset (CnfLit V))) : SimpleGraph ({x // x ∈ cnf_vars F} ⊕ {C // C ∈ F})
Defined in
Short Resolution Refutations for CNFs with Bounded Weighted Incidence Treewidth, arXiv:2610.02047, Sec. 3.2 (incidence graph of a CNF formula)
Verified
06 Oct 2026
Axioms
none listed
Built on 3
  • cnf_varsThe set var(F) of variables occurring in a CNF formula F, given as a finite set of clauses, each a finite set of literals.
  • cnf_lit_varThe variable of a literal: var(x) = var(not x) = x.
  • CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
Used by 2

Lean source view module on GitHub

/-- The incidence graph of a CNF formula. -/
def cnf_incidence_graph {V : Type*} [DecidableEq V] (F : Finset (Finset (CnfLit V))) : SimpleGraph ({x // x ∈ cnf_vars F} ⊕ {C // C ∈ F}) :=
  SimpleGraph.fromRel fun a b =>
    match a, b with
    | Sum.inl x, Sum.inr C => ∃ l ∈ C.1, cnf_lit_var l = x.1
    | _, _ => False
See it in the graphDiscuss this resultChallenge it