49 Composing constructions

We can compose previous constructions by Boolean connectives to define new circuit families:

• The set ${\mathrm{ATMOST}}_k^n\subseteq \{0,1{\}}^n$ of strings with at most $k$ $1$s is computed by

$${\mathrm{EXACT}}_0^n(\overrightarrow{x})\vee {\mathrm{EXACT}}_1^n(\overrightarrow{x})\vee \cdots {\mathrm{EXACT}}_k^n(\overrightarrow{x})$$

• The set ${\mathrm{MAJ}}^n\subseteq \{0,1{\}}^n$ of strings with a majority of its bits 1 is computed by

$$\neg {\mathrm{ATMOST}}_{\lfloor \frac{n}{2}\rfloor }^n$$

• The set of strings with a majority of $1$s and an even number of $1$s is computed by

$${\mathrm{MAJ}}^n(\overrightarrow{x})\wedge \underset{i=1}{\overset{n}{⨁}}\overrightarrow{x}$$