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, variablev : V, and clausesC, 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
f1is contained in a CNF formulaf2(that is,f1 ⊆ f2), andf2is 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 clausecis… - 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 ++ f2of two CNF formulas is satisfiable (CnfSatisfiable (f1 ++ f2)), then bothf1andf2are 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