is_dnf_tautology
def
A DNF formula A is a tautology if for every Boolean truth assignment to its variables, at least one conjunction term in A is satisfied.
Statement
def is_dnf_tautology {V : Type*} (A : List (List (CnfLit V))) : Prop
- Defined in
- arXiv:2611.01055, Section 2.2
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Built on 1
- CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
- Used by 2
- 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…
- 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…
Read back from the Lean
For a type V and a list of lists of literals A : List (List (CnfLit V)) (representing a DNF formula as a disjunction of conjunctions of literals), is_dnf_tautology A asserts that for every truth assignment τ : V → Bool, there exists a term t ∈ A such that for every literal l ∈ t, τ v = true if l is CnfLit.pos v, and τ v = false if l is CnfLit.neg v.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A DNF formula is a tautology if every truth assignment satisfies at least one term. -/ def is_dnf_tautology {V : Type*} (A : List (List (CnfLit V))) : Prop := ∀ τ : V → Bool, ∃ t ∈ A, ∀ l ∈ t, match l with | CnfLit.pos v => τ v = true | CnfLit.neg v => τ v = false