Project: Optimal Circuit Synthesis with SAT · Searching Small Circuits
Lesson 6
The number of Boolean functions grows so rapidly with the number of variables, that makes exhaustive search too slow even for functions on \(5\) variables.
A SAT solver gives a more general way to search for a circuit and certify that a smaller one does not exist.
Problem. How many Boolean functions on \(n\) variables are there? Give your answer as a formula in \(n\).