AFTD Auto-Formalizing Theoretical Domains

CnfLit

inductive

A CNF literal over a variable type V is either a positive variable or a negated variable.

Statement

inductive CnfLit (V : Type*)
Defined in
standard textbook definition (propositional logic: literals of a CNF formula)
Verified
06 Oct 2026
Axioms
none listed
Used by 30
  • is_dnf_tautologyA DNF formula A is a tautology if for every Boolean truth assignment to its variables, at least one conjunction term in A is satisfied.
  • cnf_restrictThe restriction F|x=b of a CNF formula F: delete every clause containing the literal satisfied by x = b, and in the remaining clauses…
  • cnf_incidence_treewidthThe incidence treewidth tw*(F) of a CNF formula F: the treewidth of its incidence graph.
  • cnf_resolution_soundnessSoundness of the resolution rule: for any truth assignment τ : V → Bool, variable v : V, and clauses C, D : List (CnfLit V), if…
  • depth_three_amc_soundnessFor any natural number n, any DNF formula A : List (List (CnfLit (Fin n))), any real shift parameter ε > 0, and any proof size r : ℕ, if A…
  • cnf_not_satisfiable_of_has_empty_clauseA CNF formula containing the empty clause cannot be satisfied by any assignment because the empty clause contains no literals to be made…
  • cnf_lit_varThe variable of a literal: var(x) = var(not x) = x.
  • resolution_refutation_of_pos_negBase case for unit contradiction: a formula containing complementary unit clauses {x} and {not x} admits a resolution refutation of length…
  • cnf_satisfiable_append_sum_iffLet f be a CNF formula over a variable type V and g a CNF formula over a variable type W. Replace every literal of f by the literal of the…
  • has_depth_three_amc_bounded_bias_proofLet n be a natural number, A a DNF formula represented as a list of terms where each term is a list of literals of type CnfLit (Fin n), ε…
  • cnf_satisfiable_subsetIf every clause of a CNF formula f1 is contained in a CNF formula f2 (that is, f1 ⊆ f2), and f2 is satisfiable (…
  • depth_three_amc_of_bounded_biasFor every natural number n, every DNF formula A : List (List (CnfLit (Fin n))), every real shift parameter ε, and every proof size s : ℕ,…
  • cnf_single_clause_satisfiable_iffA CNF formula consisting of a single clause c, namely [c], is satisfiable (CnfSatisfiable [c]) if and only if the clause c is…
  • is_resolution_derivationA resolution derivation from a CNF formula F (a finite set of clauses, each a finite set of literals) is a sequence of clauses C_1, ...,…
  • is_resolution_refutation_monoMonotonicity of resolution refutations: if F1 is a subset of F2, any resolution refutation of F1 is also a resolution refutation of F2 of…
  • cnf_lit_decidable_eqDecidable equality on CNF literals, derived from decidable equality on the underlying variables.
  • resolution_refutation_exists_of_unsatCompleteness of resolution, the length-free part of the problem: every unsatisfiable CNF formula has a resolution refutation.
  • resolution_refutation_of_empty_memBase case: if a formula contains the empty clause, it admits a resolution refutation of length 1 (namely [∅]).
  • has_depth_three_amc_proofLet n be a natural number, A a DNF formula represented as a list of terms where each term is a list of literals of type CnfLit (Fin n), ε…
  • cnf_incidence_treewidth_emptyThe incidence treewidth of the empty formula is 0.
  • cnf_satisfiable_of_appendIf the concatenation f1 ++ f2 of two CNF formulas is satisfiable (CnfSatisfiable (f1 ++ f2)), then both f1 and f2 are satisfiable…
  • op_983_dnf_familyThe explicit separating DNF family: over the variables Fin n, one all-positive full-subset term for every subset S of Fin n, together with…
  • 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.
  • depth_three_amc_separation_from_asymptotic_familyAny asymptotic family of DNF formulas satisfying the AMC upper bound and bounded-bias lower bound for k ≥ k₀ extends to a full family…
  • cnf_lit_complThe complement of a literal, negating its polarity.
  • resolution_refutation_pos_neg_exampleSanity check: the formula consisting of the clauses {x_0} and {not x_0} has the resolution refutation x_0, not x_0, empty clause, of…
  • cnf_incidence_treewidth_le_cardUniversal upper bound: the incidence treewidth of any CNF formula F is at most |vars(F)| + |F|.
  • cnf_incidence_graphThe 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…
  • is_resolution_refutationA resolution refutation of F is a resolution derivation from F whose last clause is the empty clause; its length is the number of clauses…
  • CnfSatisfiableA CNF formula (a list of clauses, each a list of literals) is satisfiable if there is a truth assignment such that every clause contains…

Lean source view module on GitHub

/-- A literal over variable type `V`, either a positive or negative occurrence of a variable. -/
inductive CnfLit (V : Type*) | pos (v : V) : CnfLit V
  | neg (v : V) : CnfLit V
See it in the graphDiscuss this resultChallenge it