Suppose $g\in \mathbb R[x_1,\dots,x_{16}]$ is a polynomial with the same vanishing set as $f$ within $\{0,1\}^{16}$. Define $h\in \mathbb R[x_1,\dots,x_{16}]$ to be the polynomial you obtain by changing every occurrence of $x_i^d$ in the monomials appearing in $g$ to $x_i$. Therefore $h$ is a multilinear polynomial with the same vanishing set as $g$ within $\{0,1\}^{16}$, and moreover $\deg (h)\le \deg(g)$.

Next we can show that any such multilinear polynomial must have degree at least $4$, implying $\deg g\geq 4$. Let's expand
$$h=\sum_{S\subset \{1,\dots 16\}}c_Sx_S,$$
where $x_S=\prod_{i\in S} x_i$. You can notice that $c_{\emptyset}=0$, and you can proceed by induction on $|S|$ to prove $c_S=0$ for $|S|\le 3$. Denote by $e_S$ the $\{0,1\}$ characteristic vector of $S$. Suppose $|I|\le 3$ and we have checked the coefficients $c_J=0$ for all $J\subset I$. Since $h(e_I)=\sum_{J\subseteq I} c_Jx_J=c_I$ we conclude that $c_I=0$, because $f(e_I)=0$.