AFTD Auto-Formalizing Theoretical Domains

DecisionTree.buildFull

defimported Lean

Build a complete decision tree querying variables 0, 1, …, n−1 in order.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
def DecisionTree.buildFull {n : ℕ} (f : (Fin n → Bool) → Bool)
    (k : ℕ) (acc : Fin n → Bool) : DecisionTree n
Defined in
TCSlib, `DecisionTree.buildFull`
Lean proof
By Hydroxyi, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 TCSlib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
none listed
Built on 1
  • DecisionTreeA decision tree on $n$ Boolean variables: a leaf $\mathtt{leaf}\,b$ outputs $b$, and a branch $\mathtt{branch}\,i\,lo\,hi$ queries…
Used by 3
  • dtDepthThe decision-tree depth of $f : (\mathrm{Fin}\,n \to \mathrm{Bool}) \to \mathrm{Bool}$ is the least $d$ such that some decision tree of…
  • DecisionTree.buildFull_evalThe complete tree computes f on every input it is consistent with. Proof sketch. Induction on the number of variables still to be…
  • DecisionTree.buildFull_depthThe complete tree started at level k has depth at most n - k.

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
/-- Build a complete decision tree querying variables 0, 1, …, n−1 in order. -/
def DecisionTree.buildFull {n : ℕ} (f : (Fin n → Bool) → Bool)
    (k : ℕ) (acc : Fin n → Bool) : DecisionTree n :=
  if h : k < n then
    .branch ⟨k, h⟩
      (DecisionTree.buildFull f (k + 1) (Function.update acc ⟨k, h⟩ false))
      (DecisionTree.buildFull f (k + 1) (Function.update acc ⟨k, h⟩ true))
  else
    .leaf (f acc)
termination_by n - k
See it in the graphDiscuss this resultChallenge it