Representing binary functions with a finite gate set without exponential blow-up?

It is pretty well taught that any binary function can be represented using CNF. But conversion to CNF can take an exponential number of gates. The truth table is exponentially sized relative to the number of input variables.

Is there any form of representing truth tables that requires only a polynomial or quasipolynomial number of gates? I know there are ones that preserve satisfiability, not equality---but is there anything that preserves equality?

No. No matter what representation of functions as circuits/formulas you use, there will exist some functions that require exponential size to represent. This was proven by Shannon in 1949. See Shannon's result that some Boolean functions require exponential circuits.

Intuitively, you can count the number of circuits/formulas of polynomial size, and it is much less than the number of functions.

StackExchange Computer Science Q#162733, answer score: 13