Let \(C\) be a Boolean circuit on \(n\) variables of the form of a single gate — an AND gate or an OR gate — applied to a list of child circuits, and let \(c\) be one of those children. If the depth of \(C\) is at most \(d\), then the depth of \(c\) is at most \(d - 1\).

Let \(g = \mathrm{node}\, (\mathit{isAnd},\, cs)\) be an internal gate of a Boolean circuit on \(n\) variables, with \(cs\) the list of its child subcircuits, and let \(s\) be a natural number with \(\mathrm{size}(g) \le s\). Then the sum of the sizes of the children, \(\sum _{c \in cs} \mathrm{size}(c)\), is at most \(s - 1\) (truncated natural-number subtraction).

Let \(g\) be an internal gate of a Boolean circuit on \(n\) variables — either an AND gate or an OR gate — applied to a list of child circuits, and suppose its maximum fanin is at most \(w\). Then every child circuit occurring in that list also has maximum fanin at most \(w\).

Let \(g\) be a Boolean circuit on \(n\) variables that is a single gate — an AND or OR gate applied to a list of child circuits — and let \(c\) be one of those children. If the size of \(g\) (its total number of gate and literal nodes) is at most \(s\), then the size of \(c\) is at most \(s - 1\).

Fix \(n\) variables and let \(C_1,\dots ,C_k\) be a finite list of Boolean circuits on them, let \(\rho \) be a restriction, and let \(b\) be a Boolean flag. For a Boolean function \(f\) write \(f_\rho \) for its restriction by \(\rho \), the function \(x \mapsto f(\rho .\mathrm{extend}\, x)\). Form the circuit node with children \(C_1,\dots ,C_k\), read as an AND gate when \(b\) is true and as an OR gate when \(b\) is false, and let \(g\) be its evaluation. Then the restriction of the gate’s evaluation agrees, as a Boolean function, with the gate applied to the restricted evaluations of the children: for every assignment \(x\),

where \((C_i)_\rho \) denotes the restriction by \(\rho \) of the evaluation of \(C_i\), an empty conjunction is \(\mathrm{true}\), and an empty disjunction is \(\mathrm{false}\).

Let \(cs\) be a finite list of Boolean circuits on \(n\) variables, let \(\rho \) be a restriction on those variables, and let \(l\) be a natural number. Suppose that for every circuit \(c\) in \(cs\), the restricted function \(x \mapsto c(\rho .\mathrm{extend}\, x)\) has decision-tree depth at most \(l\). Then there is a CNF formula \(\psi \) of width at most \(l\) that computes the restriction of the AND of \(cs\): writing \(g\) for the AND gate applied to the circuits in \(cs\), one has \(\psi (x) = g(\rho .\mathrm{extend}\, x)\) for every assignment \(x : \mathrm{Fin}\, n \to \mathrm{Bool}\).

Let \(c_1,\dots ,c_m\) be Boolean circuits on \(n\) variables, let \(\rho \) be a restriction of those variables, and let \(l\) be a natural number. For a Boolean function \(g\) write \(g\! \restriction _\rho \) for its restriction by \(\rho \), the function \(x \mapsto g(\rho .\mathrm{extend}\, x)\) that fixes each coordinate assigned by \(\rho \) and reads the remaining coordinates from \(x\). Suppose that for every child \(c\) among \(c_1,\dots ,c_m\) the restricted function \(c\! \restriction _\rho \) is computed by some decision tree of depth at most \(l\). Then there is a DNF formula \(\varphi \) of width at most \(l\) that computes the restriction \(F\! \restriction _\rho \) of the OR gate \(F\) over the children, i.e. \(\varphi (x) = F\! \restriction _\rho (x)\) for every assignment \(x\), where \(F\) evaluates to the disjunction of the values \(c_1,\dots ,c_m\).

Fix \(n \ge 1\), an integer \(l \ge 1\), and a natural number \(t\), and write \(D(g)\) for the decision-tree depth of a Boolean function \(g\) on \(n\) variables, that is, the least depth of a decision tree computing \(g\). For a function \(g\) and a restriction \(\rho \) on the \(n\) variables, let \(g\! \restriction _{\rho }\) denote the function obtained from \(g\) by fixing each coordinate to the value \(\rho \) assigns it and leaving the coordinates \(\rho \) marks free as inputs. Let \(c_1,\dots ,c_m\) be Boolean circuits on \(n\) variables, and let \(F\) be the function computed by a single AND gate, or by a single OR gate, applied to \(c_1,\dots ,c_m\); the bound below holds for either gate. Suppose a restriction \(\rho _1\) satisfies \(D\! \left(c_i\! \restriction _{\rho _1}\right) \le l\) for every \(i\). Draw a random restriction \(\rho _2\) under which each of the \(n\) variables is independently left free with probability \(p = \tfrac {1}{40 l}\) and otherwise fixed, taking each of the values \(0\) and \(1\) with probability \(\tfrac {1-p}{2}\), and let \(\rho _1 \circ \rho _2\) be the composite restriction that keeps every value fixed by \(\rho _1\) and applies \(\rho _2\) to the coordinates \(\rho _1\) leaves free. Then