Arithmetization of Boolean formulas

Let $F$ be a field and let $n\ge 0$. Here a Boolean formula on $x_1,\dots ,x_n$ is a finite rooted syntax tree whose leaves are variables or the constants $\mathrm{\perp },\mathrm{\top }$, whose unary nodes are NOT, and whose ordered binary nodes are AND or OR. Its Boolean value is obtained from a truth assignment by the usual truth tables: NOT reverses a bit, AND is true exactly when both bits are true, and OR is true exactly when at least one bit is true. Its arithmetization is the formal polynomial $P_{\phi }\in F[X_1,\dots ,X_n]$ defined from the leaves upward by $P_{\mathrm{\perp }}=0,P_{\mathrm{\top }}=1,P_{x_i}=X_i,P_{\mathrm{\neg }\psi }=1-P_{\psi },$ $P_{\psi \wedge \theta }=P_{\psi }{P}_{\theta },P_{\psi \vee \theta }=P_{\psi }+P_{\theta }-P_{\psi }{P}_{\theta }\mathrm{.}$ Here field and polynomial ring mean Field and Polynomial rings in finitely many commuting indeterminates by iteration. Retain the original formula tree with these gate operations; a gate can use its two already computed child values more than once. Expanding into monomials is unnecessary. Boolean false and true are identified with the distinct field elements $0$ and $1$.

Every child has smaller tree height than its parent, so the displayed rules assign a unique polynomial at each node in finitely many stages. All the operations remain in the polynomial ring. For $n=0$ that ring is $F$, and the same construction applies to formulas with only constant leaves.