Let \(\varphi \) be a DNF formula on \(n\) variables, that is, a list of terms, each term a list of literals, and let its De Morgan dual CNF be obtained by negating every literal of every term. Then the dual CNF has the same width as \(\varphi \), where the width of a formula is the maximum number of literals appearing in any of its terms (equal to \(0\) when the formula is empty).

Let \(\varphi \) be a DNF formula on \(n\) variables — a disjunction of terms, each term a conjunction of literals — and let \(x \in \{ 0,1\} ^n\) be an assignment. Form its De Morgan dual CNF by negating every literal of every term of \(\varphi \) and reading each resulting term as a clause (a disjunction of literals), so that the whole is a conjunction of clauses. Then this dual CNF evaluates on \(x\) to the negation of the value of \(\varphi \) on \(x\).

Let \(c\) be a Boolean circuit whose depth is at least \(1\). Then \(c\) is not a literal: it is an internal gate, so there exist a Boolean flag \(\mathit{isAnd}\) and a list \(cs\) of child circuits for which \(c\) is the node with gate type \(\mathit{isAnd}\) applied to the children \(cs\).

Let \(C\) be the Boolean circuit consisting of a single gate (an AND gate or an OR gate, according to a flag \(\mathit{isAnd}\)) applied to a list \(cs\) of child circuits, so that the depth of \(C\) equals \(1\) plus the maximum depth among the circuits in \(cs\). If the depth of \(C\) is at most \(1\), then every child circuit \(c \in cs\) has depth \(0\); that is, each child is a literal.

Let \(c\) be a Boolean circuit on \(m\) variables whose depth is \(0\). Then \(c\) is a leaf: there exists a literal \(l\) such that \(c\) is the single-literal circuit built from \(l\).

Fix a number of variables \(m\), a gate type \(isAnd \in \{ \mathrm{true}, \mathrm{false}\} \), and a list \(cs\) of Boolean circuits on \(m\) variables, and form the circuit \(\mathrm{node}(isAnd, cs)\) whose root gate is applied to the children in \(cs\). If this circuit has depth at most \(1\), then every child \(c\) in \(cs\) is a literal; that is, there exists a literal \(l\) with \(c = \mathrm{lit}(l)\).

Let \(g_1,\dots ,g_m\) be DNF formulas on \(n\) Boolean variables, let \(\rho \) be a restriction of these variables, and let \(l\in \mathbb {N}\). For each \(i\), write \(f_i\) for the restriction of \(g_i\) by \(\rho \), that is, the Boolean function \(x \mapsto g_i(\rho .\mathrm{extend}\, x)\) that evaluates \(g_i\) with the coordinates fixed by \(\rho \) set accordingly and the free coordinates supplied by \(x\), and suppose that every \(f_i\) has decision-tree depth at most \(l\). Then for each \(i\) there is a DNF formula \(\varphi _i\) of width at most \(l\) that computes \(f_i\), in which no term repeats a literal and no two literals of the same term share a variable; and there is a CNF formula \(\psi _i\) of width at most \(l\) that also computes \(f_i\).

Fix natural numbers \(m,n\) and a width bound \(l\). Let \(c_1,\dots ,c_k\) be Boolean circuits on \(m\) variables, each of which is a single literal, and let \(N\) be the OR node whose children are exactly these circuits. Suppose that to each variable index \(i \in \mathrm{Fin}\, m\) there is associated a gate function \(g_i\) taking a Boolean assignment \(x : \mathrm{Fin}\, n \to \{ 0,1\} \) to a Boolean value, and that every \(g_i\) is computed both by some DNF formula on the \(n\) inputs of width at most \(l\) and by some CNF formula on the \(n\) inputs of width at most \(l\). Then the composite function \(x \mapsto N\bigl((g_i(x))_{i}\bigr)\) — the disjunction of the literal children evaluated at the gate values \(g_i(x)\) — is itself computed by a DNF formula \(\varphi \) on the \(n\) inputs of width at most \(l\), in the sense that \(\varphi (x)\) equals the value of \(N\) on the assignment \(i \mapsto g_i(x)\) for every \(x\).

