57 The change of basis theorem for formulas

Theorem

Let ${\Omega }_1$ and ${\Omega }_2$ be complete basis. Then, for every ${\Omega }_1$-formula $A_1$ of size $n$ there is a logically equivalent ${\Omega }_2$-formula $A_2$ with depth $O(\log n)$ and size $n^{O(1)}$