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.DecisionTree.buildFull← DecisionTree.buildFull (TCSlib/BooleanAnalysis/DecisionTree.lean:106): verbatim
- 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
fon 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
khas depth at mostn - 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