# 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.