Fix natural numbers \(m\), \(n\), and \(l\), and let \(g_0, \dots , g_{m-1}\) be Boolean functions of an input \(x : \mathrm{Fin}\, n \to \{ 0,1\} \), one for each index \(i \in \mathrm{Fin}\, m\), such that each \(g_i\) is computed both by some DNF of width at most \(l\) and by some CNF of width at most \(l\). Let the circuits \(c \in cs\) each be a single literal over the variables \(0, \dots , m-1\), and let \(C\) be the AND gate whose children are exactly these literals, evaluated on an input \(x\) by substituting the value \(g_i(x)\) for the \(i\)-th variable. Then the Boolean function computed in this way — the conjunction of the literal values \(g_i(x)\) or their negations — is itself represented by a CNF \(\psi \) of width at most \(l\), in the sense that \(\psi \) evaluates to \(C\)’s value on every input \(x\).

Let \(\mathrm{data}\) be layer-2 data over \(n\) Boolean variables: a family of gates, each computing a DNF formula, sharing a common positive width bound. Let \(c_{\mathrm{top}}\) be a Boolean circuit whose input variables are indexed by these gates, and fix an integer \(l \ge 1\). Suppose that \(c_{\mathrm{top}}\) has depth exactly \(1\) (a single AND or OR gate applied to literals in the gate outputs), and that each gate computes a function that is representable both by a DNF of width at most \(l\) — one in which, within every term, distinct literals carry distinct variables and no literal is repeated — and by a CNF of width at most \(l\). Then there exist layer-2 data \(\mathrm{data}'\) of width at most \(l\) and a circuit \(c_{\mathrm{top}}'\) of depth \(0\) over the gates of \(\mathrm{data}'\) such that, for every Boolean assignment \(x\) to the \(n\) variables, the value of \(c_{\mathrm{top}}\) evaluated on the outputs of the gates of \(\mathrm{data}\) equals the value of \(c_{\mathrm{top}}'\) evaluated on the outputs of the gates of \(\mathrm{data}'\).

Fix natural numbers \(m,n,l\). Let \(c_j\) be a Boolean circuit whose \(m\) inputs are indexed by \(\mathrm{Fin}\, m\) and whose depth is at most \(1\), and let \(\mathrm{gates}\) assign to each index \(i \in \mathrm{Fin}\, m\) a Boolean function \(\mathrm{gates}_i \colon (\mathrm{Fin}\, n \to \mathbb {F}_2) \to \mathbb {F}_2\). Suppose that every \(\mathrm{gates}_i\) is computed by some DNF over \(n\) variables of width at most \(l\), and also by some CNF over \(n\) variables of width at most \(l\). Then there exist a DNF \(\varphi \) over \(n\) variables of width at most \(l\) and a sign bit \(s \in \mathrm{Bool}\) such that, for every assignment \(x \colon \mathrm{Fin}\, n \to \mathbb {F}_2\), the value \(\varphi \) takes at \(x\) when \(s = \mathrm{true}\), and its negation when \(s = \mathrm{false}\), equals the value of \(c_j\) under the assignment \(i \mapsto \mathrm{gates}_i(x)\); moreover, each term of \(\varphi \) contains no repeated literal, and no two of its literals share a variable.

Let \(g_1,\dots ,g_m \colon \{ 0,1\} ^n \to \{ 0,1\} \) be Boolean functions, and suppose that each \(g_i\) is computed both by a DNF formula of width at most \(l\) and by a CNF formula of width at most \(l\). Let \(C_1,\dots ,C_k\) be Boolean circuits on \(m\) inputs, each of depth at most \(1\). Then for every \(j \in \{ 1,\dots ,k\} \) there exist a DNF formula \(\varphi _j\) on the \(n\) variables and a sign \(\varepsilon _j \in \{ \mathrm{true},\mathrm{false}\} \) such that \(\varphi _j\) has width at most \(l\), each term of \(\varphi _j\) contains every variable at most once (so no term repeats a literal or carries a variable in both polarities), and, for every assignment \(x \in \{ 0,1\} ^n\), the value \(\varphi _j(x)\) when \(\varepsilon _j = \mathrm{true}\) and \(\lnot \varphi _j(x)\) when \(\varepsilon _j = \mathrm{false}\) equals \(C_j\bigl(g_1(x),\dots ,g_m(x)\bigr)\).

Fix an arity \(k\), a gate type given by a flag that selects AND when true and OR when false, and a family of polarities \(\sigma : \mathrm{Fin}\, k \to \mathbb {F}_2\). For each variable index \(j \in \mathrm{Fin}\, k\), let \(\ell _j\) be the literal on variable \(j\) with polarity \(\sigma (j)\), and let \(G\) be the single gate of the chosen type applied to the list \(\ell _0, \ell _1, \dots , \ell _{k-1}\). Then there is a Boolean circuit \(c'\) of depth at most \(1\) that computes the same Boolean function as \(G\): for every assignment \(g : \mathrm{Fin}\, k \to \mathbb {F}_2\), the value of \(c'\) at \(g\) equals the value of \(G\) at \(g\).

Let \(c\) be a Boolean circuit on \(m\) inputs of depth exactly \(1\), and let \(g_1,\dots ,g_m \colon (\mathrm{Fin}\, n \to \mathbb {F}_2) \to \mathbb {F}_2\) be Boolean functions on \(n\) variables, each of which is computed by some DNF formula of width at most \(l\) and also by some CNF formula of width at most \(l\). Then the composed function \(x \mapsto c\big(g_1(x),\dots ,g_m(x)\big)\) — obtained by feeding \(g_i(x)\) into the \(i\)-th input of \(c\) — is, up to an overall sign, computed by a single DNF formula of width at most \(l\) each of whose terms has no repeated literal and mentions every variable at most once (in particular no term contains both a variable and its negation). Precisely, there exist such a DNF formula \(\varphi \) and a sign bit \(s\) so that, for every \(x\), \(\varphi (x) = c\big(g_1(x),\dots ,g_m(x)\big)\) when \(s\) is positive and \(\lnot \varphi (x) = c\big(g_1(x),\dots ,g_m(x)\big)\) when \(s\) is negative.

Let \(c\) be a Boolean circuit of depth exactly \(2\) on \(m\) inputs, and let \(g_1,\dots ,g_m \colon \{ 0,1\} ^n \to \{ 0,1\} \) be Boolean functions such that each \(g_i\) is computed both by a DNF formula of width at most \(l\) and by a CNF formula of width at most \(l\), where the width of a DNF or CNF formula is the maximum number of literals occurring in any single one of its terms or clauses. Then there exist a number \(m'\), DNF formulas \(D_1,\dots ,D_{m'}\) on \(n\) variables, and a Boolean circuit \(c'\) of depth at most \(1\) on \(m'\) inputs, such that each \(D_j\) has width at most \(l\), every term of every \(D_j\) contains each variable at most once (equivalently, its literals are pairwise distinct and no two of them share a variable), and for every assignment \(x \in \{ 0,1\} ^n\),

