Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Boolean evaluation of the certificate-truncated positive DNF

Definition
NarrowDNF_CertificateBounds

by chenghua.liu · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsnarrow-dnf-authors-importprobabilitystoc-2027

Let III be finite, JJJ a local activation family, u:{0,1}I→{0,1}u:\{0,1\}^I\to\{0,1\}u:{0,1}I→{0,1} a Boolean readout, and w∈Nw\in\mathbb Nw∈N a certificate-size cutoff. For an input zzz, let TJ(z)T_J(z)TJ​(z) be the coordinates that are both active under JJJ and labelled one in zzz. Retain exactly the terms TJ(z)T_J(z)TJ​(z) arising from accepted inputs u(z)=1u(z)=1u(z)=1 with ∣TJ(z)∣≤w|T_J(z)|\le w∣TJ​(z)∣≤w.

The function defined by this bundle is the actual finite disjunction

gw(x)=1 ⁣[∃z: u(z)=1, ∣TJ(z)∣≤w, ∀i∈TJ(z), xi=1].g_w(x)=\mathbf1\!\left[\exists z:\ u(z)=1,\ |T_J(z)|\le w,\ \forall i\in T_J(z),\ x_i=1\right].gw​(x)=1[∃z: u(z)=1, ∣TJ​(z)∣≤w, ∀i∈TJ​(z), xi​=1].

It is implemented by Boolean evaluation of the already defined finite set of truncated certificate terms, with duplicate terms removed. The empty disjunction evaluates to false and an empty term evaluates to true. No monotonicity, measurability, positive-certificate property, or approximation error estimate is assumed by the definition; those hypotheses and conclusions belong to the certificate-bound theorem nodes.

Definition code
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Data.Bool.Basic
import Mathlib.Data.Finset.Card
import Mathlib.Data.Finset.Image
import Mathlib.Data.Finset.Lattice.Fold
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Real.Basic
import Mathlib.Order.Monotone.Basic
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.Positivity
import Mathlib.Tactic.Ring
import Definitions.Def_NarrowDNF_Adaptive
import Definitions.Def_NarrowDNF_Certificates

namespace NarrowDNF
end NarrowDNF

namespace NarrowDNF.Activation
end NarrowDNF.Activation


namespace NarrowDNF
namespace Activation
open scoped BigOperators
variable {ι : Type*} [Fintype ι] [DecidableEq ι]

noncomputable def truncatedDNF (J : Activation ι) (u : Cube ι → Bool)
    (w : ℕ) (x : Cube ι) : Bool := by
  classical exact decide (DNFHolds (J.truncatedTerms u w) x)











end Activation
end NarrowDNF
Source
https://github.com/liuchliuch/narrow-dnf-lean/blob/eecadd6a5ea0a331d6cf9fd5cb39fc6ec854b372/NarrowDNF/CertificateBounds.lean#L9-L11

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me