The Exercise

Take $N$ bits $X_0, \dots, X_{N-1}$, each equal to $0$ or $1$, and write $X = (X_0, \dots, X_{N-1})$ for the string they form, a point of $\{0,1\}^N$. A Boolean function $F$ of $N$ bits assigns to each string $X$ a value $F(X)$, again $0$ or $1$. The exercise gives one polynomial in $N$ variables and asks to show that, evaluated at any string of bits, it returns the logical disjunction (OR) of those bits, the value $1$ if at least one bit is $1$ and $0$ otherwise.

A Polynomial and a Boolean Function

The OR function of $N$ bits is the Boolean function $$\mathrm{OR}(X) = X_0 \vee X_1 \vee \cdots \vee X_{N-1}.$$(1)^✦

The OR polynomial $P$ is the polynomial in the variables $X_0, \dots, X_{N-1}$, with coefficients in a commutative ring $R$, given by $$P(X) = 1 - \prod_{i=0}^{N-1} (1 - X_i).$$(2)^✦

A polynomial $p$ in $X_0, \dots, X_{N-1}$ with coefficients in $R$ represents a Boolean function $F$ of $N$ bits if its value at every string of bits equals the value of $F$ there, the bits and the values $0$ and $1$ being read as the zero and the unit of $R$: $$p(X) = F(X) \qquad \text{for every } X \in \{0,1\}^N.$$(3)^✦

The Claim

What Is Checked

The claim is stated over the OR polynomial (2), the OR function (1), and the relation (3) by which a polynomial represents a Boolean function.