Fix a number of variables \(n\) and let assignments \(x\) range over \(\{ 0,1\} ^n\). Let \(C_1,\dots ,C_r\) be Boolean circuits, each on the same set of \(m\) inputs, and let \(\gamma _1,\dots ,\gamma _m\) be functions assigning to every assignment \(x\) a bit, so that feeding input \(i\) the value \(\gamma _i(x)\) turns each \(C_j\) into a Boolean function of \(x\). Fix a width bound \(l\) and, for each \(j\), a depth bound \(b_j\). Assume every child admits a DNF reduction: for each \(j\) there are a Boolean circuit \(c_j\) of depth at most \(b_j\) on some number \(m_j\) of inputs, together with DNF formulas \(g_{j,1},\dots ,g_{j,m_j}\) over \(x_1,\dots ,x_n\), each of width at most \(l\) and each of whose terms has its literals on pairwise distinct variables, such that

Then these per-child families can be amalgamated into a single one: there exist a family of DNF formulas \(h_1,\dots ,h_M\) over \(x_1,\dots ,x_n\), each of width at most \(l\) and each with all its terms’ literals on pairwise distinct variables, together with circuits \(C'_1,\dots ,C'_r\) on these \(M\) shared inputs, such that \(\mathrm{depth}(C'_j) \le b_j\) and

Fix a Boolean flag \(\mathit{isAnd}\) and a finite list \(c_1,\dots ,c_k\) of Boolean circuits on \(m\) variables, and let \(d_1,\dots ,d_k\) be Boolean circuits on \(M\) variables, one for each position of the list. Given assignments \(g : \mathrm{Fin}\, m \to \mathbb {F}_2\) and \(g' : \mathrm{Fin}\, M \to \mathbb {F}_2\) such that every re-indexed child agrees with the corresponding original child, i.e. \(d_j\) evaluated at \(g'\) equals \(c_j\) evaluated at \(g\) for each position \(j\), the gate node with flag \(\mathit{isAnd}\) over \(c_1,\dots ,c_k\) evaluated at \(g\) equals the gate node with the same flag \(\mathit{isAnd}\) over \(d_1,\dots ,d_k\) evaluated at \(g'\). Here the node is the conjunction of its children’s values when \(\mathit{isAnd} = \mathrm{true}\) and their disjunction when \(\mathit{isAnd} = \mathrm{false}\).

Let \(c\) be a Boolean circuit on \(m\) inputs whose depth is at least \(1\), and suppose each input coordinate \(i\) is fed by a Boolean function \(g_i \colon \{ 0,1\} ^n \to \{ 0,1\} \), so that \(c\) computes the map \(x \mapsto c\bigl(g_1(x),\dots ,g_m(x)\bigr)\). Fix a width bound \(l \ge 1\), and assume that every \(g_i\) is computed both by a DNF formula of width at most \(l\), each of whose terms contains at most one literal per variable, and by a CNF formula of width at most \(l\). Then there exist a number of inputs \(m'\), Boolean functions \(g'_1,\dots ,g'_{m'}\) each presented as a DNF formula of width at most \(l\) with the same restriction that no term contains two literals in the same variable, and a circuit \(c'\) of depth at most \(\mathrm{depth}(c) - 1\), such that \(c\bigl(g_1(x),\dots ,g_m(x)\bigr) = c'\bigl(g'_1(x),\dots ,g'_{m'}(x)\bigr)\) for every assignment \(x\).

Let \(D\) be layer-2 data over \(n\) variables: a family of DNF gates \(g_0,\dots ,g_{m-1}\) together with a common positive width bound. Let \(C\) be a Boolean circuit whose \(m\) inputs are indexed by these gates and whose depth is at least \(2\), and let \(l\ge 1\). Suppose that for each index \(i\) the gate \(g_i\) admits a DNF formula of width at most \(l\) that computes the same Boolean function as \(g_i\) and in which, within every term, distinct literals use distinct variables and no literal is repeated, as well as a CNF formula of width at most \(l\) computing that same Boolean function. Then there exist layer-2 data \(D'\) over \(n\) variables of width at most \(l\), with gate family \(h_0,\dots ,h_{k-1}\), and a Boolean circuit \(C'\) whose \(k\) inputs are indexed by these gates and whose depth is at most \(\mathrm{depth}(C)-1\), such that for every assignment \(x\colon \mathrm{Fin}\, n\to \{ \mathrm{true},\mathrm{false}\} \) the value of \(C\) on the input vector \(\bigl(g_i(x)\bigr)_i\) equals the value of \(C'\) on the input vector \(\bigl(h_j(x)\bigr)_j\).

Let \(n, l \in \mathbb {N}\) with \(l \ge 1\), and let \(\mathcal{D}\) be a layer-2 datum on \(n\) variables whose gates \(g_0, \dots , g_{m-1}\) are DNF formulas. Let \(C\) be a Boolean circuit on \(m\) inputs — one per gate — with \(\mathrm{depth}(C) \ge 1\), and consider the composite Boolean function \(x \mapsto C\bigl(g_0(x), \dots , g_{m-1}(x)\bigr)\). Suppose that each gate \(g_i\) admits both a DNF representation \(\varphi _i\) of width at most \(l\) computing the same function as \(g_i\) — one in which, within every term, any two literals sharing a variable coincide and no literal is repeated — and a CNF representation of width at most \(l\) computing that same function. Then there exist a layer-2 datum \(\mathcal{D}'\) on \(n\) variables of width at most \(l\), with gates \(g'_0, \dots , g'_{m'-1}\), and a Boolean circuit \(C'\) on \(m'\) inputs with \(\mathrm{depth}(C') \le \mathrm{depth}(C) - 1\), such that for every assignment \(x : \mathrm{Fin}\, n \to \mathbb {F}_2\),