Let \(g_1 : \mathrm{Fin}\, m_1 \to \alpha \) and \(g_2 : \mathrm{Fin}\, m_2 \to \alpha \) be two gate arrays, and let \(g_1 \ast g_2 : \mathrm{Fin}\, (m_1+m_2) \to \alpha \) denote their merge, which agrees with \(g_1\) on the indices \(0,\dots ,m_1-1\) and with \(g_2\) on the indices \(m_1,\dots ,m_1+m_2-1\). Then for every \(i \in \mathrm{Fin}\, m_1\), evaluating the merge at the index \(i\) regarded as an element of \(\mathrm{Fin}\, (m_1+m_2)\) (i.e. the same value \(i \lt m_1\)) returns \(g_1\, i\).

Let \(g_1 : \mathrm{Fin}\, m_1 \to \alpha \) and \(g_2 : \mathrm{Fin}\, m_2 \to \alpha \) be gate arrays, and let \(i \in \mathrm{Fin}\, m_2\). Then the merged array of \(g_1\) and \(g_2\) takes the value \(g_2(i)\) at the index \(m_1 + i\).

Let \(c\) be a Boolean circuit on \(m_1\) variables, and let \(g_1 : \mathrm{Fin}\, m_1 \to \mathbb {F}_2\) and \(g_2 : \mathrm{Fin}\, m_2 \to \mathbb {F}_2\) be assignments. Write \(\iota : \mathrm{Fin}\, m_1 \to \mathrm{Fin}\, (m_1+m_2)\), \(i \mapsto i\), for the order-preserving inclusion of the first block, and let \(g\) be the merged assignment on \(m_1 + m_2\) variables that agrees with \(g_1\) on the first \(m_1\) indices and with \(g_2\) on the last \(m_2\). Then the circuit obtained by replacing each literal index \(i\) of \(c\) by \(\iota (i)\) (keeping its sign), evaluated under \(g\), has the same value as \(c\) evaluated under \(g_1\).

Let \(m_1, m_2\) be natural numbers, let \(c\) be a Boolean circuit on \(m_2\) variables, and let \(g_1 : \mathbb {F}_2^{m_1}\) and \(g_2 : \mathbb {F}_2^{m_2}\) be Boolean assignments. Form the merged assignment on \(m_1 + m_2\) variables that takes the values of \(g_1\) on indices \(0,\dots ,m_1-1\) and the values of \(g_2\) on indices \(m_1,\dots ,m_1+m_2-1\), and re-index \(c\) by the right embedding \(i \mapsto m_1 + i\) from \(\mathrm{Fin}\, m_2\) into \(\mathrm{Fin}\, (m_1+m_2)\). Then

where each side denotes circuit evaluation; that is, evaluating the re-indexed circuit under the merged assignment gives the same Boolean value as evaluating \(c\) directly under \(g_2\).

Let \(g_1\) and \(g_2\) be families of DNF formulas over \(n\) variables, indexed by \(\mathrm{Fin}\, m_1\) and \(\mathrm{Fin}\, m_2\) respectively, and let \(\ell \) be a natural number. Suppose every formula \(g_1(k)\) has width at most \(\ell \). Form the merged array of length \(m_1+m_2\), which reproduces \(g_1\) on the first \(m_1\) indices and \(g_2\) on the remaining ones. Then for each \(i \in \mathrm{Fin}\, m_1\), the entry of the merged array at the position of \(i\) inside the first block again has width at most \(\ell \).

Let \(g_1\) and \(g_2\) be families of DNF formulas in \(n\) variables, indexed by \(\{ 0,\dots ,m_1-1\} \) and \(\{ 0,\dots ,m_2-1\} \) respectively, and let \(g\) be their merge: the family on \(\{ 0,\dots ,m_1+m_2-1\} \) that agrees with \(g_1\) on the first \(m_1\) indices and with \(g_2\) on the remaining ones, so that \(g(m_1+i)=g_2(i)\). Suppose \(l\) is a natural number for which every formula \(g_2(k)\) has width at most \(l\). Then for each index \(i\) of the second family, the merged formula \(g(m_1+i)\) has width at most \(l\).

Let \(g_1\) and \(g_2\) be two families of DNF formulas over \(n\) variables, indexed respectively by \(m_1\) and \(m_2\) positions, and let \(l\) be a natural number. Suppose every formula in \(g_1\) and every formula in \(g_2\) has width at most \(l\). Then every formula in the merged family of \(m_1 + m_2\) formulas — those of \(g_1\) in order, followed by those of \(g_2\) — also has width at most \(l\).

Let \(g_1\) and \(g_2\) be two arrays of DNF formulas over \(n\) variables, indexed respectively by \(\{ 0,\dots ,m_1-1\} \) and \(\{ 0,\dots ,m_2-1\} \), and let \(g\) be their merge: the array indexed by \(\{ 0,\dots ,m_1+m_2-1\} \) that agrees with \(g_1\) on the first \(m_1\) indices and with \(g_2\), shifted down by \(m_1\), on the remaining \(m_2\). Suppose that in every formula of \(g_1\) and in every formula of \(g_2\), any two literals lying in one and the same term whose variables coincide are in fact the identical literal. Then the merged array \(g\) inherits this property: for every index \(k\) and any two literals occurring in a common term of the formula \(g(k)\) that share the same variable, the two literals are equal.

Fix \(n \in \mathbb {N}\), and let \(g_1\) and \(g_2\) be two arrays of DNF formulas over \(n\) variables, of lengths \(m_1\) and \(m_2\) respectively; write \(g_1 \sqcup g_2\) for their merge, the array of length \(m_1+m_2\) whose first \(m_1\) entries are the formulas of \(g_1\), in order, and whose remaining \(m_2\) entries are those of \(g_2\), in order. Suppose that every term occurring in any formula of \(g_1\), and every term occurring in any formula of \(g_2\), is a list of literals with no repetition. Then the same holds for the merged array: for every index \(k\) and every term \(t\) of the formula at position \(k\) in \(g_1 \sqcup g_2\), the literals of \(t\) are pairwise distinct.