Rational function for Parity function
It will be somewhat easier to replace $\{0,1\}$ with $\{\pm 1\}$, so that the parity function is just $x_1\cdots x_n$. Since this is an affine transformation, it doesn't affect degrees. I'm also assuming that the denominator of a rational function must be non-zero for all $\pm 1$ inputs. Since we only care about $\pm 1$ inputs, we work below over the ideal generated by $\{x_i^2 - 1\}$.

We prove by induction on $n$ that if $P/Q$ represents parity of length $n$ then $PQ = \alpha \prod_{i=1}^n x_i + \cdots$ for some positive $\alpha$, where the dots represent lower degree terms. This implies that $\deg P + \deg Q \geq n$. The claim is clearly true for $n = 0$. Now consider
$$\frac{P}{Q} = \frac{x_nP_1+P_2}{x_nQ_1+Q_2}, $$
where $P_1,P_2,Q_1,Q_2$ are over $x_1,\ldots,x_{n-1}$. Substituting $x_n=\pm1$ and applying the induction hypothesis, we deduce that for some $\alpha,\beta &gt; 0$,
$$
\begin{align*}
(P_1+P_2)(Q_1+Q_2) &amp;= \alpha \prod_{i=1}^{n-1} x_i + \cdots, \\
(P_1-P_2)(Q_1-Q_2) &amp;= -\beta \prod_{i=1}^{n-1} x_i + \cdots. \\
\end{align*}
$$
Subtracting both equations, we get
$$ P_1 Q_2 + P_2 Q_1 = \frac{\alpha+\beta}{2} \prod_{i=1}^{n-1} x_i + \cdots. $$
Therefore
$$ PQ = (x_nP_1+P_2)(x_nQ_1+Q_2) = x_n(P_1Q_2+P_2Q_1) + \cdots = \frac{\alpha+\beta}{2} \prod_{i=1}^n x_i + \cdots. $$