AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it