# Construct a Circuit computing all boolean functions over n bits

Let $$n∈N$$ . Construct a circuit with $$C_n(x_1,\dots,x_n)$$ with $$2^{2^n}$$ outputs $$y_1,\dots,y_{2^{2^n}}$$ which computes all distinct boolean functions $$f_i:\{0,1\}^n→\{0,1\}$$ such that $$y_i$$ is the output of $$f_i$$ and satisfying $$Size(C_n)\in O(2^{2^n})$$

Remark: The circuit is in a model of fan-in 2.

I've already found a solution in $$O(2^{2^n + n})$$ but I can't find less even recursively.

Given the circuit $$C_n$$, you can compute $$C_{n+1}$$ using $$O(2^{2^{n+1}})$$ additional gates. Indeed, each output gate of $$C_{n+1}$$ is of the form $$(\lnot x_{n+1} \land y_i) \lor (x_{n+1} \land y_j)$$ for some $$i,j$$, so can be computed from the outputs of $$C_n$$ using $$O(1)$$ additional gates.

In total, the circuit $$C_n$$ uses $$O(2^{2^n} + 2^{2^{n-1}} + \cdots) = O(2^{2^n})$$ gates.

There is such a circuit with exactly $$2^{2^n}$$ nodes (which is, of course, minimal possible). I’m assuming arbitrary nodes in the circuit can be designated as output nodes, including input nodes and nodes of nonzero fan-out; otherwise you would have to copy them, leading to at most double the size.

Start with the $$n$$ input nodes $$x_1,\dots,x_n$$, and repeat the following in arbitrary order until it is no longer applicable, where $$f_y$$ denotes the Boolean function computed by node $$y$$ of the circuit:

• Pick a node $$y$$ such that $$\neg f_y$$ is not computed by any node of the circuit, and add a new node $$\neg y$$.

• Pick a pair of nodes $$y$$ and $$y'$$ such that $$f_y\land f_{y'}$$ is not computed by any node of the circuit, and add a new node $$y\land y'$$.

When the construction stops, the set of functions $$\{f_y:y\in C\}$$ is closed under $$\neg$$ and $$\land$$, hence it contains all Boolean functions in $$n$$ inputs. On the other, by construction, no two nodes of the circuit compute the same function. Thus, the size of the circuit equals the number of functions in $$n$$ variables, viz. $$2^{2^n}$$.

An alternative construction with the same result: take any circuit that computes all functions in $$n$$ inputs, and keep removing redundant nodes. That is, if $$y\ne y'$$ compute the same function, and (wlog) $$y$$ does not depend on $$y'$$, then remove $$y'$$, and redirect all output wires of $$y'$$ to use $$y$$ instead. When you cannot do this any longer, no two nodes compute the same function, hence the size of the circuit is $$2^{2^n}$$, again.